A
思路:找到RL结构或者LR结构,否则-1;
ac代码:
void s(){
int n;
cin >> n;
string a;
cin >> a;
for(int i = 0; i < n - 1; i ++){
if(a[i] == 'R' && a[i + 1] == 'L'){
cout << "0\n";
return;
}else if(a[i] == 'L' && a[i + 1] == 'R'){
cout << i + 1 << endl;
return;
}
}
cout << "-1\n";
}
B
偶数的构造1 -1 1 -1 1 -1....
奇数的构造:
3不可构造
5: 1 -2 1 -2 1
7: 2 -3 2 -3 2 -3 2
9: 3 -4 3 -4 3 -4 3 -4 3
........
通项:n/2-1 -(n/2) n/2-1 -(n/2) n/2-1 -(n/2)
ac代码:
void s(){
int n;
cin >> n;
if(n == 3) {
cout <<"NO\n";
return;
}
cout << "YES\n";
if(n % 2 == 0){
for(int i = 1; i <= n; i ++){
if(i & 1) {
cout << 1 << " ";
}else {
cout << -1 <<" ";
}
}
cout << endl;
}else{
for(int i = 1; i <= n; i ++){
if(i & 1) {
cout << n / 2 - 1 << " ";
}else {
cout << -(n / 2) <<" ";
}
}
cout << endl;
}
}
C
m作为前缀和最小点。那么从m向左向右的“缀和”都必须>=0

准确来说就是:[1, m-1]之间的后缀和>=0且[m+1,n]之间的前缀和>=0
最后就是用小根堆优化或者multiset的set.begin()或者set.rbegin(); 而不是*set.end()
ac
long long func(vector<long long> a, int l, int r){
long long ans = 0, sum = 0;
priority_queue<long long, vector<long long> , greater<long long>> s;
for(int i = l; i <= r; i ++){
sum += a[i];
s.push(a[i]);
while(sum < 0) {
sum -= 2LL * s.top();
s.pop();
ans ++;
}
}
return ans;
}
void s(){
int n, m;
cin >> n >> m;
vector<long long> a(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
long long ans = 0;
ans += func(a, m + 1, n);
vector<long long> b;
for(int i = m ; i >= 1; i --) b.push_back(-a[i]);
ans += func(b, 1 - 1, m - 1 - 1);
cout << ans << endl;
}