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);
}
全部评论

相关推荐

头像
牛客674665490号
05-18 22:33
河南大学 计算机类
点赞 评论 收藏
转发
头像
勇敢的小猫拒绝996
今天 11:10
信息技术岗
点赞 评论 收藏
转发
头像
不想上班秋招侠就要上岸了
05-08 19:12
华中师范大学 计算机类
点赞 评论 收藏
转发
头像
thefy
05-15 19:03
已编辑
电子科技大学 计算机类
点赞 评论 收藏
转发
头像
Stank
05-16 02:58
中山大学 电子信息类
华为实习一面（技术面）
5.14下午两点的面试，岗位：硬件技术工程师里面的高频细分方向。&nbsp;流程：&nbsp;首先自我介绍（2~3分钟）不必多说。&nbsp;然后挑了个竞赛经历问（本人竞赛经历有点多），但这个竞赛（蓝桥杯单片机设计开发）是软件的，而面试官又想考察我硬件的知识，有点小微妙。问的问题里比较普遍的是：1、这个比赛的难点，以及怎么解决。2、从这个比赛里面学到什么。然后问了几句关于项目的东西，但也是很表面，偏向于介绍，可能因为项目里自己承担的部分是算法部分。&nbsp;然后做两道题，爬涉及到面试保密问题，所以这里就不说具体的问题是啥了。&nbsp;然后机试的题目里面抽一道出来回答。&nbsp;总结：一般般吧，表现得不是很优秀，...
查看2道真题和解析
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
834267次浏览 13153人参与
# 机械制造薪资爆料 #
321300次浏览 3741人参与
# 晒一晒我的offer #
3480691次浏览 55365人参与
# 0offer是寒冬太冷还是我太菜 #
429753次浏览 4954人参与
# 金三银四，你有感觉到吗 #
330712次浏览 4232人参与
# 实习生如何通过转正 #
27499次浏览 361人参与
# 海康威视求职进展汇总 #
102396次浏览 1221人参与
# 我在牛爱网找对象 #
51096次浏览 335人参与
# 毕业租房也有小确幸 #
27328次浏览 1493人参与
# 实习生应该准时下班吗 #
81276次浏览 598人参与
# 如何写一份好简历 #
276871次浏览 4113人参与
# 软件开发投递记录 #
480019次浏览 7252人参与
# 如果可以选，你最想从事什么工作 #
187052次浏览 3095人参与
# 荣耀求职进展汇总 #
71973次浏览 735人参与
# 实习必须要去大厂吗？ #
14158次浏览 225人参与
# 你遇到过哪些神仙同事 #
18908次浏览 282人参与
# 求职遇到的搞笑事件 #
19765次浏览 287人参与
# 你觉得找工作该拿大厂还是小厂练手 #
62026次浏览 873人参与
# 你觉得通信/硬件有必要实习吗？ #
23719次浏览 429人参与
# 实习工作，你找得还顺利吗？ #
43208次浏览 477人参与
牛客网
牛客企业服务