A - Ahahahahahahahaha

题意：

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

输入：

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

输出：

输出删减完以后的01串。

思路：

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

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

B - Big Vova

参考： B. Big Vova（暴力）

题意：

给你一个长度为n的数组a，求一个数组b，可以使得数组c的字典序最大，其中
$c_i=GCD(b_1,…,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 \pmod a_j$ 的值。你最终要按顺序输出这个置换。

输入：

根据输出的询问，给出 $a_i \pmod a_j$ 的值。

输出：

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

思路：

对任意的 $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;
}