Codeforces Round #580 (Div. 2)

- 日理万妓 2023-06-04 11:58 9阅读 0赞

## Solutions ##

--------------------

### A. Choose Two Numbers ###

题意：  
给出\\(A,B\\)两个集合，\\(A,B\\) 集合分别选一个数\\(a,b\\) ，使得\\(a+b\\notin\\ A,B\\)  
思路：  
每个集合选出最大值，必定满足条件。emmmmm比赛的时候傻了。

### B. Make Product Equal One ###

题意：  
给出\\(a\_1,a\_2,\\dots,a\_n\\)，可以进行任意次操作：选择其中任意一个数\\(+1,-1\\)，使得最后\\(a\_1\{\\ast\}a\_2\{\\ast\}\\dots\{\\ast\}a\_n=1\\)。  
思路：  
负数就变为\\(-1\\)，整数就变为\\(1\\)，但是若负数个数为奇数，则需要有一个变为\\(1\\)，但是存在\\(0\\)的话，则不需要。

### C. Almost Equal ###

题意：  
给出数字\\(n\\)，你需要安排的数为\\(1\\sim2n\\)，组成一个环。每连续\\(n\\)个数求一次和\\(sum\_i\\),输出一个合法的序列，使得\\(\{\\forall\}i,j,\\ \{\\mid\}sum\_i-sum\_j\{\\mid\}\{\\leq\}1\\)  
思路：  
比赛时我构造出序列，然后队友写出\\(check\\) 代码，构造时发现分为两部分，右边最上面写一个最大的，左边最下面写次大的，然后左边再写次次大的，右边再写次次次大的，交替进行。可以理解为右边为先手，然后左边变为先手。构造完以后，用数组模拟成环，然后前缀和搞一搞模拟\\(check\\) 即可。  
正解：  
我们定义\\(s\_i=a\_i+a\_\{i+1\}+a\_\{i+2\}+\{\\dots\}+a\_\{i+n-1\}\\)，  
\\(S\_\{i+1\}-S\_\{i\}=\\left(a\_\{i+1\}+a\_\{i+2\}+a\_\{i+3\}+\\cdots+a\_\{i+n\}\\right)-\\left(a\_\{i\}+a\_\{i+1\}+a\_\{i+2\}+\\cdots+a\_\{i+n-1\}\\right)=a\_\{i+n\}-a\_\{i\}\\) 根据题意有\\(\{\\mid\}a\_\{i+n\}-a\_i\{\\mid\}\{\\leq\}1\\)，因为\\(a\\)数组都是不同的，所以\\(\{\\mid\}a\_\{i+n\}-a\_i\{\\mid\}=1\\)  
则根据题意有：\\(a\_\{i+n\}-a\_i,a\_\{i+n+1\}-a\_\{i+1\}\\) 有相反的符号。 证：若他们都等于\\(1\\)，则\\(S\_\{i+2\}-S\_i=(S\_\{i+2\}-S\_\{i+1\})+(S\_\{i+1\}-S\_\{i\})=(a\_\{i+n+1\}-a\_\{i+1\})+(a\_\{i+n\}-a\_i)=2\\)，若都为\\(-1\\)也一样。因此，对于\\(a\_\{i+n\}-a\_i\\)，他们是交替的\\(1,-1,1,\\dots\\)。

*  如果\\(n\\)为偶数，存在矛盾\\(a\_\{i+n\}-a\_i=-(a\_\{(i+n)+n\}-a\_\{i+n\})\\)，但是由于交替，所以他们应该是相等的
 *  如果\\(n\\)为奇数，\\(i:1\{\\sim\}n\\)
    
     *  若\\(i\\)为奇数，\\(a\_i=2i,a\_\{i+n\}=2i-1\\)
     *  若\\(i\\)为偶数，\\(a\_i=2i-1,a\_\{i+n\}=2i\\)

