打得不是很理想，考后来补题。

T1 儒略日

解析：一道超级恶心的大大大大大大模拟，是那种是个人都会写但都不想写的狗屎题目。

我的做法是分三段处理，即公元前，公元后到 1582.10.151582.10.15 前，公元后 1582.10.151582.10.15 及以后。三段的处理方式略有不同。第一段中是模 44 余 11 的年份是闰年，并且年份数字是减小的；第二段中模 44 余 00 的年份是闰年，年份数字增加；第三段和第二段的不同在于闰年的判断方式。分别把三段内每一段的总天数手算出来，然后分段处理即可。一定注意细节不要写错。(考场上有个地方有顺序问题，没判于是直接从 100→0100\to 0)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=100010;
int q;
long long r,ansy,ansm,ansd;
long long da[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
long long p[13];
inline bool check(long long x)
{
	if(x%400==0)
		return true;
	if(x%100==0)
		return false;
	if(x%4==0)
		return true;
	return false;
}
int main()
{
	scanf("%d",&q);
	while(q--)
	{
		scanf("%lld",&r);
		ansy=4713;
		ansm=ansd=1;
		if(r<1721424)
		{
			long long x=r/1461;
			long long rest=r%1461;
			ansy-=4*x;
			int flag=0;
			if(rest>=366&&(!flag))
			{
				rest-=366;
				ansy--;
				flag++;
			}
			if(rest>=365&&flag==1)
			{
				rest-=365;
				ansy--;
				flag++;
			}
			if(rest>=365&&flag==2)
			{
				rest-=365;
				ansy--;
				flag++;
			}
			if(rest>=365&&flag==3)//就是这狗日的flag没判导致100->0
			{
				rest-=365;
				ansy--;
				flag++;
			}
			for(int i=1;i<=12;i++)
				p[i]=da[i];
			if(ansy%4==1)
				p[2]++;
			for(int i=1;i<=12;i++)
			{
				if(rest<p[i])
				{
					ansm=i;
					break;
				}
				rest-=p[i];
			}
			ansd+=rest;
			while(ansd>p[(ansm-1)%12+1])
			{
				ansd-=p[(ansm-1)%12+1];
				ansm++;
			}
			while(ansm>12)
			{
				ansm-=12;
				ansy--;
			}
			printf("%lld %lld %lld BC\n",ansd,ansm,ansy);
			continue;
		}
		r-=1721424;
		ansy=ansm=ansd=1;
		if(r<577737)
		{
			long long x=r/1461;
			long long rest=r%1461;
			ansy+=4*x;
			int flag=1;
			if(rest>=365&&flag==1)
			{
				rest-=365;
				ansy++;
				flag++;
			}
			if(rest>=365&&flag==2)
			{
				rest-=365;
				ansy++;
				flag++;
			}
			if(rest>=365&&flag==3)
			{
				rest-=365;
				ansy++;
				flag++;
			}
			if(rest>=366&&flag==4)//这里也是，tmd
			{
				rest-=366;
				ansy++;
				flag++;
			}
			for(int i=1;i<=12;i++)
				p[i]=da[i];
			if(ansy%4==0)
				p[2]++;
			for(int i=1;i<=12;i++)
			{
				if(rest<p[i])
				{
					ansm=i;
					break;
				}
				rest-=p[i];
			}
			ansd+=rest;
			while(ansd>p[(ansm-1)%12+1])
			{
				ansd-=p[(ansm-1)%12+1];
				ansm++;
			}
			while(ansm>12)
			{
				ansm-=12;
				ansy++;
			}
			printf("%lld %lld %lld\n",ansd,ansm,ansy);
			continue;
		}
		r-=577737;
		ansy=1582;
		ansm=10;
		ansd=15;
		if(r<78)
		{
			if(r<17)
				ansd+=r;
			else if(r<47)
			{
				r-=17;
				ansm=11;
				ansd=1+r;
			}
			else
			{
				r-=47;
				ansm=12;
				ansd=1+r;
			}
			printf("%lld %lld %lld\n",ansd,ansm,ansy);
			continue;
		}
		r-=78;
		ansy=1583;
		ansm=ansd=1;
		long long x=r/146097;
		long long rest=r%146097;
		ansy+=400*x;
		int flag=0;
		if(rest>=36525&&(!flag))
		{
			rest-=36525;
			ansy+=100;
			flag++;
		}
		if(rest>=36524&&flag==1)
		{
			rest-=36524;
			ansy+=100;
			flag++;
		}
		if(rest>=36524&&flag==2)
		{
			rest-=36524;
			ansy+=100;
			flag++;
		}
		if(rest>=36524&&flag==3)//也是也是，吐了
		{
			rest-=36524;
			ansy+=100;
			flag++;
		}
		while(rest>=366)
		{
			if(check(ansy))
			{
				rest-=366;
				ansy++;
			}
			else
			{
				rest-=365;
				ansy++;
			}
		}
		if(rest>=365)
		{
			if(!check(ansy))
			{
				rest-=365;
				ansy++;
			}
		}
		for(int i=1;i<=12;i++)
			p[i]=da[i];
		if(check(ansy))
			p[2]++;
		for(int i=1;i<=12;i++)
		{
			if(rest<p[i])
			{
				ansm=i;
				break;
			}
			rest-=p[i];
		}
		ansd+=rest;
		while(ansd>p[(ansm-1)%12+1])
		{
			ansd-=p[(ansm-1)%12+1];
			ansm++;
		}
		while(ansm>12)
		{
			ansm-=12;
			ansy++;
		}
		printf("%lld %lld %lld\n",ansd,ansm,ansy);
	}
	return 0;
}//200+行代码，我就这

T2 动物园

解析：这 TM 才是真正的签到题，枯了，CCF 居然开始不按难度梯度来排题了。

一道很水的题，对于每 11 位，如果动物园中有这一位为 11 的动物或者这 11 位不需要购买任何饲料，那么这 11 位对饲料就没有影响，即新的动物这 11 位可以为 11。假设这样的位有 pp 个，答案即为 2p−n2 ^{p}-n。唯一需要注意的地方是数据范围中，当 n=0,p=64n=0,p=64 时，答案会爆 unsigned long long，因此需要特判一手。(考场上居然又没特判，我就这)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<vector>
using namespace std;
#define INF 1e9
const int maxn=1000010;
bitset<100> p;
vector<int> a[110];
int n,m,c,k;
unsigned long long ans,cnt;
int main()
{
	scanf("%d%d%d%d",&n,&m,&c,&k);
	for(int i=1;i<=n;i++)
	{
		unsigned long long x;
		scanf("%llu",&x);
		p|=x;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
	}
	for(int i=0;i<k;i++)
	{
		long long r=a[i].size();
		if(r<=0||p[i])
			cnt++;
	}
	if(n==0&&cnt==64)
	{
		printf("18446744073709551616");
		return 0;
	}
	if(cnt==0)
		ans=(1ull<<cnt)-n;
	else
		ans=(1ull<<(cnt-1))-n+(1ull<<(cnt-1));
	printf("%llu",ans);
	return 0;
}

T3 函数调用

解析：一道比较正常的题。其实想法并不难，但是就是没有想出来。

我们可以把题目看成把所有数都乘上一个数 mulmul，然后再给其中一些数加上 addiadd _{i}，其中 mulmul 是所有被调用的第二类函数给所有数乘的 VjV _{j} 的积。

函数的调用关系是 DAG，这个不难发现，因此可以通过建图后，一遍 dfs 求出 mulimul _{i} 代表第 ii 个函数调用后能将所有数乘上 mulimul _{i}。

所以现在的难点在于如何求 addiadd _{i}。

我们假设其中一个数的操作序列(把第三类操作展开)是 abaabbaab....\texttt{abaabbaab....}，其中 a\texttt{a} 代表第一个函数操作，加上某个数 kk，bb 代表第二个函数操作，乘上某个数 pp，那么这个数的答案为：

ansi={[(ai+k1)p1+k2]p2+k3}p3+⋯=(p1p2p3⋯ )ai+(p1p2p3⋯ )k1+(p2p3⋯ )k2+(p3⋯ )k3+⋯\begin{aligned} ans _{i} & =\{[(a _{i}+k _{1})p _{1}+k _{2}]p _{2}+k _{3} \}p _{3}+\cdots \\ & =(p _{1}p _{2}p _{3}\cdots)a _{i}+(p _{1}p _{2}p _{3}\cdots)k _{1}+(p _{2}p _{3}\cdots)k _{2}+(p _{3}\cdots)k _{3}+\cdots \end{aligned}

拆开后，我们发现每个第一类操作加的数都会最终乘上一个系数，这个数就是在他之后的所有第二类操作和第三类操作乘的数的积。我们只要把这个系数求出来即可。我们通过算每个操作对它所调用的单点加法的贡献来计算这个系数。

我们设 dpidp _{i} 代表第 ii 个函数对它所调用的单点加法产生了 dpidp _{i} 倍的贡献，我们可以先把每个函数一开始调用时的产生的贡献求出，对于第三类函数先不处理，最后再用拓扑排序更新真正的 dpidp _{i}。一开始我们可以倒序来处理所有函数调用，同时算出 mulmul 来：

  • 对于第一类函数，我们令 dpi←dpi+muldp _{i}\gets dp _{i}+mul；
  • 对于第二类函数，我们令 mul←mul×Vimul\gets mul\times V _{i}；
  • 对于第三类函数，我们令 dpi←dpi+mul,mul←mul×mulidp _{i}\gets dp _{i}+mul,mul\gets mul\times mul _{i}。

然后我们再拓扑排序，求出每个第三类操作真正的 dpidp _{i}，同时算出 addiadd _{i}。

  • 对于第一类函数，我们令 addPi←addPi+fi×Viadd _{P _{i}}\gets add _{P _{i}}+f _{i}\times V _{i}；
  • 对于第三类函数，我们从后往前处理所有调用的函数。我们令 w=dpiw=dp _{i}，然后对于每个调用的函数 jj，令 fj←fj+fif _{j}\gets f _{j}+f _{i}，然后使 w←w×muljw\gets w\times mul _{j}。

最后每个数输出 ai×mul+addia _{i}\times mul+add _{i} 即可。时间复杂度 O(n+m)O(n+m)。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1e9
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn=100010;
const int mod=998244353;
int n,m,Q,f[maxn],deg[maxn],dp[maxn];
long long a[maxn],mul[maxn],num=1,add[maxn];
bool vis[maxn];
queue<int> q;
struct oper
{
	int type;
	long long P,V,C;
	vector<int> g;
}p[maxn];
void dfs(int u)
{
	vis[u]=1;
	mul[u]=(p[u].type==2)?p[u].V:1;
	for(int i=0;i<p[u].g.size();i++)
	{
		int v=p[u].g[i];
		if(!vis[v])
			dfs(v);
		mul[u]=mul[u]*mul[v]%mod;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&p[i].type);
		if(p[i].type==1)
		{
			scanf("%lld%lld",&p[i].P,&p[i].V);
			p[i].V%=mod;
		}	
		else if(p[i].type==2)
		{
			scanf("%lld",&p[i].V);
			p[i].V%=mod;
		}		
		else
		{
			scanf("%lld",&p[i].C);
			for(int j=1;j<=p[i].C;j++)
			{
				int x;
				scanf("%d",&x);
				p[i].g.push_back(x);
				deg[x]++;
			}
		}
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
		scanf("%d",&f[i]);
	for(int i=1;i<=m;i++)
		if(!deg[i]&&!vis[i])
			dfs(i);
	for(int i=Q;i>=1;i--)
	{
		int u=f[i];
		if(p[u].type==1)
			dp[u]=(dp[u]+num)%mod;
		else if(p[u].type==2)
			num=num*p[u].V%mod;
		else
		{
			dp[u]=(dp[u]+num)%mod;
			num=num*mul[u]%mod;
		}
	}
	for(int i=1;i<=m;i++)
		if(!deg[i])
			q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(p[u].type==1)
			add[p[u].P]=(add[p[u].P]+dp[u]*p[u].V%mod)%mod;
		long long w=dp[u];
		for(int i=p[u].g.size()-1;i>=0;i--)
		{
			int v=p[u].g[i];
			deg[v]--;
			if(!deg[v])
				q.push(v);
			dp[v]=(dp[v]+w)%mod;
			w=w*mul[v]%mod;
		}
	}
	for(int i=1;i<=n;i++)
		printf("%lld ",(a[i]*num+add[i])%mod);
	return 0;
}

