NOIP2018 划水记+题解

NOIP2018

day0

3:30才睡着,超级担心明天会困
upd:学到了,以后如果困的话可以喝红牛

day1

居然一点也不困?感觉状态不错

考试前曾经感叹:如果到时候有现在这么好用的键盘就好了……
结果居然还成真了!一模一样……
然后不卡空间好评,瞎jb开
评测机超强好评(没注意评测费,听说加了100),不用担心被卡常了

t1,一开始想着差分,但很难做
先写了一个不会算复杂度的做法,应该蛮多分的吧,就是solve(l,r),暴力找最小值去分割
然后发现随便卡……但显然可以线段树优化,log找到最左边的最小值,然后以此为分割在右边找
那分析一下势能,时间为 $O(nlog^2 n)$
好慢啊拍起来已经1h了

t2,加法线性空间?各种二元函数分析?联想到 HAOI2018奇怪的背包?
搞了20min还是不会,看下一题

t3,居然还真的非常可做
二分答案后,设g表示向上的唯一一条链的长度
那么现在问题就是给出一个序列,两两配对成至少ln的链,相同条数下选择【上传最大链】的方案
我的做法:维护一个set,每次取出最小,找到能配对的中最小的,都从中删除
所有被废弃的取mx上传
时间的话,看这次评测机配置这么高,应该不会被卡常的吧

回去看t2,找性质
注意到只会是小的影响大的,所以从小到大考虑
显然最后一定是原先的子集,否则那个多出来的至少会表示出【其本身】
用一个无限背包表示某个数是否被表示,如果能显然不要

一开始想着值域参考【小凯的疑惑】的话,不互质更小,上限ab,但开不下
想了想,只需要知道当前这个数而已(此时上面的性质尚未透彻,所以有怀疑),
所以只要每次跑值域大小即可

彻底检查完所有方面,看了几次注意事项后,还剩1h,挂机玩3d软件去了……

上限:100+100+100
感觉明天应该会很难【回忆起gdoi】

jcp的t2,没想出值域那个性质,其他人普遍没问题

下午看到师兄们去看毒液,和lxj突发奇想用手机看【在一年前就躺在u盘】的秒五
晚上去看看我在广州的新家(组的),老爸真爱吹啊,什么广州CBD区……
不过感觉老爸老妈还是有点东西的,以他们的性格不会随便花钱,虽然我不像我弟那样喜欢关心家底
吸取经验,跑步跑到【真·上气不接下气】
顺利早早睡着,打算以后比赛都要这样(scy不可多得的又一句有用的建议)

day2

t1,一开始想线性做法,5min后不会,反正放平方,懒得想了,也拍不了,走了走了
此时40min,因为代码有点小bug

t2,这好像很性质?很爆搜?但暂时没思路,走了

t3, n方暴力显然
100%不会,发现很多特殊点,一般都是提示(noip就是良心)
如果是一条链,类型一只要正反跑一次,中间合并就好,类型二同理,但并不会类型3
深度?哦先dp好,每次重新跑一次祖先的链,那么复杂度就是和深度相关的
树上?感觉应该和【正反跑】类似,但不太会
此时已经10点,设限20min
因为用贪心来决策,dp只计数,计算出每个节点的 $g(x)=min f[x][0/1]$ 后,可以二次扫描
记录 $oth(x,0/1)$ 表示当前的选择,然后除了x子树以外的答案(子树间互不影响)
那么询问1就搞定了,询问2的话分类讨论,预处理allg和allf1表示无限制下,儿子们的两种和即可

如果我会处理一条链上,固定前后,的答案的话,就可以树剖+虚树,然后套上询问2了(感觉这才是询问2意义所在啊)
ps:不过赛后问了问栋老师,好像不是这样做的

回去看t2,以为状压就好了,瞎jb找了个转移的限制条件,就瞎jb写了,还过了2 2的点
然而其实根本不会转移……又不是加法原理或者乘法原理……毫无去重思路

剩下时间不算多,赶快写t3,最后暴力过了大样例,然后和暴力拍了询问1
匆忙检查各种文件,和d1形成鲜明对比,最后t2特判了样例……好歹有10分

上限:100+10+84
怎么高一只有我拿了t3的40,目前只知道gay队(TYB)和我差不多
但所有人第二题都顺利找规律拿了50pt……感觉从结果上血亏,不过那个耐心杠特殊数据的体验还是很好的

看了看知乎,t3好像是动态dp?
不过似乎学过的tyb也没做出来
羊好像是我校唯一做出t2的
栋好像是我校唯一会做t3的,不过没写完
感觉可能是历年正解难度最大的一次,不过暴力分太足了可能线不会差太多

