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

        找到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有的话基本会写。