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;
}
```