T4 贪吃蛇

解析：一道看起来很简单，但是有很多细节的题。

首先有一个结论：当前最强的蛇吃了最弱的蛇后，如果没有变成最弱的蛇，那么他一定选择从吃。

证明：假如当前蛇从小到大排序为 a1,a2,⋯ ,ana _{1},a _{2},\cdots,a _{n}，所以最强的为 ana _{n}，最弱的为 a1a _{1}，吃掉后会变成 an−a1a _{n}-a _{1}。现在我们分类讨论：

  • 假如 an−a1a _{n}-a _{1} 依然是最强的，那么肯定吃；
  • 假如 an−a1a _{n}-a _{1} 不是最强的，那么此时 an−1a _{n-1} 是最强的，a2a _{2} 是最弱的，吃掉后变成 an−1−a2a _{n-1}-a _{2}，又因为 a1≤a2,an−1≤ana _{1}\le a _{2},a _{n-1}\le a_{n}，所以 an−1−a2≤an−a1a _{n-1}-a _{2}\le a_{n}-a _{1}。即后面的蛇吃掉后会比 an−a1a _{n}-a _{1} 更弱。因此如果后面的蛇不会死掉，那么我这条 an−a1a _{n}-a _{1} 的蛇也不会死。因为有蛇会死在我前面，所以可以吃。