上限494,随便fail一道题就很悬了(特别是我这种中考无限粗心选手)
日常模拟赛上限得分和实际得法相差巨大选手
再次上演,比赛完当天晚上一个人在竞赛室写游记系列
准备去上文化课了……希望能进wc,不然想想【别人都在训练我在文化课】就很难受

成绩

先立个flag,进了就氪个迎新礼包,没进弃游,剩下看天意……

upd 2018.11.15 发代码速度好评
然后到处去测
学军和牛客478=100+100+100+100+10+68
洛谷441(被卡常,没有参考价值)
然后看了看,应该是d2t3询问2的情况写错了(当时只拍了询问1,没时间,只能肉眼看了好多次,结果还是错)
rose是真的牛逼,d1t3大样例没过,3个oj平均分95
(因为其采用了后面找前面的策略,而这个我记得对拍一下就错,为什么出的数据都卡不掉?我的改改交上去也和他差不多)

upd 2018.11.20 ccf本来说昨天10点,居然咕咕咕了22h……
100+100+95+100+10+68=473
好像又被卡常了……但明明学军都没事啊?
总之就是只有pkuwc了

d2t3 保卫王国 题解

$g(x)=min f[x][0/1]$
注意到dp是计数的,基本没有决策
显然轻重链剖分,然后非常好的性质就是只有一个重儿子
$s0(x)=\sum f(lightson,1)$
$s1(x)=z(x)+\sum g(lightson)$
$f(x,0)=s0(x)+f(hson,1)$
$f(x,1)=s1(x)+min f(hson,0/1)$

考虑用矩阵优化,每个点,开一个大小为2乘2的矩阵,不表示状态,只表示转移
然后询问就是x和y,不允许的状态设inf,重写min运算,如果有-1就表示不能转移
然后定义矩阵运算@, $c_{i,j}=min a_{i,k}+b_{k,j}$
这个运算是满足结合性( $(a@b)@c=a@(b@c)$ )的,证明可以联想floyd

先从x=1的特殊点开始,那么y就向上dp到链
dp状态的表示,是1乘2的矩阵,即f(x,0/1)
每次重链之间,暴力转移就好了
不特殊的话同理,x和y各自跳到lca,然后暴力转移合并成一个状态,然后再跳到根
时间复杂度 $8 \times n log^2 n$
应该能过大部分点

如何更快?
因为儿子是多个的,而父亲只有一个,应该从儿子角度考虑(这也是树上问题重要思想)
设 $fs(x,t,0/1,0/1)$ 表示【x的状态,x的第 $2^t$ 个父亲的状态确定】时,祖先子树内,除了x子树的答案外都合法,最小代价
注意到前面的做法,答案是 $f(1,0/1)$ ,因为那是总代价
但现在,为了更好地动态回答答案,必须把答案拆开,所以fs是只保证上述区域合法时候的答案
虽然稍微有点非常规,但显然只是本题计数dp的另一种形式罢了

想通上述内容后,预处理转移显然
回答询问时,中间的祖先的状态,因为只和上一个有关,做一个简单的dp即可

