csp2020小结

初试

众所周知，参加csp/NOIP系列比赛最不稳的就是初试，有时候准备了一年多结果初试没过，功亏一篑。

这一次赛前对于初试的准备较少，记得考csp2019前我还是把《信息学奥赛一本通——初赛篇》看了一遍的 ~~记得NOIP2018也是这么干的~~ 。u1s1，这本书写的还是很好的，初赛的很多内容都有涵盖到，但是时间复杂度计算这一块没有，需要额外补充。

点击查看csp-s1试题

选择题

全都化成二进制就好比较就行了
送分题
一张图片大小s：$2048\times 1024 \times 32 \div 8 = 8388608 byte$ ,总大小：$s\times 24\times 8\times 60 = 96,636,764,160byte= 90GB$
模拟一下就行了
四个选项都代进去算一下，哪个不重复就是哪个
0-1背包经典的动规，送分题
邻接表建图必须，OIer肯定都会
$12\times 12 = 144$,注意不用除以2
写过的都会
反正我是全列出来一个一个消的
等差数列求和,注意区间就可以了
括号法:$a*(b+c)-d \rightarrow (a*(b+c))-d \rightarrow (a(bc+)*)d- \rightarrow abc+*d-$ 当然画表达式树也行
基本常识，送分题

阅读程序

1. n等于1000不会越界，注意题中是$<$ 而不是$<=$
2. n可以是-1，当然不一定
3. 将i和j互换，$d[i]+d[j]-(d[i] & d[j])$的值不改变，结果当然也不会改变
4. 也是将i和j互换，只要不等于就会执行下方语句，结果当然不改变
5. 化为二进制判断一下~~其实是我懒得写~~
6. 只用管二进制的最后一位就行了，奇数二进制的最后一位是1，偶数是0，按选项推一下就行了~~其实是我懒得写~~
不会，瞎蒙的，好像错了很多QAQ
一看就令人懵逼，我怎么可能会呢，好像蒙错了很多QAQ

完善程序

1. 此处就是因为整数除法有精度问题才用乘法的，后面的语句有提示，变形一下就有了。但是为什么我在比赛的时候没有意识到呢QAQ
2. 1. 看着后面else里的应该知道选啥了吧？
3. 此处依然和（1）一样，为了精度改用乘法
4. 体积比B小，直接全部都要！但为什么我又错了QAQ
这种题，怎么会做呢？我用上下文对称做法，结果又错了一堆QAQ

总结

总的来说，选择题比较容易，大题比较难。但是我错了很多能对的题，可能主要是因为看到会做太兴奋了QAQ

~~而且完善程序不是用对称法就能做对的QAQ~~

复试

前言

先来揭露一下圈钱组织的真面目：

嗯，这转折，绝了。

一些准备

本来以为它要考很多dp，考前特地去练了很多，结果最后还是没有做出来QAQ

由于csp2019考了很多树，我还特意去学了树剖，结果一个都没考QAQ

不过，考前特地看了~~最快的~~快读。这次数据量这么大，总算有用了一次

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


#include<cstdio>
#define ll long long
ll read()
{
	char c=getchar();
	ll num=0;
	while(c>'9'||c<'0')
	{
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
		num=(num<<1)+(num<<3)+(c^'0');
		c=getchar();
	}
	return num;
}

还有，不要用cin！不要用cin！即便加了网传的奇淫技巧：

1
2


ios::sync_with_stdio(0);
cin.tie(0);

也没用！

活生生的教训仍历历在目：

用scanf的：

用cin+上述“优化”的：

~~真是一个令人悲桑的故事啊~~

T1儒略日

这道题一看似曾相识，于是上来先推公式，无果，于是想想其他做法

想了半天想不出来，于是暴力模拟！一天一天的往初始日期累加

写了一个用来计算指定月份天数的函数，也就是判断闰年，然后返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


int DayInMon(int y,int m)
{
	bool r_year=false;
	if(y<0)
	{
		if((-(y+1))%4==0) r_year=true;
	}
	else if(y<1582)
	{
		if(y%4==0) r_year=true;
	}
	else 
	{
		if(y%4==0&&(y%400==0||y%100!=0)) r_year=true; 
	}
	if(m==2) return r_year? 29:28;
	if(m<=7) return m%2==0? 30:31;
	else return m%2==0? 31:30;
}

然后又写了一个日期加一的函数，就是如果天数到头月+1，年份到头年+1。然后特判年份为-1时下一年为1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


