NOIP2018退役赛。脑中想象过无数次的长篇退役文也没时间写了，就简单记录一下。
Day0
刚考完期中考，周五还要上课，十分疲惫。还是背了一天板子，虽然这一年又学了很多，准备却很不充分。重点看了些基础算法。
Day1
一大早就到了华二，7:30左右，天气晴好。发现数论很虚在车上狂看数论。
考场在三楼机房二，同考场还有朱先生韩先生和flx佬。位子在最后一排靠墙，很安静干扰少。按惯例考前30分钟应当是能试机的，却被监考很强硬的制止了，让我怀疑是不是被针对了（
解压密码也不好好报，解了好几次，绝了（
开考
T1
真的没见过，考后才知道是原题……一开始看到区间就方了还以为是区间dp，毕竟就在前一次模拟赛就做过一个题目描述很接近的石子涂颜色区间dp。后来简单推了一下没找到贪心的反例，就直接模拟每次找最长区间贪心了。还调了优先队列优化。
事后和flx对了下说是分治才发现我手动用队列模拟了递归过程……
期望得分：80到100
洛谷自测：100
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<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=100005;
struct node{
int st,ed,l,mi;
node(int a,int b,int c,int d){
st=a;
ed=b;
l=c;
mi=d;
}
bool operator<(const node s)const{
return s.l>l;
}
};
priority_queue<node> q;
int a[MAXN];
int main(){
int n;
scanf("%d",&n);
int mi=MAXN;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]<mi)mi=a[i];
}
node now(0,0,0,0);
q.push(node(1,n,n,mi));
int ans=0,tst;
while(!q.empty()){
now=q.top();
q.pop();
if(now.l==0)break;
ans+=now.mi;
mi=MAXN;
tst=now.st;
for(int i=now.st;i<=now.ed;i++){
a[i]-=now.mi;
if(a[i]!=0&&mi>a[i])mi=a[i];
if(a[i]==0){
q.push(node(tst,i-1,i-tst,mi));
tst=i+1;
mi=MAXN;
}
}
q.push(node(tst,now.ed,now.ed-tst+1,mi));
}
printf("%d",ans);
return 0;
}
|
T2
读题读到一半就慌了：这不是去年T1的升级版，大凯的疑惑嘛……
大概只要参加过去年比赛的思路都会被这么带偏罢（
开始我还照这个思路想着（带着对数论的恐惧……），各种gcd……突然发现实际是求：如果能用其它面额表示一种，这种就可以删去。而这题就是之前模拟赛的原题了，我清晰地记得ywd说过是个背包（完全背包），然后我对dp有阴影，最后选择了搜索，并加了个记忆化。
但我根本不能确定这记忆化的正确性，这导致了我做完后化了半个小时对拍（对拍程序还写错了、哭）最终赌了一把交了记忆化了版本。
期望得分：100或0（哭了）
洛谷自测：100
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<cstdio>
#include<cstring>
int n;
bool f;
int a[105];
bool vis[105]={0};
bool dp[25005];
void dfs(int v){
if(f||dp[v])return;
for(int i=1;i<=n;i++)
if(!vis[i]&&v>=a[i]){
if(v-a[i]==0){
f=1;
return;
}
else{
dfs(v-a[i]);
dp[v-a[i]]=1;
}
}
}
int main(){
int t;
scanf("%d",&t);
for(int k=1;k<=t;k++){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int ans=n;
for(int i=1;i<=n;i++){
memset(dp,0,sizeof(dp));
f=0;
vis[i]=1;
dfs(a[i]);
vis[i]=0;
if(f)ans--;
}
printf("%d\n",ans);
}
return 0;
}
|
T3
这是D1的败笔了，可能也是缺乏比赛经验罢，面对如此详尽的数据约定竟不知道如何骗分……
一开始想的是算出任意两点的最短路，再从长到短贪。再仔细一看题发现是明显错误的(
于是先暴力了个Floyd（第一次还没打对），骗m==1的情况。
然后就不知道了……连暴力都不会打，又想了个办法记录每条最短路的编号，又是队列又是向量的，反正乱搞一通后删光了。只留了个Floyd……
期望得分：5或10
洛谷自测：10
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
| #include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF=20000000;
int g[1005][1005];
int main(){
int n,m;
scanf("%d%d",&n,&m);
int a,b,w,ma=0;
if(m==1){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=INF;
for(int i=1;i<=n-1;i++){
scanf("%d%d%d",&a,&b,&w);
g[a][b]=w;
g[b][a]=w;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(g[i][j]>g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(ma<g[i][j])ma=g[i][j];
printf("%d",ma);
return 0;
}
return 0;
}
|
Day2
D2就全线爆炸了。最大的问题还是心理素质不过关吧。有几重因素干扰实力发挥就马上受影响了……先是因为进博会调休，D2比完还要上课的，而考场就在比赛的时候上课，机房的铃声又没关，甚至还有播通知的，绝了。题目难度和D1也不是一个层次，其实做到一半就耳赤了。
T1
刚读完题，就蒙了：这不就是个裸的深搜吗？？样例2也没仔细看，直接就打了，深搜还卡了一下……30分钟后，和大样例4一对，我发现事情没那么简单……再看了数据说明有数了：对无环图裸深搜，得60分
那有环怎么办呢？我想的是先找环再在搜的时候“反悔”。然而在得60分后我选择了做后面两题，等我灰头土脸回来后发现连环都不会找了，先打上并查集……然后删掉……再打上tarjan……然后删掉……
最终也没有成功，交了个裸搜。
期望得分：60
洛谷自测：60
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
| #include<cstdio>
bool g[5005][5005]={0};
bool vis[5005]={0},f;
int cnt=0,pa[5005];
int n,m;
void pr(){
for(int i=1;i<=n;i++)
printf("%d ",pa[i]);
}
void dfs(int i){
if(f)return;
for(int j=1;j<=n;j++)
if(g[i][j]&&!vis[j]){
vis[j]=1;
cnt++;
pa[cnt]=j;
if(cnt==n){
pr();
f=1;
return;
}
else dfs(j);
vis[j]=0;
}
}
int main(){
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
g[a][b]=1;
g[b][a]=1;
}
vis[1]=1;
pa[1]=1;
cnt=1;
f=0;
dfs(1);
return 0;
}
|
T2
看完题就崩了，首先题面就不友好，花了些时间理解，看到mod后明白是数学题，心里凉了半截。
数据范围也很迷，小于8的数据似乎在暗示打表（
我就带着打表的觉悟搜起来。可是搜也写不对（心态已经崩了），不管怎样搜出来所有状态都是合法的……
最后手算了<=3的情况（还算错了）
唯一稍微开心些的是在考场上想了个生成01矩阵的方法（然而并没有什么卵用……）：
1
2
3
4
5
6
7
8
9
|
for(int k=0;k<pow(2,n*m);k++){
seed=k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
g[i][j]=seed&1;
seed>>=1;
}
}
|
期望得分：0到20（悲）
洛谷自测：5
1
2
3
4
5
6
7
8
9
10
11
| #include<cstdio>
int main(){
int n,m;
scanf("%d%d",&n,&m);
if(n==1||m==1)printf("0");
else if(n==2&&m==3||n==3&&m==2)printf("54");
else if(n==2&&m==2)printf("12");
else if(n==3&&m==3)printf("112");
else if(n==5&&m==5)printf("7xxx");
return 0;
}
|
T3
心态已经爆炸，看着对骗分这么友好的数据一点都不会骗。
先瞄准了A组数据，一条链的情况。我想这应该是个dp，但是dp实在写不出很清晰的思路，最后糊了一个上去……
期望得分：0（别说了）
洛谷自测：0（别说了）
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
| #include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int dp[2005][2005]={0};
int w[2005];
int fm(int st,int ed){
return min(dp[st][ed],dp[st][ed-1]);
}
int main(){
int n,m;
char s[10];
scanf("%d%d",&n,&m);
scanf("%s",s);
int a,b,x,y;
if(s[0]=='A'){
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n-1;i++)
scanf("%d%d",&a,&b);
for(int i=0;i<=n;i++){
dp[i][i+1]=w[i];
for(int j=i+2;j<=n;j++)
dp[i][j]=min(dp[i][j-1],dp[i][j-2]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&a,&b,&x,&y);
if(abs(a-b)==1&&x==0&&y==0)
printf("-1\n");
else if(x==1&&y==0)
printf("%d",fm(0,a)+fm(a,n));
else if(x==0&&y==1)
printf("%d",fm(0,b)+fm(b,n));
else if(x==0&&y==0)
printf("%d",fm(0,n));
else printf("%d",fm(0,a)+fm(a,b)+fm(b,n));
}
}
else{
for(int i=1;i<=m;i++)
printf("-1\n");
}
return 0;
}
|