你们好，这里是喜欢玩保龄球的纸张ZGC。
原题移步题单，首页更新为准
[T5]
T1有大难度，先看T5。
果然前几天复习的板子派上了用场。
首先我们知道 1 + 2 + … + x = \frac{x (x + 1)}{2}
写成整除/同余方程的形式：
$2n \mid x(x + 1) \Rightarrow x(x + 1) \equiv 0 \pmod{2n}$
烧烤一下，x 和 x + 1 就一定含有 n 的因数。
枚举 d \mid n，令 x = ds (s \in \mathbb{Z})，x + 1 = \frac{n}{d} t(t \in \mathbb{Z})。
减一减，得到 \frac{n}{d} t – ds = 1。
先不用在意 d 的符号。
好熟悉的形式，这不是不定方程吗，显然的可以用exGCD来求，由裴蜀定理，这个东西在 (d, \frac{n}{d}) = 1 的时候是一定有解的。
$90pts$ 是简单的，直接枚举 $d$ 判断，复杂度我不知道，反正大概是根号再带个 $\log$。
$100pts$，我们考虑优化以上过程。
将 2n 写成质因数分解的形式，
即 2n = p_1 ^ {\alpha_1} p_2 ^ {\alpha_2} p_3 ^ {\alpha_3} … p_k ^ {\alpha_k}。
$d$ 和 $\frac{n}{d}$ 互质的情况当且仅当 $d = p_{t1} ^ {\alpha{t1}} p_{t2} ^ {\alpha{t2}} … p{tc} ^ {\alpha{t_c}}$，
$t_1, t_2, …, t_k \leq k$ 且互不相同。
这时候比较好办了，线性筛一遍，2n 质因数分解，然后最后直接一遍 dfs 选 d 就行。
仅供参考的代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
LL read()
{
LL x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
if (!b)
{
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= (a / b) * x;
}
LL n, res;
int st[N], primes[N], cnt;
vector<LL> V;
void dfs(int u, LL d)
{
if (u == (int)V.size())
{
if (d == 1)return;
LL x, y;
exgcd(d, n / d, x, y);
res = min(res, ((d * (-x) % n) + n) % n);
res = min(res, (((-y) * (n / d)) % n + n) % n);
return;
}
if (d > n / d)return;
dfs(u + 1, d * V[u]);
dfs(u + 1, d);
}
void work()
{
V.clear();
n = read();
if (n & 1)res = n;
else res = n * 2 - 1;
LL t = n;
n <<= 1;
for (int i = 0; i < cnt && primes[i] <= t / primes[i]; i ++)
{
LL c = 1;
while (!(t % primes[i]))
{
c *= primes[i];
t /= primes[i];
}
if (!i)c <<= 1;
if (c > 1)V.push_back(c);
}
if (t > 1)V.push_back(t);
sort(V.begin(), V.end());
while (V.size() && V.back() >= n / V.back())V.pop_back();
dfs(0, 1);
printf("%lld\n", res);
}
int main()
{
for (int i = 2; i < N; i ++)
{
if (!st[i])primes[cnt ++] = i;
for (int j = 0; j < cnt && primes[j] < N / i; j ++)
{
st[primes[j] * i] = 1;
if (!(i % primes[j]))break;
}
}
LL T = read();
while (T --)work();
return 0;
}
可惜没想到最后一步，但似乎也没那么可惜。
[T1]
啥我们关电脑OJ(gdnoj)竟然有随机化的题目了
好吧没那么随机，更愿意称之为人类智慧题目。
$O(n ^ 2)$ 的算法是好想的（然后我没打保龄了）
注意不到 2^{64} = ({2 ^ {16}}) ^ {4}，且题目要求 3 个二进制位不同，也就是这样每 16 位分一组后，满足要求的数对 (x, y) 一定会有一组是相同的。
开一个 hash_table，记录同一组内的编，一一试一试，至于这样做为什么是对的，原因是题目里的一句话：数据随机生成。
所以理论上乱搞也不是不行。
链表实现的时候注意开 4 倍空间，原因是每个数被插入了 4 次。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 150005;
unordered_map<ULL, int> h[4];
int n, ne[N << 2], idx = 1, st[N];
ULL a[N], w[N][4], e[N << 2];
int check(ULL x)
{
int cnt = 0;
while (x)
{
if ((++ cnt) > 3)return 0;
x -= (x & (-x));
}
return (cnt == 3);
}
int main()
{
freopen("hashing.in", "r", stdin);
freopen("hashing.out", "w", stdout);
scanf("%d", &n);
ULL mod = 1 << 16;
for (int i = 1; i <= n; i ++)
{
ULL x;
scanf("%llu", &a[i]);
x = a[i];
for (int j = 0; j < 4; j ++)
{
w[i][j] = x % mod;
x /= mod;
}
int res = 0;
for (int pos = 0, cnt = 0; pos < 4; pos ++)
{
for (int j = h[pos][w[i][pos]]; j; j = ne[j])
{
int k = e[j];
if (st[k] == i)continue;
st[k] = i;
if (++ cnt == n)break;
res += check(a[i] ^ a[k]);
}
e[idx] = i;
ne[idx] = h[pos][w[i][pos]];
h[pos][w[i][pos]] = idx ++;
}
printf("%d\n", res);
}
return 0;
}
[T2]
大失败。
在不该求稳的时候求稳，在该求稳的地方冒险，活该保龄。
首先题目所描述的点就是割点，上一个 tarjan 板子，基本上结束了。
对于 dfn_u \leq low_j 的 j，记录 Size_j，给 u 点的贡献就是 Size_j(n – Size_j – 1)， cnt \leftarrow cnt + Size_j
枚举完所有儿子后，外部点还会再产生 cnt(n – cnt – 1) 的贡献。
注意事实上每对点的贡献被重复计算两次，因此除 2。
还有一种做法是圆方树，可惜我对它的记忆已经停留在两年前了。
建立出圆方树后，由于是一棵树结构，因此可以直接 DP，计算方法与第一个方法是类似的。
理论上的复杂度其实差不多？不知道，不会证明。
#include <bits/stdc++.h>
using namespace std;
const int N = 50005;
int n, m;
vector<int> G[N];
typedef long long LL;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
int dfn[N], low[N], Size[N], timestamp;
LL res[N];
void tarjan(int u)
{
int cnt = 0;
dfn[u] = low[u] = ++timestamp;
Size[u] = 1;
for (int j : G[u])
{
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
if (dfn[u] <= low[j])
{
res[u] += Size[j] * (n - Size[j] - 1);
cnt += Size[j];
}
Size[u] += Size[j];
}
else low[u] = min(low[u], dfn[j]);
}
res[u] += cnt * (n - cnt - 1);
}
int main()
{
n = read(), m = read();
while (m --)
{
int a = read(), b = read();
G[a].push_back(b);
G[b].push_back(a);
}
tarjan(1);
for (int i = 1; i <= n; i ++)printf("%lld\n", (res[i] >> 1) + n - 1);
return 0;
}
[T3]
他还是忘不了网络流（恼
准确的说是最小割。
首先既然要算最大收益，不妨考虑算最小损失。
把源点考虑成本方阵营，把汇点考虑成敌方阵营。
对于每个点 i，这样连边：
- 连一条 $(S, i, \sum{j = 1}^{n} E{i,j})$ 的边。
- 连一条 (i, T, w_i) 的边。
- 对于任意点 j，连 (i, j, 2 \times E_{i,j})
其实都很好理解，对于第一类边，割断代表不需要这个 i；对于第二类边，割断代表将 i 收入囊中；对于第三类边，连了获得 $E{i,j}，不连损失E{i, j}，差值是2 \times E_{i, j}$。
然后结束了。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1005, M = 2002005;
const LL INF = 1e10;
int n, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], cur[N], d[N];
int read()
{
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ '0');
ch = getchar();
}
return x * f;
}
void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}
int bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S;
d[S] = 0;
cur[S] = h[S];
while (hh<=tt)
{
int u = q[hh ++];
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if(d[j] == -1 && f[i])
{
d[j] = d[u] + 1;
cur[j] = h[j];
if (j == T)return 1;
q[++tt] = j;
}
}
}
return 0;
}
LL get(int u, LL limit)
{
if(u == T)return limit;
LL ans = 0;
for(int i = cur[u]; ~i && ans < limit; i = ne[i])
{
cur[u] = i;
int j = e[i];
if (d[j] == d[u] + 1 && f[i])
{
LL v = get(j, min((LL)f[i], limit - ans));
if (!v)d[j] = -1;
f[i] -= v;
f[i ^ 1] += v;
ans += v;
}
}
return ans;
}
LL dinic()
{
LL res=0, ans;
while (bfs())
{
while (ans = get(S,INF))res += ans;
}
return res;
}
int main()
{
memset(h, -1, sizeof h);
n = read();
S = 0, T = n + 1;
for (int i = 1, x; i <= n; i ++)
{
x = read();
add(i, T, x);
}
LL sum = 0;
for (int i = 1; i <= n; i ++)
{
int cost = 0;
for (int j = 1; j <= n; j ++)
{
int x = read();
if (x)add(i, j, x << 1);
cost += x;
}
add(S, i, cost);
sum += cost;
}
printf("%lld", sum - dinic());
return 0;
}
[T4]
感觉挺好的题目，至少能理解
似乎可以贪心，但是不会。
于是考虑二分答案后 DP。
具体地，我们二分答案 k 表示划分 k 个集合。
我们现在只在意每一种数 和 划分出多少奇数集合
状态这不就有了，定义 f_{i, j} 表示考虑前 i 种数， j 到现在共有 j 个集合内元素数量为奇数的可行性 [0/1]。
初状态 f_{0, 0} = 1
转移用刷表法，枚举 p 表示 p 个填元素数量为奇数的集合，$cnt{i + 1} – p个填元素数量为偶数的集合，有f{i + 1, j + cnt{i + 1} – 2p} \leftarrow f{i, j}$。
这里严格限定 p 范围，因为显然 p \leq cnt_{i + 1}，因此 (i, p) 数量是 n，因此DP过程是 O(n ^ 2) 的。
至于填写方案，与昨天/前天/大前天的所有填写方案一样，记录前驱。
不需要卡常，开心。
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 1e3 + 5;
typedef pair<int, int> PII;
int n, cnt, f[N][N], w[N];
PII C[N], pre[N][N];
vector<int> res[N];
int check(int k)
{
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 0; i < cnt; i ++)
{
for (int j = 0; j <= k; j ++)
{
if (!f[i][j])continue;
int l = max((j + C[i + 1].y - k) / 2, max(C[i + 1].y - k + j, 0));
int r = min((j + C[i + 1].y) / 2, min(j, C[i + 1].y));
for (int p = l; p <= r; p ++)
{
pre[i + 1][j + C[i + 1].y - 2 * p] = {i, j};
f[i + 1][j + C[i + 1].y - 2 * p] = 1;
}
}
}
return f[cnt][0];
}
void work()
{
cnt = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i ++)scanf("%d", &w[i]);
if (n & 1)
{
puts("-1");
return;
}
sort(w + 1, w + n + 1);
int l = 0, r = n / 2;
for (int i = 1; i <= n; i ++)
{
if (w[i] != w[i - 1])
{
if (C[cnt].y > (n >> 1))
{
puts("-1");
return;
}
l = max(l, C[cnt].y);
C[++ cnt] = {w[i], 0};
}
C[cnt].y ++;
}
if (!check(n / 2))
{
puts("-1");
return;
}
while (l < r)
{
int mid = (l + r) >> 1;
if (check(mid))r = mid;
else l = mid + 1;
}
check(l);
PII cur = {cnt, 0};
vector<PII> op;
while (cur.x)
{
op.push_back(cur);
cur = pre[cur.x][cur.y];
}
int last = 0;
for (int i = op.size() - 1; ~i; i --)
{
//last -> op[i].y
//j = last, j + C[i + 1].y - 2 * p = op[i].y
//last + C[i + 1].y - 2 * p = op[i].y
//2 * p = last + C[op[i].x].y - op[i].y
//p = (last + C[op[i].x].y - op[i].y) / 2
int j = (last + C[op[i].x].y - op[i].y) / 2;
int k = C[op[i].x].y - j;
// printf("%d %d %d\n", op[i].x, j, k);
for (int t = 1; t <= l; t ++)
{
if (j && (res[t].size() & 1))
{
res[t].push_back(C[op[i].x].x);
j --;
}
else if (k && !(res[t].size() & 1))
{
res[t].push_back(C[op[i].x].x);
k --;
}
}
last = op[i].y;
}
printf("%d\n", l);
for (int i = 1; i <= l; i ++)
{
printf("%d ", res[i].size());
for (auto j : res[i])printf("%d ", j);
puts("");
res[i].clear();
}
}
int main()
{
freopen("maze.in", "r", stdin);
freopen("maze.out", "w", stdout);
int T;
scanf("%d", &T);
while (T --)work();
return 0;
}