A - Overall Winner
题目大意
A和T两人玩游戏, 给定一串只由A和T组成的字符串, 如果第i个字符是A, 则A赢得第i轮的胜利, 反之则T赢; 当遍历完整个字符串后, 谁赢的轮数多谁就是最终赢家, 如果一样则谁最先达到该轮数谁赢, 输出赢家的名字
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
signed main(){
int n;
cin>>n;
string s;
cin>>s;
int a=0,b=0;
bool f=false;
if(n%2==0) f=true;
for(int i=0;i<n;i++){
if(s[i]=='T') a++;
else b++;
if(f&&(a==n/2||b==n/2)){
if(a==n/2) cout<<'T';
else cout<<'A';
return 0;
}
}
if(a>b) cout<<'T';
else cout<<'A';
return 0;
}
B - Fill the Gaps
题目大意
给定n个数字, 要求补齐各个数字之间的数; eg: 输入1 5 2, 输出1 2 3 4 5 4 3 2;
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int q[N];
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>q[i];
if(i>1){
if(q[i]>q[i-1]+1){
for(int j=q[i-1]+1;j<q[i];j++){
cout<<j<<' ';
}
}
else if(q[i]<q[i-1]-1){
for(int j=q[i-1]-1;j>q[i];j--){
cout<<j<<' ';
}
}
}
cout<<q[i]<<' ';
}
return 0;
}
C - AtCoder Cards
题目大意
给出两个字符串, 字符串内的字符可以随意调整顺序; 问是否有一种排序可以让两个字符串相同; 本题有个特殊规则, 字符串里的'@'字符可以被替换成'a' 't' 'c' 'o' 'd' 'e' 'r'这六个字符里的任意一个;
解题思路
我们可以先把s1和s2字符串里面各自'@'的数量存起来; 然后遍历两个字符串, 我们可以得到每个字符在s1和s2里数量的差值; eg: s1里面有1个'c', s2里面有2个'c', 那么'c'的值就是-1, 这个我们可以用map来存; 遍历完字符串之后我们接着遍历所有差值不为0的字符, 如果该字符不是atcoder里面的一个, 那么就一定配对失败; 如果是的话, 我们可以根据差值的正负来判断是用s1还是s2的'@'来抵消, 如果'@'不够就配对失败; 结束遍历之后还要再看看s1和s2剩余'@'的数量是否一致, 如果不一致自然也是配对失败;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
set<char> s;
map<char,int> mp;
signed main(){
s.insert('a');
s.insert('t');
s.insert('c');
s.insert('o');
s.insert('d');
s.insert('e');
s.insert('r');
string s1,s2;
cin>>s1>>s2;
int len=s1.size();
int x=0,y=0;
for(int i=0;i<len;i++){
if(s1[i]=='@') x++;
else mp[s1[i]]++;
}
for(int i=0;i<len;i++){
if(s2[i]=='@') y++;
else mp[s2[i]]--;
}
bool f=true;
for(auto t:mp){
char a=t.first;
int b=t.second;
if(b!=0){
if(s.count(a)==0){
f=false;
break;
}
else {
if(b>0) y-=b;
else x+=b;
if(x<0||y<0){
f=false;
break;
}
}
}
}
if(x!=y) f=false;
if(f) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
D - Bitmask
题目大意
给定一个只由1, 0, ?组成的字符串s以及一个数字n, s可以被看作是一个数的二进制表示, ?可以被替换为0或1; 在s可能表示的所有数里面, 我们需要输出小于n的最大的数, 如果没有则输出-1;
解题思路
首先我们可以把所有?看作是0, 这样我们就可以得到s可以表示的最小的数num, 然后我们可以把每个?所代表的数存到vector里面, eg: 如果?在第4位, 那么它就代表数字8; 然后我们从大到小遍历vector, 然后不断更新num直到找到答案;
注意: 之所以从大到小遍历是因为对于二进制来说, 某一位上表示的数是它前面所有位表示的数的总和+1; 如果这一位不满足才能继续看后面的, 如果满足则必须选这一位, 因为即使把后面的全选了也不如选这一位大;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
vector<int> st;
vector<int> v;
bool cmp(int a,int b){
return a>b;
}
signed main(){
string s1;
int n;
cin>>s1>>n;
reverse(s1.begin(),s1.end());
int num=0;
int a=1;
for(int i=0;i<s1.size();i++){
if(s1[i]=='1') num+=a;
else if(s1[i]=='?') v.push_back(a);
a=a*2;
}
sort(v.begin(),v.end(),cmp);
if(num>n) cout<<-1;
else if(num==n) cout<<n;
else{
for(int x:v){
int y=num+x;
if(y>n) continue;
else if(y==n){
cout<<n;
return 0;
}
else num=y;
}
cout<<num;
}
return 0;
}
E - Pac-Takahashi
题目大意
题目给定了由1~n编号的n个顶点, 初始情况下没有边与他们相连; 接下来有k次操作, 每次操作有两种选择: 一是"1 u v" 表示建立一条边将顶点u和v相连; 二是"2 u" 表示删除所有与顶点u相连的边;
对于每一次操作结束后, 需要输出当前有多少个顶点是没有边与它们相连的
解题思路
题目问孤立点的个数, 但是我们更容易求出联通点的个数, 最后用总数减一下即可;
我们可以用一个setst[N]来储存每个点都有哪些点与其相连; 对于1操作直接插入即可, 对2操作我们可以用erase清楚其联通点与当前点的边, 再用clear处理当前点即可; 注意数量的变化, 什么时候+1或者-1;
神秘代码
F - Anti-DDoS
题目大意
在一个黑板上有n个数集, 且所有集合里的数都是1～m; 现在定义一种操作, 如果两个集合有至少一个相同的数字元素, 那么我们可以删除这两个集合, 然后把这两个集合的并集加进来, 请问最少需要多少次操作可以让1和m位于同一个集合里;
解题思路
这题我是没做出来, 看了佬的解析才发现这竟然是一个最短路问题; 我们可以把每个集合也看作是一个中心点, 集合里的数都与中心点通过无向边相连, 这样就把所有集合整合成了一个无向图, 为了避免混淆, 我们可以让中心点从m+1开始编号; 因为我们只记录进行了几次操作, 也就是并了多少个集合, 所以只有中心点的边权为1, 其他都为0; 在这个无向图里面我们找到从1到m的最短距离即为所求; (太强了Orz)
注意: 是只需要1和m在一个集合即可, 不是1~m; (当时就读错题了.....)
神秘代码