//#define DEBUG
    #include<bits/stdc++.h>
    using namespace std;
    #define lson (rt<<1)
    #define rson (rt<<1|1)
    const int N=100010;
    const int inf=0X3f3f3f3f;
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    const double eps = 1e-6;
    const double pi = acos(-1.0);
    const int mod = 1000000007;
    typedef long long ll;
    
    int a[N],b[N],c[4*N];
    ll ans[4*N];
    int main() {
        #ifdef DEBUG
        freopen("in.txt","r",stdin);
        #endif
        int n;
        scanf("%d",&n);
        bool flag=true;
        int cura=0,curb=0;
        int x=2*n;
        while(x) {
            if(flag) {
                b[++curb]=x--;
                a[++cura]=x--;
            } else {
                a[++cura]=x--;
                b[++curb]=x--;
            }
            flag=!flag;
        }
        int cur=0;
        for(int i=cura;i>=1;i--) c[++cur]=a[i];
        for(int i=curb;i>=1;i--) c[++cur]=b[i];
        int len=cur;
        for(int i=1;i<=len;i++) c[++cur]=c[i];
        //for(int i=1;i<=cur;i++) printf("%d\n",c[i]);
        set<ll> s;
        for(int i=1;i<=n;i++)ans[i]=ans[i-1]+c[i];
        s.insert(ans[n]);
        for(int i=n+1;i<=3*n;i++){
            ans[i]=ans[i-1]-c[i-n]+c[i];
            s.insert(ans[i]);
        }
        if(s.size()>2)puts("NO");
        else if(s.size()==2){
            set<ll>::iterator it=s.begin();
            ll s1,s2;
            s1=*it;
            it++;
            s2=*it;
            if(abs(s1-s2)!=1)puts("NO");
            else {
                puts("YES");
                for(int i=1;i<=2*n;i++)printf("%d%c",c[i],i==2*n?'\n':' ');
            }
        }
        else {
            puts("YES");
            for(int i=1;i<=2*n;i++)printf("%d%c",c[i],i==2*n?'\n':' ');
        }
    }

### D. Shortest Cycle ###

题意：  
给出\\(a\_1,a\_2,\{\\dots\},a\_n\\)，当作图中的\\(n\\)个点，对于\\(\{\\forall\}i,j(i\{\\neq\}j),a\_i\\&a\_j\{\\neq\}0\\)，\\(a\_i\\)和\\(a\_j\\)连一条边，然后求最小环。  
思路：  
比赛时队友考虑二进制，都把\\(60\\)个位置画出来了。我也准备好\\(floyd\\)最小环了。但是沙雕了，感觉每个位置都连边，复杂度太大emmmmmm。其实二进制对应位置\\(1\\)的个数大于\\(2\\)，那么最小环就是\\(3\\)，然后最多\\(120\\)个点\\(60\\)条边（可能不确切），然后\\(floyd\\)跑最小环即可。  
\\(floyd\\)求最小环：\\(d\[i\]\[j\]\\)为\\(i\\)到\\(j\\)不包含\\(k\\)点的最短距离。所以对于当前\\(k\\)，我们已经求得\\(1\{\\sim\}k-1\\)的\\(d\[i\]\[j\]\\)，然后枚举\\(1\{\\sim\}k-1\\)的\\(d\[i\]\[j\]\\)，然后更新答案，\\(ans=min(ans,a\[i\]\[k\]+a\[k\]\[j\]+d\[i\]\[j\])\\)，表示包含\\(k\\)的环，其中\\(a\\)数组为最初距离。

//#define DEBUG
    #include<bits/stdc++.h>
    using namespace std;
    const int N=100010;
    const int inf=0X3f3f3f3f;
    const long long INF = 0x3f3f3f3f3f3f3f3f;
    const double eps = 1e-6;
    const double pi = acos(-1.0);
    const int mod = 1000000007;
    typedef long long ll;
    
    int ans=60;
    ll b[N],a[150][150],d[150][150];
    int tot;
    
    int main() {
        #ifdef DEBUG
        freopen("in.txt","r",stdin);
        #endif
        int n;
        scanf("%d",&n);
        ll x;
        for(int i=1;i<=n;i++) {
            scanf("%lld",&x);
            if(x) b[++tot]=x;
        }
        for(int i=0;i<=60;i++) {
            int cnt=0;
            for(int j=1;j<=tot;j++) {
                if(b[j]&(1ll<<i)) ++cnt;
            }
            if(cnt>=3) {puts("3");return 0;}
        }
        for(int i=1;i<=tot;i++) {
            for(int j=1;j<=tot;j++)
                if(i==j) d[i][j]=a[i][j]=0;
                else d[i][j]=a[i][j]=inf;
        }
        for(int i=1;i<=tot;i++) {
            for(int j=1;j<=tot;j++) {
                if(i==j) continue;
                if(b[i]&b[j]) a[i][j]=d[i][j]=1;
            }
        }
        //memcpy(d,a,sizeof(a));
        for(int k=1;k<=tot;k++) {
            for(int i=1;i<=k-1;i++) {
                for(int j=1;j<=k-1;j++)
                    if(i!=j&&a[i][k]+a[k][j]+d[i][j]<ans)
                        ans=a[i][k]+a[k][j]+d[i][j];
            }
            for(int i=1;i<=tot;i++) {
                for(int j=1;j<=tot;j++)
                    if(d[i][j]>d[i][k]+d[k][j])
                        d[i][j]=d[i][k]+d[k][j];
            }
        }
        if(ans==60) puts("-1");
        else printf("%d\n",ans);
    }

转载于:https://www.cnblogs.com/ACMerszl/p/11396093.html