本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-16 21:57:22

前言：

当年的国赛题目现在居然变成了一个绿题
本题解只是我的做题思路，还没实际写代码测试，可能有错。

题目分析：

题目给定的是一个递推式，序列里一个数由上一个数生成。而且数据范围特别大，要求第 $10^{18}$ 项，不难想到通过矩阵加速来解决这道题。
设两个矩阵：
$ B = \left[ {\begin{array}{cc} x_{0}\ c\ \end{array} } \right] $

$ C = \left[ {\begin{array} {cc} x_{1}\ c\ \end{array} } \right] $

现在要构造出一个矩阵 $B$，使得 $A \cdot B = C$
因为 $x_1 = x_{0} \cdot a + c \cdot 1$，所以矩阵 $A$ 的第一行为：$[a,1]$。
因为 $c = x_0 \cdot 0 + c \cdot 1$，所以矩阵 $A$ 的第二行为 $[0,1]$
也就是说：
$ A = \left[ {\begin{array} {cc} a,1\ 0,1\ \end{array} } \right] $

现在构造出了矩阵，那么非常的显然，答案就是：$A^{n} \cdot B$，矩阵快速幂即可。 算了我对“显然”解释一下：第 $n$ 项是由第 $n-1$ 项 乘矩阵 $A$ 得来的，不能理解手动推算一下就能的出来。

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	ll n,m,a,c,x0,g;
	struct Matrix
	{
		ll imap[2][2];
		Matrix()
		{
			memset(imap,0,sizeof(imap));
		}
		void init()
		{
			imap[0][0]=imap[1][1]=1;
		}
		ll guisucheng(ll a,ll b)
		{
			ll res=0;
			while(b)
			{
				if(b&1)res=(res+a)%m;
				a=a*2%m;
				b>>=1;
			}
			return res;
		}
		Matrix operator*(Matrix b)
		{
			Matrix res;
			for(int i=0;i<2;i++)
			{
				for(int j=0;j<2;j++)
				{
					for(int k=0;k<2;k++)
					{
						res.imap[i][j]+=guisucheng(imap[i][k],b.imap[k][j]);
						res.imap[i][j]%=m;
					}
				}
			}
			return res;
		}
	};
	Matrix ksm(Matrix base,ll b)
	{
		Matrix res;
		res.init();
		while(b)
		{
			if(b&1)res=res*base;
			base=base*base;
			b>>=1;
		}
		return res;
	}
	Matrix A,B;
	void main()
	{
		scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);
		A.imap[0][0]=a;
		A.imap[0][1]=A.imap[1][1]=1;
		B.imap[0][0]=x0;
		B.imap[1][0]=c;
		Matrix ans=ksm(A,n)*B;
		printf("%lld",ans.imap[0][0]%g);
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-22 14:48:23

前言：

被 D 题降智，E 题写了个 kruskal 结果被卡了，F 题是个普及组难度的原题但是我没去看，最后 rating：
$\color{brown}\text{706} \rightarrow \color{brown}\text{725}$，什么时候才能上 $\color{green}\text{6kyu}$

A

int ch=getchar();
cout<<char(ch);
两行代码结束。
复杂度：$O(1)$

B

这个东西直接模拟就行了。
复杂度：$O(n+k)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=105;
	int a[maxn],b[maxn];
	int k,n;
	int imax=0;
	void main()
	{
		cin>>n>>k;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			imax=max(imax,a[i]);
		}
		for(int i=1;i<=k;i++)
		{
			cin>>b[i];
			if(a[b[i]]==imax)
			{
				printf("Yes");
				return;
			}
		}
		printf("No");
		
	}
}
int main()
{
	Main::main();
	return 0;
}

C