有了这个结论，我们可以大胆地吃一部分蛇。但是如果吃了变成最弱地蛇我们到底还要吃不吃呢？

可以来推一下：

如果 ana _{n} 吃掉 a1a _{1} 后变成了最弱的蛇，那么下次该用 an−1a _{n-1} 吃 an−a1a _{n}-a _{1} 这条蛇，如果 an−1−(an−a1)a _{n-1}-(a _{n}-a _{1}) 不是最弱的蛇，那么他会选择吃，这样 ana _{n} 就会凉掉，所以 ana _{n} 当初选择不吃。如果 an−1−(an−a1)a _{n-1}-(a _{n}-a _{1}) 是最弱的蛇，那么就要考虑下一条最强蛇 an−2a _{n-2} 吃掉这条 an−1−(an−a1)a _{n-1}-(a _{n}-a _{1}) 的蛇后是否是最弱的蛇了。如果吃掉后不是最弱的蛇就会选择吃，这样 an−1a _{n-1} 就凉了，所以 an−1a _{n-1} 当初不会吃，所以 ana _{n} 就不会死，所以可以吃。如果吃了变成了最弱的蛇，就会考虑下一条蛇……

这个问题就是一种递归了，直到某条蛇吃了后不是最弱的蛇或者只剩下 22 条蛇为止。这样最后一条蛇会吃，倒数第二条为了保命不吃，倒数第三条可以吃，倒数第四条会不吃，倒数第五条可以吃……

