A题 Plus One on the Subset （签到）

有 \(T(1\leq T \leq 10^4)\) 组数据。

给定长度为 \(n\) 的数组 \(\{a_n\}\)，你可以进行多次操作，每次操作中，你可以将任意个元素的值加上 1。问需要至少多少次操作，才能讲数组中所有数的值变为相同？

\(1\leq n \leq 50, 1\leq a_i\leq 10^9\)

显然，答案为数组的最大值减去最小值。

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n, a[N];
int solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    return a[n] - a[1];
}
int main()
{
    int T;
    cin >> T;
    while (T--) cout << solve() << endl;
    return 0;
}

B题 Make AP （枚举）

有 \(T(1\leq T \leq 10^4)\) 组数据。

给定三个数 \(a,b,c\)，问能否给其中某个数乘上正整数 \(m\)，使得这三个数按原顺序成等差数列？

\(1\leq a,b,c\leq 10^8\)

显然，枚举到底给哪个数乘一下即可：

1. 乘 \(a\)，那么看 \(2b-c\) 是不是 \(a\) 的倍数即可。
2. 乘 \(c\)，同理，看 \(2b-a\) 是不是 \(c\) 的倍数即可。
3. 乘 \(b\)，先看 \(\frac{a+c}{2}\) 是不是整数，然后看它是不是 \(b\) 的倍数即可。

其中，倍数还要除一下，保证一定是一个正整数。

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n, a[N];
bool can(int x, int y) {
	return x % y == 0 && x / y > 0;
}
bool solve() {
    int a, b, c;
	cin >> a >> b >> c;
	if (can(2 * b - a, c)) return true;
	if ((a + c) % 2 == 0 && can((a + c) / 2, b)) return true;
	if (can(2 * b - c, a)) return true;
	return false;
}
int main()
{
    int T;
    cin >> T;
    while (T--) cout << (solve() ? "YES" : "NO") << endl;
    return 0;
}

C题 Division by Two and Permutation

有 \(T(1\leq T \leq 10^4)\) 组数据。

现在有 \(n\) 个数，分别记为 \(a_1,a_2,\cdots,a_n\)。

现在我们可以对某个数 \(x\) 不断进行除以 2 的操作（向下取整），问我们能否对这些数进行若干次操作，使得其变为一个从 1 到 \(n\) 的排列？

\(1\leq n \leq 50, 1\leq a_i\leq 10^9\)

方法一：二分图匹配

比赛期间直接被干破防了，直接上的二分图匹配（逃

一个数在操作的时候，如果能进入区间 \([1,n]\)，那么建立一个原数到这个新数的边（例如 22，进行不断操作可以得到 11, 5, 2, 1, 0，那么我们将 11 这个点和 5, 2, 1 连边）。

建立好这个图之后，跑一次二分图匹配即可，使用匈牙利算法的期望复杂度为 \(O(Tn^2\log n)\)（边的期望数量为 \(n\log n\) 条）。

#include<bits/stdc++.h>
using namespace std;
const int N = 60, M = 600;
int n, a[N];
//
int tot = 0, ver[M], Head[N], Next[M];
void init() {
	tot = 0;
	memset(ver, 0, sizeof(ver));
	memset(Head, 0, sizeof(Head));
	memset(Next, 0, sizeof(Next));
}
void addEdge(int u, int v) {
    ver[++tot] = v;
    Next[tot] = Head[u], Head[u] = tot;
}
//
int vis[N], match[N];
bool dfs(int u) {
    for (int i = Head[u]; i; i = Next[i]) {
        int v = ver[i];
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

bool solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    //build
    init();
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        while (x) {
            if (x <= n) addEdge(i, x);
            x /= 2;
		}
	}
	//run
	int ans = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    return ans == n;
}
int main()
{
    int T;
    cin >> T;
    while (T--) cout << (solve() ? "YES" : "NO") << endl;
    return 0;
}

方法二：贪心

我们仿照上面的方式建图，但是别跑二分图匹配了，毕竟才是 Div3 的 C 题，肯定有啥性质可以用来简化。

