Codeforces Round #629 (Div. 3)

Codeforces Round #629 (Div. 3)

A.Divisibility Problem

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    //IN
    int _;cin>>_;
    while(_--){
        ll a,b;
        sc("%lld%lld",&a,&b);
        if(a%b==0)O(0);
        else{
            ll x=a/b;
            O((x+1)*b-a);
        }
    }
}

B.K-th Beautiful String

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
   // IN
    int _;cin>>_;
    while(_--){
        int n,k;
        sc("%d%d",&n,&k);
        if(n==2){
            O("bb");continue;
        }
        int a=n-2;
        for(;a;){
            int b=n-a-1;
            if(k>b)k-=b,a--;
            else break;
        }
        for(int i=0;i<a;i++)putchar('a');putchar('b');
        for(int i=0;i<n-a-1-k;i++)putchar('a');putchar('b');
        for(int i=0;i<k-1;i++)putchar('a');putchar(10);
    }
}

C.Ternary XOR

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    //IN
    int _;cin>>_;
    while(_--){
        int n;sc("%d",&n);
        vector<int>y(n,0),p(n,0);
        int b[3]={0};
        string x;cin>>x;
        for(int i=0;i<n;i++){
            if(x[i]=='0')y[i]=0,p[i]=0;
            else if(x[i]=='2'){
                if(b[1])y[i]=0,p[i]=2;
                else y[i]=1,p[i]=1;
            }
            else {
                if(b[1])y[i]=0,p[i]=1;
                else y[i]=1,p[i]=0;
            }
            b[x[i]-'0']=1;
        }
        for(int i=0;i<n;i++)pr("%d",y[i]);O("");
        for(int i=0;i<n;i++)pr("%d",p[i]);O("");
    }
}

D.Carousel

答案只能是1，2，3；去掉末尾和首项相同的元素，如果长度为1就是1，长度偶数或者长度减小了就是2，
否则再找有没有相邻相同的，有就是2，否则就是3.细节处理起来有点麻烦。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int t[N],a[N];
int main(){
    //IN
    int q;cin>>q;
    while(q--){
        int n;sc("%d",&n);
        for(int i=0;i++<n;sc("%d",&t[i]),a[i]=t[i]);
        int m=n;
        while(a[1]==a[m]&&m)m--;
        if(m<=1){
            O(1);
            for(int i=0;i<n;i++)pr("1 ");
            O("");continue;
        }
        if(n%2==0){
            O(2);
            for(int i=0;i<n;i++)pr("%d ",i%2==0?2:1);
            O("");
            continue;
        }
        if(n==m){
            int p=0;
            for(int i=1;i<n;i++){
                if(t[i]==t[i+1]){
                    p=i;break;
                }
            }
            if(p){
                O(2);
                for(int i=1;i<=p;i++)pr("%d ",i%2==0?2:1);
                if(p&1)pr("1 ");else pr("2 ");
                for(int i=p+2;i<=n;i++)pr("%d ",i%2==0?1:2);
                O("");
            }else{
                O(3);
                for(int i=1;i<n;i++)pr("%d ",i%2==0?2:1);
                O(3);
            }
        }else{
            O(2);
            for(int i=0;i<n;i++)pr("%d ",i%2==0?1:2);
            O("");
        }
    }
}

E.Tree Queries

这题转化为求k个点是否在一条链上，可以用序判断，对于，两个点，，
他们在一条链上的条件为： ,对深度排序，可以满足这种关系。
或者对于所有节点 。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int k[N],f[N];
int L[N],R[N],t;
vector<int>g[N];
int n,m;
void dfs(int u,int fa){
    f[u]=***]=++t;
    for(int& v:g[u]){
        if(v==fa)continue;
        dfs(v,u);
    }
    R[u]=t;
}
int main(){
    sc("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);f[1]=1;
    while(m--){
        int x;sc("%d",&x);
        for(int i=0;i++<x;sc("%d",&k[i]),k[i]=f[k[i]]);
        int mx=n,ma=1;
        for(int i=1;i<=x;i++)mx=min(mx,R[k[i]]),ma=max(ma,L[k[i]]);
        int ok=ma<=mx;
        puts(ok?"YES":"NO");
    }
}

F.Make k Equal

先排序，枚举当序列都变成时的最小值，分几种情况讨论。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(const T& s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>&it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,k;
int a[N],x=0,cnt=0;
ll pre[N],suf[N];
int main(){
    cin>>n>>k;
    for(int i=0;i++<n;sc("%d",&a[i]));sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+a[i];
    for(int i=n;i>=1;i--)suf[i]=suf[i+1]+a[i];
    for(int i=2;i<=n;i++)if(a[i]==a[i-1])x++;else cnt=max(cnt,x),x=1;cnt=max(cnt,x);
    if(cnt>=k)return O(0);ll ans=1e18+11;
    for(int i=1;i<=n;i++){
        ll res=1LL*(i-1)*a[i]-pre[i-1]-1LL*a[i]*(n-i)+suf[i+1]-(n-k);
        if(i>=k)res=min(res,1LL*(i-1)*a[i]-pre[i-1]-(i-k));
        if(n-i+1>=k)res=min(res,suf[i+1]-1LL*(n-i)*a[i]-(n-i+1-k));
        ans=min(ans,res);
    }
    O(ans);
}
全部评论

相关推荐

11-20 23:18
Fachhochschule lübeck Erlang
点赞 评论 收藏
分享
11-18 23:23
中国药科大学 外贸业务员
点赞 评论 收藏
分享
11-19 12:12
北京理工大学 管理培训生
点赞 评论 收藏
分享
点赞 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
299007次浏览 2638人参与
# 如果不工作真的会快乐吗 #
58853次浏览 515人参与
# 阿里云管培生offer #
16795次浏览 294人参与
# 地方国企笔面经互助 #
3724次浏览 9人参与
# 美团求职进展汇总 #
1326669次浏览 12446人参与
# 选完offer后，你后悔学本专业吗 #
19636次浏览 143人参与
# 北方华创开奖 #
26415次浏览 285人参与
# 正在实习的你，几点下班 #
51591次浏览 385人参与
# 国央企薪资爆料 #
8000次浏览 65人参与
# 如何一边实习一边秋招 #
991874次浏览 12638人参与
# 提前批简历挂麻了怎么办 #
146349次浏览 1948人参与
# 学历or实习经历，哪个更重要 #
50849次浏览 401人参与
# 海康威视求职进展汇总 #
398668次浏览 3405人参与
# 米哈游求职进展汇总 #
175790次浏览 1458人参与
# 投递实习岗位前的准备 #
1178901次浏览 18390人参与
# 面试体验感最好的是哪家？ #
85015次浏览 845人参与
# 实习生应该准时下班吗 #
167359次浏览 1159人参与
# 得物求职进展汇总 #
66155次浏览 682人参与
# 求职遇到的搞笑事件 #
70682次浏览 576人参与
# 网申一定要掌握的小技巧 #
5309次浏览 53人参与
# 0offer是寒冬太冷还是我太菜 #
897858次浏览 8008人参与
# 腾讯求职进展汇总 #
195694次浏览 1641人参与
牛客网
牛客企业服务