可以枚举 $0 \rightarrow 9$ 代表最终每个都显示的数字，然后枚举每一秒，每一秒再枚举每个可以点击的按钮即可。
算一下就可以发现，最多 1000 秒就能使所有的卷轴显示相同的数字，因为极端情况下 $10$ 秒才能控制一个卷轴，最多有 $n$ 个卷轴，$n \le 100$，$10 \times 100 = 1000$。
总复杂度： $O(10 \times 1000 \times n) = O(10000n)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=105;
	char s[maxn][15];
	int n;
	bool vis[maxn];
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s[i]);
		}
		int ans=0x3f3f3f3f;
		for(int i=0;i<10;i++)\/\/zimu
		{
			int col=0;
			for(int t=0;t<=1000;t++)\/\/miaoshu
			{
				bool flag=1;
				for(int j=1;j<=n;j++)
				{
					if(!vis[j])
					{
						if(s[j][t%10]==(i+'0'))
						{
							vis[j]=1;
							break;
						}
					}
				}
				for(int j=1;j<=n;j++)
				{
					if(!vis[j])
					{
						flag=0;
						break;
					}
				}
				if(flag)
				{
					col=t;
					break;
				}
			}
			ans=min(ans,col);
			for(int j=1;j<=n;j++)
			{
				vis[j]=0;
			}
		}
		printf("%d",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

D

可以先计算所有情况，然后再减去不合法情况。
假设由有 $n$ 个元素，那么在其中任意选择 $3$ 个元素的情况有 $\dfrac{n \cdot (n-1) \cdot (n-2)}{6}$ 个，任意选择 $2$ 个元素的情况有 $\dfrac{n \cdot (n-1)}{2}$ 个。
那么先定义两个函数，方便后面使用：

long long sum_3(long long n)
{
	return n*(n-1)*(n-2)\/6;
}
long long sum_2(long long n)
{
	return n*(n-1)\/2;
}

设一个元素 $a_i$ 在数组中重复出现了 $x$ 次，数组有 $n$ 个元素。将会出现两种不合法情况，来分类一下。

1. 第一种情况是三元组的组成元素全都是 $a_i$，这种情况有 $\dfrac{x \cdot (x-1) \cdot (x-2)}{6}$个，也就是 sum_3(x)。
2. 第二种情况是三元组的两个元素是 $a_i$，直接在数组所有重复的 $a_i$ 中挑选有 $\dfrac{x \cdot (x-1)}{2}$ 个组合，显然，每个组合都会与其他 $n-2$ 个元素形成新的组合，有 $\dfrac{x \cdot (x-1)}{2} \cdot (n-2)$ 个情况。但是别忘了，其中有 $\dfrac{x \cdot (x-1)}{2} \cdot (x-2)$ 种情况会组合成三个元素都相等的三元组，而这些情况已经在第一条处理过，这里不需要再处理，所以实际上只用处理 $\dfrac{x \cdot (x-1)}{2} \cdot [n-2-(x-2)]=\dfrac{x \cdot (x-1)}{2} \cdot (n-x)$ 个情况

综上，设每个元素出现了 $x_i$，数组有 $n$ 个元素，那么答案就是：
$\dfrac{n \cdot (n-1) \cdot (n-2)}{6} - \sum_{i=1}^{n} (\dfrac{x_i \cdot (x_i-1) \cdot (x_i-2)}{6} + \dfrac{x_i \cdot (x_i-1)}{2} \cdot (n-x_i))$
复杂度 $O(n)$（unordered_map 是 $O(1)$的）

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	unordered_map<int,int> im;
	int a[maxn];
	int n;
	ll sum_3(ll n)
	{
		return n*(n-1)*(n-2)\/6ll;
	}
	ll sum_2(ll n)
	{
		return n*(n-1)\/2ll;
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			im[a[i]]++;
		}
		ll ans=sum_3(n);
		for(int i=1;i<=n;i++)
		{
			if(im[a[i]])
			{
				ans-=sum_3(im[a[i]]);
				ans-=sum_2(im[a[i]])*ll(n-im[a[i]]);
				im[a[i]]=0;
			}
		}
		printf("%lld",ans);

	}
}
int main()
{
	Main::main();
	return 0;
}

E

不懂 prim 的请自行百度
这道题让构造一棵树使得 $1$ 到每个点的距离之和最短。最短路 + 生成树，那么肯定就是 prim（赛时我不会 prim，所以寄了）。
这道题算是把堆优化版 prim 板子改改就能过的那种，来说一下：

1. 把更新最短路的地方改成 dijkstra 的做法。
2. 用 pair 的第一个关键字来存储边权，第二个关键字存储边的编号。当要取出队首节点时，直接取出 edge[que.top().second].to 即可。
3. 如果 $1$ 点存入小根堆种，取出队首节点时不会取出 $1$ 点，而是取出 $1$ 指向的节点，所以应该建立一个 $0$ 号节点并将其连向 $1$ 节点，初始时将 $0$ 号节点压入小根堆。
4. 用一个 queue<int> ans 来存储每个需要的边，每弹出队首，就将这条边加入其中，也就是：int id=que.top().second; ans.push((id+1)\/2); 注：之所以 $id$ 要加 $1$ 然后除以 $2$ 是因为建图的时候建的双向边，编号为 $1,2$ 的是一条边，编号为 $3,4$ 的是一条边..........

这道题就结束了。
复杂度： $O((n+m)logm)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	const int maxm=2e5+5;
	int head[maxn<<1];
	bool vis[maxn];
	ll dis[maxn];
	struct EDGE
	{
		int to,nxt,val;
	}edge[maxm<<1];
	int cnt;
	inline void add(int u,int to,int val)
	{
		edge[++cnt].to=to;
		edge[cnt].val=val;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int n,m;
	inline void prim()
	{
		queue<int> ans;
		priority_queue<pair<ll,int>> que;
		for(int i=0;i<=n;i++)
		{
			dis[i]=1e18;
		}
		dis[1]=0;
		que.push(make_pair(0,m*2+1));
		int tot=0;
		while(tot<n&&!que.empty())
		{
			int id=que.top().second;
			int u=edge[id].to;		
			que.pop();
			if(vis[u])continue;
			vis[u]=1;
			ans.push(((id+1)>>1));
			tot++;
			for(int i=head[u];i;i=edge[i].nxt)
			{
				int to=edge[i].to;
				if(dis[to]>dis[u]+ll(edge[i].val))
				{
					dis[to]=dis[u]+ll(edge[i].val);
					que.push(make_pair(-dis[to],i));
				}
			}
		}
		ans.pop();
		while(ans.size()!=0)
		{
			printf("%d ",ans.front());
			ans.pop();
		}
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			int xi,yi,zi;
			scanf("%d%d%d",&xi,&yi,&zi);
			add(xi,yi,zi);
			add(yi,xi,zi);
		}
		add(0,1,0);
		prim();
	}
}
int main()
{
	Main::main();
	return 0;
}

F