发现，数和数之间存在着传递性关系（例如 25 和 12，12 可以化为区间里面的数，25肯定也能），形成了一种类似于拓扑序的关系。

那么，根据贪心，我们可以猜想出两个结论：

1. 对于区间 [1,n] 之间的数，应该先填大数后填小数（因为能够满足大数的数不是很多）
2. 对于某个数 \(x\)，如果有多个数满足，优先选那个小的（大的用来去尝试填别的

不是很会证明正确性，但是反正A了，复杂度 \(O(Tn^2)\)。（不知道为啥，实际跑起来的话两个程序的速度差不多，都是900+ms，明明匹配要多个对数复杂度）

#include<bits/stdc++.h>
using namespace std;
const int N = 60;
int n, a[N];
//
int vis[N];
vector<int> e[N];
void init() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < N; ++i) e[i].clear();
}
bool solve() {
    init();

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    //build
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        int x = a[i];
        while (x) {
            if (x <= n) e[x].push_back(i);
            x /= 2;
        }
    }
    //solve
    for (int i = n; i >= 1; i--) {
        bool flag = false;
        for (int j : e[i])
            if (!vis[j]) {
                vis[j] = 1;
                flag = true;
                break;
            }
        if (!flag) return false;
    }
    return true;
}
int main()
{
    int T;
    cin >> T;
    while (T--) cout << (solve() ? "YES" : "NO") << endl;
    return 0;
}

D题 Palindromes Coloring （二分，贪心）

有 \(T(1\leq T \leq 10^4)\) 组数据。

给定一个长度为 \(n\) 的小写字母字符串 \(s\)。

现在有 \(k\) 种颜色，你可以对每个字符选择涂一个颜色（或者不填，但是得保证每个颜色至少被一个字符选择）。随后，对于每个颜色，你将这个颜色的字符全部提出来，并应当能将其排列为一个回文串。

可行性上讲并不难（每个颜色仅对应一个字符即可），所以我们想求出另一个东西：使得 \(k\) 个回文串里面的最短长度最长，并求出这个最长的最短长度。

\(1\leq k \leq n \leq 2*10^5\)

最小值最大，不难想到二分（逃）

显然，字符串内部的顺序和答案无关，所以我们直接统计每个字符有多少个先。

分析回文串，会发现他有这两个性质（其实是一个）：

1. 至多仅有一个字符，它的出现次数是奇数
2. 对于其他字符，它们的出现次数均为偶数

那么，我们直接对上面的统计再做一下化简，直接分成长度为 1 的小段和长度为 2 的小段即可（例如 bxyaxzay，我们可以拆成 aa, xx, yy, b, z，即 3 个长度为 2 的小段和 2 个长度为 1 的小段）。）发现这样对于最后答案并无影响，而且能大幅度降低状态表示的复杂度。

那么就到了喜闻乐见的二分时间，对于需要 check 的长度 \(x\)：

1. 如果 \(x=2t\)，那么添加长度为 1 的小段将毫无意义，直接看看长度为 2 的小段够不够就行了（有没有 \(tk\) 个）
2. 如果 \(x=2t+1\)，先尝试拼凑出 \(k\) 个长度为 \(2t\) 的串，然后将长度为 2 的小段打散放入长度为 1 的小段中，看看数量够不够给这些半成串拼好（有没有 \(k\) 个）

综上，总复杂度为 \(O(Tn)\)。

（这题还有点小坑，例如 t 和 k 相乘爆 int，可以用 long long 或者限定二分范围的方式来处理

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, k;
char s[N];
//
int vis[26];
int a1, a2;
int check(int x) {
	int t = x / 2;
	if (t * k > a1) return false;
	if (x % 2 == 0) return true;
	else {
		int A1 = a1, A2 = a2;
		A1 -= k * t, A2 += 2 * A1;
		return A2 >= k;
	}
}
int solve() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    //solve
    a1 = a2 = 0;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i)
    	vis[s[i] - 'a']++;
	for (int i = 0; i < 26; ++i) {
		int x = vis[i];
		int x2 = x % 2, x1 = (x - x2) / 2;
		a1 += x1, a2 += x2;
	}
    int l = 0, r = n / k + 1;
    while (l < r) {
    	int mid = (l + r + 1) >> 1;
    	if (check(mid)) l = mid;
    	else r = mid - 1;
	}
	return l;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) printf("%d\n", solve());
    return 0;
}

