考得还行吧，不过这次区分度不是很大。
接力比赛
题目大意
给出 (n+m) 个人，每个人有两个权值 (v,w)，从 (n,m) 个人分别选出若干人使得两队 (sum v) 相同的情况下，(sum w) 最大。
(nle 1000,vle 1000)
思路
不难看出这个题目没有什么特别严谨的做法，直接随机化乱搞就好了，具体来说就是限定任意时刻两队 (v) 的差值不大于某个值，然后做 01 背包即可。
树上竞技
题目大意
有一棵 (n) 个点的树，在上面选取 (m) 个点作为关键点。找树上的一个点，使得所有关键点到该点的距离之和最小。现在问总共 (inom{n}{m}) 种情况的最小距离和。
(nle 10^6)，答案对 (10^9+7) 取模。
思路
不难看出可以对每一条边计算贡献，对于连接的大小为 (v) 的子树，贡献就是：
[sum_{i=1}^{m-1} min(i,m-i) imes inom{v}{i} imes inom{n-v}{m-i}
]
然后拆开就是：
[[mmod 2=0]m/2 imes inom{v}{m/2} imes inom{n-v}{m/2}+sum_{i=1}^{(m-1)/2}i imes (inom{v}{m-i} imes inom{n-v}{i}+inom{v}{i} imes inom{n-v}{m-i})
]
你发现后面那个式子比较对称，于是我们只需要考虑后面一部分。
设 (p=(m-1)/2)
[sum_{i=1}^{p}i imes inom{v}{i} imes inom{n-v}{m-i}
]
[=vsum_{i=1}^{p}inom{v-1}{i-1} imes inom{n-v}{m-i}
]
考虑其组合意义，发现就是 (n-1) 个球放到 (m-1) 个盒子里，每个盒子最多只能放一个求，满足前面 (v-1) 个盒子球的个数不超过 (p-1) 的方案数。
你发现这个玩意可以递推，设 (h(s)) 表示 (v=s) 的答案，那么 (h(s)) 比 (h(s-1)) 减少的就是 (s-2) 前面有 (p-1) 个，且 (s-1) 放了，所以可以得到递推式：
[h(s)=h(s-1)-inom{s-2}{p-1} imes inom{n-s}{m-p-1}
]
然后预处理一下就可以做到 (Theta(n)) 了。
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 1000000007
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
vector <int> G[MAXN];
int n,m,p,ans,H[MAXN],siz[MAXN],fac[MAXN],ifac[MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
int qkpow (int a,int b){int res = 1;for (;b;b >>= 1,a = mul (a,a)) if (b & 1) res = mul (res,a);return res;}
int binom (int a,int b){return a >= b ? mul (fac[a],mul (ifac[b],ifac[a - b])) : 0;}
void dfs (int u){
siz[u] = 1;
for (Int i = 0;i < G[u].size();++ i){
int v = G[u][i];
dfs (v),siz[u] += siz[v];
}
for (Int k = 0;k < G[u].size();++ k){
int v = G[u][k];
ans = add (ans,add (H[siz[v]],H[n - siz[v]]));
if (m % 2 == 0) ans = add (ans,mul (m / 2,mul (binom (siz[v],m / 2),binom (n - siz[v],m / 2))));
}
}
signed main(){
int T;read (T);
while (T --> 0){
read (n),read (m),p = (m - 1) / 2;
for (Int i = 1;i <= n;++ i) G[i].clear();ans = 0;
for (Int i = 2,fa;i <= n;++ i) read (fa),G[fa].push_back (i);
fac[0] = 1;for (Int i = 1;i <= n;++ i) fac[i] = mul (fac[i - 1],i);
ifac[n] = qkpow (fac[n],mod - 2);for (Int i = n;i;-- i) ifac[i - 1] = mul (ifac[i],i);
H[1] = p >= 1 ? binom (n - 1,m - 1) : 0;for (Int i = 2;i <= n;++ i) H[i] = dec (H[i - 1],mul (binom (i - 2,p - 1),binom (n - i,m - p - 1)));
for (Int i = 1;i <= n;++ i) H[i] = mul (H[i],i);
dfs (1),write (ans),putchar ('
');
}
return 0;
}
虚构推理
题目大意
给出 (n) 个时钟，求出一个时刻使得该时刻分针分针角度最大值最小。
(nle 5 imes 10^4)。
思路
直接二分，判断的话直接区间取交即可，判断时钟的时刻是否包含分针的时刻即可。
问题就是如何取交，实际上你发现每一个区间长度都是固定的，所以排个序就好了。
记忆碎片
题目大意
给出一个树的 (n-1) 条边的权值，问有多少个无向完全图满足其最小生成树的权值为这 (n-1) 个权值。
(nle 40)
思路
并不保证时间复杂度正确！！！
我们发现我们完全可以 dp，我们可以设 (dp[i][S]) 表示对于前 i 小权值满足其连通块大小集合为 S 的方案数。转移的话直接讨论当前边是否存在即可，如果不存在，说明已经在连通块内部，否则一定在连通块外部。
时间复杂度玄学，反正能过就行了。
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define mod 1000000007
#define MAXN 40005
#define MAXM 1005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
vector <int> cur,S[MAXN];
map <vector <int>,int> G;
int n,m,tot,E[MAXN],dp[MAXM][MAXN];
bool flg[MAXN];
int mul (int a,int b){return 1ll * a * b % mod;}
int dec (int a,int b){return a >= b ? a - b : a + mod - b;}
int add (int a,int b){return a + b >= mod ? a + b - mod : a + b;}
void Add (int &a,int b){a = add (a,b);}
void dfs (int s,int mx){
if (mx == 0){
if (s == 0){
S[++ tot] = cur,G[cur] = tot;
for (Int v : cur) E[tot] = add (E[tot],v * (v - 1) / 2);
}
return ;
}
dfs (s,mx - 1);
if (s >= mx) cur.push_back (mx),dfs (s - mx,mx),cur.pop_back();
}
signed main(){
read (n),m = n * (n - 1) / 2;
for (Int i = 1,x;i <= n - 1;++ i) read (x),flg[x] = 1;
dfs (n,n),dp[0][1] = 1;
for (Int i = 1;i <= m;++ i)
for (Int j = 1;j <= tot;++ j){
if (!dp[i - 1][j]) continue;
int tmp = dp[i - 1][j];
if (flg[i]){
vector <int> cur = S[j];
for (Int x = 0;x < cur.size();++ x)
for (Int y = x + 1;y < cur.size();++ y){
vector <int> now;
now.push_back (cur[x] + cur[y]);
for (Int z = 0;z < cur.size();++ z) if (z != x && z != y) now.push_back (cur[z]);
sort (now.begin(),now.end(),greater<int>());
Add (dp[i][G[now]],mul (cur[x] * cur[y],tmp));
}
}
else Add (dp[i][j],mul (tmp,E[j] - (i - 1)));
}
write (dp[m][tot]),putchar ('
');
return 0;
}