暑假集训六
别问为什么从六开始。
题面
A.接力比赛
两个01背包跑一遍。
别问代码为啥写的这么阴间。
Code
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 1010, MAXV = 1e6 + 10;
const long long INF = 1e18 + 1145141919810;
int n, m;
long long w, v, ans;
long long sum_w[MAXN], sum_b[MAXN];
long long dp[2][MAXV];
bool vis_w[MAXV], vis_b[MAXV];
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
int main(){
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
n = read(), m = read();
vis_w[0] = true;
for(register int i = 1; i <= n; i++){
w = read(), v = read();
sum_w[i] = sum_w[i - 1] + w;
for(register int j = 1; j <= w; j++)
dp[0][j + sum_w[i - 1]] = -INF;
for(register int j = sum_w[i - 1]; j >= 0; j--){
if(vis_w[j]){
dp[0][j + w] = max(dp[0][j + w], dp[0][j] + v);
vis_w[j + w] = true;
}
}
}
vis_b[0] = true;
for(register int i = 1; i <= m; i++){
w = read(), v = read();
sum_b[i] = sum_b[i - 1] + w;
for(register int j = 1; j <= w; j++)
dp[1][j + sum_b[i - 1]] = -INF;
for(register int j = sum_b[i - 1]; j >= 0; j--){
if(vis_b[j]){
dp[1][j + w] = max(dp[1][j + w], dp[1][j] + v);
vis_b[j + w] = true;
}
}
}
long long len = max(sum_w[n], sum_b[m]);
for(register int i = 1; i <= len; i++){
if(vis_w[i] && vis_b[i])
ans = max(ans, dp[0][i] + dp[1][i]);
}
printf("%lld", ans);
return 0;
}
B.树上竞技
按照边去考虑，如果在一条边 \(E\) 的两侧分别有 \(x\) 和 \(m-x\) 个关键点，
不妨令 \(x\leqslant m-x\) 那么最后的汇聚点一定在 \(m-x\) 这个方向，
这样可以只让 \(x\) 条边经过 \(E\)，代价较小
然后设某条边两侧分别共有 \(s\) 和 \(n-s\) 个点，容易发现我们需要求
\[\sum\limits_{i=1}^{m-1}\min\{i,m-i\}\times C_{s}^{i}C_{n-s}^{m-i} \]发现 \(\min\) 不是很好处理，考虑把它拆开来,还要加上 \(m\) 为偶数的情况,用 \(\operatorname{DFS}\) 预处理节点子树大小，原式可以化成
\[ans=\sum\limits_{u=2}^{n}\sum\limits_{i=1}^{\frac{m-1}{2}}i\times C_{size[u]}^{i}C_{n-size[u]}^{m-i}+i\times C_{size[u]}^{m-i}C_{n-size[u]}^{i}+[m\%2==0]\frac{m}{2}\times C_{s}^{\frac{m}{2}}C_{n-s}^{\frac{m}{2}} \]后面的一小点式子可以暴力硬扫，考虑前面的怎样优化
不妨设 \(k=\frac{m}{2}\)，发现比较显然地，
\[\sum\limits_{i=1}^{k}i\times C_{s}^{i}C_{n-s}^{m-i}=s\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i} \]不妨令 \(f(s)=\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}\)，那么答案就是
\[\sum\limits_{u=2}^{n}f(size[u])+ f(n-size[u]) \]考虑如何求出 \(f(s)\)，发现它的组合意义是 \(n-1\) 个物品里选择了 \(m-1\) 个，前面 \(s-1\) 个物品中选择了 \(k-1\) 个的方案数
如何递推 \(f(s)\) ？
不难发现，\(f(s)\) 变成 \(f(s+1)\) 变少的部分就是前 \(s-1\) 个点中选择 \(k-1\) 个，选择了 \(s\) 为第 \(k\) 个点，后面 \(n-s-1\) 个点里选择了 \(m-k-1\) 个点
这是为什么呢？我们考虑如果没有选择 \(s\) 作为第 \(k\) 个点
那么前 \(s\) 个点中选择 \(k-1\) 个点和前 \(s-1\) 个点中选择 \(k-1\) 个是等价的
所以必须让 \(s\) 作为第 \(k\) 个点被选择，多出来的方案数根据乘法原理就是
\[C_{s-1}^{k-1}C_{n-s-1}^{m-k-1} \]也就是说
\[f[s+1]=f[s]+C_{s-1}^{k-1}C_{n-s-1}^{m-k-1} \]统计答案即可。
算是偷的markdown。
Code
#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int Mod = 1e9 + 7;
const int MAXN = 1e6 + 10;
int n, m, k, cnt;
LL ans;
int head[MAXN], size[MAXN];
LL fac[MAXN], inv[MAXN];
LL f[MAXN];
struct Edge{
int to, next;
}e[MAXN << 1];
inline void Add(int u, int v){
e[++cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt;
}
LL Fast_Pow(LL a, LL w, LL p){
LL ans = 1;
while(w){
if(w & 1) ans = ans * a % p;
a = a * a % p;
w >>= 1;
}
return ans;
}
LL Inv(LL a, LL p){
return Fast_Pow(a, p - 2, p);
}
LL C(LL n, LL m, LL p){
if(!m) return 1;
if(m > n) return 0;
return fac[n] * inv[m] % p * inv[n - m] % p;
}
void init(){
fac[1] = 1;
for(register int i = 2; i <= n; i++)
fac[i] = 1LL * fac[i - 1] * i % Mod;
inv[n] = Inv(fac[n], Mod);
for(register int i = n - 1; i >= 0; i--)
inv[i] = 1LL * inv[i + 1] * (i + 1) % Mod;
}
void dfs(int rt, int fa){
size[rt] = 1;
for(register int i = head[rt]; i; i = e[i].next){
int v = e[i].to;
if(v == fa) continue;
dfs(v, rt);
size[rt] += size[v];
ans = 1LL * (ans + f[size[v]] % Mod + f[n - size[v]] % Mod) % Mod;
if(!(m & 1)) ans = 1LL * (ans + C(size[v], m / 2, Mod) * C(n - size[v], m / 2, Mod) % Mod * (m / 2) % Mod) % Mod;
}
}
inline int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
int main(){
freopen("meeting.in", "r", stdin);
freopen("meeting.out", "w", stdout);
n = read(), m = read();
init();
for(register int i = 1; i <= n - 1; i++){
int u;
u = read();
Add(u, i + 1);
Add(i + 1, u);
}
k = (m - 1) / 2;
if(k >= 1) f[1] = C(n - 1, m - 1, Mod);
for(register int i = 2; i <= n; i++)
f[i] = 1LL * ((f[i - 1] - C(i - 2, k - 1, Mod) * C(n - i, m - k - 1, Mod) % Mod) % Mod + Mod) % Mod;
for(register int i = 2; i <= n; i++)
f[i] = 1LL * f[i] * i % Mod;
dfs(1, 0);
printf("%lld", ans);
return 0;
}
C.虚构推理
其实不用题解那么麻烦，可以枚举时间再lower_bound优化查询。
查询到和当前时间的角最大的时间就可以。
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 5e4 + 10;
const long double EPS = 1e-10;
int n;
long double ans = 1e10;
long double angle_h[MAXN], angle_m[MAXN];
struct Clock{
int h, m, s;
}c[MAXN];
inline long double fmax(long double x, long double y){
return (x - y > EPS) ? x : y;
}
inline long double fmin(long double x, long double y){
return (y - x > EPS) ? x : y;
}
inline long double fabs(long double x){
return (0 - x > EPS) ? -x : x;
}
long double Get_Cut(long double angle1, long double angle2){
return fmin(fabs(angle1 - angle2), 360.0 - fabs(angle1 - angle2));
}
long double Find_Cut(long double angle, long double *clock){
int pos1, pos2;
if(180.0 - angle > EPS){
pos1 = lower_bound(clock + 1, clock + 1 + n, angle + 180.0) - clock;
pos2 = pos1 - 1;
}
else{
pos1 = lower_bound(clock + 1, clock + 1 + n, angle - 180.0) - clock;
pos2 = pos1 - 1;
}
if(pos1 == n + 1) pos1 = 1;
if(pos2 == 0) pos2 = n;
return fmax(Get_Cut(angle, clock[pos1]), Get_Cut(angle, clock[pos2]));
}
int main(){
freopen("unreal.in", "r", stdin);
freopen("unreal.out", "w", stdout);
scanf("%d", &n);
for(register int i = 1; i <= n; i++){
scanf("%d:%d:%d", &c[i].h, &c[i].m, &c[i].s);
if(c[i].h >= 12) c[i].h -= 12;
angle_m[i] = 1.0 * c[i].m * 6.0 + c[i].s * 0.1;
angle_h[i] = 1.0 * c[i].h * 30.0 + c[i].m * 0.5 + c[i].s / 120.0;
}
sort(angle_m + 1, angle_m + 1 + n);
sort(angle_h + 1, angle_h + 1 + n);
for(register long double h = 0; h < 12; h++){
for(register long double m = 0; m < 60; m++){
for(register long double s = 0; s < 60; s += 0.1){
long double m_angle = 1.0 * m * 6.0 + s * 0.1;
long double h_angle = 1.0 * h * 30.0 + m * 0.5 + s / 120.0;
ans = fmin(ans, fmax(Find_Cut(m_angle, angle_m), Find_Cut(h_angle, angle_h)));
}
}
}
printf("%Lf", ans);
return 0;
}
D.记忆碎片
不会，可以去看Delov 大佬的题解
或者SoyTony大佬的题解