【题目记录】——CodeForce Deltix Round, Summer 2021

缺乏、安全感 2022-09-14 09:23 113阅读 0赞

### 文章目录 ###

*  B. Take Your Places! 思维+字符串
 *  C. Compressed Bracket Sequence 思维+括号匹配+序列
 *  D Take a Guess 位运算公式

# B. Take Your Places! 思维+字符串 #

题目地址[B. Take Your Places!][B. Take Your Places]  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rCU5rS-6aOe6bmw_size_20_color_FFFFFF_t_70_g_se_x_16]  
题目大意：给一个长为n的序列，每次操作只能将相邻的两个数字交换位置，问最少需要多少次操作让序列中所有与奇数相邻的数都是偶数，与偶数相邻的数都是奇数，若无法实现则输出-1  
**思路**：首先看到当奇数和偶数的差值大于1时就不可能实现目标，输出-1。  
关键是从结果的角度入手进行分类，还有就是将一个数移到某个位置所需的交换次数。  
然后是看最后的结果，如果是奇数的个数比偶数多那么结果就是奇数在第一个，如果是偶数的个数比奇数多，那么就是偶数在第一位，如果奇数和偶数个数相同，结果就是奇数在前和偶数在前取最小值。  
当时做的时候知道了这个情况，但是不知道怎么算交换次数。。。  
**交换次数的计算**：因为只有奇数和偶数所以我们只需要关注奇数（偶数）需要放的位置，奇数（偶数）排好之后偶数（奇数）就已经排好了。  
我当时写的代码并不是按这个思路算的，而是将所有奇数偶数的位置都放了一次，最后除了个2，好吧，我承认我有赌的成分。  
但最后还是对了，后面我补了一个正确解法。

//错误实例
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=1e5;
    //int a[N];
    vector<int> ev,od;
    void solve()
    { 
        int n;
        scanf("%d",&n);
        int odd = 0,even = 0;
        for(int i = 1;i <= n;i++)
        { 
            int t;
            scanf("%d",&t);
            if(t%2)
            { 
                odd++;
                od.push_back(i);
            }
            else
            { 
                even++;
                ev.push_back(i);
            }
        }
        ll ans = 0;
        if(abs(even-odd)>=2)
        { 
            printf("-1\n");
        }
        else if(even>odd)
        { 
            int odt = 0,evt = 0;
            for(int i = 1;i <= n;i++)
            { 
                if(i%2)
                { 
                    ans+=abs(ev[evt]-i);
                    evt++;
                }
                else
                { 
                    ans+=abs(od[odt]-i);
                    odt++;
                }
            }
            printf("%lld\n",ans/2);
        }
        else if(odd > even)
        { 
            int odt = 0, evt = 0;
            for(int i = 1;i <= n;i++)
            { 
                if(i%2)
                { 
                    ans+=abs(od[odt]-i);
                    odt++;
                }
                else
                { 
                    ans+=abs(ev[evt]-i);
                    evt++;
                }
            }
            printf("%lld\n",ans/2);
        }
        else
        { 
            ll ans1 = 0;
            int odt = 0, evt = 0;
            for(int i = 1;i <= n;i++)
            { 
                if(i%2)
                { 
                    ans+=abs(od[odt]-i);
                    odt++;
                }
                else
                { 
                    ans+=abs(ev[evt]-i);
                    evt++;
                }
            }
            odt = 0, evt = 0;
            for(int i = 1;i <= n;i++)
            { 
                if(i%2)
                { 
                    ans1+=abs(ev[evt]-i);
                    evt++;
                }
                else
                { 
                    ans1+=abs(od[odt]-i);
                    odt++;
                }
            }
            printf("%lld\n",min(ans1,ans)/2);
        }
        od.clear();
        ev.clear();
    }
    
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    // int t = 1;
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

