T1 出题人
由于 \(a\) 序列中存在偶数的情况很容易构造，下面分析前提为 \(a\) 序列的所有数为奇数。
假设当前我们已知序列 \(b\) ，对于 \(b_i,b_j\) ，如果存在 \(k\) 满足 \(a_k=b_i+b_j\) ，那么连接 \(i,j\) 所对应的点，由于点数为 \(n\) ，边数至少为 \(n\) ，因此原图中至少存在一个环。如果可以构造一个环，只需要将其他点挂在环上任意节点即可。
考虑构造这样一个大小为 \(k\) 的环，对于环上相邻两个位置 \(i,i+1\) ，满足 \(b_i+b_{i+1}=a_i\) （特殊的， \(b_1+b_k=a_k\) ），那么有 \(2\sum b=\sum a\) ，由于 \(\sum a\) 一定为偶数，因此 \(k\) 一定为偶数，那么我们将环上相邻两点看为一组计算，容易发现 \(\sum b_i=a_1+a_3+a_5+……+a_{k-1}\) 。实际上，如果我们能够构造两个集合 \(A,B\) ，使得两个集合大小相等并且两个集合内元素的和相等，那么原问题一定存在解。
一个比较显然的思路是 \(3^n\) 枚举当前数属于 \(A,B\) 集合或不属于任何集合，优化考虑进行折半搜索，假设当前序列存在一组合法解，满足 \(A\) 集合在序列左侧选择的元素的和为 \(A_L\) 右侧为 \(A_R\) ，同理 \(B\) 集合为 \(B_L,B_R\) ，那么有 \(A_L+A_R=B_L+B_R\) ，简单移项有 \(A_L-B_L=B_R-A_R\) ，对于左右两部分的任意集合状态维护 \(A-B\) 的值即可。（集合大小的限制按照同样的方法维护）
最后我们将所有状态排序，使用单调指针可以在 \(O(3^{\tfrac{n}{2}})\) 的复杂度内判断是否存在合法解，排序考虑在 Dfs 时进行归并排序，复杂度 \(O(3^{\tfrac{n}{2}})\) 。
特别注意
这是新发现的一种玄学问题，用一个几乎下午才解决。
由于此题较为卡空间，因此我们需要将集合元素总和的限制和集合大小的限制放到一个 long long 中存储。
具体的我们采取的方式是对集合大小乘以 \(1e15\) 加到集合总和中。
然而它挂了……（但是调成 \(1e12\) 并不会挂）
更加离谱的是全程 long long 最大值为 \(1e17\) ，完全没有溢出。
通过 gdb 调试，我们发现最终的得到的序列与预期得到的序列的排序关键值存在 \(1\) 的差距。
通过合理猜测，发现直接写 \(1e15\) 会将原有的 long long 类型强制转化为 double ，然而 double 运算时会产生精度丢失，所以……
我竟然在一道完全不使用 double 的题上丟精了？
code
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <ctime>
#include <iostream>
#include <cassert>
using namespace std;
const int max1 = 30, max2 = 14348907;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const long long B = 1e15;
int n;
long long a[max1 + 5], b[max1 + 5], len;
pair <long long, int> save[2][max2 + 5], tmp[max2 / 3 + 5][3];
vector <long long> v1, v2;
bool vis[max1 + 5];
void Solve ( long long x )
{
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= n; j ++ )
if ( b[i] + b[j] == x )
{ printf("%d %d\n", i, j); return; }
return;
}
void Merge ( int total, int id )
{
int now0, now1, now2;
now0 = now1 = now2 = 0;
for ( int i = 0; i < total; i ++ )
{
if ( tmp[now0][0] < tmp[now1][1] )
{
if ( tmp[now0][0] < tmp[now2][2] )
save[id][i] = tmp[now0++][0];
else
save[id][i] = tmp[now2++][2];
}
else
{
if ( tmp[now1][1] < tmp[now2][2] )
save[id][i] = tmp[now1++][1];
else
save[id][i] = tmp[now2++][2];
}
assert(now0 <= total && now1 <= total && now2 <= total);
}
return;
}
int Dfs ( int now, int lim, int id, int base )
{
if ( now == lim + 1 )
{
save[id][0].first = 0LL;
save[id][0].second = 0;
return 1;
}
int total = Dfs(now + 1, lim, id, base), power = 1;
for ( int i = base; i < now; i ++ )
power = power + power + power;
for ( int i = 0; i < total; i ++ )
{
tmp[i][0] = save[id][i];
tmp[i][1] = save[id][i];
tmp[i][2] = save[id][i];
tmp[i][1].first += B;
tmp[i][1].first += a[now];
tmp[i][1].second += power;
tmp[i][1].second += power;
tmp[i][2].first -= B;
tmp[i][2].first -= a[now];
tmp[i][2].second += power;
}
tmp[total][0].first = tmp[total][1].first = tmp[total][2].first = inf;
Merge(total + total + total, id);
return total + total + total;
}
int BitA ( int x, int lim )
{
int A = 0;
for ( int i = 0; i < lim; i ++ )
{
if ( x % 3 )
A += 1 << i;
x /= 3;
}
return A;
}
int BitB ( int x, int lim )
{
int B = 0;
for ( int i = 0; i < lim; i ++ )
{
if ( x % 3 == 2 )
B += 1 << i;
x /= 3;
}
return B;
}
int main ()
{
freopen("problemsetter.in", "r", stdin);
freopen("problemsetter.out", "w", stdout);
int pos = 0;
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i]);
if ( !( a[i] & 1 ) )
pos = i;
}
if ( pos )
{
b[1] = a[pos] >> 1, len = 1;
for ( int i = 1; i <= n; i ++ )
if ( i != pos )
b[++len] = a[i] - b[1];
}
else
{
int mid = n >> 1, total1 = Dfs(1, mid, 0, 1), total2 = Dfs(mid + 1, n, 1, mid + 1), P = 0, Q = 0;
for ( int i = 0; i < total2; i ++ )
save[1][i].first = -save[1][i].first;
for ( int i = 0, j = total2 - 1; i < total1; i ++ )
{
while ( j != -1 && save[1][j].first < save[0][i].first )
--j;
if ( j != -1 )
{
if ( save[0][i].first == save[1][j].first )
{
if ( save[0][i].second || save[1][j].second )
{
P = BitA(save[0][i].second, mid) ^ ( BitA(save[1][j].second, n - mid) << mid );
Q = BitB(save[0][i].second, mid) ^ ( BitB(save[1][j].second, n - mid) << mid );
break;
}
}
}
}
if ( !P && !Q )
{ printf("No\n"); return 0; }
P = P ^ Q;
v1.clear(), v2.clear();
for ( int i = 1; i <= n; i ++ )
{
if ( P >> i - 1 & 1 )
v1.push_back(a[i]), vis[i] = true;
if ( Q >> i - 1 & 1 )
v2.push_back(a[i]), vis[i] = true;
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
long long now = 0;
int siz = v1.size(), len = 0;
for ( int i = 0; i < siz; i ++ )
{
now = v1[i] - now;
b[++len] = now;
now = v2[i] - now;
b[++len] = now;
}
for ( int i = 1; i <= n; i ++ )
{
if ( vis[i] )
continue;
b[++len] = a[i];
}
}
printf("Yes\n");
for ( int i = 1; i <= n; i ++ )
printf("%lld ", b[i]);
printf("\n");
for ( int i = 1; i <= n; i ++ )
Solve(a[i]);
return 0;
}
T2 彩色挂饰
树的情况很容易考虑，设 \(f_{i,j}\) 表示 \(i\) 节点选择颜色 \(j\) 时，将以 \(i\) 为根的子树全部喷涂的最小代价。
考虑无相连通图如何处理，比较套路的想法是建立圆方树进行 dp ，仍然沿用之前的 dp 定义， \(i\) 为圆点时 \(f_{i,j}\) 表示当前节点颜色为 \(j\) 时当前子树的答案， \(i\) 为方点时 \(f_{i,j}\) 表示当前节点的父节点颜色为 \(j\) 时当前子树的答案。
考虑圆点的转移，容易发现是
\[f_{u,i}=1+\sum_{v}f_{v,i}-1 \]然后考虑方点的转移，由于点双内节点个数较少，因此考虑状压 dp ，首先预处理 \(F(S)\) 表示当前 \(S\) 集合内所有元素的联通性，转移只需要存在一个元素 \(x_i\) ，满足 \(F(S-\{x_i\})\) 并且 \(x_i\) 与 \(S\) 集合内有连边，则 \(F(S)\) 为 True 。
同时预处理 \(val(S,i)\) 表示 \(S\) 集合内节点全部为颜色 \(i\) 时的最小喷涂代价，同时计算 \(G(S)=\min_i (val(S,i))\)，然后对 \(G(S)\) 做子集卷积存储到 \(H(S)\) 中。
转移只需要枚举当前节点的父节点所在的同色连通块集合 \(S\) ，显然有转移：
\[f_{i,j}=\min_S(val(S,j)+h(U-S)) \]最后根节点 dp 数组的最小值为所求答案。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
const int max1 = 1e5, max2 = 20, max3 = 6, max4 = 1 << 6;
const int inf = 1e7;
int n, m, k, lim, c[max1 + 5];
vector <int> edge[max1 + 5];
int dfn[max1 + 5], low[max1 + 5], s[max1 + 5], dfs_clock, top, block;
vector <int> tree[max1 * 2 + 5];
int f[max1 * 2 + 5][max2 + 5];
int point[max3 + 5], cnt, E[max3 + 5];
bool connect[max4 + 5];
int minval[max4 + 5], g[max4 + 5];
void Tarjan ( int now )
{
dfn[now] = low[now] = ++dfs_clock;
s[++top] = now;
for ( auto v : edge[now] )
{
if ( !dfn[v] )
{
Tarjan(v);
low[now] = min(low[now], low[v]);
if ( low[v] == dfn[now] )
{
int x; ++block;
do
{ x = s[top--]; tree[block].push_back(x); } while ( x != v );
tree[now].push_back(block);
}
}
else
low[now] = min(low[now], dfn[v]);
}
return;
}
void Dfs ( int now, int fa )
{
if ( now <= n )
{
if ( !c[now] )
{
for ( int i = 1; i <= k; i ++ )
f[now][i] = 1;
}
else
{
for ( int i = 1; i <= k; i ++ )
f[now][i] = inf;
f[now][c[now]] = 1;
}
for ( auto v : tree[now] )
{
Dfs(v, now);
for ( int i = 1; i <= k; i ++ )
{
if ( f[now][i] == inf )
continue;
f[now][i] += f[v][i] - 1;
}
}
}
else
{
for ( auto v : tree[now] )
Dfs(v, now);
cnt = 0;
for ( auto v : tree[now] )
point[++cnt] = v;
point[++cnt] = fa;
for ( int i = 1; i <= cnt; i ++ )
{
E[i] = 0;
for ( auto v : edge[point[i]] )
{
int num = 0;
for ( int j = 1; j <= cnt; j ++ )
if ( point[j] == v )
num = j;
if ( num )
E[i] |= 1 << num - 1;
}
}
connect[0] = false;
minval[0] = 0;
for ( int s = 1; s < 1 << cnt; s ++ )
{
connect[s] = true;
if ( __builtin_popcount(s) > 1 )
{
connect[s] = false;
for ( int i = 1; i <= cnt; i ++ )
{
if ( !( s >> i - 1 & 1 ) )
continue;
if ( connect[s ^ ( 1 << i - 1 )] && ( E[i] & s ) )
{ connect[s] = true; break; }
}
}
minval[s] = inf;
if ( connect[s] )
{
for ( int t = 1; t <= k; t ++ )
{
int sum = 1;
for ( int i = 1; i <= cnt; i ++ )
if ( s >> i - 1 & 1 )
sum += f[point[i]][t] - 1;
minval[s] = min(minval[s], sum);
}
}
}
for ( int s = 0; s < 1 << cnt; s ++ )
{
g[s] = minval[s];
for ( int t = s; t; t = ( t - 1 ) & s )
g[s] = min(g[s], g[s ^ t] + minval[t]);
}
for ( int i = 1; i <= k; i ++ )
f[now][i] = inf;
if ( !c[fa] )
{
for ( int i = 1; i <= k; i ++ )
{
for ( int s = 1 << cnt - 1; s < 1 << cnt; s ++ )
{
if ( !connect[s] )
continue;
int sum = 1;
for ( int j = 1; j <= cnt - 1; j ++ )
if ( s >> j - 1 & 1 )
sum += f[point[j]][i] - 1;
sum += g[( ( 1 << cnt ) - 1 ) ^ s];
f[now][i] = min(f[now][i], sum);
}
}
}
else
{
for ( int s = 1 << cnt - 1; s < 1 << cnt; s ++ )
{
if ( !connect[s] )
continue;
int sum = 1;
for ( int j = 1; j <= cnt - 1; j ++ )
if ( s >> j - 1 & 1 )
sum += f[point[j]][c[fa]] - 1;
sum += g[( ( 1 << cnt ) - 1 ) ^ s];
f[now][c[fa]] = min(f[now][c[fa]], sum);
}
}
}
return;
}
int main ()
{
freopen("colorful.in", "r", stdin);
freopen("colorful.out", "w", stdout);
scanf("%d%d%d%d", &n, &m, &k, &lim);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &c[i]);
for ( int i = 1, u, v; i <= m; i ++ )
{
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
block = n; Tarjan(1);
Dfs(1, 0);
int ans = inf;
for ( int i = 1; i <= k; i ++ )
ans = min(ans, f[1][i]);
printf("%d\n", ans);
return 0;
}
T3 逆转函数
首先考虑 \(O(n^2)\) 暴力，枚举逆转中心 \(i\) ，之后暴力向两侧扩展，如果出现冲突则停止。
发现这个过程类似 manacher 算法，因此考虑利用同样的思想进行优化，考虑记录最靠右的逆转区间 \(mid,R\) ，设当前枚举的逆转中心为 \(i\) ，简单思考发现 \(i\) 的最大逆转半径可以从 \(mid+mid-i\) 处继承，因为逆转时的对应关系类似一种置换，而将左半部分的置换向右对称，置换的数会发生变化，但置换结构不变。
同时 manacher 算法中存在操作 \(p_i=\min(p_{2mid-i},R-i)\) ，因此考虑实现这步操作。由于 \(R\) 是靠右的逆转区间，因此 \(2mid-i+p_{2mid-i}\le R\) ，那么有 \(i+p_{2mid-i}-R\le 2(i-mid)\) ，由于 \(R-i\ge p_{2mid-i}\) 时 \(i\) 会成为下一个 \(mid\) ，因此暴力撤销的次数为逆转中心右移的次数，显然这是 \(O(n)\) 的。
code
#include <cstdio>
using namespace std;
const int max1 = 3e5;
const int mod = 998244353;
int n, m, a[max1 + 5];
int pos[max1 + 5], Prev[max1 + 5], Suffix[max1 + 5], power[max1 + 5];
int point[max1 + 5], father[max1 + 5], deep[max1 + 5], count[max1 + 5], sum[max1 + 5], total, ans;
void Add ( int &x, int y )
{
x = x + y;
if ( x >= mod )
x = x - mod;
return;
}
int main ()
{
freopen("invfunc.in", "r", stdin);
freopen("invfunc.out", "w", stdout);
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &a[i]);
for ( int i = 1; i <= m; i ++ )
pos[i] = 0;
for ( int i = 1; i <= n; i ++ )
{
Prev[i] = pos[a[i]];
pos[a[i]] = i;
}
for ( int i = 1; i <= m; i ++ )
pos[i] = n + 1;
for ( int i = n; i >= 1; i -- )
{
Suffix[i] = pos[a[i]];
pos[a[i]] = i;
}
power[0] = 1;
for ( int i = 1; i <= m; i ++ )
power[i] = 1LL * power[i - 1] * m % mod;
ans = 0;
point[0] = father[0] = deep[0] = count[0] = sum[0] = total = 0;
for ( int i = 1, mid = 0, R = 0; i <= n; i ++ )
{
int u = 0;
if ( R >= i )
{
u = point[mid + mid - i];
while ( i + deep[u] - 1 > R )
u = father[u];
}
while ( i - deep[u] >= 1 && i + deep[u] <= n )
{
bool flag = false;
flag |= Suffix[i - deep[u]] < i + deep[u] && a[i + i - Suffix[i - deep[u]]] != a[i + deep[u]];
flag |= Prev[i + deep[u]] > i - deep[u] && a[i + i - Prev[i + deep[u]]] != a[i - deep[u]];
if ( flag )
break;
int now = ++total;
father[now] = u;
deep[now] = deep[u] + 1;
count[now] = count[u];
if ( Suffix[i - deep[u]] >= i + deep[u] )
++count[now];
if ( a[i - deep[u]] != a[i + deep[u]] && Prev[i + deep[u]] <= i - deep[u] )
++count[now];
sum[now] = sum[u];
Add(sum[now], power[m - count[now]]);
u = now;
}
Add(ans, sum[u]);
point[i] = u;
if ( i + deep[u] - 1 >= R )
{
mid = i;
R = i + deep[u] - 1;
}
}
point[0] = father[0] = deep[0] = count[0] = sum[0] = total = 0;
for ( int i = 1, mid = 0, R = 0; i <= n - 1; i ++ )
{
int u = 0;
if ( R > i )
{
u = point[mid + mid - i];
while ( i + deep[u] > R )
u = father[u];
}
while ( i - deep[u] >= 1 && i + 1 + deep[u] <= n )
{
bool flag = false;
flag |= Suffix[i - deep[u]] < i + 1 + deep[u] && a[i + i + 1 - Suffix[i - deep[u]]] != a[i + 1 + deep[u]];
flag |= Prev[i + 1 + deep[u]] > i - deep[u] && a[i + i + 1 - Prev[i + 1 + deep[u]]] != a[i - deep[u]];
if ( flag )
break;
int now = ++total;
father[now] = u;
deep[now] = deep[u] + 1;
count[now] = count[u];
if ( Suffix[i - deep[u]] >= i + 1 + deep[u] )
++count[now];
if ( a[i - deep[u]] != a[i + 1 + deep[u]] && Prev[i + 1 + deep[u]] <= i - deep[u] )
++count[now];
sum[now] = sum[u];
Add(sum[now], power[m - count[now]]);
u = now;
}
Add(ans, sum[u]);
point[i] = u;
if ( i + deep[u] >= R )
{
mid = i;
R = i + deep[u];
}
}
printf("%d\n", ans);
return 0;
}