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\)
显然，枚举到底给哪个数乘一下即可：
- 乘 \(a\)，那么看 \(2b-c\) 是不是 \(a\) 的倍数即可。
- 乘 \(c\)，同理，看 \(2b-a\) 是不是 \(c\) 的倍数即可。
- 乘 \(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,n] 之间的数，应该先填大数后填小数（因为能够满足大数的数不是很多）
- 对于某个数 \(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 的小段即可（例如 bxyaxzay，我们可以拆成 aa, xx, yy, b, z，即 3 个长度为 2 的小段和 2 个长度为 1 的小段）。）发现这样对于最后答案并无影响，而且能大幅度降低状态表示的复杂度。
那么就到了喜闻乐见的二分时间，对于需要 check 的长度 \(x\)：
- 如果 \(x=2t\)，那么添加长度为 1 的小段将毫无意义，直接看看长度为 2 的小段够不够就行了（有没有 \(tk\) 个）
- 如果 \(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，方程大致如下：
\[f_i=\begin{cases} f_{i-2}+v(i-1,i) \\ f_{i-3}+v(i-2,i)\end{cases} \]\(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\) 的值。
我不清楚怎么用文字来描述这玩意，但是核心步骤就是以下部分：
- 将左右端点 \(L,R\) 和 $x $ 都加上一个数 \(delta\)，使得区间的 mid 变成 \(n\) 的倍数
- 加上 \(delta\) 后，我们得到此时 \(\lfloor\frac{x}{n}\rfloor\) 的值，我们令其为 \(t\)，那么我们得到新区间 \([tn,(t+1)n-1]\)。我们注意到，这个区间的左右端点都是 \(n\) 的倍数，而 \([L,R]\) 的中间值也是 \(n\) 的倍数，这意味着只要你取两个区间的交，则能将区间长度缩小一半
- 反复进行以上步骤，直到 \(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;
}