//正确示例：
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N=1e5;
    void solve()
    { 
        int n;
        scanf("%d",&n);
        ll ans1 = 0, ans2 = 0;
        int odt = 1, evt = 1;
        for(int i = 1;i <= n;i++)
        { 
            int t;
            scanf("%d",&t);
            if(t%2)
            { 
                ans1 += abs(i-(2*odt-1));
                odt++;
            }
            else
            { 
                ans2 += abs(i-(2*evt-1));
                evt++;
            }
        }
        if(abs(evt-odt)>=2)
        { 
            printf("-1\n");
        }
        else if(evt>odt)
        { 
            printf("%lld\n",ans2);
        }
        else if(odt > evt)
        { 
            printf("%lld\n",ans1);
        }
        else
        { 
            printf("%lld\n",min(ans1,ans2));
        }
    }
    
    int main()
    { 
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# C. Compressed Bracket Sequence 思维+括号匹配+序列 #

题目地址[C. Compressed Bracket Sequence][]  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rCU5rS-6aOe6bmw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
**题目大意**：给一个数字序列，奇数位置的数表示左括号的数量，偶数位置的数表示右括号数量，问整个序列中有多少合法连续子序列  
**错误**：我当时没有想到遍历应该如何处理类似于"(())()()"这种序列的组合情况，所以一直没想着往遍历的方向上想这个问题。当时是这么想的，把能消掉的先消掉，然后能连到一起的几组括号就按照排列组合的计算方法计算，结果最后还是没做出来。我当时没有注意到几组括号能连到一起的条件，如果右括号多余了，那个前面几组括号就不可能跟后面的连接到一起了，跳出循环，如果左括号多余了，就向后累加多余的左括号，不做其他处理。  
对于“()()()”这种连续的序列的遍历方式是这样的，需要两个指针，第一个指针从最左边一组括号开始，第二个指针从下一组括号开始根据条件判断第一个指针所在括号是否能与当前指针所在括号连到一起，如果能就连到一起看做一组合法括号，然后直到第二个指针向右移动结束，第一个指针向右循环即可。  
遍历的过程类似下面这样求"abc"的连续子串  
a,ab,abc,b,bc,c  
**思路**：那么整体思路就是上面叙述的那样了，

/* ** */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const ll N = 1006;
    ll a[N];
    void solve()
    { 
        int n;
        scanf("%d",&n);
        for(int i = 1;i <= n;i++)
        { 
            scanf("%d",a+i);
        }
        ll ans = 0;
        for(int i = 2;i <= n;i+=2)
        //小细节，从右括号开始遍历，就不需要考虑n为奇数的情况了
        //每一次循环计算的是当前组括号的对数，以及他能够连接右边的括号的数量
        { 
            ll lef;    //当前剩余的左括号数量
            ll _lef;   //后面剩余的左括号的数量
            if(a[i]<=a[i-1])
            { 
                lef=(a[i-1]-a[i]);
                _lef = 0;
                ans+=a[i];
            }
            else
            { 
                ans+=a[i-1];
                continue;
            }
            for(int j = i+2;j <= n;j+=2)
            { 
                if(a[j] < a[j-1])
                { 
                    _lef += (a[j-1]-a[j]);
                }
                else
                { 
                    ll righ = a[j]-a[j-1];
                    if(righ<_lef)
                    { 
                        _lef-=righ;
                    }
                    else        //righ=_lef在这里处理是因为当多余的右括号为0时，也会有一个连续几组的括号序列是符合条件的
                    { 
                        righ-=_lef;
                        _lef = 0;
                        if(righ > lef)
                        { 
                            ans+=(lef+1);
                            break;
                        }
                        else
                        { 
                            ans += (righ + 1);
                            lef -= righ;
                        }
                    }
                }
            }
        }
        printf("%lld\n",ans);
    }
    
    int main()
    { 
    	ll t = 1;
    	while(t--)
    	{ 
    		solve();
    	}
        return 0;
    }

# D Take a Guess 位运算公式 #

题目地址[D Take a Guess][]  
**题目大意**：求出一个长度为n的序列里第k大的数，每次操作可询问下标为i,j对应两个数的与值与或值，在操作数量小于2n的情况下求出答案。  
**思路**：根据位运算的性质，有这样两个公式

> a+b=a&b+a|b  
> a+b=2\*(a&b)+a^b

这样每两次操作直接求出a&b与a|b，进而得到a^b，假设p\[i\]=a\[i\] ^ a\[i+1\]，进而可以用2n-2次操作求出整个p，随后知道a的任意一项即可得到整个序列值.  
关键就是这两个公式  
AC代码：

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    int k,n,a[maxn],x,y,b[3],p[maxn];
    int main() { 
        scanf("%d%d",&n,&k);
        for(int i=1; i<=n-1; i++) { 
            printf("and %d %d\n",i,i+1);//设置下标
            fflush(stdout);//刷新标准输出，我也不知道为什么，题目这么要求的
            scanf("%d",&x);//与
            printf("or %d %d\n",i,i+1);//设置下标
            fflush(stdout);
            scanf("%d",&y);
            if(i<=2)b[i]=x+y;//求出a[1]+a[2]和a[2]+a[3]
            p[i]=y-x;//获得异或
        }
        printf("and %d %d\n",1,3);
        fflush(stdout);
        scanf("%d",&x);
        printf("or %d %d\n",1,3);
        fflush(stdout);
        scanf("%d",&y);
        a[1]=(b[1]-b[2]+x+y)/2;
        for(int i=1;i<=n-1;i++)
            a[i+1]=a[i]^p[i];
        sort(a+1,a+1+n);
        printf("finish %d\n",a[k]);
        fflush(stdout);
        return 0;
    }

[B. Take Your Places]: https://codeforces.com/contest/1556/problem/B
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rCU5rS-6aOe6bmw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/97ed7d5d7bf445659f4028ed39050493.png
[C. Compressed Bracket Sequence]: https://codeforces.com/contest/1556/problem/C
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5rCU5rS-6aOe6bmw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/eea95b187ae44f34923cb5572fa34210.png
[D Take a Guess]: https://codeforces.com/contest/1556/problem/D