初中最后一年OI，不过文化课上倒没掉什么链子，应该说上学期期末和第一次月考成绩还是比较好的，底气足一点。
Day -35
意识到了初赛的重要性，今年两个组报初赛的人都多的不得了，发觉这个比复赛还要凶险，于是开始认真复习初赛知识点。
然而我初赛还是很菜的，一星期里总是在担心。
Day -30
初赛当天。
上午是 S 组，考场在交附，环境挺不错的，但是由于某些众所周知的原因服务器卡了，一开始 $20$ 分钟不能登陆，最后是延时了 $20$ 分钟，现场还不算太混乱。
下午是 J 组，考场在华师大，半小时做完后无聊，在草稿纸上默岳阳楼记，默完一节发现草稿纸要交，就不默了，开始背自己的答案。
今年初赛的难度，实在是非常简单，考完之后 J 和 S 的答案都出来了，自批了一下，J 是 $100$ 分，S 是 $94$ 分，比几次模拟考都要高（平时 S 大概是 $88$ 分上下）…这成绩放在浙江估计也过了。
要说对考卷的分析，主要是完善程序太简单。
J 组的阅读题有一道是 $a,b$ 数组互指，还有一道是普通分治，都是些大水题。J 组的完形题第一道递归水题是复读机就会做，另一道是基数排序模板也特别无聊。
S 组的阅读题一道是问 $s$ 删掉最长多少的子串还有 $t$ 作为子序列，另一道听说是 DSU，但是我不知道，反正题做出来了，就是数路径的方法，都是水题。S 组的完形题有一道图论题，本来以为放这个位置好歹要拓扑排序 + Priority_queue 一类的东西，结果程序居然是个暴力；另外一道就比较搞笑了，中午刷洛谷的时候听人说初赛考状压 DP，我还在考虑我们做的是不是一张卷子，然后发现两套卷子仅顺序不同，那就滑稽了，状压 + DP=状压 DP？总的来说水题为主，难度较低。
总体来说，最大的收获是知道了 cin 不能输入空串。
初赛是没问题了，不过这一天挺忙的，晚上的 ABC 比赛耽误了 $40$ 分钟才发现，最后只做了前五题。
Day -15
这段时间跟着教练一直在做历年真题，但是我太菜了，基本都有一道题不会做，2017 和 2018 有两道不会做的。
感觉 NOIP2018 真的有点难，赛道修建比较考代码能力，然后填数游戏就是个神仙题，到现在我也不能独立证出结论。好在近两年没有什么搜索题和图论题，最讨厌的就是华容道和斗地主这种了。
希望今年多出数论和树论。（树论毒奶中了）
Day -4
期中考完了，文化课可以先扔一边了。
接下来就要做几件事：
熟悉一下 NOI Linux 系统（然而如果不出问题的话我还是选 Windows）；
打一遍所有模板（数据结构，图论，分治，动态规划），高精度和省选不考的除外；
如果来得及就补一下前几次模拟赛的题（估计来不及）；
休息半天，准备 AK 普及，提高 450+。
Linux 下的编辑感觉真没有 Windows 方便，找不到怎么补全括号最烦了。另外某谷上几次比赛都太毒瘤了（省选模拟赛），之前几年的题（大搜索除外）和一套本省同年级神仙 gyr 的题做了一下。
Day -2
两天之内打了很多的板子（ST 表，树状数组，线段树，左偏树。主席树，Kruskal 重构树，SPFA 负环，单调队列，单调栈，三分法，lucas 定理，杜教筛，KMP，Manacher），有不少来不及打了只能看一遍（三种 Tarjan 是最虚的所以看了两遍，扩展 BSGS，各种 Trie）。
正常的题就来不及写了，就写了一些以前做过的数据结构综合题（Peaks 之类的）。
Day 0
考前最后一天，休息，看一下考试的一些细节要求，颓洛谷和 B 站。
Day 1
Day1 进考场先打了个 Tarjan 板子，还没打完就公布密码了。
拿到题先根据别人的经验仔细阅读了第一页，WTF 题面里就有两道是树？
先看 T1，感觉是个大水题，没急着写，先去看了看后面两题。喜闻乐见的是 T2 长得像个数据结构，应该是套路题，T3 是个非套路题，不过我当时想着应该有足够时间做出来吧。
先去写了下 T1，刚开始觉得是个和异或有关的东西，但是没有一眼推出结论，只好老老实实写递归，没注意到 long long 就看 T2 了。
T2 一开始花了几分钟写出来一个暴力，结果没过样例，发现 idea 错了。然后恍惚了一会，顺眼看到第一题的 (1<<64)，于是顺手开了个 unsigned long long。
发现以前自己出题的时候出过类似 T2 的 idea，所以立刻想了个差不多的算法，只是实现起来繁琐一点，花了一点时间写了个倍增+询问离线+计数数组。最后所有样例都过了，两题基本上稳了，时间过去了一个小时不到一点，开始看 T3。
T3 看到范围是 $2000$ 开心了一会。贪心倒是很容易想：从小到大每个数字尽量到小的点上去，检验是否可以就行了。但是连个 $O(n^3)$ 也口胡不出来，看了一下有 $n\leq 10$ 的 $10$ 分，先写掉了，然后再想正解，又想不出来就写了一个菊花图的部分分。然后时间就差不多了，Day1 就这样在恍惚间过去了。
（结果后来发现菊花图写错了）
以下是题解（T3不会做）：
T1: Code
设 $solve(p,q)$ 表示求第 $q$ 个 $p$ 位格雷码。
- $p=1$，则结果与 $q$ 相等（$q=1$ 则结果为 $1$，$q=0$ 则结果为 $0$）；
- $p>1, q< 2^{p-1}$，则最高位为 $0$，递归 $solve(p-1,q)$；
- $p>1, q\ge 2^{p-1}$，则最高位为 $1$，同时后面要逆过来，可以推得后面的位是 $solve(p-1,2^p-1-q)$。
于是做完了。
代码
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
| #include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MAXN=75;
ull n,k;
int ans[MAXN];
void solve (ull p,ull q) {
if (p==1) {ans[p]=q;return;}
if (q<(1ull<<(p-1))) {
ans[p]=0;
solve(p-1,q);
} else {
ans[p]=1;
solve(p-1,(1ull<<(p-1))+((1ull<<(p-1))-1)-q);
}
return;
}
int main () {
freopen("code.in","r",stdin);
freopen("code.out","w",stdout);
cin >> n >> k;
solve(n,k);
for (int i=n;i>=1;i--) {cout << ans[i];}
cout << endl;
return 0;
}
|
T2: Brackets
记 $d_i$ 表示 $i$ 到根的路径中左括号的个数减右括号的个数，$pr_i$ 表示$i$的祖先中第一个 $d$ 值比 $i$ 小的。$query(i,v)$ 表示查询 $i$ 到根节点中有多少个点 $d$ 值为 $v$。然后 $i$ 这个点的答案设为 $dp(i)$，那么：
表示首先考虑右端点不是 $i$ 的，然后考虑是 $i$ 的，那么 $d_i$ 必为路径上最小的 $dep$（否则不满足前缀的要求），所以要差分掉 $pr_i$ 上面的答案。
计算 $query$ 可以离线，所有询问按 dfn 排序，用桶记录当前 dfs 到的点到根的路径上所有点的 $d$，然后询问就是求桶里一个位置的值了。
代码
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
| #pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=500010;
struct Q {
Q () {ps=v=fr=flg=0;}
Q (int a,int b,int c,int d) {ps=a,v=b,fr=c,flg=d;}
int ps,v,fr,flg;
}q[2*MAXN];
int n,x,eg,tot,cnt,cur,v[MAXN],dep[MAXN],bac[2*MAXN],hd[MAXN],ver[2*MAXN],nx[2*MAXN];
int f[MAXN][22],mn[MAXN][22],dfn[MAXN],pre[MAXN];
ll dp[MAXN],ans;
char c[MAXN];
bool cmp (Q a,Q b) {return dfn[a.ps]<dfn[b.ps];}
void add_edge (int x,int y) {
ver[++eg]=y;
nx[eg]=hd[x];
hd[x]=eg;
return;
}
void dfs1 (int x,int fa) {
dep[x]=dep[fa]+v[x],dfn[x]=++cnt,f[x][0]=fa,mn[x][0]=dep[fa];
for (int i=1;i<=20;i++) {
f[x][i]=f[f[x][i-1]][i-1];
mn[x][i]=min(mn[x][i-1],mn[f[x][i-1]][i-1]);
}
int pos=x;
for (int i=20;i>=0;i--) {
if (mn[pos][i]>=dep[x]) {pos=f[pos][i];}
}
pre[x]=f[pos][0];
q[++tot]=Q(x,dep[x],x,1);
q[++tot]=Q(pre[x],dep[x],x,-1);
for (int i=hd[x];i;i=nx[i]) {
if (ver[i]==fa) {continue;}
dfs1(ver[i],x);
}
return;
}
void dfs2 (int x,int fa) {
while (cur<=tot&&q[cur].ps==x) {
dp[q[cur].fr]+=1ll*q[cur].flg*bac[q[cur].v];
cur++;
}
bac[dep[x]]++;
for (int i=hd[x];i;i=nx[i]) {
if (ver[i]==fa) {continue;}
dfs2(ver[i],x);
}
bac[dep[x]]--;
return;
}
void dfs3 (int x,int fa) {
dp[x]+=dp[fa];
for (int i=hd[x];i;i=nx[i]) {
if (ver[i]==fa) {continue;}
dfs3(ver[i],x);
}
return;
}
int main () {
freopen("brackets.in","r",stdin);
freopen("brackets.out","w",stdout);
scanf("%d",&n);
scanf("%s",c+1);
bac[MAXN-10]=1,dep[0]=MAXN-10;
for (int i=1;i<=n;i++) {v[i]=(c[i]=='('?1:-1);}
for (int i=2;i<=n;i++) {
scanf("%d",&x);
add_edge(i,x),add_edge(x,i);
}
dfs1(1,0);
sort(q+1,q+tot+1,cmp);
cur=1;
while (cur<=tot&&q[cur].ps==0) {cur++;}
dfs2(1,0);
dfs3(1,0);
for (int i=1;i<=n;i++) {ans^=(1ll*i*dp[i]);}
printf("%lld\n",ans);
return 0;
}
|
S-Day1 期望得分：$100+100+35=235.$
下午考 PJ，得到密码前先打了个 Dijkstra 板子，后来手残删掉了（如果不删还可以省点时间）。
看了 T1 直接花了一分半钟切掉了，然后看 T2，结果一点思路都没有：PJ 的 T2 也能这么难吗？然后又看了 T3 和 T4，发现 T3 好像很可做，但还是先看了 T2。
盯着 T2 看了两分钟突然意识到可以枚举所有券，然后就做完了。
然后 T3 几乎就立刻想出来了，每天独立做完全背包，贪心一下发现肯定是对的。
做完 T3 只过了大概 $20$ 分钟，还有三个小时想 T4，看了两分钟以后意识到了奇偶性的问题，其实就是要求长度分别为奇数和偶数的最短路了，接下来就很精彩了。
现场脑子抽掉了，没想到分层图/直接 BFS 等简单方法，联想到了“图论”和“奇偶性”这两个东西以后在大脑里就搜索到了一道叫做校园旅行的题（HNOI 2019，黑题），依稀记得那道题是根据奇环缩边，于是这道题也狂想奇环这方面的事。
神奇的是我真想出来了，推了大概 $10$ 分钟的结论发现：虽然奇环很多，但是只要建最短路树后只要枚举一条非树边的奇环即可，然后奇环数量就少了。
然后接着想怎么推一个点经过非树边到 $1$ 的最短路，第一反应是在最短路树上 DP，于是写了一下，发现大样例里有一行是错的，于是自己 Hack 了一下发现确实是错的——经过奇环的时候不一定走树边，所以实际上求完奇环后只要求所有端点的单源最短路，这样的话连到超级源点再跑带权的 dijkstra 就可以了（考试前试机打的板子删了只好重写），然后就过了大样例。
最后 1h，很无聊。
以下是题解：
T1: Number
利用 STL bitset 的 count 功能。
水题，可以用 scanf + %s 读入。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=12;
int n,ans;
char c[MAXN];
int main () {
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
scanf("%s",c+1);
int n=strlen(c+1);
for (int i=1;i<=n;i++) {
if (c[i]=='1') {ans++;}
}
printf("%d\n",ans);
return 0;
}
|
T2: Transfer
利用树套树减小常数，增大时间复杂度。
对于每一个 $1$，暴力枚举前面 $45$ 个操作，寻找最早的满足要求的花费掉。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,f[MAXN],v[MAXN],t[MAXN],vis[MAXN],ans;
int main () {
freopen("transfer.in","r",stdin);
freopen("transfer.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d%d%d",&f[i],&v[i],&t[i]);
if (f[i]==0) {ans+=v[i];}
else {
int flag=0;
for (int j=max(1,i-46);j<=i-1;j++) {
if (f[j]==0&&!vis[j]&&v[j]>=v[i]&&t[i]-t[j]<=45) {
vis[j]=1;
flag=1;
break;
}
}
if (!flag) {ans+=v[i];}
}
}
printf("%d\n",ans);
return 0;
}
|
T3: Souvenir
考虑第一天买第三天卖相当于是第二天先卖了，然后同一天又买进来，第三题再卖出去。也就是说，存在一种最优策略，今天买的东西一定明天卖。
所以每一天就独立了，对于第 $i$ 天的第 $j$ 件商品，可以花费 $p_{i,j}$ 的价格赚到 $p_{i+1,j}-p_{i,j}$ 的差价，每个商品都可以买无限个，再加上金币数量始终不超过 $10^4$，每天都完全背包即可。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=10010,MAXM=110;
int t,n,m,dp[MAXN],pri[MAXM][MAXM],wl[MAXM],vl[MAXM];
int main () {
freopen("souvenir.in","r",stdin);
freopen("souvenir.out","w",stdout);
scanf("%d%d%d",&t,&n,&m);
for (int i=1;i<=t;i++) {
for (int j=1;j<=n;j++) {
scanf("%d",&pri[i][j]);
}
if (i>=2) {
memset(dp,0,sizeof(dp));
for (int j=1;j<=n;j++) {
wl[j]=pri[i-1][j],vl[j]=pri[i][j]-pri[i-1][j];
for (int k=wl[j];k<=m;k++) {
dp[k]=max(dp[k],dp[k-wl[j]]+vl[j]);
}
}
int tmp=0;
for (int j=1;j<=m;j++) {tmp=max(tmp,dp[j]+m);}
m=tmp;
}
}
printf("%d\n",m);
return 0;
}
|
T4: Work
好像跟网上其他人的解法很不一样呢…
题目其实是要求，有没有一种从 $1$ 到 $u$ 的路径，恰好经过 $L$ 条边。
考虑到每条边可以重复经过，所以如果存在 $a$ 条边的路径，那么 $a+2k (k\in N)$ 的路径也存在。于是首先可以确定，如果 $1$ 到 $i$ 的最短路记为 $dis_i$，则如果 $dis_u\ge L$ 且 $dis_u\equiv L\mod 2$，那么答案是肯定的。
接下来考虑 $dis_u\ne L\mod 2$ 的情况，也就是到 $1$ 的路径中改变了一次奇偶性的情况。也就是路径中的某一段有两种奇偶性不同的通过方法，那么将两条路径拼起来就得到了一个奇环，所以如果这种情况可行，必然经过了最短路以外的一个奇环。
然而奇环本身不容易统计，所以考虑换一个角度。先可以建出 $1$ 为根的最短路树，那么树上当然没有环，奇环只能在非树边中产生，而且我们有如下结论：
必然可以只通过只有一条非树边的奇环，且只需要通过这样的一条奇环达到改变奇偶性的最短路。
结论容易用反证法证明（考场上看出来了也就懒得证），如果只有一个奇环是经过两个非树边的，那么这两个非树边分别与其他树边构成的环中必然有一个奇环。
于是，只要枚举经过哪个奇环即可，而通过奇环其实就是通过奇环中的那个非树边（不一定要绕圈），所以我们可以从任一个点出发必经过一条指定边的最短路。
如果奇环中非树边为 $(u,v)$，那么 $u$ 通过这条边的最短路显然是 $dis_v+1$，于是其他点如果要从 $u$ 到达这条边，最短路也就是 $dis(x,u)+dis_v+1$ 了，有很多这样的 $u$，不能分别跑最短路，所以建一个超级源点，把所有非树边的端点向超源连权值为上面那个 $dis_v+1$ 的边，然后从超源跑最短路即可。
好像很烦的样子…不过程序好写，就是两遍最短路。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n,m,qu,eg,eg2,x,y,hd2[MAXN],ver2[2*MAXN],nx2[2*MAXN],dis[MAXN],vis[MAXN];
int hd[MAXN],ver[4*MAXN],nx[4*MAXN],edge[4*MAXN],dis2[MAXN],vis2[MAXN];
priority_queue < pair<int,int> > q;
priority_queue < pair<int,int> > q2;
void add_edge (int x,int y,int z) {
ver[++eg]=y;
nx[eg]=hd[x],edge[eg]=z;
hd[x]=eg;
return;
}
void add_edge2 (int x,int y) {
ver2[++eg2]=y;
nx2[eg2]=hd2[x];
hd2[x]=eg2;
return;
}
int main () {
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
memset(dis,0x3f,sizeof(dis));
memset(dis2,0x3f,sizeof(dis2));
scanf("%d%d%d",&n,&m,&qu);
for (int i=1;i<=m;i++) {
scanf("%d%d",&x,&y);
add_edge2(x,y),add_edge2(y,x);
}
q.push(make_pair(0,1));
dis[1]=0;
while (!q.empty()) {
pair <int,int> a=q.top();
q.pop();
if (vis[a.second]) {continue;}
vis[a.second]=1;
for (int i=hd2[a.second];i;i=nx2[i]) {
if (dis[ver2[i]]>dis[a.second]+1) {
dis[ver2[i]]=dis[a.second]+1;
q.push(make_pair(-dis[ver2[i]],ver2[i]));
}
}
}
for (int i=1;i<=n;i++) {
for (int j=hd2[i];j;j=nx2[j]) {
add_edge(i,ver2[j],1);
if ((dis[i]&1)==(dis[ver2[j]]&1)) {
add_edge(i,n+1,dis[ver2[j]]+1);
add_edge(n+1,i,dis[ver2[j]]+1);
}
}
}
q2.push(make_pair(0,n+1));
dis2[n+1]=0;
while (!q2.empty()) {
pair <int,int> a=q2.top();
q2.pop();
if (vis2[a.second]) {continue;}
vis2[a.second]=1;
for (int i=hd[a.second];i;i=nx[i]) {
if (dis2[ver[i]]>dis2[a.second]+edge[i]) {
dis2[ver[i]]=dis2[a.second]+edge[i];
q2.push(make_pair(-dis2[ver[i]],ver[i]));
}
}
}
for (int i=1;i<=qu;i++) {
scanf("%d%d",&x,&y);
if (dis[x]%2==y%2) {
if (dis[x]<=y) {printf("Yes\n");}
else {printf("No\n");}
} else {
if (dis2[x]<=y) {printf("Yes\n");}
else {printf("No\n");}
}
}
return 0;
}
|
J 期望得分：$100+100+100+100=400.$
Day 2
解压以后先看 T1：呀今年 T1 怎么不是水题，还是 Yazid 的题，那肯定做不出来的呀。
然后看 T2：早上刚看的 1D/1D 的动态规划怎么套不上去？
再看 T3：哈哈怎么感觉是个简单题。
然后花了一个半小时做了 T3，回去水了前两道题的部分分。由于 T1 有 Yazid，也就没想正解。
不要想着 Day 2 翻盘，因为你根本不知道盘是什么。
只做出来 T3，但好像写错了，就不写题解了。
S-Day2 期望得分：$64+64+100=228$。
选手程序跟几个网站数据出来了。
洛谷：$J 400 / S 423$
OI题库：$J 400 / S 363$
牛客：$J 400 / S 378$
遗憾：一心以为 D2T3 满分结果连几个部分分也懒得去打（保险没了），而 D2T1 其实是个大水题却没做满分。
今年就这么结束了…三个网站前五题总分一模一样（$338$），第六题就很秀了，各个地方得分都不一样，最坏打算就是只拿十几分了…
S 真实成绩：$100+100+10+64+64+25=363$
J 真实成绩：$100+100+100+100=400$
初中 OI 生涯大概就这样了吧，两个月后也许能混个 WC，省队希望不大了（CSP 提前丢了很多分，输在了起跑线上）。