ABC370

## A - Raise Both Hands （模拟）

题意：输入l，r，如果l=1r=0输出yes，l=0r=1输出no，否则输出Invalid

代码：

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
    int l,r;cin>>l>>r;
    if(l==1&&r==0)cout<<"Yes"<<endl;
    else if(l==0&&r==1)cout<<"No"<<endl;
    else cout<<"Invalid"<<endl; 
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1; 
    while(t--)sol();
    return 0;
}

```

## B - Binary Alchemy（模拟）

题意：当元素i和元素j组合在一起，如果i>=j，他们就变成aij，否则aji，求最后得到的元素

代码：

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
    int n;cin>>n;
    int a[n+10][n+10];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    int b=1;
    for(int i=1;i<=n;i++){
        if(b<i){
            b=a[i][b];
        }
        else b=a[b][i];
    }
    cout<<b<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1; 
    while(t--)sol();
    return 0;
}

```

## C - Word Ladder（模拟）

题意：给定两个数，每次可以修改一个字符，每次修改完必须是字典序最小，输出每次修改完的字符

代码：

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void sol(){
    string s,t;cin>>s>>t;
    vector<string>v;
    map<string,int>mp;
    while(s!=t){
        string ss=s;
        mp.clear();
        for(int i=0;i<s.size();i++){
            char c=ss[i];
            if(ss[i]!=t[i]){
                ss[i]=t[i];
                mp[ss]++;
                ss[i]=c;
            }
        }
        for(auto &x:mp){
            v.push_back(x.first);
            s=x.first;
            break;
        }
    }
    cout<<v.size()<<endl;
    for(int i=0;i<v.size();i++)cout<<v[i]<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1; 
    while(t--)sol();
    return 0;
}

```

## D - Cross Explosion（二分）

题意：给定h×w的墙，给定q个坐标，如果当前坐标有墙则摧毁，否则摧毁离它最近的上下左右四个墙

分析：将每一行每一列存入1-w，1-h，用二分寻找上下左右离当前位置最近的四个坐标并消除，最后求出每一行剩余个数相加

代码：

```
#include<bits/stdc++.h> 
using namespace std;
int main() {
  int H, W, Q;
  cin >> H >> W >> Q;
  vector<set<int>> g1(H), g2(W);
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      g1[i].insert(j);
      g2[j].insert(i);
    }
  }
  auto erase = [&](int i, int j) { g1[i].erase(j), g2[j].erase(i); };

  while (Q--) {
    int R, C;
    cin >> R >> C;
    --R, --C;
    if (g1[R].count(C)) {
      erase(R, C);
      continue;
    }
    // up
    {
      auto it = g2[C].lower_bound(R);//第一个大于r 
      if (it != begin(g2[C])) erase(*prev(it), C);//*prev(it)it的前一个值 
    }
    // down
    {
      auto it = g2[C].lower_bound(R);
      if (it != end(g2[C])) erase(*it, C);
    }
    // left
    {
      auto it = g1[R].lower_bound(C);
      if (it != begin(g1[R])) erase(R, *prev(it));
    }
    // right
    {
      auto it = g1[R].lower_bound(C);
      if (it != end(g1[R])) erase(R, *it);
    }
  }

  int ans = 0;
  for (int i = 0; i < H; i++) ans += g1[i].size();
  cout << ans << "\n";
}

```

## E - Avoid K Partition（dp+前缀和）

题意：将一组数组任意分成若干份，这些分割方法中，有多少种没有任何一段子序列的和等于k

分析：用fi记录前i个数划分情况，用前缀和记录区间和，pre[j]=pre[i]-k，用map记录

代码：

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll mod=998244353;
ll a[N],f[N],pre[N];
void sol(){
    ll n,k,sum=1;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+a[i];
    }
    map<ll,ll>mp;
    f[0]=1;mp[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=(sum-mp[pre[i]-k]%mod+mod)%mod;
        mp[pre[i]]=(mp[pre[i]]+f[i])%mod;
        sum=(sum+f[i])%mod;
    }
    cout<<f[n]<<endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t=1; 
    while(t--)sol();
    return 0;
}

```