T1 通配文件

下文 $m$ 均表示 $\sum|t_i|$ 。

先考虑一个文件、一个通配字符子串，怎么判断合法的方案数。

定义 $f_{i,j}$ 表示已经考虑完了字符串中的前 $i$ 个点，目前将所有*替换之后匹配了目标文件前 $j$ 个字符的方案数。

转移显然：当 $s_{i 1}$ 为字母，若文件第 $j 1$ 字符与 $s_{i 1}$ 相等，则 $f_{i 1,j 1}\gets f_{i,j}$ ；如果 $s_{i 1}$ 为*，则 $f_{i 1,j}=\sum\limits_{x=0}^j f_{i,x}$ 。

单个时间复杂度 $O(nm^2)$ （暴力转移）或 $O(nm)$ （前缀和优化），总体时间复杂度 $O(n^3m^2)$ 至 $O(n^2m)$ 。

我们考虑将所有子串的贡献统一处理。

定义 $f_{i,j}$ 表示已经考虑完了字符串中的前 $i$ 个点，目前将所有*替换之后匹配了目标文件前 $j$ 个字符的方案数总和。

那么转移变成：当 $s_{i 1}$ 为字母，若文件第 $j 1$ 字符与 $s_{i 1}$ 相等，则 $f_{i 1,j 1}\gets f_{i,j}$ ；如果 $s_{i 1}$ 为*，则 $f_{i 1,j}=\sum\limits_{x=0}^j f_{i,x}$ 。最后，令 $f_{i,0}\gets f_{i,0} 1$ （新增一个子串开头）。

最后， $ans=\sum\limits_{i=1}^n f_{i,len}$ 。意为枚举子串右端点。

对于每一个文件求解即可。时间复杂度 $O(nm^2)$ 。经前缀和优化可做到 $O(nm)$ 。

T2 树

题目提到至多改变一个点颜色，因此可以考虑枚举改变颜色的点。
问题转化为了对于一个确定的树求价值的问题。
考虑一条边什么时候成为路径的最大边权。边权从小到大排序，每次新加一条边连接两个连通块，则这两个连通块之间的点形成的路径的最大边权的边都是该条边。
因此考虑新加边形成的贡献即可。每个连通块记录内部的白色点和黑色点个数，加边增加的贡献是两个连通块不同颜色点对数量乘该条边的边权。
具体采用并查集维护连通块即可。该问题解决。

#include<bits/stdc++.h>
using namespace std ;
const int maxn = 3000 + 10 ;
int n;
long long res = 0 ;
int c[maxn] ;
vector<array<int , 3>> edge ;
int cnt[maxn][2] ;
int fa[maxn] ;
int find(int x) {
	if(x == fa[x])  return x ;
	fa[x] = find(fa[x]) ;
	return fa[x] ;
}
void solve() {
	sort(edge.begin() , edge.end()) ;
	for(int i = 1 ; i <= n ; i ++)  fa[i] = i ;
	for(int i = 1 ; i <= n ; i ++) {
		cnt[i][0] = 0 ;
		cnt[i][1] = 0 ;
		cnt[i][c[i]] = 1 ;
	}
	long long sum = 0 ;
	for(int i = 0 ; i < n - 1 ; i ++) {
		int u = edge[i][1] ;
		int v = edge[i][2] ;
		int w = edge[i][0] ;
		int cnt00 = cnt[find(u)][0] ;
		int cnt01 = cnt[find(u)][1] ;
		int cnt10 = cnt[find(v)][0] ;
		int cnt11 = cnt[find(v)][1] ;
		sum += 1ll * w * (cnt00 * cnt11 + cnt01 * cnt10) ;
		cnt[find(u)][0] += cnt[find(v)][0] ;
		cnt[find(u)][1] += cnt[find(v)][1] ;
		fa[find(v)] = find(u) ;
	}
	res = max(res , sum) ;
}
int main() {
	std::ios::sync_with_stdio(false) , cin.tie(0) ;
	cin >> n ;
	for(int i = 1 ; i <= n ; i ++)  cin >> c[i] ;
	for(int i = 1 ; i <= n - 1 ; i ++) {
		int u , v , w ;
		cin >> u >> v >> w ;
		edge.push_back({w , u , v}) ;
	}
	solve() ;
	for(int i = 1 ; i <= n ; i ++) {
		c[i] ^= 1 ;
		solve() ;
		c[i] ^= 1 ;
	}
	cout << res << '\n';
	return 0 ;
}

