A - Raise Both Hands
题意：
给出Snuke举的左右手情况，如果只举左手，输出Yes，如果只举右手，输出No，否则输出Invalid
思路：
- 举左手：
（l == 1 && r == 0) - 举右手：
(l == 1 && r == 0) - 其他情况都是
Invalid
void solve()
{
int l = read(), r = read();
if(l == 1 && r == 0){
cout<<"Yes"<<endl;
}else if(l == 0 && r == 1){
cout<<"No"<<endl;
}else {
cout<<"Invalid"<<endl;
}
}
B - Binary Alchemy
题意：
有 \(N\) 种编号为 \(1, 2, \ldots, N\) 的元素。
元素之间可以相互组合。当元素 \(i\) 和 \(j\) 组合在一起时，如果 \(i \geq j\) 变为元素 \(A_{i, j}\) ，如果 \(i < j\) 变为元素 \(A_{j, i}\) 。
从元素 \(1\) 开始，依次与元素 \(1, 2, \ldots, N\) 结合。求最后得到的元素。
思路：
根据题意，模拟查表，逐一合成即可
void solve()
{
int n = read();
int a[N][N];
for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) a[i][j] = read();
int x = 1;
for(int t=1;t<=n;t++){
int i = max(x,t) , j = min(x,t);
x = a[i][j];
}
cout<<x<<endl;
}
C - Word Ladder
题意：
给定两个长度相等的字符串 \(S\) 和 \(T\),
用最小的操作次数，使得 \(S = T\) ，并且字符串 \(X\) 的字典序最小。
操作为，选择 \(S_i = c\) ，并且将修改后的 \(S\) 放入 \(X\) 的末尾。
思路：
- 显然S和T有多少个不同的字符就操作多少次就是次数最少
- 考虑使X的字典序最小，在S中修改字符，越靠前并且越小的字符应该越靠后修改
- 故两次遍历S,先从前往后遍历，若\(S_i < T_i\)则操作一次
- 再从后往前遍历，将剩下不一样的字符修改掉
void solve()
{
string s1 = sread(), s2 = sread();
int n = s1.length();
vector<string> ans;
for(int i=0;i<n;i++){
if(s1[i] > s2[i]){
s1[i] = s2[i];
ans.push_back(s1);
}
}
for(int i=n-1;i>=0;i--){
if(s1[i]!=s2[i]){
s1[i] = s2[i];
ans.push_back(s1);
}
}
cout<<ans.size()<<endl;
for(auto it:ans) cout<<it<<endl;
}
D - Cross Explosion
题意：
\(H \times W\) 的二维网格，初始所有格子都有墙
\(Q\) 次操作，每次操作都在\((x , y)\)处放一炸弹
- 若\((x , y)\)没有墙，则炸毁墙
- 若\((x , y)\)有墙，则分别炸毁上下左右的最近的第一面墙
思路：
对于每一个坐标\((x , y)\)，可以分成行和列来考虑
- 在第x行中，可以用二分查找找到第一个坐标大于等于y的墙
- 在第y列中，可以用二分查找找到第一个坐标大于等于x的墙
因此，我们需要一个 既能二分查找，也能插入，删除的容器
显然只有 STL:：set 能够满足
将行和列分别建立set数组，每次操作在行和列都执行即可
void solve()
{
string s1 = sread(), s2 = sread();
int n = s1.length();
vector<string> ans;
for(int i=0;i<n;i++){
if(s1[i] > s2[i]){
s1[i] = s2[i];
ans.push_back(s1);
}
}
for(int i=n-1;i>=0;i--){
if(s1[i]!=s2[i]){
s1[i] = s2[i];
ans.push_back(s1);
}
}
cout<<ans.size()<<endl;
for(auto it:ans) cout<<it<<endl;
}
E - Avoid K Partition
题意：
给定一个数组 \(A\)，划分成若干个子区间，使得没有子区间的和为 \(K\)
求划分方案数
思路：
涉及到子区间的和，显然要用到前缀和来优化，预处理一个前缀和数组 pre[N]
- 线性DP: (会TLE)
设 \(f_i\) 表示当前枚举到的连续子序列以 \(i\) 结尾的不同方案数- \(i\) 从1到n遍历
- \(j\) 从0到i-1，pre[i] - pre[j] 即为最后一个子序列的和，若该值不等于K，则将该划分方案加入到 f[i]中
void solve()
{
int n = read(), k = read();
const int mod = 998244353;
vector<int> v(1);
for(int i=1; i<=n; i++) v.push_back(read());
vector<int> f(n+1),pre(n+1);
for(int i=1;i<=n;i++){
pre[i] = v[i] + pre[i-1];
}
f[0] = 1;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(pre[j] != pre[i] - k){
f[i] = (f[i] + f[j])%mod;
}
}
}
cout<<f[n]<<endl;
}
- 考虑优化，pre[j] 只要不等于 pre[i] - k 即可，因此不需要遍历每个子区间，只需要在所有方案的和中减去子区间和是k的方案即可
- 用map来存储不同子区间和的方案的个数，即pre[i]的方案个数（方案个数就是符合条件的f[i]的值)
- 用sum来记录所有子序列的划分方案的和
void solve()
{
int n = read(), k = read();
vector<int> v(1);
for(int i=0;i<n;i++) v.push_back(read());
const int mod = 998244353;
vector<int> pre(n+1),f(n+1);
unordered_map<int,int> cnt;
for(int i=1;i<=n;i++) pre[i] = pre[i-1] + v[i];
f[0] = 1;
cnt[0] = 1;
int sum = 1;
for(int i=1;i<=n;i++){
f[i] = sum - cnt[pre[i] - k];
f[i]%=mod, f[i]+=mod, f[i]%=mod;
sum = (sum+f[i])%mod;
cnt[pre[i]] += f[i];
}
cout<<f[n]<<endl;
}
- 注意到：若没有和为 \(K\) 的条件，长度为n的数组划分方案的个数为2的n次方