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){ // samex;
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;
}
}
}
// er fen
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{ // specific i0 & i1
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)!

题目

A Thanos Sort

没啥讲的,阅读理解,模拟实现

B Kanban Numbers

我的解题过程:搜索kanban->signboard->led number,尝试和led显示相关,未果

你群群友,有暴力枚举过B题的orz

实际解法是 标题+英语, kanban number = 'k' 'a' 'n' ban number,也就是 英文不含字母k a n

C Mystery Circuit

量子计算相关(实际没有到量子)

有工具Quirk

  1. 4位2进制表示
  2. 前后倒序
  3. 按工具上面的按钮
  4. 前后倒序
  5. 再转换为10进制数

3->0011->1100->1011->1101->13

https://en.wikipedia.org/wiki/Quantum_logic_gate

首先十字+圆圈 表示的是一个非门

然后 竖着看,黑色的点是控制点,也就是竖着一条线上黑点 传入的数据 全是1时,非门才工作

这就是工具的运作原理,因为数也只有15个,你可以枚举打表,也可以实现这个控制逻辑

D Pigeon d’Or

我也发现是错误单词了,https://www.grammarcheck.net/editor/ 可以检查拼写错误,但是ai的范围是误导XD..我还在想 1 2 3 4 5的样例数据是怎么解释。

正确的解法是,把错的字母连接起来,变成一个句话,这句话就是一个英文描述的公式,66666

E Fourier Doodles

这是近年的机器学习识数梗

我已经发现的有:前20张图size很大[指文件大小,不是图片尺寸]

正确解法就是 标题+压缩包,如题名 的傅里叶,把前20个图做傅里叶,然后拼出表达式,即可

请把下面程序放到和图片同目录下,然后运行(自行用pip install安装依赖包)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/python2
from PIL import Image
import numpy as np
from scipy import fftpack
import matplotlib.pyplot as plt

if __name__ == '__main__':
plt.figure(figsize=(5, 5)) # 画布大小
for i in range(1, 21): # 20张图片
img = Image.open(str(i) + '.png').convert('L') # 灰度 多色应该也可以,但是还要加更多处理
imgout = fftpack.fftshift(fftpack.fft2(img)) # 2维傅里叶
psd2D = np.log(np.abs(imgout)) # (256,256) 取log
plt.subplot(4, 5, i) # 把它们依次显示在画布上
plt.axis('off')
plt.imshow(psd2D, cmap='Greys_r')
plt.show()

官方题解给的在线工具 http://www.ejectamenta.com/Imaging-Experiments/fourierimagefiltering.html

F Neat Numbers

嗯。。我去google查了单词,但。。。。 google的翻译并不能成功的帮助我

正确解法是 标题+英文单词理解+样例,neat words要的是所有大写字母 都是直线段组成的 即可AEFHIKLMNTVWXYZ,相对来说其它字母是带有

G AI Takeover

和机器人石头剪刀布,它有6个测试,6种策略,对你是未知的,你需要自行猜测

如果你们出一样的,算机器人赢

机器人不会peeking你的选择(就是理论上同时)

R石头P布S剪刀

你需要的是20场内赢至少10场

题解:关键在于成功的猜到机器人的6种方法

题透: 机器人的方案

  1. 全R
  2. 全P
  3. 全S,
  4. 循环R-P-S
  5. 从R开始,然后总是扮演人类玩家的最后一步,
  6. 从R开始,然后总是发挥击败人类玩家最后一步的动作。

赛内建议的探测方法,用memory allocation ,或者sleep time,也就是可以读到的cf输出,来编码你直接看不到的结果,从而探测,机器人的方案

综上

真好玩+只会签到,题目都有实际的背景,出题不是乱出….总结逐渐开花

D

题目HERE

题目大意

1<=m<=100'000

$ dp[x] =1 + \sum_{j=1}^{m}\frac{dp[gcd(j,x)]}{m} $

求$ans=\sum_{i=1}^{m}\frac{dp[i]}{m}$

上面公式怎么来的呢,一眼可见

解法

我做的时候卡在变形上了

首先,我们观察到右侧的dp中是j与x的gcd,那么也就是取值范围都是 x的约数,那么变形有

$f[n]=1+\sum_{d|n}\frac{f[d]\cdot g(n, d)}{m}$

其中g(n,d)表示 从1到m,和n gcd后结果为d的 数 的个数,也就是

$ g(n, d) = \sum_{i=1}^m[gcd(n, i)=d] $

同时乘上m,并把右侧 的f[n]的部分移到左侧

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\cdot g(n, d)$