E题 Masha-forgetful （DP，字符串处理，模拟）

题意繁杂，难以翻译，告辞

我们把需要简化的字符串分割成若干串，每一串都能在前面的几个电话号码里面找到对应段。

显然，串越短越好（这是显然的），加上题目只要求输出合法方案，但没有限制段数量，那我们必然遵循最短原则。因为段长度至少为 2，那么我们直接找长度为 2 和 3 的串，总计 1100 种，直接对于每一类都记录一下他们的对应坐标。

然后对于字符串，我们直接开一手 DP，方程大致如下：

\(v(l,r)\) 指字符串 \([l,r]\) 上的串映射的坐标，加法指往后面贴方案，两个式子是指随便哪个满足均可。

思路说起来简单，结果代码调麻了，凑合看看吧（估计复杂度为 \(O(nm\log_2^{1100})\) 吧，也就是 \(O(nm)\) 自带超巨大常数，毕竟一堆 STL 也挺慢的

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, m;
char book[N][N], s[N];
struct Node {
    int l, r, id;
    void print() {
        printf("%d %d %d\n", l, r, id);
    }
};
map<string, Node> vis;
string getStr(char *str, int l, int r) {
    string res = "";
    for (int i = l; i <= r; ++i)
        res += str[i];
    return res;
}

