CEOI

CEOI2019:4/6

CEOI2018:0/?

CEOI2017:0/?

CEOI2016:0/?

质量不错

CEOI2019

CEOI2019 D1T2 Dynamic Diameter Loj3163 动态直径

请先思考后再展开

就是线段树nlogn动态维护直径的裸题,这里有教程

CEOI2019 D1T3 Cubeword Loj3164 立方填词

请先思考后再展开

这题的关键在于注意到最后一个subtask只有16分,所以一定做法差不多,就是搞点特技
这叫由数据分布知出题人心态(雾

首先要转化奇葩题意,通过和6个样例快乐van耍后发现:
先按照单词长度分组,对每组求出结果求和;然后把每组的单词正反都插入某个字典,去重后求val(a,b)表示两段字母分别为a和b下可选单词方案数。现在有有一个立方体的8个格点(带标号),每个格点可以填62种字母,然后每个方案的权值就是立方体12条边的权值乘积。
subtask2:5次方的,一种是如官方题解般,如下图所示编号,然后考虑完i就可以丢掉i-5的信息了,或者像我想的,以某个点为1,然后bfs分成4层(1+3+3+1),画一下具体哪些边,发现也是保存某4个的信息转移。
subtask3:优化到4次方的话,其实上面的第二种应该是更接近的(然而我并没有想到),不过如果你从立方体分割成5个四面体的角度考虑说不定第一种好想?不过与我这种立体几何极差的人无关……
因为你看到第二种就知道他是有层的,例如可以搞成二分图,考虑某侧的4个点($a,b,c,d$),然后你把边具体地画出来

!!你惊讶地发现,外面每个点会过来选3个点覆盖,故每个方案的方案数就是$f(a,b,c)f(a,b,d)f(a,c,d)f(b,c,d)$
其中f表示任意选一个外面的点t覆盖这三个点的方案数,故是四次方的
然后 我脑抽就直接写了交上去只有84,因为漏考虑前面还有一个7的常数了,而且是满的复杂度,会被卡
subtask4这里结合分数的分布其实不难想。正经来说就是考虑你只关心这4个点的组合而不是所有方案,枚举的时候只需要枚举$a \le b \le c \le d$,系数就是多重集,这样常数/24,不过我的代码并没有怎么重视常数优化
code

CEOI2019 D2T1 Dynamic Diameter Loj3165 游乐园

题意补充:一对点间最多会有一条边

请先思考后再展开

首先你需要看过或能自己yy出dag的计数

记$no(S)=点集生成子图无边,ned(T\to S\setminus T)=连过去翻转了多少边,然后下面所有转移的条件都是T \subseteq S,no(T)=1,T \ne \emptyset$

那么不难写出一个dp式:$f(S,cnt)=\sum_T (-1)^{|T|+1}f(S \setminus T,cnt-ned(T \to S \setminus T))$,这个是非常经典的容斥,因为若T能转移,则T的子集也能

方法一($2^nn^2$):考虑观察一下题目的性质,一个dag方案所有边翻转还是个dag,他们的权值和=m,所以我们只需要计算出方案数,然后$*m/2$即可;方案数的计算会非常简单:$f(S)=\sum_T (-1)^{|T|+1}f(S \setminus T)$ ,这个搞个子集卷积就好了,见fwt教程及州区划分

看了看zsy的代码,并没有看懂……好像是个求逆?

方法二($3^n$):这个方法复杂度对本题不是最优,但如果改改这道题,废掉上面那个性质,就必须这样做了(也就是拓展性较强,才不是因为我太菜没想到上面的性质),而且这个做法的容斥,我曾一度以为是错的(容斥太差

看着dp方程,自然想怎么省掉一维,很自然的思路是 $设g(S)=权值和$

$g(S)=\sum_T (-1)^{|T|+1}(g(S \setminus T)+f(S \setminus T)*ned(T \to S \setminus T))$,这个怎么$3^n$?对每个S存一下$record(T)=ned(T \to S \setminus T)$,每次从去掉lowbit的地方转移过来即可

接下来分析正确性,你注意到这不是普通的方案容斥,而是带权值的;但注意到其权值满足$\forall A满足条件且\subseteq T,val(T)=val(A)+val(T \setminus A),因为no(A)=1$

设当前根集合为T,设容斥系数$pp_i$表示集合大小为i(显然只和大小有关),那么我们希望:

$val=\sum_{a=1}^{贡献边数} (\sum_{i=1}^{|T|}pp_iC_{n-1}^{i-1}+\sum_{i=1}^{|T|}pp_iC_{n-1}^{i} )=val*\sum_{i=1}^{|T|}pp_iC_n^i$,即考虑在本次被包含或在下一次被包含,然后这就是经典的容斥系数了,$pp_i=(-1)^{i+1}$;这里漏想了括号里右边的部分,所以以为是错误的做法……

code,这个做法因为有模常数稍大,需要常数优化才能通过

CEOI2019 D2T2 Magic Tree Loj3166 魔法树

请先思考后再展开

这题一开始乱想了想都不太行,然后立刻第一直觉就是dsu on tree,确实猜对了
设dp(x,time)然后先考虑序列,再考虑树,发现转移如下:
每次对每棵孩子的子树的整个dp序列做前缀mx,然后把各个孩子一一对应加起来,此时是递增的
然后如果x上有果实(time,val),那么dp(x,time)+=val,就是可能凸出来

为了让复杂度和子树大小相关,考虑只存储与前面不同的地方,并且仔细观察转移发现我们应当存储的是前缀mx后的结果
方向一:
直接存储具体的值,那么需要写一个动态开点权值线段树,然后到时候启发式合并就是后缀加
然后考虑x上果实的时候需要找到下一个比dp(x,time)+val更大的地方,中间删除,这个利用单调的特性是可以求的
这种写法应该是可行的,但码量较大,考虑怎么减小
方向二:
考虑差分,这个我确实没想到,主要是观察到我们需要的是后缀加,同时注意到差分后我们只需要处理val,而且中间要被删除
考虑每个数只会被删除一个,所以是可以暴力删除的,可以用map或者set来写,非常好写

上述两个方向的复杂度都是log方

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
const int N=1e5+10;
int fa[N],now[N];
map<int,ll> mp[N];typedef map<int,ll>::iterator IT;
int merg(int x,int y)
{
if(mp[x].size()>mp[y].size()) swap(x,y);
for(IT it=mp[x].begin();it!=mp[x].end();it++) mp[y][it->FR]+=(it->SE);
return y;
}
pr a[N];
void main()
{
int n=qread(),m=qread();qread();
for(int i=1;i<=n;i++) now[i]=i;
for(int i=2;i<=n;i++) fa[i]=qread();
for(int i=1;i<=m;i++){int x=qread(),t=qread(),val=qread();a[x]=MP(t,val);}
for(int i=n;i>=2;i--)
{
int t=now[i],ti=a[i].FR;ll val=a[i].SE,bkup=val;
mp[t][ti]+=val;IT gg=mp[t].find(ti);gg++;
while(gg!=mp[t].end())
{
IT tmp=gg;if(val<gg->SE){mp[t][gg->FR]-=val;break;}
val-=gg->SE;gg++;mp[t].erase(tmp);
}
now[fa[i]]=merg(now[fa[i]],t);
}
ll ans=0;for(IT it=mp[now[1]].begin();it!=mp[now[1]].end();it++) ans+=(it->SE);
write(ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/2558.html
转载请注明出处,谢谢!