现在问题还有怎么计算g

观察g的表达式,说明i一定是d的倍数,所以可以变成d*?

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(n,i*d)=d] $

$ g(n, d) = \sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(\frac{n}{d},i)=1]$

注意到右侧的 求和部分实际是要gcd=1时,返回1,其它情况返回0,这和

$\mu * 1 = \epsilon$对应,也就是莫比乌斯,$\mu$函数 的因子和的性质,详细内容见下方我之前的莫反总结中写到的性质和证明

$\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|gcd(\frac{n}{d},i)}\mu(t)$

$=\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{t|\frac{n}{d},t|i}\mu(t)$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac {\lfloor \frac{m}{d} \rfloor} {t} \rfloor$

$=\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

综上

$(m-\lfloor\frac{m}{n}\rfloor)f[n]=m+\sum_{d|n,d\neq n}f[d]\sum_{t|\frac{n}{d}}\mu(t)\cdot \lfloor \frac{m}{dt} \rfloor$

官方题解

官方题解

[题解1]

没有看懂后面的变形,怎么突然1就没了,m的系数移动后也没了??

方法也是讲如何计算g(n,d),计算多少个p=1->m 使得 gcd(p,n)=d

假设用乘法表示n和p,n=d*a,p=d*b, 有1<=p<=m,gcd(a,b)=1,也就是1<=b<=m/d

然后对a因数分解,因此b不能含有a的任何因子,然后用 容斥算,因为n很小最多6个不同的质因子,所以简单dp

[题解2 就是莫反了]

总结

我之前的莫反总结

参考

CODE 代码很丑见谅XD

E

题目HERE

题目大意

n个人 最大5000

m个组 最大5000

每个人有潜力值最大 5000

每个人仅属于一个组

每一轮删除一个指定的人index_i(输入提供)

一共d轮,最大n

每一轮,从各组中选一个人构成数组,选出后放回原来的组,求每一轮的最大mex

mex:{数组中未出现的最小自然数},如 mex{0,1,2,3,6,7} = 4

解法

先倒转顺序,离线处理,把删除人变为向组中加人

网络流

起始节点到各个组节点建一条边,

各组的人向他的潜力值节点建立边

潜力值0 向end建立边


当潜力值i 连接到end后,总流量等于i+1时(因为从0开始),把潜力值i+1也连接到end

O(轮数*网络流复杂度) <= O(d*(m+n+mex))

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
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
#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);

#define ST 0
#define END 10005
#define POT(v) (v+5001)

// 0 , 1-5000 , 5001-10002 10005
// st->1 -> group->1 -> potential(5001+mex+1) ->1(dynamic add) -> end

// reverse order

map<int,int>flow[10010];

int n,m,d;
int p[10010];
int c[10010];
bool notin[10010];
int order[10010];
int ans[10010];
int mex = 0;
int vis[100010];

int dfs(int i,int load){
if(i == END)return load;
vis[i] = true;
for(auto item:flow[i]){
if(vis[item.first])continue;
if(item.second != 0){
int ret = dfs(item.first,min(load,item.second));
if(ret != 0){
flow[i][item.first] -= ret;
flow[item.first][i] += ret;
return ret;
}
}
}
return 0;
}

int getflow(){
int ret = dfs(ST,1);
rep(i,0,m+1){
vis[i]=false;
}
rep(i,0,5000){
vis[POT(i)] = false;
}
return ret;
}

int main(){
cin>>n>>m;
rep(i,1,n+1){
scanf("%d",p+i);
}
rep(i,1,n+1){
scanf("%d",c+i);
}
scanf("%d",&d);
rep(i,0,d){
scanf("%d",order+i);
notin[order[i]] = true;
}
// built
// ST->group
rep(i,1,m+1){
flow[ST][i] = 1;
}
// group->mex
rep(i,1,n+1){
if(notin[i])continue;
flow[c[i]][POT(p[i])] = 1;
}
// mex 0 -> end
flow[POT(mex)][END] = 1;
per(i,0,d){
while(getflow()){
flow[POT(++mex)][END] = 1;
}
ans[i] = mex;
// [order]->mex
flow[c[order[i]]][POT(p[order[i]])]+=1;
}
rep(i,0,d){
printf("%d\n",ans[i]);
}
return 0;
}

总结

CODE

E

题目HERE

题目大意

数组a[n], 其中2<=n<=100'000,-1'000'000'000<=a[i]<=1'000'000'000

a[i+1]-a[i] >= k[i] ,其中-1'000'000<=k[i]<=1'000'000

