题目1

题目链接
题目大意：
有n个整数的数组a，现在需要构造一个1到n的排列b；
令𝑐𝑖 = 𝑎𝑖−𝑏𝑖，希望最终𝑐𝑖 出现尽可能多的不同整数。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤40000)
每个样例两行
第一行整数𝑛(1≤𝑛≤4⋅1e4)
第二行整数𝑎1,𝑎2,…,𝑎𝑛(1≤𝑎𝑖≤1e9)

输出：
每个样例一行，输出符合要求的1-n排列。

Examples
input
3
1
100000
2
1 1
3
10 3 3

output
1
2 1
1 3 2

题目解析：
当n=1时，只有1个解；
当n=2时，假如a1<a2,那么令c[1]=a1-2,c[2]=a2-1，由于a1<a2且2>1，那么c1必然<c2;
当n=3时，同理我们可以把3、2、1依次与数组中较小值进行匹配，可以保证最终的值各不相同。

class Solution {
    static const int N = 201010;
    pair<int, int> a[N];
    int b[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i < n; ++i) {
                cin >> a[i].first;
                a[i].second = i;
            }
            sort(a, a + n);
            for (int i = 0; i < n; ++i) {
                b[a[i].second] = n - i;
            }
            for (int i = 0; i < n; ++i) cout << b[i] << " ";
            cout << endl;
        }
    }
}
ac;

题目2

题目链接
题目大意：
有一个长度为n的01字符串s，现在可以构造另外一个长度为n的字符串L，这个字符串有x个字符为1；
现在想知道当x为0、1、2、3、、、、n时，字符串s和l每个字符按照位置进行异或操作后，最终生产的字符串是否为回文串；
比如说s=101011，当x=2时，我们可以构造字符串L为010100，这样生成的字符串为111111，是回文串；

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤100000)
每个样例两行
第一行整数𝑛，表示字符串长度 (1≤𝑛≤1e5)
第二行字符串s

输出：
每个样例一行，输出长度为n+1的字符串，第i个字符为1表示可以构造有i个字符1的字符串l，使得最终生成字符串是回文串。

Examples
input
5
6
101011
5
00000
9
100100011
3
100
1
1

output
0010100
111111
0011111100
0110
11

题目解析：
首先对字符串进行回文串匹配，初始cnt=1，假如某个位置无法匹配回文串的要求，我们用cnt++记录；
这样cnt就可以表示回文串中不匹配的数量，不匹配只有01和10两种情况，此时需要一个字符串1和一个字符0，来进行异或操作；

那么最终x应该要>=cnt，因为需要提供足够多的1来修正不匹配的字符；
但是x也不能太多，因为需要有cnt数量的0来做匹配，最终x要<=n-cnt；
那是否满足cnt <= x <= n-cnt就有解呢？
还要考虑回文串中，是否为奇数。
如果回文串为偶数，那么最终的x - cnt的数量还需要是奇数；
如果回文串为奇数，存在最中间的位置可以任意操作，那么x - cnt可以为奇数或者偶数。

class Solution {
    static const int N = 201010;
    char str[N];
    int ans[N];
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            cin >> str;
            int cnt = 0;
            for (int i = 0; i < n / 2; ++i) {
                if (str[i] != str[n - i - 1]) ++cnt;
            }
            if (!cnt) ans[0] = ans[n] = 1;
            else ans[0] = ans[n] = 0;
            for (int i = 1; i < n; ++i) {
                ans[i] = 0;
                if (i >= cnt && i <= (n - cnt)) {
                    if ((i - cnt) % 2 == 0) { // 剩下为偶数，没有问题
                        ans[i] = 1;
                    }
                    else {
                        if (n % 2) ans[i] = 1; // 中间有留1个位置，可以随意变
                    }
                }
            }
            for (int i = 0; i <= n; ++i) putchar('0' + ans[i]);
            cout << endl;
        }
    }
}
ac;

题目3

题目链接
题目大意：
有一个整数数组s，长度为n；一个数组的MEX值，就是该数组没有出现过的非负整数的最小值，比如说 MEX({0,1,2,4}) = 3 .
现在Alice和Bob两个人在玩游戏，Alice先手。游戏规则如下：
Alice可以添加一个整数𝑥(0≤𝑥≤1e9)到数组中，要求该整数在数组中没有；
Bob可以移除一个整数y，y必须要小于最近一次Alice添加的整数x，并且该数字在数组存在；
Alice的目标是尽可能让数组最终的MEX值更大，Bob的目标是让最终的MEX值尽可能小。

现在让你扮演Alice，使得最终MEX尽可能大。

输入：
第一行，整数𝑡 表示t次游戏 (1≤𝑡≤100000)
每个样例有多行：
第一行整数𝑛(1≤𝑛≤1e5)
第二行整数数组s (0≤𝑠1<𝑠2<…<𝑠𝑛≤1e9)
接下来有多行，每行一个整数y：
如果y>=0，表示Bob从数组中移除该数字；
y=-1，表示该次游戏结束；

输出：
每个样例若干行，每行一个整数x，表示要添加的整数；

Examples
input
3
5
1 2 3 5 7

7

5

-1

3
0 1 2

0

-1

3
5 7 57

-1
output
8

57

0

3

0

0

样例解释：
样例一的整个操作过程 {1,2,3,5,7 } → {1,2,3,5,7,8 } → {1,2,3,5,8 } → {1,2,3,5,8,57 } → {1,2,3,8,57 } → {0,1,2,3,8,57 }. 最终游戏结束 MEX(𝑆)=4

