A - Lucky Direction
翻译：
给你一个字符串 D，代表八个方向（北、东、西、南、东北、西北、东南、西南）之一。方向与其代表字符串之间的对应关系如下。
- 北： N
- 东： E
- 西： W
- 南： S
- 东北方 ：NE
- 西北： NW
- 东南： SE
- 西南： SW
打印与 D 表示的方向相反的字符串。
思路：
使用map对应即可
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();map<string,string> mp;mp["N"] = "S";mp["S"] = "N";mp["E"] = "W";mp["W"] = "E";mp["NE"] = "SW";mp["SW"] = "NE";mp["NW"] = "SE";mp["SE"] = "NW";string s;cin>>s;cout<<mp[s]<<endl;
}B - Seek Grid
翻译：
给你一个 N×N 网格 S 和一个 M×M 网格 T。从上往下第 i 行和从左往右第 j 列的单元格用 (i,j) 表示。
S 和 T 中单元格的颜色用
个字符
(1≤i,j≤N）表示和
个字符
（1≤i,j≤M）来表示。在网格 S 中，如果
找到S内的T。更准确地说，输出满足以下条件的整数 a 和 b（1≤a,b≤N-M+1）：
对于i,j来说 i,j (1≤i,j≤M).
思路：
以S中（a，b）为右上角遍历M*M的网格，判断是否相同。
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n,m;cin>>n>>m;vector<string> S(n),T(m);for (int i=0;i<n;i++){cin>>S[i];}for (int i=0;i<m;i++){cin>>T[i];}for (int a=0;a<=n-m;a++){for (int b=0;b<=n-m;b++){// judge sameint f = 1;for (int i=0;i<m;i++){if (!f) break;for (int j=0;j<m;j++){if (T[i][j]!=S[a+i][b+j]){f = 0;break;}}}if (f){cout<<a+1<<" "<<b+1<<endl;return;}}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();
}C - Pigeonhole Query
翻译：
有N 只鸽子，编号从1 到N，还有N 个巢，编号从1 到N。最初，鸽子i 在巢i 中，其中
1≤i≤N。你将收到Q 个查询，需要按顺序处理。查询有两种类型，每种查询的格式如下：
1 P H：将鸽子P 移动到巢H。2：输出包含多于一只鸽子的巢的数量。
思路：
用两个数组（nests，pigeon）分别记录，nests[i]记录巢i中有几只鸽子，pigeon[i]记录鸽子i在哪个巢穴中。
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();int n,q,f,p,h,res = 0;cin>>n>>q;vector<int> nests(n+1,1),pigeon(n+1);for (int i=0;i<=n;i++) pigeon[i] = i;while (q--){cin>>f;if (f==1){cin>>p>>h;// move pif (nests[pigeon[p]]-- ==2){res -= 1;}pigeon[p] = h;if (nests[pigeon[p]]++ == 1){res += 1;}}else if (f==2){cout<<res<<endl;}}
}D - Gravity
翻译：
有一个
行 W 列的网格。左起第 x 列和下起第 y 行的单元格用 (x,y) 表示。
共有 N 个图块。每个区块是 1×1 的正方形，第 i 个区块（1≤i≤N）在 0 时刻位于单元格
。
在
时，区块按照以下规则移动：
- 如果整个底行都布满了图块，则移除底行的所有图块。
- 对于剩余的每个区块，按照从下到上的顺序，执行以下操作：
- 如果该图块位于最下面一行，或者它下面的单元格中有一个图块，则不做任何操作。
- 否则，将该图块向下移动一格。
给您 Q 个查询。对于第 j 个查询 (1≤j≤Q)，请回答区块 A j 在时间
.
思路：
预处理答案。
哪些块一定会消失？会构成底行都为图块的块。那么先就求会消掉的层数，即每列的最少块数。
那么最后会处于同一行的什么时候消失呢？这个由最终同行的最高点决定。
不消失的块则一直存在。
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){ll n,w;cin>>n>>w; // block_down_time[i]：第i块在哪个时间点消失vector<ll> block_down_time(n+1,-1);// down_block[i]：第i列中包含的块（块所处高度，第几块）vector<vector<pair<ll,ll>>> down_block(w+1);for (ll x,y,i=1;i<=n;i++){cin>>x>>y;down_block[x].emplace_back(y,i);}// 有几行可被移除ll can_removes = INT_MAX;for (ll i=1;i<=w;i++){sort(down_block[i].begin(),down_block[i].end());can_removes = min(can_removes,(ll)down_block[i].size());}// 遍历消失的行，得到最终相同行的消失时间for (ll i=1;i<=can_removes;i++){ll need_time = 0;for (ll j=1;j<=w;j++){need_time = max(need_time,down_block[j][i-1].first);}for (ll j=1;j<=w;j++){block_down_time[down_block[j][i-1].second] = need_time;}}// queryll q,t,a;cin>>q;while (q--){cin>>t>>a;// 不会消失 或 还没到消失的点if (block_down_time[a]==-1 || block_down_time[a]>t){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();
}E - Hierarchical Majority Vote
翻译：
对于长为
的二进制字符串
我们定义一个如下操作得到一个长为
的二进制字符串
：
- 将B的元素分为三组并得到每个组中的主要值。也就是对于
,让
为
中出现最频繁的值。
你被给予 对于长为
的二进制字符串
。. 设 A ′ =
′ 是对 A 进行 N 次上述操作后得到的长度为 1 的字符串。
确定A中最少要改变多少元素使得
的值改变。
思路：
以010011101为例
010 011 101 第2层
0 1 1 第1层
1 第0层
定义dfs( i, j )为第i层的第j块改变为
如果当前 j 块下的3个块中有2个k1, k2与最终值不同，则min( dfs(i+1 , k1), dfs( i+1, k2))
如果当前 j 块下的3个块中有3个k1, k2,k3与最终值不同,则
min( dfs(i+1 , k1)+dfs( i+1, k2), dfs(i+1 , k2)+dfs( i+1, k3), dfs(i+1 , k3)+dfs( i+1, k1))
终止条件为i>=n返回1表示当前块要改。
实现：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n;string s;cin>>n;cin>>s;//colors[i][j]：第i层的第j块的颜色vector<vector<int>> colors(n+1);// 得到每层每块改变前的颜色for (char c:s) colors[n].push_back(c-'0');for (int i=n-1;i>=0;i--){for (int j=0;j<pow(3,i);j++){int cnt1 = 0,cnt0 = 0;for (int z=3*j;z<3*j+3;z++){if (colors[i+1][z]==1) cnt1++;else cnt0++;}colors[i].push_back(cnt1>cnt0 ? 1 : 0);}}// need：最终值int need = colors[0][0]^1;// memo[i][j]：第i层第j块中最少要改变的块数vector<vector<int>> memo(n+1);// 初始化memofor (int i=0;i<=n;i++) memo[i].resize(pow(3,i),-1);auto dfs = [&](auto&& dfs,int i,int j)->int{if (i>=n) return 1;int& res = memo[i][j];if (res!=-1) return res;res = INT_MAX;// cnt_need：有几个与最终值不同的int cnt_need = 0,base = 3*j;for (int k=base;k<base+3;k++){if (colors[i+1][k]!=need) cnt_need++;} if (cnt_need==2){for (int k=base;k<base+3;k++){if (colors[i+1][k]!=need) res = min(res,dfs(dfs,i+1,k));}}else if (cnt_need==3){for (int k1=base;k1<base+3;k1++){for (int k2 = k1+1;k2<base+3;k2++){if (colors[i+1][k1]!=need && colors[i+1][k2]!=need){res = min(res,dfs(dfs,i+1,k1)+dfs(dfs,i+1,k2));}}}}return res;};cout<<dfs(dfs,0,0)<<endl;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();
}有建议可以评论，我会积极改进qwq。
codeforces比赛时间十点左右的场基本不会当天写了，atcoder有的话基本会写。