q个操作1<=q<=100'000

操作类型1,对a[i] 增加x,其中0<=x<=1'000'000,如果操作后无法满足上面与k的关系,则调整a[i+1]=a[i]+k[i] 直到所有 的值都满足

操作类型2,求sum of a[l->r]

解法

一眼就是个线段树,但是比以往遇到的线段树,要难维护一些,注意一下需要维护的状态

limiaomiao的解法

  1. [l->r] 实际的 差: der
  2. [l->r] 的差前缀和的和 :sum[l->r] = (der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r])

build tree

der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[r]-a[l]的实际差值

sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)

add val

对a[i]增加x的操作

实际是对 a[i-1]和a[i]的差 增加,以及 对a[i]和a[i+1]的差 的减少x

这样,线段树上操作,[这样感觉会被卡,但看limiaomiao的代码 有个神奇操作,加了一个set来记录,哪些的差值和k不同] 这样每次改变值,最多能产生1个 新的和k不同的差,那么每次的时间消耗=1+消耗的不同于k的值

所以总时间 = 操作数+ 总消耗 <= 操作数+ 初始不同的个数+过程中产生的不同的个数,是线性关系

询问

ans_sum[l->r]

=a[l]+...+a[r]

= a[l]*(r-l+1)+ ((der[l])+(der[l]+der[l+1])+...+(der[l]+...+der[r]))

= getval(a[l])×(r-l+1)+query_sum(l->r)

我这里的思路

注意到实际维护的是a[i+1]-a[i]-k[i] >= 0

那么线段树,可以是在数组b[i]=a[i+1]-a[i]-k[i]上面建立

b[i]所以要全非负

build tree

der[o]= der[o<<1] + der[o<<1 | 1] 记录的是a[l->r]的差值再减去这一段k的差值保证非负

sum[o]= sum[o<<1] + sum[o<<1 | 1] + der[o<<1] * length of (o<<1 | 1)

add val

同样 对a[i]增加x的操作

实际是对 a[i-1]和a[i]的差 增加,以及 对a[i]和a[i+1]的差 的减少x

注意到这样的话,增加x的部分就可以先lazy掉,

在减少的部分,如果 der[l->r] < x 那么这一段整个der都是0,可以lazy掉,保证了每次的log级别的操作

除此以外,每次可能访问的时候,把lazy的部分向下分发一下

询问

ans_sum[l->r]

=a[l]+...+a[r]

= a[l]*(r-l+1)+ ((der[l]+k[l])+(der[l]+k[l]+der[l+1]+k[l+1])+...+(der[l]+k[l]+...+der[r]+k[r]))

= getval(a[l])×(r-l+1)+query_sum(l->r)+sum_der_k(l->r)

总结

相比之下 我这样写,线段树的lazytag的多两个lazytag,而且 对于k也要维护一个sum的线段树,更难写

题目HERE

题目大意

给你

a1 个1

a2 个2

a8 个8

求用这些数中的一部分相加,得到的 最大的 不大于W的 数为多少

其中

1<=ai<=10^16

0<=W<=10^18

解法

翻译自官方题解

假设在未知的最优解中 i 取c_i

L = lcm(1,,,,8) = 840

那么c_i可以表示为

c_i= (L/i)*P_i+q_i 根据除法余数性质可以让q满足 0<=q<L/i

(L/i)*P_i个i是L的倍数(且是1,2,3,4…倍 占满)(小学未知数乘法?)

所以只用枚举q_i的部分

然而这样 所有方案840**8/8/7/6/5/4/3/2/1=6147715553280000000时间内肯定过不了

dp[1->x types of items][weight] = 把构成weight的部分去除后 还能最多有多少个L 这里的构成

空间O(8*8L)

时间O(8L*sum(L/1+L/2+...+L/8))

ans = max{ weight + L * min(dp[0][weight],(W-j)/L) (0<=weight<=8L)

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 9;
const int L = 840;

typedef long long li;

li dp[N][L * N];
li W;
li cnt[N];

int main()
{
cin >> W;
for(int i = 0; i < 8; i++)
cin >> cnt[i];
for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
dp[0][0] = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < L * N; j++)
{
if(dp[i][j] == -1) continue;
int b = L / (i + 1);
if(cnt[i] < b)
b = cnt[i];
for(int k = 0; k <= b; k++)
{
li& d = dp[i + 1][j + k * (i + 1)];
d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
}
}
}
li ans = 0;
for(int j = 0; j < L * N; j++)
{
if(j > W || dp[8][j] == -1)
continue;
ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
}
cout << ans << endl;
}
0%