AtCoder Beginner Contest 370（A~E）

A

读题的时候有一些细节注意一下。

#include <bits/stdc++.h>using namespace std;int main()
{int l , r; cin >> l >> r;if((l + r) == 0 || (l + r) == 2 ) {cout << "Invalid\n";} else if ((l + r) == 1) {if(l == 1) {cout << "Yes\n";} else {cout << "No\n";}}return 0;
}

B

模拟

#include <bits/stdc++.h>using namespace std;
const int N = 110;
int a[N][N];int main()
{int n;cin >> n;for(int i = 1; i <= n; i ++) {for(int j = 1; j <= i;j ++) {cin >> a[i][j];}}int now = a[1][1];for(int i = 2; i <= n; i ++) {if(now >= i) {now = a[now][i];} else {now = a[i][now];}}cout << now << '\n';return 0;
}

C

可以先预处理出修改的顺序order。
先正着扫一遍，对于$s[i]>t[i]$越靠前的修改会导致更小的字典序。
然后倒着扫一遍,对于$s[i]<t[i]$的修改，越靠后的修改会导致更小的字典序。
然后按照预处理出的修改顺序去修改即可。

#include <bits/stdc++.h>using namespace std;
const int N = 110;
int a[N][N];int main()
{string s, t;cin >> s >> t;if(s == t) {cout << 0 << '\n';return 0;} else {int now = 0, cnt = 0;vector<string>stk;for(int i = 0; i < s.size(); i++) {if(s[i] != t[i]) {cnt ++ ;}}cout << cnt << '\n';vector<int>order(s.size() + 1);for(int i = 1; i <= cnt; i ++) {bool f = true;for(int j = 0; j < s.size(); j ++ ) {if(!order[j] && s[j] > t[j]) {order[j] = i;f = false;break;}}if(!f) continue;for(int j = s.size() - 1; j >= 0; j -- ) {if(!order[j] && s[j] < t[j]) {order[j] = i;break;}}}for(int i = 1; i <= cnt; i ++ ) {for(int j = 0; j < s.size(); j ++ ) {if(order[j] == i) {s[j] = t[j];cout << s << '\n';}}}}return 0;}

D

stl的应用。
用两个set数组维护每行每列存在的墙。，然后当墙存在时，直接在对应的行列set里面删除。
其他情况需要去分情况维护对应set。

#include <bits/stdc++.h>using namespace std;
using i64 = long long;
const int N = 4e5 + 10, MOD = 998244353;
set<int>h[N], w[N];
int H, W, q;int main()
{cin >> H >> W >> q;for(int i = 1; i <= H; i ++ ) {for(int j = 1; j <= W; j ++ ) {h[i].insert(j);}}for(int i = 1; i <= W; i ++ ) {for(int j = 1; j <= H; j ++ ) {w[i].insert(j);}}i64 ans = H * W;while(q -- ) {int x, y;cin >> x >> y;if(h[x].find(y) != h[x].end()) {h[x].erase(y);w[y].erase(x);ans --;continue;}auto it = h[x].lower_bound(y);if(it != h[x].end()) {w[*it].erase(x);h[x].erase(*it);ans --;}it = h[x].lower_bound(y);if(it != h[x].begin()) {it = prev(it);w[*it].erase(x);h[x].erase(*it);ans --;}it = w[y].lower_bound(x);if(it != w[y].end()) {h[*it].erase(y);w[y].erase(*it);ans --;}it = w[y].lower_bound(x);if(it != w[y].begin()) {it = prev(it);h[*it].erase(y);w[y].erase(*it);ans --;}}cout << ans << '\n';
}

E

看到这种题目：脑子里面就应该想到不是$组合数学$就是$计数类dp$.
最开始我是用组合数学去做的，但是发现后面重复情况不太好做，然后用计数类dp可以解决这道问题。

有个比较显然的dp思路是
$dp[i]:以i结尾，并且满足要求的方案数$
于是有转移$dp[i]+=dp[j],j<i,s[i]-k!=s[j-1]$
对于$!=$其实是不太好处理，不妨容斥，考虑用总的去减相等的。
这样需要记录前面所有的$dp[i]$,同时需要维护所有前缀和相同的$dp[i]$的值。

#include <bits/stdc++.h>using namespace std;
using i64 = long long;
const int N = 4e5 + 10, MOD = 998244353;
i64 a[N], f[N], n, k;
i64 s[N];/** f[i] : 以i结尾满足条件的方案数* i可以向j转移的条件是s[i] - s[j - 1] != k,所有这样的j，构成了f[i]* for(int i = 1; i <= n; i ++ ) {*  for(int j = 1; j <= i; j ++ ) {*      if(s[i] - s[j-1] != k) {*          f[i] = (f[i] + f[j]) % MOD;*      }*  }* }* 可以观察第二重循环，是对所有的sum(f[j])(j < i)减去sum(f[j])  (j < i && s[i] - s[j - 1] == k)* 于是可以用一个map记录前面s[j]的所有dp[j]的和即mp[s[j]],这样转移的时候就可直接O(1)转移*/int main()
{cin >> n >> k;map<i64, i64> mp;for(int i = 1; i <= n; i ++ ) {cin >> a[i];s[i] = s[i - 1] + a[i];}mp[0] = 1;f[0] = 1;i64 sum = 1;//维护的是f[j] j < i的和for(int i = 1; i <= n; i ++ ) {f[i] = (sum - mp[s[i] - k] % MOD + MOD) % MOD;(mp[s[i]] += f[i]) %= MOD;(sum += f[i]) %= MOD;}cout << f[n] << '\n';
}