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

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

cpp
#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！即便加了网传的奇淫技巧：

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

也没用！

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

用scanf的：

用cin+上述“优化”的：

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

T1儒略日

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

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

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

cpp
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：

cpp
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分稳了~~分不在多，及格就行~~~

完整代码如下：

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

cpp
#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行：

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

这里我之前写的是：

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

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

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

但是！注意第85行：

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

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

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

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

cpp
	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行：

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

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

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

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

样例1输入
3
10
100
1000

样例1输出
11 1 4713 BC
10 4 4713 BC
27 9 4711 BC

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

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

cpp
		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)~~

cpp
#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）

题意很简单，就是一个二进制的题，我很快就写出了代码：

cpp
#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了就走了~~丝毫没有意识到问题的严重性~~

cpp
#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;
}

而且！因为我忘记了乘法能不能直接取模，于是我就没给乘法取模，样例3 long long乘爆了输出全是0！

更严重的是，这份线段树打挂了，至今都没调处来哪里挂了

交了份官方数据，发现只有三分之一的数据是TLE的

凉了凉了。。。。。。

~~不过这还有10分？~~

T4贪吃蛇

我看到这题我就知道不会做，更何况到这里只剩半个小时了，放弃，回去检查了。

总结

总的来说，这次复试存在重大失误，只剩70了，估计水个三等都难QAQ

~~好像比去年好？但这我拿不到奖有什么关系？~~

不过还有NOIP ~~真·有分就行~~

目录