前言
没想到我竟然能有幸成为参加noip2020中7k+人的一员话说不是有分就能去的吗今天考完了，特地来写个小结
赛前准备
虽然在考完csp后并不认为我能参加noip，但我还是去机房参加训练（毕竟万一进了不是很亏？）在得知noip有分就行的消息后，我更加努力地准备腐
于是在洛谷上做了一些题。为什么是做了一些题呢？因为我太菜了，做一道题都要很久QAQ。到了比赛前没有奥赛课的时候，我看那些高三大佬都翘课来准备，于是我周三周四的晚修请假来机房训练（还不敢翘课）。在这两个晚上，我着重搞了搞之前鸽了很久都快忘了的算法，包括但不限于线段树，树链剖分，并查集，最小生成树，最短路，倍增LCA（主要是我也忘了我搞了啥）
这里有一点经验，就是在学算法的时候不要看别人的代码，自己按照思路写印象会更深刻，捡起来也会更快。还有，写板子但时候一定要打上完备的注释（我基本一行一个），这样每次只要看看注释就知道自己当时在想什么了。最好还能有自己的blog，当然用markdown渲染也行。
最令人惊讶的是有一位大佬竟然在进场的时候前提到了gcd！然后我才发现我在准备的时候忘记搞gcd了！这波要是他不提一下我t1就凉了，妙啊！说的好像t1没凉一样
来自大佬的gcd超短模板
1
2
3
4
|
ll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
}
|
一些坑点
- 判断换行符的时候要判三个：‘\n’‘\r’‘\n\r’ (我就是因为这个洛谷上一题爆零了)
- printf("%s",“str”)会re(上面那位大佬就是因为这个noip一题爆零了,申诉还不让过,说是编译器bug人人平等???)
t1 water
题目传送门
上来一眼看到还以为是网络流！真是骇死我了。。。。。。
然后瞎写了一阵，把样例打进去，咦？怎么输入还没完就输出答案了？才发现还有中间节点QAQ
于是删掉重来，一开始就想到了bfs，但是STL的queue不会用，主要是不知道怎么取出队头。。。。。。那就手写吧！于是手写了top，empty，push和pop。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
int que[1000010];
int front=0;int tail=0;
int top()
{
return que[front];
}
void pop()
{
if(front<tail) front++;
}
void push(int a)
{
que[tail++]=a;
}
bool empty()
{
return front==tail;
}
|
然后又写了个分数的结构体，用构造函数初始化分母为1。由于之前重载运算符写吐了，这次直接就写了两个函数，一个搞加法，一个搞除法。
然而一输样例，发现竟然输出了负数！于是把int 改了ll，问题依旧。后来把通分时算lcm先乘后除就好了。
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
|
struct fen
{
ll up;
ll down;
fen()
{
down=1;
}
};
fen add(fen &a,fen b)
{
ll g=gcd(a.down,b.down);
ll lcm=a.down/g*b.down;
a.up*=lcm/a.down;
b.up*=lcm/b.down;
a.up+=b.up;
a.down=lcm;
g=gcd(a.up,a.down);
a.up/=g;
a.down/=g;
return a;
}
void chu(fen &a,int b)
{
a.down*=b;
ll g =gcd(a.up,a.down);
a.up/=g;
a.down/=g;
}
|
这里要注意一点，这里不只是bfs就行了的，节点要先把水都排进来最后才能排出去，也就是说当一个节点的流入全部算完后才能入队去算流出。这不就是拓扑序嘛。。。。。。emmmm，调的我有亿点久QAQ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void bfs()
{
while(!empty())
{
int now=top();
pop();
int h=head[now];
fen water;
water.up=out[now].up;
water.down=out[now].down;
chu(water,tot[now]);
while(h)
{
--intot[E[h].to];
add(out[E[h].to],water);
if(!intot[E[h].to]) push(E[h].to);
h=E[h].next;
}
}
}
|
然而！数据范围是100000而我看成了1000。。。。。。又是一个100变60的伤心故事。。。。。。
ps:猥琐的ccf的猥琐数据的最后一个点爆了unsigned long long!我不觉得有哪个人会在考场上写高精度QAQ
完整代码:
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
|
#include<cstdio>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
return b? gcd(b,a%b):a;
}
struct fen
{
ll up;
ll down;
fen()
{
down=1;
}
};
fen add(fen &a,fen b)
{
ll g=gcd(a.down,b.down);
ll lcm=a.down/g*b.down;
a.up*=lcm/a.down;
b.up*=lcm/b.down;
a.up+=b.up;
a.down=lcm;
g=gcd(a.up,a.down);
a.up/=g;
a.down/=g;
return a;
}
ll rd()
{
ll num=0;bool f=false;char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=true;
c=getchar();
}
while(c>='0'&&c<='9')
{
num=(num<<1)+(num<<3)+(c^'0');
c=getchar();
}
if(f) return -num;
else return num;
}
fen out[100010];
ll tot[100010];
struct edge
{
int to;
int next;
}E[101000];
int head[101000];int cnt=0;
void add_edge(int a,int b)
{
E[++cnt].to=b;
E[cnt].next=head[a];
head[a]=cnt;
}
void chu(fen &a,int b)
{
a.down*=b;
ll g =gcd(a.up,a.down);
a.up/=g;
a.down/=g;
}
int que[1000010];
int front=0;int tail=0;
int top()
{
return que[front];
}
void pop()
{
if(front<tail) front++;
}
void push(int a)
{
que[tail++]=a;
}
bool empty()
{
return front==tail;
}
int intot[100010];
void bfs()
{
while(!empty())
{
int now=top();
pop();
int h=head[now];
fen water;
water.up=out[now].up;
water.down=out[now].down;
chu(water,tot[now]);
while(h)
{
--intot[E[h].to];
add(out[E[h].to],water);
if(!intot[E[h].to]) push(E[h].to);
h=E[h].next;
}
}
}
int final[100010];
int Ftot=0;
signed main()
{
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
//int n=rd(),m=rd();
int n,m;
scanf("%d",&n);
scanf("%d",&m);
for(int i=1;i<=n;i++)
{
//tot[i]=rd();
scanf("%lld",&tot[i]);
if(!tot[i]) final[++Ftot]=i;
for(int j=0;j<tot[i];j++)
{
int to;
scanf("%d",&to);
add_edge(i,to);
++intot[to];
}
}
for(int i=1;i<=m;i++)
{
out[i].up=1;
push(i);
}
bfs();
for(int i=1;i<=Ftot;i++)
{
printf("%lld %lld\n",out[final[i]].up,out[final[i]].down);
}
fclose(stdin);
fclose(stdout);
return 0;
}
|
t2 string
题目传送门
这种题一看就不会。我估摸着应该是dp，但是这和我不会有什么关系呢？
于是随便写了点东西没思路就走了，最后用半个小时写了只有1个字母的情况。但是复杂度有亿点大。嗯，好问题。。。。。。 关键是这种情况都没写对QAQ
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
|
#include<cstdio>
using namespace std;
char s[100010000];
int rdstr()
{
char c=getchar();
while(c<'a'||c>'z') c=getchar();
int len=0;
while(c<='z'&&c>='a')
{
s[len++]=c;
c=getchar();
}
return len;
}
int main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
int T;
scanf("%d",&T);
while(T--)
{
int ans=0;
int len=rdstr();
for(int i=1;i<len-1;i++)
{
int left=len-i;
for(int j=1;j<=(left>>1);j++)
{
if(left%j) continue;
int tot=left/j;
for(int k=1;k<tot;k++)
{
if(k%2>i%2) continue;
ans++;
}
}
}
printf("%d\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
|
t3 ball
难得noip竟然考spj！spj都来了，交互题还会远吗？
看到这玩意，第一反应就是不会做。不会做咋办，那就来打个暴力吧。一开始想了一大堆方案，比如从上往下找同色珠子集中到一根柱子上之类的，但都要么不可行，主要是要么不会写。到最后，想到要是能交换两根柱子上的任意两个珠子就好了。我盲猜用一根空的柱子是可以的，于是开始研究，最后还真给研究出来了！
首先先确定两颗珠子的深度大小关系,防止下面操作的时候爆柱子
1
2
3
4
5
6
7
8
9
|
if(i>j) //i<j
{
int c=b;
b=a;
a=c;
c=j;
j=i;
i=c;
}
|
然后把深度大的那一串(a)连带着要移动的那一颗移到空柱子上
1
2
3
4
5
6
7
8
|
for(int k=tot[a];k>=i;k--)//a:i~top to empty
{
//printf("%d %d\n",a,empty);
mem(a,empty);
tot[a]--;
stick[empty][++tot[empty]]=stick[a][k];
++atot;
}
|
然后把深度小的那一串(b)连带着要移动的那一颗移到刚刚移走一串的那根柱子(a)上.由于a上移走的那一串要比这一串多,所以不会爆出柱子
1
2
3
4
5
6
7
8
|
for(int k=tot[b];k>=j;k--)//b:j~top to a
{
//printf("%d %d\n",b,a);
mem(b,a);
tot[b]--;
stick[a][++tot[a]]=stick[b][k];
++btot;
}
|
然后我们就可以把原本属于a的那一颗移到b上.柱子类似栈,移动完是倒序的,所以刚刚要交换的两颗珠子现在都到了最上面
1
2
3
4
|
//printf("%d %d\n",empty,b);//empty: top to b
mem(empty,b);
stick[b][++tot[b]]=stick[empty][tot[empty]--];
--btot;
|
然后就要把刚刚从b上移走的那一串还回来,当然,要移到a上的那一颗先放到empty上.由于empty刚刚移走了一颗,这样做仍然不会爆柱子
1
2
3
4
5
6
7
8
9
|
//printf("%d %d\n",a,empty);//a:top to empty
mem(a,empty);
stick[empty][++tot[empty]]=stick[a][tot[a]--];
for(int k=0;k<btot;k++)//a:j~top to b
{
//printf("%d %d\n",a,b);
mem(a,b);
stick[b][++tot[b]]=stick[a][tot[a]--];
}
|
这样做完,a上要移动到的那个位置就暴露出来了,把empty上的东西移动回来就可以了
1
2
3
4
5
6
|
for(int k=tot[empty];k>0;k--)//empty to a
{
//printf("%d %d\n",empty,a);
mem(empty,a);
stick[a][++tot[a]]=stick[empty][tot[empty]--];
}
|
然后主程序就简单了,不妨认为一根柱子最下面的那一颗是这跟柱子的颜色(反正题目也没规定),前面的柱子都移动好了,从上往下一旦遇到不一样颜色的珠子,就在后面的柱子上找一个颜色一样的交换一下就行了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
for(int i=1;i<n;i++)
{
int k=i+1;
int l=m;
for(int j=2;j<=m;j++)
{
if(stick[i][j]==stick[i][1]) continue;
for(;k<=n;k++)
{
bool flag =false;
if(!l) l=m;
for(;l>0;l--)
{
if(stick[k][l]==stick[i][1])
{
change(i,j,k,l);
flag=true;
break;
}
}
if(flag) break;
}
}
}
|
但是由于复杂度太大，经过了不懈随意地卡常，大样例还是跑了1.4s，不过还好答案是对的,最后骗到了40分。
完整代码:
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
|
#include<cstdio>
using namespace std;
int stick[60][410];
int tot[60];
int empty;
int ans1[820010],ans2[820010];
int cnt=0;
void mem(int a,int b)
{
ans1[++cnt]=a;
ans2[cnt]=b;
}
int rd()
{
int num=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
{
num=(num<<1)+(num<<3)+(c^'0');
c=getchar();
}
return num;
}
void change(int a,int i,int b,int j)//change a[i] and b[j]
{
if(i>j) //i<j
{
int c=b;
b=a;
a=c;
c=j;
j=i;
i=c;
}
int atot=0,btot=0;
for(int k=tot[a];k>=i;k--)//a:i~top to empty
{
//printf("%d %d\n",a,empty);
mem(a,empty);
tot[a]--;
stick[empty][++tot[empty]]=stick[a][k];
++atot;
}
for(int k=tot[b];k>=j;k--)//b:j~top to a
{
//printf("%d %d\n",b,a);
mem(b,a);
tot[b]--;
stick[a][++tot[a]]=stick[b][k];
++btot;
}
//printf("%d %d\n",empty,b);//empty: top to b
mem(empty,b);
stick[b][++tot[b]]=stick[empty][tot[empty]--];
--btot;
//printf("%d %d\n",a,empty);//a:top to empty
mem(a,empty);
stick[empty][++tot[empty]]=stick[a][tot[a]--];
for(int k=0;k<btot;k++)//a:j~top to b
{
//printf("%d %d\n",a,b);
mem(a,b);
stick[b][++tot[b]]=stick[a][tot[a]--];
}
for(int k=tot[empty];k>0;k--)//empty to a
{
//printf("%d %d\n",empty,a);
mem(empty,a);
stick[a][++tot[a]]=stick[empty][tot[empty]--];
}
}
int main()
{
freopen("ball.in","r",stdin);
freopen("ball.out","w",stdout);
int n=rd(),m=rd();
//scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
tot[i]=m;
for(int j=1;j<=m;j++)
{
//scanf("%d",&stick[i][j]);
stick[i][j]=rd();
}
}
empty=n+1;
for(int i=1;i<n;i++)
{
int k=i+1;
int l=m;
for(int j=2;j<=m;j++)
{
if(stick[i][j]==stick[i][1]) continue;
for(;k<=n;k++)
{
bool flag =false;
if(!l) l=m;
for(;l>0;l--)
{
if(stick[k][l]==stick[i][1])
{
change(i,j,k,l);
flag=true;
break;
}
}
if(flag) break;
}
}
}
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
{
printf("%d %d\n",ans1[i],ans2[i]);
}
fclose(stdin);
fclose(stdout);
return 0;
}
|
t4 walk
题目传送门
这是人能做的题吗？输-1拿5分就回去调t1去了最后发现骗到了十分
1
2
3
4
5
6
7
8
9
10
|
#include<cstdio>
using namespace std;
int main()
{
freopen("walk.out","w",stdout);
printf("-1");
fclose(stdout);
return 0;
}
|
小结
- 带零食没有用处，因为你根本就没有心思吃
- 比赛前多多交流很重要
- 大胆尝试，不会就打暴力（当然也有可能连暴力都打不出来）
- 心态很重要，部分分还是可以拿一下的
- 眼睛是个好东西QAQ
一些有趣的事情
训练的时候，写完快读突发奇想
众所周知在main函数外面是不能执行函数的，但是把函数的返回值赋给变量竟然还就可以了！
至于怎么结束程序不re,不是可以用exit(0)嘛~
甚至都不需要main函数，有个main数组或是main指针竟然还能顺利通过编译！
感受一下不用main就能执行的a+b(虽然洛谷上会CE)