Node dp[N];
int Last[N];
int calc(int x) {
    if (x == 0) return 0;
    return calc(Last[x]) + 1;
}
void print_ans(int x) {
    if (x == 0) return;
    print_ans(Last[x]);
    dp[x].print();
}
void solve()
{
    //read
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%s", book[i] + 1);
    scanf("%s", s + 1);
    //init
    vis.clear();
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= m; ++j)
            vis[getStr(book[i], j - 1, j)] = (Node){j - 1, j, i};
    for (int i = 1; i <= n; ++i)
        for (int j = 3; j <= m; ++j)
            vis[getStr(book[i], j - 2, j)] = (Node){j - 2, j, i};
    //solve
    memset(Last, -1, sizeof(int) * (m + 1));
    Last[0] = 0;
    for (int i = 1; i <= m; ++i) {
        if (i >= 2 && Last[i - 2] != -1 && vis.find(getStr(s, i - 1, i)) != vis.end()) {
            dp[i] = vis[getStr(s, i - 1, i)];
            Last[i] = i - 2;
        }
        else if (i >= 3 && Last[i - 3] != -1 && vis.find(getStr(s, i - 2, i)) != vis.end()) {
            dp[i] = vis[getStr(s, i - 2, i)];
            Last[i] = i - 3;
        }
    }
    //
    if (Last[m] == -1) puts("-1");
    else {
        printf("%d\n", calc(m));
        print_ans(m);
    }
}
int main()
{
	int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

F题 Interacdive Problem （二分，交互）

现在给定正整数 \(n\)。

现在我们知道有一个数 \(x\)，不了解其具体值，仅仅知道其范围在区间 \([1,n)\) 上。

不过我们可以和电脑进行交互，从而获得关于这个数的一些信息：

\(+ \; c\) ：给数 \(x\) 加上 \(c\)，然后返回 \(\lfloor\frac{x}{n}\rfloor\) 的值

现在希望我们进行不超过 10 次操作，来求出 \(x\) 的现在的值（进行了若干次操作之后的值），并向电脑输出他（具体格式遵循题目规范，此处不再赘述）

\(2<n\leq 1000,1\leq x,c < n\)

经典二分＋交互，很烦。

我们看一手样例，发现我们可以设两个变量 \(L,R\)，为 \(x\) 的可能取值的上下界，然后通过询问来不断缩短范围，直到确定 \(x\) 的值。显然，初始条件为 \(L=1,R=n-1\)，而 10 次也恰好为 \(\log_2^{1000}\) 这样子，那思路就显然了：每次询问都得将上下界范围缩小至原来一半，直到彻底求出 \(x\) 的值。

我不清楚怎么用文字来描述这玩意，但是核心步骤就是以下部分：

1. 将左右端点 \(L,R\) 和 $x $ 都加上一个数 \(delta\)，使得区间的 mid 变成 \(n\) 的倍数
2. 加上 \(delta\) 后，我们得到此时 \(\lfloor\frac{x}{n}\rfloor\) 的值，我们令其为 \(t\)，那么我们得到新区间 \([tn,(t+1)n-1]\)。我们注意到，这个区间的左右端点都是 \(n\) 的倍数，而 \([L,R]\) 的中间值也是 \(n\) 的倍数，这意味着只要你取两个区间的交，则能将区间长度缩小一半
3. 反复进行以上步骤，直到 \(L=R\)（需要至多 \(\log_2^{1000}=10\) 次，正好为题目给定的限制），即为要求输出的 \(x\)

#include<bits/stdc++.h>
using namespace std;
int n;
void add(int v) {
    printf("+ %d\n", v);
    fflush(stdout);
}
int query() {
    int x;
    scanf("%d", &x);
    return x;
}
int main()
{
    scanf("%d", &n);
    int L = 1, R = n - 1;
    while (L < R) {
        int mid = (L + R + 1) >> 1;
        int delta = (mid / n + 1) * n - mid;
        L += delta, R += delta;
        add(delta);

        int t = query();
        int L1 = t * n, R1 = (t + 1) * n - 1;
        if (L <= L1 && L1 <= R) L = L1;
        else R = R1;
    }
    printf("! %d", L);
    fflush(stdout);
    return 0;
}

G题 MinOr Tree （二进制技巧，图联通）

有 \(T(1\leq T \leq 10^4)\) 组数据。

给定一个 \(n\) 点 \(m\) 边的无向带权图，要求我们从中选出（或者说是 仅保留） \(n-1\) 条边，使得图联通的同时，让边权的或和（ \(w_1 \operatorname{or} w_2 \operatorname{or}\cdots \operatorname{or} w_{n-1}\)）最小化，并输出之。

\(3\leq n \leq 2*10^5,n -1\leq m \leq 2*10^5,1\leq w_i\leq 10^9\)，无自环

按照二进制表示的原理，我们从高位到低位依次考虑（考虑到 \(10^9<2^{30}\)，所以我们只考虑 30 位）

例如，对于最高位（30位），我们先考虑看能不能尝试选出一些边，使得 \(\operatorname{or}\) 完之后这一位为 0（也就是选出所有的边，他们在这一位上面为 0）且这些边足够使得图联通。如果能，那么保留下这些边进入下一轮，反之则保留所有边。如此往复，重复 30 次，即可得出所求的最小值。

复杂度方面，每一轮判联通可以使用并查集（\(O(m\log{n})\)）或者深搜（\(O(n+m)\)），然后一共判 30 轮。

 #include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int n, m;
struct Edge {
    int u, v, w;
};
vector<Edge> e1, e2;
//
int fa[N];
int find(int x) {
    if (x != fa[x]) fa[x] = find(fa[x]);
    return fa[x];
}
bool check() {
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
    int cnt = n;
    for (Edge e : e2) {
        int u = e.u, v = e.v;
        u = find(u), v = find(v);
        if (u != v) fa[u] = v, cnt--;
    }
    return cnt == 1;
}
int solve()
{
    //read & init
    scanf("%d%d", &n, &m);
    e1.clear();
    e2.clear();
    for (int i = 0; i < m; ++i) {
        Edge e;
        scanf("%d%d%d", &e.u, &e.v, &e.w);
        e1.push_back(e);
    }
    //solve
    int res = 0;
    for (int dig = 29; dig >= 0; dig--) {
        for (Edge e : e1)
            if (((e.w >> dig) & 1) == 0) e2.push_back(e);
        if (check()) swap(e1, e2);
        else res |= 1 << dig;
        e2.clear();
    }
    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) printf("%d\n", solve());
    return 0;
}