Codeforces Round #628 (Div. 2)

A.
写2个数,使得gcd(a,b)+lcm(a,b)=x;
解  1和x-1即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
void work()
{
    int n;
    scanf("%d",&n);
    printf("%d %d\n",n-1,1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

B.
给长度为n个数组,问n个这样的数组排在一起的LCS(最长上升子序列)
因为有n个这样的数组,所以从每个数组中取一个的话,不需要考虑每个值在数组中的位置,所以就是数组中不重复数个数。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
void work()
{
    int n;
    scanf("%d",&n);
    set<int>s;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        s.insert(x);
    }
    printf("%d\n",s.size());
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

C.
给n个点的无向图加不重复的边权,使得u,v 之间的MEX的最大值最小(MEX为未出现的自然数中最小的那个,MEX[0,1,2,4]=3,MEX[0,2]=1,MEX[1,5]=0)
为了使得MEX的最大值最小,那么必然我们较小的数要在更少的u,v中出现,那么就把小的数分配到叶子节点的边上,这样只有u,v中一个为这个叶子时,才会包含这个值,其他任意分配即可。
证明:考虑0,1,2 这3个数,如果这3个数不在同一条链上,那么MEX必定为0,1,2中的一个,所以将0,1,2分在不同的链上即可,所以放在叶子节点的边上。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
vector<int>v[100005];
struct node
{
    int u,v;
}a[100005];
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[i].u=x;
        a[i].v=y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    int l=0;
    int r=n-2;
    for(int i=1;i<n;i++){
        if(v[a[i].u].size()==1||v[a[i].v].size()==1){
            printf("%d\n",l++);
        }else{
            printf("%d\n",r--);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

D.
给定u,v,让你生成一个数组,使得异或和为u,和为v。
首先判断不存在情况,显然如果u,v奇偶不同,那么就无法满足,然后u是必定小于等于v的。接着就是判断,根据当前二进制u[i]和v[i]的情况,如果u[i]为1并且v[i]为1,那么在这个二进制位+1即可。如果u[i]为1,v[i]为0,那么需要将一个ans[i]退到ans[i-1],这样可以使得和不变但是异或值发生变化(需要注意的是,ans[i]为0时要从上面借),如果u[i]为0,v[i]位1,那么对ans[i-1]+2,这样异或不变,和增加,如果u[i],v[i]都为0,则不需要进行操作。最后根据ans[i]的值拼凑数组即可。
发现自己想多了 简洁做法看下面那个

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
bool a[68];
bool b[68];
int ans[68];
void work()
{
    ll x,y;
    scanf("%lld%lld",&x,&y);
    int tot=0;
    for(ll tmp=1;tmp<=max(x,y);tmp*=2,tot++){
        if(x&tmp)a[tot]=1;
        if(y&tmp)b[tot]=1;
    }
    if(a[0]!=b[0]){
        printf("-1\n");return;
    }
    if(x>y){
        printf("-1\n");return;
    }
    for(int i=tot-1;i>=0;i--){
        if(a[i]&&!b[i]){
            if(ans[i]==0){
                for(int j=i+1;j<tot;j++){
                    if(ans[j]>=2){
                        ans[j]-=2;
                        for(int k=j-1;k>=i;k--){
                            ans[k]+=2;
                        }
                        ans[i]+=2;
                        break;
                    }
                }
            }
            ans[i]-=1;
            ans[i-1]+=2;
        }
        if(!a[i]&&b[i]){
            ans[i-1]+=2;
        }
        if(a[i]&&b[i]){
            ans[i]++;
        }
    }
    int sum=0;
    for(int i=0;i<tot;i++){
        sum=max(sum,ans[i]);
    }
    if(sum==0){
        printf("0\n");return;
    }
    printf("%d\n",sum);
    // for(int i=0;i<tot;i++){
    //     printf("%d ",ans[i]);
    // }
    // printf("\n");
    for(int i=1;i<=sum;i++){
        ll tmp=0;
        for(int j=0;j<tot;j++){
            if(ans[j]){
                tmp^=(1ll<<j);
                ans[j]--;
            }
        }
        printf("%lld ",tmp);
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

打扰了 发现想复杂了,弄成v=u+t+t就行了。。。(还没交)

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
bool a[68];
bool b[68];
int ans[68];
void work()
{
    ll x,y;
    scanf("%lld%lld",&x,&y);
    int tot=0;
    for(ll tmp=1;tmp<=max(x,y);tmp*=2,tot++){
        if(x&tmp)a[tot]=1;
        if(y&tmp)b[tot]=1;
    }
    if(a[0]!=b[0]){
        printf("-1\n");return;
    }
    if(x>y){
        printf("-1\n");return;
    }
    if(x==0&&y==0){
        printf("0\n");return;
    }
    if(x==y){
        printf("%d\n%lld\n",1,x);
        return;
    }
    printf("3\n%lld %lld %lld\n",y-x,(y-x)/2,(y-x)/2);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T=1;
    //scanf("%d",&T);
    //cin>>T;
    while(T--){
        work();
    }
}

 

 

“Codeforces Round #628 (Div. 2)”的3个回复

  1. Long time reader, first time commenter — so, thought I’d drop a comment..
    — and at the same time ask for a favor.

    Your wordpress site is very simplistic – hope you don’t mind me asking what theme you’re using?
    (and don’t mind if I steal it? :P)

    I just launched my small businesses site –also built in wordpress like
    yours– but the theme slows (!) the site down quite a bit.

    In case you have a minute, you can find it by searching for “royal cbd” on Google (would appreciate any
    feedback)

    Keep up the good work– and take care of yourself during the coronavirus scare!

    ~Justin

    1. Thank you for your comments.The name of the theme is Twenty Seventeen.I tried to enter your website, but it did not respond in “ask you over 18 years of olds”, no matter which one I chose.I hope this theme will help you.

发表评论

电子邮件地址不会被公开。 必填项已用*标注