最后就是,感觉码量和实现思维量无论哪种做法都很耗时,至少1h
考场上就算会,除非很早ak,否则拿84足够了

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
//Zory-2018
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
#ifdef DEBUG
const int LOCAL=1;
#else
const int LOCAL=0;
#endif
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int qread()
{
int ans=0,f=1;char c=getchar();
while(c<'0' or c>'9') {if(c=='-') f=-1;;c=getchar();}
while(c>='0' and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
const int MAX_N=110000;
int n;
int z[MAX_N];//点权
int hou[MAX_N],dep[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
ll add(ll a,ll b)
{
if(a<0 or b<0) return -1;
return a+b;
}
ll mymin(ll a,ll b) {return a<b?a:b;}
ll min(ll a,ll b)
{
if(a<0) return b;
if(b<0) return a;
return mymin(a,b);
}
ll dec(ll a,ll b)
{
if(a<0 or b<0) return -1;
return a-b;
}
int bin[30];
ll ff[MAX_N][30];//father
ll fs[MAX_N][30][2][2];
struct Predp
{
ll f[MAX_N][2];//dp
Predp(){memset(f,0,sizeof f);}
void dp(int x,int fa)
{
ff[x][0]=fa;
f[x][0]=0;f[x][1]=z[x];
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dep[y]=dep[x]+1;dp(y,x);
f[x][0]=add(f[x][0],f[y][1]);
f[x][1]=add(f[x][1],min(f[y][0],f[y][1]));
}
}
void preST()
{
memset(fs,-1,sizeof fs);
f[0][0]=f[1][1],f[0][1]=min(f[1][0],f[1][1]);
for(int x=1;x<=n;x++)
{
int fa=ff[x][0];
fs[x][0][1][0]=dec(f[fa][0],f[x][1]);
fs[x][0][0][1]=fs[x][0][1][1]=dec(f[fa][1],min(f[x][1],f[x][0]));
}
for(int t=1;t<=20;t++)
{
for(int x=1;x<=n;x++)
{
ff[x][t]=ff[ff[x][t-1]][t-1];
int mid=ff[x][t-1];
fs[x][t][0][0]=min( add(fs[x][t-1][0][0],fs[mid][t-1][0][0]),add(fs[x][t-1][0][1],fs[mid][t-1][1][0]) );
fs[x][t][0][1]=min( add(fs[x][t-1][0][0],fs[mid][t-1][0][1]),add(fs[x][t-1][0][1],fs[mid][t-1][1][1]) );
fs[x][t][1][0]=min( add(fs[x][t-1][1][0],fs[mid][t-1][0][0]),add(fs[x][t-1][1][1],fs[mid][t-1][1][0]) );
fs[x][t][1][1]=min( add(fs[x][t-1][1][0],fs[mid][t-1][0][1]),add(fs[x][t-1][1][1],fs[mid][t-1][1][1]) );
}
}
}
}predp;
ll ans[2][8000][2];//简单dp, ans[x或者y][序数][以此状态结尾]=最小代价
int tmp[2];
void jump(int typ,int &x,int t)
{
int now=++tmp[typ];
ans[typ][now][0]=ans[typ][now][1]=-1;
for(int a=0;a<=1;a++)//x
for(int b=0;b<=1;b++)//anc
ans[typ][now][b]=min(ans[typ][now][b], add(ans[typ][now-1][a],fs[x][t][a][b]) );
x=ff[x][t];
}
ll solve(int x,int a,int y,int b)//点x,y
{
if(dep[x]<dep[y]) swap(x,y),swap(a,b);
tmp[0]=0;tmp[1]=0;
ans[0][0][a]=predp.f[x][a];ans[0][0][a^1]=-1;
ans[1][0][b]=predp.f[y][b];ans[1][0][b^1]=-1;
for(int t=20;t>=0;t--) if(bin[t]<=dep[x]-dep[y]) jump(0,x,t);
if(x==y) ans[0][tmp[0]][b^1]=-1;
else
{
for(int t=20;t>=0;t--) if(ff[x][t]!=ff[y][t]) jump(0,x,t),jump(1,y,t);
int lca=ff[x][0];
int now=++tmp[0];
ans[0][now][0]=ans[0][now][1]=-1;
for(int c=0;c<=1;c++)
for(int t1=0;t1<=1;t1++)
for(int t2=0;t2<=1;t2++)
{
if(c==0 and (t1==0 or t2==0)) continue;//debug 这种情况要特判
ll t=add(ans[0][now-1][t1],fs[x][0][t1][c]);
t=add(t,ans[1][tmp[1]][t2]);
if(c==0) t=dec(t,predp.f[y][1]);
else t=dec(t,min(predp.f[y][0],predp.f[y][1]));
ans[0][now][c]=min(ans[0][now][c],t);
}
x=lca;
}
//x为当前lca,开始向上
for(int t=20;t>=0;t--) if(ff[x][t]>0) jump(0,x,t);
return min(ans[0][tmp[0]][0],ans[0][tmp[0]][1]);
}
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
int m;char op[10];scanf("%d%d%s",&n,&m,op);
for(int i=1;i<=n;i++) scanf("%d",&z[i]);
for(int i=1;i<=n-1;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
predp.dp(1,0);
predp.preST();
while(m--)
{
int x,a,y,b;scanf("%d%d%d%d",&x,&a,&y,&b);
printf("%lld\n",solve(x,a,y,b));
}
}
};
int main()
{
mine::main();
}

d2t2 填数游戏 题解

某些性质:
$若w(p1)>w(p2),则s(p1) \leq s(p2)$
显然既然字符串的比较从前往后,所有长度相同的路径间都要满足条件
那么显然每个对角线都应该满足从右上往左下【一段0然后一段1】
当(i,j+1)和(i+1,j)相同时,以(i+1,j+1)为左上角的矩阵,对角线上必须相同
否则从(i,j)走出来,然后路径字典序不同,合并后可能交换走

真题解

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

哪怕是一杯奶茶,也将鼓励我继续创作!
0%