void add()
{
	if(day<DayInMon(year,month))
	{
		day++;
	}
	else
	{
		if(month<12)
		{
			month++;
			day=1;
		}
		else
		{
			if(year==-1) year++;
			year++;
			month=1;
			day=1;
		}
	}
}

但是看到数据范围，O(Qr)的复杂度肯定爆啊

于是想着优化

优化1：既然一天一天加慢，那我一个月一个月加不就好了？

然而，由于要考虑的特殊情况太多，像什么闰不闰年，哪天被删了之类的，头疼。。。。。。

打了半天样例都没过，一瞥旁边的那位兄台，人家都开始打T2了！

好家伙，不打了，换！

优化2：一看80%数据范围：$Q=10^5,r_i<=10^7$！想到了啥？离线处理！

何为离线处理？就是一个对于多询问的优化方法，将所有询问由小到大排个序并记录原始顺序（毕竟输出还要按照原来的顺序输出），从头开始，遇到就记录答案，最后按原来的顺序输出。

打完心里美滋滋，想着80分稳了~~分不在多，及格就行~~~

完整代码如下：

~~一个模拟打这么多行我也是醉了~~

  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


#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
	char c=getchar();
	ll num=0;
	while(c>'9'||c<'0')
	{
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
		num=(num<<1)+(num<<3)+(c^'0');
		c=getchar();
	}
	return num;
}
ll year=-4713,month=1,day=1;
int DayInMon(int y,int m)
{
	bool r_year=false;
	if(y<0)
	{
		if((-(y+1))%4==0) r_year=true;
	}
	else if(y<1582)
	{
		if(y%4==0) r_year=true;
	}
	else 
	{
		if(y%4==0&&(y%400==0||y%100!=0)) r_year=true; 
	}
	if(m==2) return r_year? 29:28;
	if(m<=7) return m%2==0? 30:31;
	else return m%2==0? 31:30;
}
void add()
{
	if(day<DayInMon(year,month))
	{
		day++;
	}
	else
	{
		if(month<12)
		{
			month++;
			day=1;
		}
		else
		{
			if(year==-1) year++;
			year++;
			month=1;
			day=1;
		}
	}
}
ll Ayear[100010],Amonth[100010],Aday[100010];
struct que
{
	ll rnk;
	ll date;
}q[100010];
bool cmp(que a,que b)
{
	return a.date<b.date;
}
int main()
{
	freopen("julian.in","r",stdin);
	freopen("julian.out","w",stdout);
	ll T=read();
	ll maxon=0;
	for(ll i=1;i<=T;i++)
	{
		q[i].date=read();
		q[i].rnk=i;
		if(maxon<q[i].date) maxon=q[i].date;
	}
	ll da=0;
	sort(q,q+T,cmp);
	ll cnt=1;
		ll lu=maxon;
		while(lu)
		{
			da++;
			if(year==1582&&month==10&&day==4)
			{
				lu--;
				day=15;
			}
			else 
			{
				add();
				lu--;
			}
		while(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}
		}	
for(int i=1;i<=T;i++)
{
		if(Ayear[i]<0)
		printf("%lld %lld %lld",Aday[i],Amonth[i],-Ayear[i]);
		else printf("%lld %lld %lld",Aday[i],Amonth[i],Ayear[i]);
		if(year<0) printf(" BC");
		putchar('\n');
}
fclose(stdin);
fclose(stdout);
return 0;
}

等到出成绩，我人都傻了，好家伙，爆零！

回来交了洛谷，才发现犯了3个致命的错误

注意第101行：

1
2
3
4
5
6
7


		while(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}

这里我之前写的是：

1
2
3
4
5
6
7


		if(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}

当有询问是重复的时候就会引起错误！

幸好我最后检查的时候把它改过来了。

但是！注意第85行：

1

sort(q,q+T,cmp);

明明应该是下面这个好不好！

1

sort(q,q+T+1,cmp);

这是个遗留问题，因为我之前的输入写的是：

1
2
3
4
5
6


	for(ll i=0;i<T;i++)
	{
		q[i].date=read();
		q[i].rnk=i;
		if(maxon<q[i].date) maxon=q[i].date;
	}

但是我改了读入没改sort！于是。。。。。。爆零快乐QAQ

除此之外，注意第114行：

1

if(year<0) printf(" BC");

