AtCoder Beginner Contest 329 题解A~F

A - Spread

输入字符串，字符之间加上空格输出

B - Next

输出数组当中第二大的数

C - Count xxx

统计每个字符出现过的最长长度，再累加即可

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
signed main()
{IOS
int n;cin>>n;
string a;
cin>>a;
vct<int>cnt(35,0);
vct<int>mas(35,0);
if(cnt[a[0]-'a']==0){cnt[a[0]-'a']++;mmax(mas[a[0]-'a'],cnt[a[0]-'a']);}
for(int i=1;i<n;i++){if(cnt[a[i]-'a']==0){cnt[a[i]-'a']++;mmax(mas[a[i]-'a'],cnt[a[i]-'a']);}if(a[i]==a[i-1]){cnt[a[i]-'a']++;}else {mmax(mas[a[i-1]-'a'],cnt[a[i-1]-'a']);cnt[a[i-1]-'a']=0;}
}int ans=0;
mmax(mas[a[n-1]-'a'],cnt[a[n-1]-'a']);
for(int i=0;i<35;i++){ans+=mas[i];
}
cout<<ans<<endl;return 0;
}

D - Election Quick Report

给定数组，每次第次的票加一，每次都输出最多票的人,

我们用记录当前最大票数的人，在第次投票时，答案只有和两个人，每次视情况输出，并且更新的值即可.

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
bool cmp(int a,int b){return a>b;
}
signed main()
{IOS
int n,m;cin>>n>>m;
vct<int>a(m+1);
vct<int>cnt(n+1);cin>>a[1];
int mas=a[1];cout<<a[1]<<endl;
cnt[a[1]]++;
for(int i=2;i<=m;i++){cin>>a[i];cnt[a[i]]++;if(a[i]!=mas){if(cnt[a[i]]>cnt[mas]){mas=a[i];printf("%lld\n",mas);}else if(cnt[a[i]]==cnt[mas]&&a[i]<mas){mas=a[i];printf("%lld\n",mas);}else {printf("%lld\n",mas);}}else{printf("%lld\n",mas);}}return 0;
}

 E - Stamp

给一张空白的纸，一个印章,问是否可以印成的样子(印章每次会覆盖重复的部分) 

利用BFS搜索

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N= 2e5+7;
signed main()
{IOSint n,m;cin>>n>>m;string s,t;cin>>s>>t;vct<bool>st(N);queue<int> q;for(int i=0;i+m-1<n;i++){bool flag=1;for(int j=0;j<m;j++){if(s[i+j]!=t[j])flag=0;}if(flag)q.push(i),st[i]=1;}while(!q.empty()){int u=q.front();q.pop();for(int j=0;j<m;j++)s[u+j]='#';for(int i=max(u-m+1,0*1ll);i<=u+m-1&&i+m-1<n;i++){if(!st[i]){int flag=1;for(int j=0;j<m;j++){if(s[i+j]!='#'&&s[i+j]!=t[j])flag=0;}if(flag)q.push(i),st[i]=1;}}}bool isok=1;for(int i=0;i<n;i++){if(s[i]!='#')isok=0;}if(isok)cout<<"Yes"<<endl;else cout<<"No"<<endl;return 0;
}

F - Colored Ball

每次操作将a位置当中的元素，放到b位置，因为是颜色，故用set集合

如果按照题目的要求直接写不加优化的话亲测TLE

故当a当中的元素多于b的时候，交换a,b当中的元素，再插入a,效果相同，这样可以达到最优效果

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define INF 0x3f3f3f3f
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define int long long
#define pb push_back
#define vct vector
#define checkbit __builtin_popcount
#define gcd __gcd
#define use int T;cin>>T;while(T--)
#define LEN length()
#define all(a) a.begin(),a.end()
template<class T> bool mmax(T &u, T v) { return u < v ? (u = v, 1) : 0; }
template<class T> bool mmin(T &u, T v) { return u > v ? (u = v, 1) : 0; }
#define lowbit(x) (x&(-x))
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
using namespace std;
typedef pair<int,int>pii;
const int N= 2e5+7;
signed main()
{IOSint n,q;cin>>n>>q;int x;set<int>tot[n+1];for(int i=1;i<=n;i++){cin>>x;tot[i].insert(x);}while(q--){int a,b;cin>>a>>b;if(tot[a].size()>tot[b].size())swap(tot[a],tot[b]);for(auto z:tot[a]){tot[b].insert(z);}tot[a].clear();cout<<tot[b].size()<<"\n";}return 0;
}