题目解析：
题目看起来复杂，其实分析下Alice和Bob的策略，会发现逻辑比较简单：
Alice想要MEX值尽可能大，那么必须从小开始填充未出现的字符；
Bob想要MEX值尽可能小，那么必须从小开始移除出现的字符；

那么为了让题目交互起来更加简单：
先手采用这样的策略，先填充一个数字。
后手移除任何数字，都选择添加该数字。

class Solution {
    static const int N = 101010;
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            map<int, int> h;
            for (int i = 0;i < n; ++i) {
                int tmp;
                cin >> tmp;
                h[tmp] = 1;
            }
            int first = -1, second = -1;
            for (int i = 0; i < n + 10; ++i) {
                if (h.find(i) != h.end()) continue;;
                if (first == -1) {
                    first = i;
                }
                else if (second == -1) {
                    second = i;
                    break;
                }
            }
            cout << first << endl;;
            while (true) {
                int p;
                cin >> p;
                if (p == -1) break;
                cout << p << endl;
            }
        }
    }
}
ac;

题目4

题目链接
题目大意：
有若干个城市在洪水后被冲毁，现在需要重建；
我们用n x m的矩阵来表示，每个元素都代表一个城市，元素为0表示城市被摧毁，元素为1表示该城市被重建了；
城市重建有两种方式，首先是指定若干个城市直接重建；
另外一种方式，是由其他城市协助重建，可以被协助重建的条件是：
当且仅当这个城市在横、竖两个方向上，都有相邻的城市已经被重建。
比如说
10
11
右上角的城市就可以被协助重建。

现在想知道最少需要指定多少个城市，才能让所有城市都被重建。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例一行，整数 𝑛 and 𝑚 (2≤𝑛,𝑚≤100 )

输出：
每个样例一行，输出满足要求的最小重建数量。

Examples
input
3
2 2
5 7
3 2

output
2
7
3

题目解析：
首先从小样例情况开始分析，容易知道n=2，m=2的情况是：
01
10
或者
10
01
剩下的城市协助重建即可。

当增加到3x3时候，考虑可以直接从2x2的基础上开始思考，并且为了充分利用协助重建，我们可以假设2x2已经完全重建。
110
110
000
这样我们很容易想到，只需要在右下角添加 一个1，剩下的1可以自动补齐。

至此，我们很容易得到一个策略，就是不断在右下角添加数字，得到一个最优解。

class Solution {
    static const int N = 201010;
    int dir[4][2] = {1,1,  -1,1,  1,-1,   -1,-1};
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n, m;
            cin >> n >> m;
            /*
             01000
             10000
             00100
             00011
             */
            cout << 2 + max(n - 2, m - 2) << endl;
        }
    }
}
ac;

题目5

题目链接
题目大意：
给出一个n个节点的树，现在每次可以选择两个节点，将两个节点之间的最短路径上，所有节点都合并成一个节点，类似下图的操作：

和原来节点相连的边，改为和新合并成的点相连。

问，最少要进行多少次操作，剩下的节点只有1个。

输入：
第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000)
每个样例第一行，整数 𝑛 (2≤𝑛≤100000)
接下来n-1行，整数 𝑢𝑖 and 𝑣𝑖 ，表示两个点之间存在一条边 (1≤𝑢𝑖,𝑣𝑖≤𝑛,𝑢𝑖≠𝑣𝑖 )

输出：
每个样例一行，输出满足要求的最小操作次数。

Examples
input
4
4
1 2
1 3
3 4
9
3 1
3 5
3 2
5 6
6 7
7 8
7 9
6 4
7
1 2
1 3
2 4
4 5
3 6
2 7
6
1 2
1 3
1 4
4 5
2 6

output
1
3
2
2

题目解析：
题目给出来的图，就比较好分析。
每次操作都会减少若干个节点，最终是从n个节点变成1个节点，这是一个节点数量单调递减的过程。
那么可以知道，每次应该尽可能多的去选择节点，比如说从根节点到叶子节点作为一条路径，我们每次选择两条最长的路径，组成一条当前树上的最长路径，进行合并。
但是这种做法，如何证明就是最优解？有没有可能局部最优会破坏全局最优。
在思索和这个过程的时候发现，沿着上面的思路，每次选择两条到叶子节点的路径，融合之后就会减少一个叶子节点。当不存在叶子节点的时候，就只剩下一个节点。
这个过程的最优性也比较容易保证，对于有m个叶子节点的树，每次操作只能减少2个叶子节点。最优解就是m/2。

剩下的问题，就是如何确定根节点？
答案就是不需要根节点，从任意点出发，只有一个点相连就是叶子节点，计算叶子节点数量即可。

class Solution {
    static const int N = 201010;
    vector<int> g[N];
    int dfs(int u, int fat) {
        int ret = g[u].size() == 1;
        for (int i = 0; i < g[u].size(); ++i) {
            int v = g[u][i];
            if (v == fat) continue;;
            ret += dfs(v, u);
        }
        return ret;
    }
public:
    void solve() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            for (int i = 0; i <= n; ++i) g[i].clear();
            for (int i = 1; i < n; ++i) {
                int u, v;
                cin >> u >> v;
                g[u].push_back(v);
                g[v].push_back(u);
            }
            cout << (dfs(1, 0) + 1) / 2 << endl;
        }
    }
}
ac;