Codeforces Round #653 (Div.3)

A.Required Remainder

思路

水题，直接上代码。

#include<bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	IO;
    int t;cin>>t;
    while(t--)
    {
        int x,y,k;cin>>x>>y>>k;
        int times=k/x;
        if(times*x+y<=k)cout<<times*x+y<<"\n";
        else cout<<(times-1)*x+y<<"\n";
    }	
    return 0;
}

B.Multiply by 2, divide by 6

思路

水题，直接上代码。

#include<bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	IO;
    int t;cin>>t;
    while(t--)
    {
        int n,num=0;cin>>n;
        while(1)
        {
            if(n%6==0)n/=6,num++;
            else if(n%3==0)n/=3,num+=2;
            else break;
        }
        if(n==1)cout<<num<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}

C.Move Brackets

思路

简单贪心。

#include<bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	IO;
	int t;cin>>t;
    while(t--)
    {
        int n;cin>>n;
        int del=0,ans=0;string s;cin>>s;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]==‘(‘)del++;
            else
            {
                if(!del)ans++;
                else del--;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

D. Zero Remainder Array

思路

很显然所有元素进行%k处理，考虑到不论做哪一种操作X每次都增加1，实际上答案就是（X在0~K-1这个区间中循环的次数-1）*K+（K-最后一次循环时剩下的最大那个数）+1，那么开map记下出现次数最多且数值最大的余数及其出现次数，套进公式就能A，结果记得开long long。

\(ans=(maxx-1)*k+k-maxpos+1\)

#include<bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);//cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=2e5+50;
int a[maxn];
map<int,int> mp;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	IO;
	int t;cin>>t;
    while(t--)
    {
        mp.clear();
        ll n,k,maxx=0,tot=0,maxpos=-1;cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            if(a[i]%k)
            {
                tot++;mp[a[i]%k]++;
                if(maxx<mp[a[i]%k])maxx=mp[a[i]%k],maxpos=a[i]%k;
                else if(maxx==mp[a[i]%k]&&maxpos>a[i]%k)maxpos=a[i]%k;
            }
        }
        //cout<<"maxx="<<maxx<<" maxpos="<<maxpos<<" tot="<<tot<<"\n";
        if(tot==0)cout<<0<<"\n";
        else cout<<(ll)(maxx-1)*(ll)k+(ll)k-(ll)maxpos+1<<"\n";
    }
    return 0;
}

E1.Reading Books (easy version)

思路

用集合可以轻松模拟解决的问题，开三个mutliset (开了set的我查了半个小时的错~_~) 分别存两个人都喜欢的书、只有A喜欢的书、只有B喜欢的书，如果第一个集合与第二个集合之和、第一个集合与第三个集合之和均≥k即有解，由于 set和 multiset自动排序，接下来就直接分情况从三个集合里取首元素进行比较，取完一个删一个，答案累加在ans中就完事啦。（具体分情况直接见代码）

#include<bits/stdc++.h>
#define ll long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
multiset<int>s1,s2,s3;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	//IO;
	int n,k;cin>>n>>k;
    for(int i=1,f1,f2,tmp;i<=n;i++)
    {  
        cin>>tmp>>f1>>f2;
        if(f1==1&&f2==1)s1.insert(tmp);
        else if(f1==1&&f2==0)s2.insert(tmp);
        else if(f1==0&&f2==1)s3.insert(tmp);
    }
    if((s1.size()+s2.size()<k)||(s1.size()+s3.size()<k))return cout<<-1,0;
    int tot1=0,tot2=0,ans=0;
	while(1)
    {
        //cout<<"tot1="<<tot1<<" tot2="<<tot2<<"\n";
        //system("pause");
        if(tot1>=k&&tot2>=k)break;
        if(tot1>=k&&tot2<k)
        {
            //cout<<1;
            if(s1.size()&&s3.size())
            {
                //cout<<1<<"gg\n";
                if(*s1.begin()<=*s3.begin())ans+=*s1.begin(),s1.erase(s1.begin());
                else ans+=*s3.begin(),s3.erase(s3.begin());
            }
            else if(s1.size())ans+=*s1.begin(),s1.erase(s1.begin());
            else ans+=*s3.begin(),s3.erase(s3.begin());
            tot2++;
        }
        else if(tot1<k&&tot2>=k)
        {
            //cout<<2;
            if(s1.size()&&s2.size())
            {
                //cout<<1<<"gg\n";
                if(*s1.begin()<=*s2.begin())ans+=*s1.begin(),s1.erase(s1.begin());
                else ans+=*s2.begin(),s2.erase(s2.begin());
            }
            else if(s1.size())ans+=*s1.begin(),s1.erase(s1.begin());
            else ans+=*s2.begin(),s2.erase(s2.begin());
            tot1++;
        }
        else
        {
            //cout<<3;
            if(s1.size()&&s2.size()&&s3.size())
            {
                //cout<<1<<"gg\n";
                if(*s1.begin()<=*s2.begin()+*s3.begin())ans+=*s1.begin(),s1.erase(s1.begin());
                else ans+=*s2.begin()+*s3.begin(),s2.erase(s2.begin()),s3.erase(s3.begin());
            }
            else if(s1.size())ans+=*s1.begin(),s1.erase(s1.begin());
            else ans+=*s2.begin()+*s3.begin(),s2.erase(s2.begin()),s3.erase(s3.begin());
            tot1++;tot2++;
        }
    }
    cout<<ans;
    return 0;
}

E2.Reading Books (hard version) && F.Cyclic Shifts Sorting

思路

没有想到特别完美的解法= =
(其实就是我懒得想，跑去%大神题解了QAQ)

Codeforces Round #653 (Div.3) 部分题解

原文：https://www.cnblogs.com/-Dominate-/p/13284345.html