这样，ana _{n} 吃不是就和最后一条蛇的奇偶性相关了。如果 ana _{n} 不吃游戏就结束，ana _{n} 吃掉后，那么 an−1a _{n-1} 必定不吃，下一轮结束。

所以我们模拟两个阶段即可：

  • 阶段一：所有最强🐍吃掉后都不是最弱的，都会选择吃；
  • 阶段二：所有最强🐍吃掉后都是最弱🐍，直到有条蛇吃了之后不是最弱或者只剩两条为止。

阶段一结束后，我们就直接判断阶段二的奇偶性看看能不能再吃一次即可。我们用 set 可以方便维护最强最弱蛇，时间复杂度 O(Tnlog⁡n)O(Tn\log n)，期望得分 7070 分。

如果我们采用 [NOIP2016] 蚯蚓里的做法，用两个双端队列 q1,q2q _{1},q _{2} 来维护单调性，那么时间复杂度为 O(Tn)O(Tn)，期望得分 100100 分。

所以这样的做法为：

  • 阶段一：每次从 q1,q2q _{1},q _{2} 尾部取出最强的蛇，从 q1q _{1} 头部取出最弱的蛇，如果吃了是最弱的蛇，那么就进入第二阶段，否则直接装入 q2q _{2} 的头部；
  • 阶段二：此时最弱的蛇一直是吃蛇的那条蛇，所以没必要丢队列里，单独维护一下即可。