乍一看好像没问题，但是！我存年份明明用的是Ayear[i]啊。。。

这输出明显要么全部带BC，要么不带BC，这不爆零谁爆零？

但是，这么明显我为什么没发现呢？看看样例：

11 1 4713 BC
10 4 4713 BC
27 9 4711 BC

14 9 763
15 8 3501
12 7 6239

好家伙，样例里要么都是带BC的，要么都是不带BC的！~~CCF老坑批了。。。~~

还有，注意我写的while循环：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


		while(lu)
		{
			da++;
			if(year==1582&&month==10&&day==4)
			{
				lu--;
				day=15;
			}
			else 
			{
				add();
				lu--;
			}
		while(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}
		}

好家伙，我竟然没有意识到输入会有0！这样若遇到0，啥都不会输出！~~真是快乐~~

80->0 ！

另附修正后的80分代码：~~(什么？你说丑，那是dev太烂了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


#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
	char c=getchar();
	ll num=0;
	while(c>'9'||c<'0')
	{
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
		num=(num<<1)+(num<<3)+(c^'0');
		c=getchar();
	}
	return num;
}
ll year=-4713,month=1,day=1;
int DayInMon(int y,int m)
{
	bool r_year=false;
	if(y<0)
	{
		if((-(y+1))%4==0) r_year=true;
	}
	else if(y<1582)
	{
		if(y%4==0) r_year=true;
	}
	else 
	{
		if(y%4==0&&(y%400==0||y%100!=0)) r_year=true; 
	}
	if(m==2) return r_year? 29:28;
	if(m<=7) return m%2==0? 30:31;
	else return m%2==0? 31:30;
}
void add()
{
	if(day<DayInMon(year,month))
	{
		day++;
	}
	else
	{
		if(month<12)
		{
			month++;
			day=1;
		}
		else
		{
			if(year==-1) year++;
			year++;
			month=1;
			day=1;
		}
	}
}
ll Ayear[100010],Amonth[100010],Aday[100010];
struct que
{
	ll rnk;
	ll date;
}q[100010];
bool cmp(que a,que b)
{
	return a.date<b.date;
}
int main()
{
	freopen("julian.in","r",stdin);
	freopen("julian.out","w",stdout);
	ll T=read();
	ll maxon=0;
	for(ll i=1;i<=T;i++)
	{
		q[i].date=read();
		q[i].rnk=i;
		if(maxon<q[i].date) maxon=q[i].date;
	}
	ll da=0;
	sort(q+1,q+T+1,cmp);
	ll cnt=1;
			while(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}
		ll lu=maxon;
		while(lu)
		{
			da++;
			if(year==1582&&month==10&&day==4)
			{
				lu--;
				day=15;
			}
			else 
			{
				add();
				lu--;
			}
		while(da==q[cnt].date)
		{
			Ayear[q[cnt].rnk]=year;
			Amonth[q[cnt].rnk]=month;
			Aday[q[cnt].rnk]=day;
			cnt++;
		}
		}	
for(int i=1;i<=T;i++)
{
		if(Ayear[i]<0)
		printf("%lld %lld %lld",Aday[i],Amonth[i],-Ayear[i]);
		else printf("%lld %lld %lld",Aday[i],Amonth[i],Ayear[i]);
		if(Ayear[i]<0) printf(" BC");
		putchar('\n');
}
fclose(stdin);
fclose(stdout);
return 0;
}

T2动物园

写完T1，赶紧来写T2（T1就打了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
47
48
49
50
51
52
53
54
55
56


#include<cstdio>
#include<algorithm>
#include<set>
#define ll long long
using namespace std;
ll read()
{
	char c=getchar();
	ll num=0;
	while(c>'9'||c<'0')
	{
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
		num=(num<<1)+(num<<3)+(c^'0');
		c=getchar();
	}
	return num;
}
int A[1000010];
int q[1000010],p[1000010];
ll cnt=0;
set <ll> cannot;
int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	ll n=read(),m=read(),c=read(),k=read();
	for(int i=0;i<n;i++) A[i]=read();
	for(int i=0;i<m;i++)
	{
		p[i]=read();
		q[i]=read();
	}
	for(int i=0;i<m;i++)
	{
		bool flag=false;
		for(int j=0;j<n;j++)
		{
			if(A[j]&(1<<(p[i]))) 
			{
				flag=true;
			}
		}
		if(!flag&&cannot.find(1<<(p[i]))==cannot.end()) 
		{
			cnt++;
			cannot.insert(1<<(p[i]));
		}
	}
	printf("%lld",(1<<(k-cnt))-n);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

