Hello 2023 A--C

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;

}