/*
 * @Author: clorf 
 * @Date: 2020-11-11 15:58:25 
 * @Last Modified by: clorf
 * @Last Modified time: 2020-11-11 18:10:23
 */
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<cctype>
#include<deque>
#define INF 2e9
using namespace std;
const int maxn=1000010;
const double Pi=acos(-1.0);
const double eps=1e-7;
//1.数组开小
//2.没用long long/爆了类型存储范围
//3.写之前式子没推清楚
//4.变量写错(想当然typo/没想清楚含义)
//5.写之前没想清楚复杂度
//6.常量数字与long long连用时要加ll！！！
//7.考虑无解和多解的情况
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(!isdigit(ch)) {f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int t,n,a[maxn],k,ans;
deque<pair<int,int> > q1,q2;
int main()
{
	scanf("%d",&t);
	for(int _=1;_<=t;_++)
	{
		if(_==1)
		{
			scanf("%d",&n);
			for(int i=1;i<=n;i++)
				scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;i++)
			q1.push_back(make_pair(a[i],i));
		while(1)
		{
			if(q1.size()+q2.size()==2)
			{
				ans=1;
				break;
			}//只剩2条蛇
			int x,y,id;
			y=q1.front().first;
			q1.pop_front();//最弱
			if(q2.empty()||(!q1.empty()&&q1.back()>q2.back()))
			{
				x=q1.back().first;
				id=q1.back().second;
				q1.pop_back();
			}
			else
			{
				x=q2.back().first;
				id=q2.back().second;
				q2.pop_back();
			}//最强
			pair<int,int> z=make_pair(x-y,id);//吃掉后
			if(q1.empty()||q1.front()>z)//成为最弱，进入第二阶段
			{
				ans=q1.size()+q2.size()+2;//这一步不吃剩下的蛇
				int flag=0;
				while(1)
				{
					flag++;
					if(q1.size()+q2.size()+1==2)
					{
						if(!(flag&1))
							ans--;
						break;
					}
					int x,id;
					if(q2.empty()||(!q1.empty()&&q1.back()>q2.back()))
					{
						x=q1.back().first;
						id=q1.back().second;
						q1.pop_back();
					}
					else
					{
						x=q2.back().first;
						id=q2.back().second;
						q2.pop_back();
					}//最强
					z=make_pair(x-z.first,id);//更新最弱
					if(!((q1.empty()||z<q1.front())&&(q2.empty()||z<q2.front())))//不是最弱
					{
						if(!(flag&1))
							ans--;
						break;
					}
				}
				break;
			}
			else
				q2.push_front(z);
		}
		printf("%d\n",ans);
		if(_<t)
		{
			scanf("%d",&k);
			for(int i=1;i<=k;i++)
			{
				int x,y;
				scanf("%d%d",&x,&y);
				a[x]=y;
			}
			while(!q1.empty())
				q1.pop_back();
			while(!q2.empty())
				q2.pop_back();
		}
	}
	return 0;
}