不到半个小时就写完了，心里想着A了A了就去看T3了。

但是！可能是写的太快，我并没有意识到n,m都是小于$10^6$

并且输出可以是$2^{64}$爆long long

要知道，只要建一个变量把A数组全部按位或就可以把内层循环去掉了，然后再改一下输出就能A了QAQ

100->60！

T3调用

看到此题，我心中狂喜，这不就是线段树裸题吗？~~丝毫没有注意到数据范围~~

于是打了一遍板子，过了前两个样例，想着A了A了就走了~~丝毫没有意识到问题的严重性~~

  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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196


#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
#define mod 998244353
using namespace std;
ll read()
{
	char c=getchar();
	ll num=0;
	while(c>'9'||c<'0')
	{
		c=getchar();
	}
	while(c<='9'&&c>='0')
	{
		num=(num<<1)+(num<<3)+(c^'0');
		c=getchar();
	}
	return num;
}
#define ls (p<<1)
#define rs (ls|1)
#define mid (ln[p]+rn[p]>>1)
int num[100010],ln[400010],rn[400010];
ll la[400010],lm[400010];
ll dat[400010];
int mx;
void build(int p,int l,int r)
{
	mx=max(mx,p);
	ln[p]=l;rn[p]=r;
	lm[p]=1;
	if(l==r)
	{
		dat[p]=num[l];
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void down(int p)
{
	if(ln[p]==rn[p]) return;
	if(ln[ls]==rn[ls])
	{
		if(lm[p]!=1) 
		{
			dat[ls]*=lm[p];
		}
		if(la[p])
		{
			dat[ls]+=la[p];
		}
		dat[ls]%=mod;
	}
	else
	{
		la[ls]*=lm[p];
		lm[ls]*=lm[p];
		la[ls]+=la[p];
		la[ls]%=mod;
	}
	if(ln[rs]==rn[rs])
	{
		if(lm[p]!=1) 
		{
			dat[rs]*=lm[p];
		}
		if(la[p])
		{
			dat[rs]+=la[p];
		}
		dat[rs]%=mod;
	}
	else
	{
		la[rs]*=lm[p];
		lm[rs]*=lm[p];
		la[rs]+=la[p];
		la[rs]%=mod;
	}
	lm[p]=1;la[p]=0;
}
void add(int p,int pos,int v)
{
	if(ln[p]==rn[p])
	{
		dat[p]+=v;
		return;
	}
	down(p);
	if(pos<=mid) add(ls,pos,v);
	else add(rs,pos,v);
}
void mut(int v)
{
	la[1]*=v;
	lm[1]*=v;
}
void out(int p)
{
	if(ln[p]==rn[p])
	{
		printf("%lld ",dat[p]%mod);
		return;
	}
	down(p);
	out(ls);
	out(rs);
}
struct fun
{
	int cla;
	int p,v;
	int tot;
	vector <int> fl;
}F[100010];
void run(int rnk)
{
	switch(F[rnk].cla)
	{
		case 1:
			{
				add(1,F[rnk].p,F[rnk].v);
				break;
			}
		case 2:
			{
				mut(F[rnk].v);
				break;
			}
		case 3:
			{
				for(int i=0;i<F[rnk].tot;i++)
				{
					run(F[rnk].fl[i]);
				}
			}
	}
}
int FUN[100010];
int main()
{
	freopen("call.in","r",stdin);
	freopen("call.out","w",stdout);
	int n=read();
	for(int i=1;i<=n;i++)
	{
		num[i]=read();
	}
	build(1,1,n);
	int m=read();
	for(int i=1;i<=m;i++)
	{
		int t=read();
		F[i].cla=t;
		switch(t)
		{
			case 1:
				{
					int p=read(),v=read();
					F[i].p=p;F[i].v=v;
					break;
				}
			case 2:
				{
					int v=read();
					F[i].v=v;
					break;
				}
			case 3:
				{
					int c=read();
					F[i].tot=c;
					for(int j=0;j<c;j++)
					{
						F[i].fl.push_back(read());
					}
				}
		}
	}
	int Q=read();
	for(int i=0;i<Q;i++)
	{
		FUN[i]=read();
	}
	for(int i=0;i<Q;i++)
	{
		run(FUN[i]);
	}
	out(1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}