AtCoder Beginner Contest 398（ABCDEF）

A - Doors in the Center

翻译：

        找到一个满足下面情况长为N的字符串：

• 每个字符是 - 或 = 。
• 是一个回文。
• 包含一个或两个 = 。如果包含两个相邻的 = 。

        如此字符串为独一无二的。

思路：

        从两端使用 = 开始构造回文。在特判下中间部分，字符串s长为2，放两个 = ；长为1 放一个 = 。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){int n;cin>>n;vector<char> s(n);for (int l=0,r=n-1;l<=r;l++,r--){s[l] = '-';s[r] = '-';}if (n%2==0){s[n/2] = '=';s[n/2-1] = '=';}else{s[n/2] = '=';}for (int i=0;i<n;i++){cout<<s[i];}cout<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

B - Full House 3

翻译：

        我们有七张牌。第 i 张牌 (i=1,...,7)上面写着一个整数 。
        请判断是否有可能从这七张牌中选出五张，使所选的牌组成座无虚席。
        当且仅当满足以下条件时，由五张牌组成的一组牌称为座无虚席：

•         对于不同的整数 x 和 y，有三张牌带有 x，两张牌带有 y

思路：

        方法一：

        记录出现两次的数的个数cnt2，和出现两个以上的数的个数cnt3。

        当cnt3>=2或(cnt3>=1且cnt2>=1)时，可行，反之不可行。

        方法二：

        记录每个数的出现次数，并放入数组a中，将a降序排序，当下标为1的值大于等于2时可行，否则不可行。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){vector<int> a(14,0);int cnt2 = 0,cnt3=0;for (int num,i=1;i<=7;i++){cin>>num;a[num]++;}for (int i=1;i<=13;i++){if (a[i]==2){cnt2++;}else if (a[i]>=3){cnt3++;}}if (cnt3>=2 || (cnt3>=1 && cnt2>0)){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();return 0;
}

C - Uniqueness

翻译：

        这有N个人，下标1到N。第 i 个人有一个整数。

        在这群人中对于满足“ 其余N-1个人的数没有与自身相同的 ”的人，找到最大的数并输出他的下标。

        如果没有人满足条件，则报告这一事实。

思路：

       先对每个数计数，在遍历N个人，找大最大的值并记录下标。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){int maxx = 0,ind = -1;int n;map<int,int> mp;cin>>n;vector<int> a(n+1);for (int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;}for (int i=1;i<=n;i++){if (mp[a[i]]==1 && maxx<a[i]){ind = i;maxx = a[i];}}cout<<ind<<endl;
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

D - Bonfire

翻译：

        有一个无限大的二维网格，篝火位于坐标 (0,0)。
        在时间 t=0 时，只有单元格（0,0）存在烟雾。

        给你一个长度为 N 的字符串 S 由 N、W、S、E 组成。在 t=1,2,...,N，以下情况依次发生：

• 风吹过，当时所有的烟都会如下移动：
  • 如果 的第 t 个字符 S 的第 t 个字符为 N，则单元格 (r,c) 单元中的烟移动到 (r-1,c) 单元。
  • 如果是 W，则单元格 (r,c) 格中的烟移至 (r,c-1) 单元。
  • 如果是 S，则单元格 (r,c) 格中的烟雾移至 (r+1,c) 单元。
  • 如果是 E，则单元格 (r,c) 格中的烟雾移至 (r,c+1)单元。
• 如果单元格 (0,0) 中没有烟雾 ，则在单元 (0,0)会有新烟产生。

        高桥站在单元格 (R,C)单元。
        对于每个整数 1≤t≤N，确定在 (R,C) 在时间 t+0.5，并按要求格式打印答案。

思路：

        由于（0，0）处的烟一直在产生，因此每一步都可以时新的开始。也就是说当最初的烟到s[ i ]时，之后的新烟是由s[ j : i ] = s[0 : i ]-s[0 : j]产生的。遍历所有步数 i ，判断当前是否存在s[ j : i ]为人所在的位置，并记录当前的前缀值 [0 : i ]。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){unordered_map<char,array<int,2>> direct;direct['N'] = {-1,0};direct['W'] = {0,-1};direct['S'] = {1,0};direct['E'] = {0,1};int n,r,c,x_min = 0,x_max = 0,y_min = 0,y_max = 0;cin>>n>>r>>c;char d;set<array<int,2>> vis;vis.insert({0,0});int now_x = 0,now_y = 0;for (int i=1;i<=n;i++){cin>>d;now_x+=direct[d][0];now_y+=direct[d][1];if (vis.find({now_x-r,now_y-c})!=vis.end()){cout<<1;}else{cout<<0;}vis.insert({now_x,now_y});}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

E - Tree Game

翻译：

        这个问题是一个交互式问题（在这个问题中，你的程序和评判系统通过输入和输出进行交流）。

        给你一棵树 G，树上有 N 个顶点，编号从 1 到 N。 第 i 条边连接顶点 i 和 。.

        你们将用这棵树与高桥玩一个游戏。首先，你们决定谁是第一名，谁是第二名。然后，从第一位玩家开始，轮流执行以下操作：

        选择一对整数 (i,j) 1≤i<j≤N 且满足以下两个条件的一对整数，然后添加一条边连接顶点 和 j 的 G.

• G 中没有连接顶点 和 j.
• 添加一条连接顶点 和 j 的边不会产生奇数循环。

无法执行此操作的棋手输棋，另一方获胜。与高桥选手下这盘棋并获胜。

思路：

        按题目是要连偶数环，画图可知会形成偶数环的两个点不管何时连都为偶数环。那么通过暴力深搜，找到所有符合条件的对，在按对的数量一次讲出即可。

        C++的endl会刷新输入输出流。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;
int n,x,y;
vector<vector<int>> tree(110);
//vector<int> depth(110,0);
set<array<int,2>> ans;
void dfs(int now,int pos,int fa,int step){
//    cout<<now<<" "<<pos<<" "<<fa<<" "<<step<<endl;// 为偶数if (step%2==0 && step>2){x = min(now,pos);y = max(now,pos);ans.insert({x,y});}for (int &i:tree[pos]){if (i!=fa){dfs(now,i,pos,step+1);}}
}
void solve(){cin>>n;for (int i=1,u,v;i<n;i++){cin>>u>>v;tree[u].push_back(v);tree[v].push_back(u);}for (int i=1;i<=n;i++){dfs(i,i,i,1);}if (ans.size()&1){cout<<"First"<<endl;do{auto i = *ans.begin();ans.erase({i[0],i[1]});cout<<i[0]<<" "<<i[1]<<endl;cin>>x>>y;ans.erase({x,y});}while (x!=-1 && y!=-1);}else{x = 0,y = 0;cout<<"Second"<<endl;while (x!=-1 && y!=-1){cin>>x>>y;ans.erase({x,y});auto i = *ans.begin();ans.erase({i[0],i[1]});cout<<i[0]<<" "<<i[1]<<endl;}}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

F - ABCBA

翻译：

        找到一个以S为前缀的最小回文。

思路：

        找到S中右端点在S右端点的最大回文子串。将其右边的多余部分反转复制到S右端即可。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 1e5+10;void solve(){string s;cin>>s;int n = s.size();int len = 1;int f = 1;for (int i=0;i<=n-1;i++){if (s[i]==s[n-1]){f = 1;for (int l=i,r=n-1;l<=r;l++,r--){if (s[l]!=s[r]){f = 0;break;}}if (f){len=n-i;break;}}}if (len==n){cout<<s<<endl;}else{cout<<s;for (int i=n-len-1;i>=0;i--){cout<<s[i];}}
}int main(){// 关闭输入输出流同步ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 不使用科学计数法// cout<<fixed;// 中间填保留几位小数，不填默认// cout.precision();solve();return 0;
}

  有建议可以评论，我会积极改进qwq。