AtCoder Beginner Contest 391（ABCDE）

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 中单元格的颜色用 $N^{2}$ 个字符 $S_{i,j}$ (1≤i,j≤N）表示和 $M^{2}$ 个字符 $T_{i,j}$ （1≤i,j≤M）来表示。在网格 S 中，如果 $S_{i,j}$ 为 '. '，则单元格 (i,j) 为白色；如果 $S_{i,j}$ 为 '#'，则单元格 (i,j) 为黑色。网格 T也相同

找到S内的T。更准确地说，输出满足以下条件的整数 a 和 b（1≤a,b≤N-M+1）：

$S_{a+i-1,b+j-1}=T_{i,j}$ 对于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

翻译：

        有一个 $10^{9}$ 行 W 列的网格。左起第 x 列和下起第 y 行的单元格用 (x,y) 表示。

        共有 N 个图块。每个区块是 1×1 的正方形，第 i 个区块（1≤i≤N）在 0 时刻位于单元格 $(X_{i},Y_{i})$ 。

        在 $t=1,2,...,10^{100}$ 时，区块按照以下规则移动：

如果整个底行都布满了图块，则移除底行的所有图块。
对于剩余的每个区块，按照从下到上的顺序，执行以下操作：
如果该图块位于最下面一行，或者它下面的单元格中有一个图块，则不做任何操作。
否则，将该图块向下移动一格。

给您 Q 个查询。对于第 j 个查询 (1≤j≤Q)，请回答区块 A j 在时间 $T_{j}+0.5$ .

思路：

预处理答案。

哪些块一定会消失？会构成底行都为图块的块。那么先就求会消掉的层数，即每列的最少块数。

那么最后会处于同一行的什么时候消失呢？这个由最终同行的最高点决定。

不消失的块则一直存在。

实现：

#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

翻译：

对于长为 $3^{n}$ 的二进制字符串 $B=B_{1}B_{2}...B_{3^{n}}$ 我们定义一个如下操作得到一个长为 $3^{n-1}$ 的二进制字符串 $C=C_{1}C_{2}...C_{3^{n-1}}$ ：

将B的元素分为三组并得到每个组中的主要值。也就是对于 $i=1,2,...,3^{n-1}$ ,让 $C_{i}$ 为 $B_{3i-2},B_{3i-1},B_{3i}$ 中出现最频繁的值。

你被给予对于长为 $3^{N}$ 的二进制字符串 $A=A_{1}A_{2}...A_{3^{N}}$ 。. 设 A ′ = $A_{1}$ ′ 是对 A 进行 N 次上述操作后得到的长度为 1 的字符串。

确定A中最少要改变多少元素使得 $A_{1}^{'}$ 的值改变。

思路：

以010011101为例

010 011 101 第2层

0 1 1 第1层

1 第0层

定义dfs( i, j )为第i层的第j块改变为 $A_{1}^{'}$ 反转值（下面都叫最终值），所要用的元素数量。

如果当前 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();
}