这道题是 合并果子 原题，相信谁都会我就不说了
大意：给定一个大小为 $l$ 的面包，要将面包分成 $n$ 块，第 $i$ 块面包大小为 $a_i$。
每次可以将一块面包切成两个任意大小的面包。每次切割面包都会产生相当于原来面包大小的代价，问完成操作的最小代价是多少。
把这个过程倒过来，变成合并面包就行了。现在问题转化为有 $n$ 个大小为 $a_i$ 的面包和一个大小为 $l - \sum a_i$ 的面包，每次可以合并任意两个面包，合并的代价为两个面包大小之和。问合并出一个大小为 $l$ 的面包的最小代价。
显然，每次选出大小最小的两个面包合并就能保证最后代价最小，用小根堆维护即可。
复杂度：$O(nlogn)$

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	ll a[maxn];
	priority_queue<ll> que;
	int n;
	ll l;
	void main()
	{
		scanf("%d%lld",&n,&l);
		ll ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			que.push(-a[i]);
			l-=ll(a[i]);
		}
		if(l>0)
		{
			que.push(-l);
		}
		n=que.size();
		for(int i=1;i<n;i++)
		{
			ll t1=-que.top();
			que.pop();
			ll t2=-que.top();
			que.pop();
			ans+=t1+t2;
			que.push(-t1-t2);
		}
		printf("%lld",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

Ex

题目简略翻译：

有 $C$ 个美丽值，分别为 $1,2,......C$
有 $N$ 个宝石，每个宝石都有一个颜色 $D_i$，和一个美丽值 $V_i$（$V_i \in {1,2,.....C}$，每个美丽值都至少会在某个宝石上出现一次）

现在要在 $n$ 个宝石中选 $C$ 个颜色互不相同的宝石，每个方案的价值是选择的这 $C$ 个宝石的美丽值的异或和。
问价值为第 $k$ 大的方案的价值

题目分析：

老子不会

代码：

#include <bits\/stdc++.h>
using namespace std;
int main()
{
	cout<<"老子不会";  
   return WA;
}  

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-23 23:06:33

前言：

谢 lhx 大佬的思路

记录思路区：

可以使用分组背包，将 $a_i,0,-a_i$ 分成一个组 可以遍历 $-\sum a_i \rightarrow \sum a_i$ 的每个数，对其中每个数进行分组背包求解方案数。
由于遍历的过程复杂度是 $O(\sum a_i)$，对每个数分组背包求解方案数的过程是 $3 \cdot n = O(n)$ 的（$3$ 是每个组的大小），所以总复杂度是 $O(n \cdot \sum a_i + q)$

UPD: 实际上上面的复杂度假了，因为分组背包的复杂度不是 $O(n)$，下面写上我的新想法：
和上面一样，仍然将 $a_i,0,-a_i$ 分成一个组，这样就有了 $n$ 个组，然后遍历这 $n$ 个组，对于每个组遍历 $\sum a_i \rightarrow -\sum a_i$（要凑成的数）计算方案数。
这样总复杂度是 $O(n \cdot \sum a_i + q)$
现在的瓶颈是我不会这种计算方案数类型的背包 dp。

做法

还没想好

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-27 22:28:05

前言：

看了 $\color{black}\text{W}\color{red}\text{YXkk}$ 和 $\color{black}\text{阮}\color{red}\text{行止}$ 的题解我总算是会了

正文：

先考虑只有两个方程的情况：
$\begin{cases} x \equiv r_1 (\mod m_1)\ x \equiv r_2 (\mod m_2) \end{cases}$
可以转化为：
$\begin{cases} x = r_1 + k_1m_1\ x = r_2 + k_2m_2 \end{cases}$
显然可得：
$r_1 + k_1m_1 = r_2 + k_2m_2$
移项之后：
$k_1m_1 + k_2(-m2) = r_2 - r_1$
然后解出 $k_1$ 和 $k_2$（求解这种方程的代码下附，其实这么简单的东西自己推一下也能推出解法）
然后 $x$ 就是 $r_1 + k_1m_1$（没错，不用 $k_2$ 和 $m_2$ 也行）

然后就是合并这两个方程，这里用到了一个定理：
$\begin{cases} x \equiv r_1 (\mod m_1)\ x \equiv r_2 (\mod m_2) \end{cases}$
设这两个方程有一个特解 $x_0$，满足
$\begin{cases} x_0 \equiv r_1 (\mod m_1)\ x_0 \equiv r_2 (\mod m_2) \end{cases}$
那么它们的通解 $x$ 满足
$x \equiv x_0 (\mod lcm(m_1,m_2))$
这样就和并成了一个方程，但是这个做法我不会证明

现在就是把方程组的每个方程都压入队列中，每次取队首的两个方程进行合并再压入队列中，直到只剩一个方程。显然这个方程的解就是最终的解。

额外：

放一份求解形如 $ax+by=c$ 这样的方程的代码（已知 $a,b,c$）

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	ll exgcd(ll a,ll b,ll& x,ll& y)
	{
		if(!b)
		{
			x=1;
			y=0;
			return a;
		}
		ll ans=exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y;
		y=tmp-a\/b*y;
		return ans;
	}
	ll a,b,c,x0,y0,x,y;
	void main()
	{
		printf("Solving ax+by=c\n");
		printf("a: ");
		scanf("%lld",&a);
		printf("b: ");
		scanf("%lld",&b);
		printf("c: ");
		scanf("%lld",&c);
		int d=exgcd(a,b,x0,y0);
		if(c%d!=0)
		{
			printf("No\n");
			return;
		}
		int k=c\/d;
		x=x0*k;
		y=y0*k;
		printf("%lld * %lld + %lld * %lld = %lld",a,x,b,y,c);
	}
}
int main()
{
	Main::main();
	return 0;
}

注意：

exgcd 的结果可能是负数

