当前位置：首页 > article >正文

AtCoder Beginner Contest 329 题解A~F

article 2024/9/20 12:04:44

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

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

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

#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

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

利用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()
{IOS
    int 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位置，因为是颜色，故用平衡树

如果按照题目的要求直接写不加优化的话亲测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()
{IOS
   int 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;
}

查看全文

http://www.kler.cn/news/135693.html