Codeforces Round #669 Div2 前三题

A - Ahahahahahahahaha

题意：

给你一个01串，最多能删去一半，删完以后要使$a_1-a_2+a_3-a_4+\dots =0$，也就是下标为奇数的数之和等于下标为偶数的数之和。

输入：

首行T，接下来T组数据，一行给出n，下一行给出n个数，即01串的主体。

4
2
1 0
2
0 0
4
0 1 1 1
4
1 1 0 0

输出：

输出删减完以后的01串。

1
0
1
0
2
1 1
4
1 1 0 0

思路：

开始想的很复杂。实际上就是讨论0和1的个数。

1. 0的个数大于等于1，也就是0的个数大于等于一半，所以直接输出所有的0；
2. 1的个数大于0，基本操作同上，但是此时需要注意，若1的个数为奇数，差值不是为0而是为1，所以是奇数少输出一个1；

B - Big Vova

参考： B. Big Vova（暴力）

题意：

给你一个长度为n的数组a，求一个数组b，可以使得数组c的字典序最大，其中
$$c_i=GCD(b_1,\dots ,b_i)$$
输入：

首行输入T，接下来T组数据，每组第一行输入n，第二行输入n个数字，即数组a本体。

7
2
2 5
4
1 8 2 3
3
3 8 9
5
64 25 75 100 50
1
42
6
96 128 88 80 52 7
5
2 4 8 16 17

输出：

按顺序输出数组b，每个元素间以空格间隔。

5 2 
8 2 1 3 
9 3 8 
100 50 25 75 64 
42 
128 96 80 88 52 7 
17 2 4 8 16 

思路：

详见链接。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 1000005
typedef unsigned long long ll;
using namespace std;

int a[N];
int b[N];
bool vis[N];

int gcd(ll c, ll b)
{
    ll tmp;
    while(b)
    {
        tmp = b;
        b = c % b; c = tmp;
    }
    return c;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        memset(vis, 0, sizeof(vis));
        int n;
        scanf("%d", &n);
        int cnt = 0;
        int maxx = -1, maxi = -1;
        for(int i = 0; i < n; i++)
        {
            scanf("%d", a + i);
            if(a[i] > maxx)
            {
                maxx = a[i];
                maxi = i;
            }
        }
        b[cnt++] = maxx;
        vis[maxi] = 1;
        for(int i = 1; i < n; i++)
        {
            int maxg = -1;
            int maxgi = -1;
            for(int j = 0; j < n; j++)
            {
                if(vis[j])
                    continue;
                if(gcd(maxx, a[j]) > maxg)
                {
                    maxg = gcd(maxx, a[j]);
                    maxgi = j;
                }
            }
            //cout << maxg << ' ' << maxgi << endl;
            b[cnt++] = a[maxgi];
            vis[maxgi] = 1;
            maxx = maxg;
        }
        for(int i = 0; i < n; i++)
            printf("%d ", b[i]);
        printf("\n");
    }
}

C - Chocolate Bunny

题意：

交互题，有一个1到n的置换（即1到n每个数出现且仅出现一次的数组），你可以询问2×n次，每次询问两个下标i和j，系统会告诉你$a_i(\mathrm{m}\mathrm{o}\mathrm{d}a{)}_j$的值。你最终要按顺序输出这个置换。

输入：

根据输出的询问，给出$a_i(\mathrm{m}\mathrm{o}\mathrm{d}a{)}_j$的值。

3

1

2

1

0

输出：

用? i j的格式询问，得到答案后用！ a b的格式输出置换。

? 1 2

? 3 2

? 1 3

? 2 1

! 1 3 2

思路：

对任意的$a_i$与$a_j$，由于置换中没有重复的数字，所以两个数一定有一个比另一个大。所以两个数互换询问后（?$a_i a_j $ ?$a_j{a}_i$），必定能问出其中一个数。如，设n>k，则n%k<k，k%n=k，所以互换询问一定能问出两个数中较小的那个数。互换询问n次，每次问两次，刚好问2×n次。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iomanip>
#define INF 0x3f3f3f3f
#define pi acos(-1)
#define N 10010
#define M 110
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int a[N];

int main()
{
    int n;
    scanf("%d", &n);
    int j = 1;
    for(int i = 2; i <= n; i++)
    {
        printf("? %d %d\n", i, j);
        fflush(stdout);
        int res1;
        scanf("%d", &res1);
        printf("? %d %d\n", j, i);
        fflush(stdout);
        int res2;
        scanf("%d", &res2);
        if(res1 > res2)
        {
            a[i] = res1;
        }
        else
        {
            a[j] = res2;
            j = i;
        }
    }
    printf("!");
    for(int i = 1; i <= n; i++)
    {
        if(!a[i])
            printf(" %d", n);
        else
            printf(" %d", a[i]);
    }
    printf("\n");
    return 0;
}

赛后总结：

• 没有及时写题解，有点记不清了，就记得A题卡了心态有点崩。还好还是涨分了。以及B题读题一直读不懂，好在C题比较简单，挽回一城。理解能力和思维还是有待提高。
• 下次一定及时写题解。说实话着急打比赛还不如慢慢来，把每一场都总结好。

多多包涵，努力进步

本文地址：https://blog.csdn.net/qq_49451105/article/details/108561549