D
题目
这题分才1800 XD,卡C卡太久了
给你一个树，树节点个数n<=3e5
有k个叶子k<n
非叶子节点有操作符f,f=0表示取子节点最小值，f=1表示取子节点最大值
你需要把值1到k的放到叶子上，使得根节点得到的结果最大，求这个最大值
题解
dp[节点] = 节点以下的叶子数量-节点以下能达到的最大值，所以dp越小越好
这样答案=k-dp[root]
举例
一个max节点i，如果它的子节点全是叶子，那么dp[i]=0
一个min节点i，如果它的子节点全是叶子，且它有m个子节点，那么dp[i]=m-1
那么更一般的
一个max节点i,dp[i] = min(dp[child])
一个min节点i,`dp[i] = i以下叶子节点总数-max(childi以下叶子节点总数-dp[childi]) 吗 ?
并不,考虑min下两个节点，分别长度，和dp为
leni,dpi 和 lenj,dpj,比如你想 (4,2),(16,8)
那么如果我们选取i为min的取值，那么这两个节点贡献的dp最小为dpi+(dpj+1)
那么如果我们选取j为min的取值，那么这两个节点贡献的dp最小为dpj+(dpi+1)
一个min节点i,`dp[i] = dp[?] + sum 剩余dp + 直接子节点个数-1;
初始化dp[叶子]=0
CODE
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);
int op[300010];
vector<int>child[300010];
int leafcnt[300010];
int n;
int dfs(int idx){
if(child[idx].size() == 0){
leafcnt[idx] = 1;
return 0;
}
if(op[idx] == 1){
int ret = 300001;
for(auto item:child[idx]){
ret=min(ret,dfs(item));
leafcnt[idx]+=leafcnt[item];
}
return ret;
}else{
int ret = 0;
for(auto item:child[idx]){
ret += dfs(item)+1;
leafcnt[idx]+=leafcnt[item];
}
return ret -1;
}
}
int main(){
cin>>n;
rep(i,0,n){
scanf("%d",op+i);
}
rep(i,1,n){
int fa;
scanf("%d",&fa);
child[fa-1].pb(i);
}
int ret = dfs(0);
printf("%d",leafcnt[0]-ret);
return 0;
}
|
E
2100分
交互题
n*n格子 (n<=1000)
里面有一条弯曲的蛇，如果碰到蛇的头和尾则会挂掉
提供一个设备，传入一个矩形，可以返回蛇身体穿过矩形边界的次数
他只能 进行2019次询问，需要得到蛇头和尾的坐标。
蛇可以1x1，也就是身体长度为0,头尾在一个格子里
蛇在询问过程中不会动。
题解
显然 如果头和尾有且只有一个在矩形,那么返回值为0或奇数
然后就先定行或列，首先如果长度不为0，那么必定不在同一个格子里，所以x和y必定有一个不同，
所以按照1xn的列和行依次尝试一定有2个为奇数返回，再二分对应的行或列
依次尝试O(2*n),二分O(2*log n),注意到只有2019次机会，所以我们需要加一些细节判断(否则会wa23)
我们注意到，如果一共n列，那么前n-1列有一个奇数出现，那么最有一列一定是奇数，如果前面全是偶数，那么最后一列也一定是偶数。行同理，所以可以少掉两个依次尝试
长度为0的，我们无法检测到，无脑输出! 1 1 1 1即可
CODE
CODE LINK
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);
int q(int x1,int y1,int x2,int y2){
printf("? %d %d %d %d\n",x1,y1,x2,y2);
fflush(stdout);
int ret;
scanf("%d",&ret);
return ret;
}
void ok(int x1,int y1,int x2,int y2){
printf("! %d %d %d %d\n",x1,y1,x2,y2);
fflush(stdout);
}
int main(){
int n;
cin>>n;
int ii0=-1;
int ii1=-1;
rep(i,1,n+1){
if(i == n){
if(ii0!=-1 && ii1 ==-1){
ii1=n;
}
break;
}
int r = q(i,1,i,n);
if(r%2==1){
if(ii0 == -1){
ii0 = i;
}else if(ii1 == -1){
ii1 = i;
break;
}
}
}
int jj0=-1;
int jj1=-1;
if(ii0 == -1){
rep(i,1,n+1){
if(i == n && jj0!=-1 && jj1 !=-1){
jj1=n;
break;
}
int r = q(1,i,n,i);
if(r%2==1){
if(jj0 == -1){
jj0 = i;
}else if(jj1 == -1){
jj1 = i;
break;
}
}
}
int l =1,r=n;
while(l != r){
int m=(l+r)/2;
int ret = q(l,jj0,m,jj0);
if(ret%2==1){
r=m;
}else{
l=m+1;
}
}
ii0=l;
l = 1;
r = n;
while(l != r){
int m=(l+r)/2;
int ret = q(l,jj1,m,jj1);
if(ret%2==1){
r=m;
}else{
l=m+1;
}
}
ii1=l;
}else{
int l =1,r=n;
while(l != r){
int m=(l+r)/2;
int ret = q(ii0,l,ii0,m);
if(ret%2==1){
r=m;
}else{
l=m+1;
}
}
jj0 = l;
l =1;
r=n;
while(l != r){
int m=(l+r)/2;
int ret = q(ii1,l,ii1,m);
if(ret%2==1){
r=m;
}else{
l=m+1;
}
}
jj1 = l;
}
if(ii0 == -1){
ok(1,1,1,1);
return 0;
}
ok(ii0,jj0,ii1,jj1);
return 0;
}
|
F
这篇文章鸽了这么久买就是因为这道题，我现在还是没有完全理解到，所以可以忽略下面所写TODO,因为下面只写了我能理解到的部分
CF 评分2800
长度l线段
随机取n个子线段,线段端点随机,可以非整数
求被这n条线段覆盖次数>=k的线段期望长度
l<=1e9
n,k<=2000
除法使用乘法逆元,结果模998244353
题解
官方
首先放缩原理,期望与l正相关，所以l就是个倍数，所以只用考虑长度为1的情况.
根据实分析
贡献累计
考虑这n个线段的2n个端点，分割出的2n+1条线段，
计算每条线段被覆盖至少k次区间的期望数量 *期望长度
首先这2n个点是相互独立的
期望数量 = (>=k)概率
现在假设我们的到了一个已经生成好的点列，我们并不知道它们的连接情况。
f(i,j,0/1 )表示以上点列 前i个点中 剩余j个点未匹配(线段左端)，满足(>=k覆盖)的段的数量,P点是否出现(0,1)
P在i点的时候,f(i,j,1) = f(i-1,j,0) // j>=k
新的线段i+j+x < 2n, f(i-1,j-1,x)->f(i,j,x)
匹配开始idea线段:f(i-1,j+1,x)*(j+1)->f(i,j,x)
所有的arrangements一共有(2n+1)!条