T3 木棍

考虑 $n=2$ 的情况，能够从 $3 \sim 8$ 中选出 3 根长度不同的木棍变出来，共 $C_6^3=20$ 种方案，其中有一种方案不行：

2 3 5 8 // 5=2+3

所以 $n=2$ 应该输出 19。

再考虑 $n=3$ 的情况， $C_9^3=84$ ，其中有 3 种情况不行：

3 4 7 11
3 4 7 12 // 7=3+4
3 4 8 12

所以应该输出 81。

20pt

手算出 $n \leq 10$ 的所有情况，写十个 if 输出答案。

40pt

用三重 for 循环枚举所有可能，然后进行判断， $O(n^3)$ 可以解决问题。

60pt

通过大眼观察法发现题目是有规律的，我们可以用 $C_{3*n}^3$ 来表示总的方案数，减去不合法的方案数。

#include <iostream>
using namespace std;
int main(){
	#define ll long long
	ll n;
	cin >> n;
	ll ans = n * (3 * n - 1) * (3 * n - 2) / 2;
	for(long long i = n; i >= 1; i -= 2)
		ans -= (i - 1) * (i) / 2;
	cout << ans % ((int)1e9 + 7)<< endl;
}

当然，我们可以简单地对大眼观察法做一个解析

$n=2,3,4,5$ 的时候，不合法方案数分别为 2、3、7、13。

4 5 9 14
4 5 9 15
4 5 9 16 // 如果第二个数字等于第一个数字 +1，第三个数字等于前两个数字之和，那么当 n=2,3,4 时，不合法的方案数分别有 1、2、3 种
4 5 10 15
4 5 10 16 // 如果第三个数字等于前两个数字之和 +1，那么当 n=2,3,4 时，不合法的方案数分别有 0、1、2 种
4 5 11 16
4 6 10 16 // n=4 和 n=2,3 的区别是第二个数字比第一个数字大 2 也能够形成一种方案。这个可以理解为 n=4 的时候多出来的一种情况

如果我们不考虑 $n=4$ 的时候多出来的这种情况，限制第二个数字只能比第一个数字大 1，那么我们可以发现 $n=2,3,4,5$ 时，不合法的方案数分别是 1、3、6、10 种。

考虑第二个数字比第一个数字大 2 的情况数，那么 $n=4,5,6,7$ 的情况数又是 1、3、6、10。第二个数字比第一个大 3，那么 $n=6,7,8,9$ 的情况数是 1、3、6、10。所以可以得到上述 for 循环代码，也就是 $i$ 每次变化 2，然后给答案减去一个等差数列求和的值（1、3、6、10... 的规律就是等差数列求和的值。）

alt

T4 群星

首先你选肯定也是选没人选过的第一个，这个结论不用说了吧。

第一个sub是给暴力的。虽然暴力不好写但形式总要走的。

第二个sub，直接考虑 dp，发现“我”选完后完全不需要关心别人选的是什么，只需要关心交换即可。这个你可以搞成一个二维 dp，也可以把转移方程搞出来手玩一下，发现就是个线性递推。所以现在目标就是求出在第几个世纪初我选到了第几个的可能性。直接求极大被选前缀有有点困难，考虑求后缀和，即一个前缀全部被占领可能性。设dp状态为i次操作后长度为j的前缀里有 $k$ 个被占据文明的可能性，i直接滚掉。转移的话，别人抢一个文明就是 $k \to min(j,k 1)$ ，战争是分讨前面选到了啥后面选到了啥之类，也不困难。

第三个sub，发现 $a_i$ 太大怎么办？容易有这样一个直觉，就是 $a_i$ 过大的情况下几乎相当于随机打乱。具体来说.过大可以证明是线性对数这个数量级，std 选的阈值是1000，就是说 $a_i$ 大于这个就直接用组合数填充 dp 数组。

2023 OI 集训营提高组第六场题解