代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=1e5+5;
	typedef long long ll;
	typedef __int128 ll128;
	typedef pair<ll128,ll128> pr;
	ll gcd(ll a,ll b)
	{
		return !b?a:gcd(b,a%b);;
	}
	ll lcm(ll a,ll b)
	{
		return a\/gcd(a,b)*b;
	}
	ll exgcd(ll a,ll b,ll& x,ll& y)
	{
		if(!b)
		{
			x=1;
			y=0;
			return a;
		}
		ll ans=exgcd(b,a%b,x,y);
		ll tmp=x;
		x=y;
		y=(ll128)tmp-ll128(a\/b)*(ll128)y;
		return ans;
	}
	pr axbyc(ll a,ll b,ll c)
	{
		ll x0,y0;
		ll d=exgcd(a,b,x0,y0);
		ll128 k=c\/d;
		ll128 x=(ll128)x0*k;
		ll128 y=(ll128)y0*k;
		return make_pair(x,y);
	}
	int n;
	ll128 m[maxn],r[maxn];
	queue<pr> equ;
	ll128 gsc(ll128 a,ll128 b,ll128 mod)
	{
		ll128 ret=0;
		while(b)
		{
			if(b&1)ret=(ret+a)%mod;
			ret=ret*2%mod;
			b>>=1;
		}
		return ret;
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			ll mi,ri;
			scanf("%lld%lld",&mi,&ri);
			equ.push(make_pair(mi,ri));
		}
		while(equ.size()>1)
		{
			pr _=equ.front();
			equ.pop();
			pr __=equ.front();
			equ.pop();
			ll128 m1=_.first;
			ll128 r1=_.second;
			ll128 m2=__.first;
			ll128 r2=__.second;
			pr ___ = axbyc(m1,-m2,r2-r1);
			ll128 k1=___.first;
			ll128 x=r1+(ll128)k1*(ll128)m1;
			equ.push(make_pair(lcm(m1,m2),(x%(ll128)lcm(m1,m2)+(ll128)lcm(m1,m2))%(ll128)lcm(m1,m2)));
		}
		printf("%lld",(ll)equ.front().second);
	}
}
int main()
{
	Main::main();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-30 21:20:43

题外话：

E 题过样例，然而没调出来。
最后 rating: $\color{brown}\text{725} \rightarrow \color{brown}\text{747}$

A

略

B

略

C

题目翻译：

给你一个空集合 $S$
有 $Q$ 次操作，每次操作分三种类型。

1. 给定 $x$，向 $S$ 中加入 $x$
2. 给定 $x$ 和 $c$，设 $m$ 等于 $c$ 与 ($x$ 在 $S$ 中出现的次数) 的 min。重复从 $S$ 中删除 $x$ 数 $m$ 次
3. 输出集合中最大的数与集合中最小的数的差，保证进行此操作时集合不为空。

数据范围：

$1\ \le Q \le 2 \cdot 10^5$
$1 \le c \le Q$
$0 \le x \le 10^9$

做法：

我说一下我的做法和 $\color{black}\text{t}\color{red}\text{ourist}$ 的做法

我的做法：
可以使用一个大根堆和一个小根堆（就是两个 priority_queue）来维护最大值和最小值。然后使用 map 记录每个数出现的次数。
当加入一个数时，就将其同时丢进大根堆和小根堆，然后 map 记录这个数出现的次数加一
删数的时候，直接将 map 记录的这个数出现的次数减一就行了。要注意的是，删数的过程可能会把最大值或最小值删没，这样会影响到操作三查询结果，所以在操作三查询的时候要将大根堆和小根堆的 (通过 map 记录的 (出为 0 的队首元素)) 通过 while 不断弹出，直到队首元素在 map 中的记录次数不为 0。
至于中间的非最大最小值的数不用管，因为查询用不着，不用将它们弹出。
复杂度： $O(nlogn)$
我的代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	int q;
	int op,x,c;
	priority_queue<int> que;
	priority_queue<int> que2;
	unordered_map<int,int> im;
	
	void main()
	{
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d",&x);
				if(!im[x])
				{
					que.push(x);
					que2.push(-x);
				}
				im[x]++;
			}
			if(op==2)
			{
				scanf("%d%d",&x,&c);
				int m=min(c,im[x]);
				im[x]-=m;
			}
			if(op==3)
			{
				while(im[que.top()]==0)
				{
					que.pop();
				}
				while(im[-que2.top()]==0)
				{
					que2.pop();
				}
				int imax=que.top();
				int imin=-que2.top();
				printf("%d\n",imax-imin);
			}
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

$\color{black}\text{t}\color{red}\text{ourist}$ 的做法：
我之所以使用两个 priority_queue 分别存储最大值和最小值，是因为 priority_queue 只能访问队首元素，只需要换一个既可以访问队列中任意元素的 STL 就行了。$\color{black}\text{t}\color{red}\text{ourist}$ 使用的是 multiset，使用这个就能完成所需功能（multiset 中的元素从小到大排序） 下附 $\color{black}\text{t}\color{red}\text{ourist}$ 的代码：
注：multiset 的队首元素实际上是 multiset.end() 的上一个地址的元素，所以使用 prev 函数获取 multiset.end() 指针的上一个地址。

\/**
 *    author:  tourist
 *    created: 28.05.2022 16:02:11       
**\/
#include <bits\/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo\/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  multiset<int> s;
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x;
      cin >> x;
      s.insert(x);
    }
    if (op == 2) {
      int x, c;
      cin >> x >> c;
      while (c--) {
        auto it = s.find(x);
        if (it == s.end()) {
          break;
        }
        s.erase(it);
      }
    }
    if (op == 3) {
      cout << (*prev(s.end()) - *s.begin()) << '\n';
    }
  }
  return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-23 22:10:12

前言：

第一次At赛场AC ABCDE祭

A-Horizon

题目分析：

签到题，只需要直接照着题目式子计算即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll a;
int main()
{
    cin>>a;
    printf("%.7lf",sqrt(a*(12800000+a)));
    return 0;
}

B - Integer Division

题目分析：

仍然是签到题，照着题目的式子计算即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll a;
int main()
{
    cin>>a;
    if(a<0)
    {
        ll ans=a\/10;
        if(a%10)ans--;
        cout<<ans;
        return 0;
    }
    cout<<a\/10;
    return 0;
}

C - Knight Fork

题目大意：

给定两个点 $a,b$，坐标分别为 $(x_1,y_1)$ 和 $(x_2,y_2)$。问是否存在一个点，与$a$ 和 $b$ 的距离都是 $\sqrt{5}$。
$-10^{9} \le x1 \le 10^{9}$
$-10^{9} \le x2 \le 10^{9}$
$-10^{9} \le y1 \le 10^{9}$
$-10^{9} \le y2 \le 10^{9}$
保证给定两点的坐标不相等。

题目分析：

直接看上去看不出什么解法，不过鬼子很良心，配了一张图：

图中所有白色的点就是与黑色点距离为 $\sqrt{5}$ 的点。
所以只需要把所有与 $a$ 的距离为 $\sqrt{5}$ 的坐标用 map 存下来，$b$ 点同理。
最后只需要用 map 判断有没有点，与 $a$ 点距离为 $\sqrt{5}$ ，也与 $b$ 点距离也为 $\sqrt{5}$。如果有，输出 Yes 否则输出 No。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
typedef long long ll;
ll xa,ya,x2,y2;
map<pair<int,int>,bool> im1;
map<pair<int,int>,bool> im2;
int main()
{
    cin>>xa>>ya>>x2>>y2;
    im1[make_pair(xa-2,ya-1)]=1;
    im1[make_pair(xa-2,ya+1)]=1;\/\/
    im1[make_pair(xa+2,ya-1)]=1;\/\/
    im1[make_pair(xa+2,ya+1)]=1;\/\/
    im1[make_pair(xa-1,ya-2)]=1;\/\/
    im1[make_pair(xa-1,ya+2)]=1;\/\/
    im1[make_pair(xa+1,ya-2)]=1;\/\/
    im1[make_pair(xa+1,ya+2)]=1;\/\/
    \/\/------------
    im2[make_pair(x2-2,y2-1)]=1;
    im2[make_pair(x2-2,y2+1)]=1;
    im2[make_pair(x2+2,y2-1)]=1;
    im2[make_pair(x2+2,y2+1)]=1;
    im2[make_pair(x2-1,y2-2)]=1;
    im2[make_pair(x2-1,y2+2)]=1;
    im2[make_pair(x2+1,y2-2)]=1;
    im2[make_pair(x2+1,y2+2)]=1;
    if((im1[make_pair(xa-2,ya-1)]&&im2[make_pair(xa-2,ya-1)])||(im1[make_pair(xa-2,ya+1)]&&im2[make_pair(xa-2,ya+1)])
    ||(im1[make_pair(xa+2,ya-1)]&&im2[make_pair(xa+2,ya-1)])||(im1[make_pair(xa+2,ya+1)]&&im2[make_pair(xa+2,ya+1)])||
    (im1[make_pair(xa-1,ya-2)]&&im2[make_pair(xa-1,ya-2)])||(im1[make_pair(xa-1,ya+2)]&&im2[make_pair(xa-1,ya+2)])||
    (im1[make_pair(xa+1,ya-2)]&&im2[make_pair(xa+1,ya-2)])||(im1[make_pair(xa+1,ya+2)]&&im2[make_pair(xa+1,ya+2)])
    )cout<<"Yes";
    else cout<<"No";
    return 0;
}

D - Prime Sum Game

题目大意：

Takahashi 和 Aoki 在玩一个游戏，规则如下：
首先，Takahashi 选择一个在 $A$ 和 $B$ 之间的数 $a$。
然后，Aoki 选择一个在 $C$ 和 $D$ 之间的数 $b$。
如果 $a + b$ 是一个质数，那么 Aoki 获胜，否则，Takahashi 获胜。
在双方都采取最优策略的情况下，输出谁会获胜。
$1 \le A \le B \le 100$
$1 \le C \le D \le 100$

题目分析：

因为 Takahashi 先手，所以只要在所有初始情况（Takahashi 选完一个数时）下有一种情况 Takahashi 必胜，那么 Takahashi 必胜。
然后需要对每一种初始情况判断 Takahashi 是否必胜。
显然，在当前初始情况下，Aoki 只要有一种方案获胜，那么在当前初始情况，Takahashi 必败。
总的来说就是只要 Takahashi 能选择的所有初始情况有胜局，那么 Takahashi 必胜，如果所有初始情况 Aoki 都能获胜，那么 Aoki 必胜.

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
int a,b,c,d;
int main()
{
    cin>>a>>b>>c>>d;
    int tak;
    int aok;
    bool ansf=0;
    for(tak=a;tak<=b;tak++)
    {
        bool ansf2=1;
        for(aok=c;aok<=d;aok++)
        {
            int num=tak+aok;
            int gh=sqrt(num);
            bool flag=1;
            for(int i=2;i<=gh;i++)
            {
                if(num%i==0)
                {
                \/\/    cout<<"num: "<<num<<endl;
                    flag=0;
                    break;
                }
            }
            ansf2&=(~flag);
        }
        ansf|=ansf2;
    }
    if(ansf)
    {
        cout<<"Takahashi";
        return 0;
    }
    cout<<"Aoki";
    return 0;
}

E - Subtree K-th Max

题目大意：

有 $N$ 个点，编号为 $1$ 到 $N$。每个点都有一个初始点权 $x_i$，有 $N-1$ 条边。
有 $Q$ 次询问，每次询问包含两个数 $(V_i,K_i)$，代表询问以 $V_i$ 为根的子树中第 $K_i$ 大的点点权是多少。
$2 \le N \le 10^{5}$
$0 \le X_i \le 10^{9}$
$1 \le A_i,B_i \le N$
$1 \le Q \le 10^{5}$
$1 \le V_i \le N$
$1 \le K_i \le 20$

题目分析

赛场上刚看到这道题时，想到了主席树。但是我太菜了只会用主席树存储线段树历史版本。再看看数据范围，$K_i$ 居然不超过 $20$，$N$ 也只有 $10^5$ 大小。这说明了什么呢？
说明了可以写爆搜预处理每个点的子树中第 $1$ 大到 第 $20$ 大的点都是哪些点！
很容易写出了下面的代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int head[maxn<<1];
struct EDGE
{
    int to,nxt;
}edge[maxn];
int cnt;
inline void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,q;
int val[maxn];
int kd[maxn][21];
bool vis[maxn];
inline bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int x)
{
    kd[x][1]=val[x];
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        dfs(to);
        int tmp[42];
        for(int j=1;j<=20;j++)
        {
            tmp[j]=kd[to][j];
        }
        for(int j=1;j<=20;j++)
        {
            tmp[j+20]=kd[x][j];
        }
        sort(tmp+1,tmp+40+1,cmp);
        for(int j=1;j<=20;j++)
        {
            kd[x][j]=tmp[j];
        }
    }
}
int main()
{
    for(int i=0;i<maxn;i++)
    {
        for(int j=0;j<=20;j++)
        {
            kd[i][j]=-0x3f3f3f3f;
        }
    }
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    int a1,b1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a1,&b1);
        add(a1,b1);
        add(b1,a1);
    }
    dfs(1);
    int v,k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&v,&k);
        printf("%d\n",kd[v][k]);
    }
    return 0;
}

顺利测过了所有样例，满怀期待的交上去之后令我震撼无比：

WA,RE,TLE 满天飞。
不过只要有 AC 的测试点就还有救。
首先 RE 的原因是，题目是双向边，所以邻接链表应该开到 $2 \cdot 10^5$ 大小。
分析一下 TLE 的原因，可以发现原来的代码存在大量的时空浪费，有很多情况子树节点数量根本到不了 $20$ 个，但是都按 $20$ 个节点来计算了。赛场上注意到了这个地方后紧急换成 vector 来存，子树有多少节点就 emplace_back 多少节点。 然后就 AC 了。
$ \color{green}\text{AC代码：}$ (我为了保险开了 4 倍数组）

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int head[maxn<<2];
struct EDGE
{
    int to,nxt;
}edge[maxn<<2];
int cnt;
inline void add(int u,int to)
{
    edge[++cnt].to=to;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
int n,q;
int val[maxn<<2];
vector<int> kd[maxn<<2];
bool vis[maxn<<2];
inline bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int x)
{
    kd[x].emplace_back(val[x]);
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        dfs(to);
        vector<int> tmp;
        for(int j=0;j<kd[to].size();j++)
        {
            tmp.emplace_back(kd[to][j]);
        }
        for(int j=0;j<kd[x].size();j++)
        {
            tmp.emplace_back(kd[x][j]);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        kd[x].clear();
        for(int j=0;j<tmp.size()&&j<20;j++)
        {
            kd[x].emplace_back(tmp[j]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    int a1,b1;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&a1,&b1);
        add(a1,b1);
        add(b1,a1);
    }
    dfs(1);
    int v,k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&v,&k);
        printf("%d\n",kd[v][k-1]);
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-26 19:02:04

A - Edge Checker

题目大意：

1 到 10 按顺序组成一个环（1 和 10 首尾连接）
给定两个数，问是否相邻。

题目分析：

签到题不需要分析。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a==1&&b==10)||(a==10&&b==1))
    {
        cout<<"Yes";
        return 0;
    }
    if(abs(a-b)<=1)cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

B - Count Distinct Integers

题目大意：

给定一个长度为 $n$ 的数组，问有多少不同的数字。

题目分析：

签到题不需要分析。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn];
map<int,int> im;
int main()
{
    int n;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(!im[a[i]])ans++;
        im[a[i]]=1;
    }
    cout<<ans;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

C - Jumping Takahashi

题目大意：

某人的起始坐标为0（向左为负向右为正）。给定两个长度为 $N$ 的数组，$a$ 和 $b$，这个人第 $i$ 次跳可以向右移动 $ai$ 个单位或 $bi$ 个单位。问经过 $n$ 次跳跃之后是否能到达点 $X$（必须跳 $N$ 次）。
$1 \le N \le 100$

题目分析：

由于本人太菜，只会 $O(2^n)$ 的爆搜，所以就来说一下怎么写爆搜过题，正确算法等我看了官方题解之后再放上来。
首先，朴素的爆搜肯定大家都会写，但是 $O(2^n)$ 的复杂度就算评测机能 $n^2$ 过百万也不行。所以要加剪枝，现在来讲一下怎么写剪枝。
剪枝一：如果当前搜到的数总和超过了 $X$ ,那么返回。
剪枝二：如果当前搜到的数字总和，后面即使每次都选最大的数，总和仍然比 $X$ 小，那么返回。
剪枝三：如果当前搜到的数字总和，后面即使每次都选最小的数，总和仍然比 $X$ 大，那么返回。 来看一看效果：

可见剪枝效果显著，但是仍然无法通过此题。
怎么办？
为了 AC，我加了一个错误的剪枝：
如果递归超过 2000万次还没有搜到结果，那么有解的可能很小（随机数据下），那么直接输出 No。
但是这个是错的，我自己就能 hack 掉。但是 At 的数据太水了所以过了。
正确做法我看完官方题解再放上来。
（还好不是 CF 赛制）

$\color{red}\text{错误}$ $\color{blue}\text{但是}$$\color{green}\text{AC的代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn];
int b[maxn];
int qzh[maxn];
int qzh2[maxn];
int n,x;
int cnt=0;
bool dfs(int i,int col)
{
    if(++cnt>=20000000)return 0;
 \/\/   cout<<"i: "<<i<<" col"<<col<<endl;
    if(col==x&&i==n+1)return 1;
    if(i==n+1)return 0;
    if(col>x)return 0;
\/\/    cout<<"qzh"<< qzh[n]-qzh[i]<<endl;
\/\/    cout<<"qzh"<< qzh2[n]-qzh2[i]<<endl;
\/\/cout<<col+(qzh[n]-qzh[i])<<endl;
\/\/cout<<col+(qzh2[n]-qzh2[i])<<endl;
    if(col+(qzh[n]-qzh[i])>x)return 0;
    if(col+(qzh2[n]-qzh2[i])<x)return 0;
 \/\/   cout<<"i: "<<i<<endl;
    if(dfs(i+1,col+a[i+1]))return 1;
    if(dfs(i+1,col+b[i+1]))return 1;
    return 0;
}

int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        qzh[i]=qzh[i-1]+min(a[i],b[i]);
        qzh2[i]=qzh2[i-1]+max(a[i],b[i]);
    }
    if(dfs(1,a[1])||dfs(1,b[1]))cout<<"Yes";
    else cout<<"No";
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

D - Strange Balls

题目大意：

有 $n$ 个球，每个球都有一个数值 $a_i$。
这些球按照顺序从第 $1$ 个到第 $n$ 个依次放入一个瓶子里。放入一个球后如果出现了有连续 $a_i$ 个球的数值为 $a_i$。那么这连续 $a_i$ 个球都会消失。
问每放入一个球之后瓶子里有多少球。

题目分析：

可以创建一个栈 $sta$，对于每一块连续的球都用一个节点 $sta_i$ 表示。对于每个节点 $sta_i$ 存储当前块有多少个球，以及当前块存的球的数值。
插入一个球之后，如果这个球数值与栈顶节点不一样，那么新建一个节点插入栈顶。如果一样，那么栈顶节点 $sta_{top}$ 存储的球数 $+1$，如果发现 $sta_{top}$ 存储的球数 $ = sta_{top}$的数值，那么删除 $sta_top$ 即可。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
int a[maxn];
int top;
struct Sta
{
    int size;
    int val;
}sta[maxn];
int ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=sta[top].val)
        {
            sta[++top]={1,a[i]};
            ans++;
            printf("%d\n",ans);
        }
        else
        {
            sta[top].size++;
            ans++;
            if(sta[top].size==a[i])
            {
                ans-=sta[top].size;
                top--;
            }
            printf("%d\n",ans);
        }
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

E - Ranges on Tree

题目大意：

$[l,r] = l,l+1,l+2.......r-1,r$
给定一棵树。树上的每个点都有两个值 $(l_i,r_i)$。
设第 $i$ 个节点的子树为集合 $s_i$。
每个点的值应满足一下要求：
一、如果点 $a$ 是点 $b$ 的子节点，那么 $[l_a,r_a]$ 应包含在 $[l_b,r_b]$ 中。
二、如果点 $a$ 和点 $b$ 是独立的两棵树，那么 $[l_a,r_a]$ 应和 $[l_b,r_b]$ 无交集。
对每个节点安排它的 $(l,r)$，使得 $max(l_1,l_2,l_3......l_n,r_1,r_2,r_3......r_n)$ 最小。

题目分析

大力 dfs!
首先确定叶子节点的值，然后，每个节点的 father 节点的值也就是 $(min({{s_i}_j}.l),max({{s_i}_j}.r))$
注： ${{s_i}_j}$ 代表 $s_i$ 的第 $j$ 个元素。
如何确定叶子结点的值呢？ 定义一个变量 $sum$ ，当前点每搜到一个子节点点就 sum++。（为了避免误差，每个点搜到第一个子节点时不用增加 $sum$）
对于搜到的每个点首先把这个点的 $l$ 设为 $sum$，从这个点搜完它的所有子节点之后，再把它的 $r$ 设为 $sum$。
这样就完成了。

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int head[maxn<<1];
struct EDGE
{
    int to,nxt;
}edge[maxn<<1];
int tot;
inline void add(int u,int to)
{
    edge[++tot].to=to;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
int n;
int rd[maxn];\/\/存储入度
struct Val
{
    int l,r;
}val[maxn];\/\/存储每个点的取值范围
int dbg;
bool vis[maxn];
int sum=1;
void dfs(int u)
{
    val[u].l=sum;
    vis[u]=1;
    bool flag=0;
    \/\/因为如果当前点有子树的话
    \/\/统计答案会多统计1
    \/\/在此需要标明以来
    \/\/减去这个误差
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int to=edge[i].to;
        if(vis[to])continue;
        if(flag)sum++;
        flag|=1;
        dfs(to);
    }
    val[u].r=sum;
}
int main()
{
    scanf("%d",&n);
    int ut,vt;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&ut,&vt);
        add(ut,vt);
        add(vt,ut);
        rd[ut]++;
        rd[vt]++;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d %d\n",val[i].l,val[i].r);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-10 21:07:28

题目大意：

有 $n$ 个格子，编号从 $1$ 到 $n$。给定一个长度为 $n$ 的序列 $a$，若 $a_i = 1$，代表第 $i$ 个格子是陆地，若 $a_i = 0$，代表第 $i$ 个格子有水。
你初始在第 $1$ 个格子，你要走到第 $n$ 个格子。路程中不能走在有水的格子上。
如果路中遇到了有水的格子，那么你需要花费硬币跳过去。假设你现在在 $pos1$，你要跳到 $pos2$，那么就要花费 $pos2-pos1$ 个硬币。你只能使用一次硬币。
问最少需要多少个硬币才能走到第 $n$ 个格子，保证有解。

题目解法：

直接遍历一遍数组 $a$，用变量 $pos1$ 记录第一个有水的格子，用变量 $pos2$ 记录最后一个有水的格子。最后答案就是 $pos2-pos1+2$。
注：
要注意特判没有一个格子有水的情况，这种情况输出 0 即可。

AC 代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=105;
    int t;
    int n;
    int a[maxn];
    void main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            int ans=0;
            int pos1=0,pos2=0;
            bool flag=1,flag2=1;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
                if(!a[i]&&flag)
                {
                    flag=0;
                    pos1=i;
                }
            }
            for(int i=n;i>=1;i--)
            {
                if(!a[i]&&flag2)
                {
                    flag2=0;
                    pos2=i;
                }
            }
            if(!pos1&&!pos2)
            {
                printf("0\n");
            }
            else printf("%d\n",(pos2-pos1+2));
        }
    }
}
int main()
{
    Main::main();
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-10 21:21:38

UPD:

修理了一些空格问题，修了一下爆炸的 markdown。

前言：

赛场上想了一个做法但自认为是错的，结果赛后看了官方题解做法差不多
我自认为球可以自己传给自己，如果错了请大佬指出来。

题目大意：

有 $n$ 个球员，每两个球员之间可以互相传球。
给定一个长度为 $n$ 的数组 $a$，$a_i$ 代表第 $i$ 个球员传球次数。
问最少有多少个球。

题目分析：

模拟一下，可以发现第个球员可以消掉 $a_i \cdot 2$ 个传球次数（其中 $a_i$ 个球是消掉自己的传球次数，另外 $a_i$ 个球是消掉别人的传球次数）。
也就是说，让他们互相抵消就行了，一对球员互相消完之后再传给下一个球员继续。最后如果只剩下了一个球员没有消完，假设这个球员还剩下 $x$ 个球，那么再拿来 $x$ 个球，自己传给自己就行了。
最后方法就是：

1. 定义一个变量 $imax$ 代表 $a$ 数组中所有元素的最大值。
2. 定义一个变量 $cnt$ 代表 $\Sigma^{n}_{i} a_i$
3. 如果 $imax \cdot 2 \le cnt$，那么只需要一个球，原因是模拟让一个球员去消掉别的所有球员的传球次数的情况，如果自己会被消掉，说明所有球员一定可以通过某种方案互相消掉。
4. 如果 $imax \cdot 2 \ge cnt+1$，那么需要 $imax \cdot 2 - cnt$ 个球，原因是模拟让一个球员去消掉别的所有球员的传球次数的情况，如果自己不会被消掉，说明无论如何一定不能只通过一个球，使所有球员互相消掉。需要引入 $imax \cdot 2 - cnt$ 个球使得最后剩下没被消掉的球员通过自己传给自己把自己传球次数消掉。

注：
需要判断所有球员传球次数都为 $0$ 的情况。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
int t,n;
const int maxn=1e5+5;
typedef long long ll;\/\/hacker造出了爆int的数据！
int a[maxn];
ll cnt=0;
int imax;
bool flag;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        flag=1;
        scanf("%d",&n);
        imax=-1;
        cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            imax=max(imax,a[i]);
            cnt+=(ll)a[i];
            flag&=(a[i]==0);
        }
        if(flag)
        {
            printf("0\n");
            continue;
        }
        if(((ll)imax<<1)<=cnt)
        {
            printf("1\n");
        }
        else{
            printf("%lld\n",(ll)(imax<<1)-cnt);
        }
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-12 10:55:50

Day -3

知道了这个比赛

Day -2

知道了这个比赛可以组团打，可以看到团内别人的代码

Day 0

加入了 sjn 的团队

Day 1

比赛开始前一个小时去看了一下团队状态，结果居然还没有下发比赛用户名和密码，过了半个小时实在忍不住发了个帖问正常吗，然而刚发帖，团队就收到了用户名密码............
比赛开始前2min，先把代码框架打好，静等开始。
开始先开A题，发现是让求一个最小生成树，但是节点数量不确定。想了20min之后放弃。开B题，什么东西啊，不会！一直开到K题，K题以前不是特别难写的模拟，就是不可做的数论。
K题是个大模拟，虽然也很难，但只剩下K题可做了，于是想了1h的K题，不会！完了，要爆零了。但这是清华出的题，爆零也不是特别不可接受。之后的1h我不停的在A题和K题之间摇摆。K题想到了一个想法，它是对的，但是我一直都没有看到题目中的 ${A_i}j \le {A_i}{j-1}$，导致一直没写。
比赛过去了3h，我连一行代码都没写，感觉彻底废了。反正是组团比赛，那就去看看别人的思路，结果直接会了......
然后开始码，码了20min完成，一测样例，爆炸。检查一下发现把两个变量搞反了，调整一下，样例又炸了。我感到十分奇怪，怎么都找不出错了。输了一下中量，发现居然是对的。再看一下输出，好家伙我把输出写错了，改正之后过了样例。
交上去，RE了？？？！！！同时发现队友的提交也RE了，可是题目说数据范围 $n \le 50$，数组够大了啊，我试一试如果把数组开到 5000 行不行，结果.............直接过了！就这样避免了爆零的悲惨结局。
我AC之后发现队友居然又交了一遍这道题，而且没过，不过还好没因此多吃罚时。

我所在团队最后结果：AC一道题，排名541st，估计晋级没戏了