这次的题有点神了，除了签到题纯白给，其他题至少关联两三个知识点，最短路径扯到二分图，还有模运算扯到逆元的。。。

探索到一半道心破碎了，不用提示真的打不动，但是用了AI提示解题，或多或少有点不好意思。。。你说这是我真实水平吧也不是，但是我确实学懂了这题。当然，只会CV然后被ban的，也是神仙了。

综上我觉得用难度系数可以评定，如果难度系数大于5，就不是一个非集训队能做出来的东西。也不需要理解的太深，因为根本没法理解。。。

然后里面包含一些仍然未解出来的题目，请见谅，我的思路过程都在上面，但是解不出是能力问题。至于为什么解不出还给它评分：因为很多人做出来了。。。

---

A题 难度系数：七星 知识点：递归+递推

我先复习了一下汉诺塔问题。老是忘老是忘，其实就是还没有根本性的理解递归。

#include<iostream>
#define i64 long long
using namespace std;
i64 n;
void hanoi(i64 n,char A,char B,char C);
int main(){
	cin>>n;
	hanoi(n,'A','B','C');
	return 0;
}
void hanoi(i64 n,char A,char B,char C){
	if(n==1){
		cout<<A<<"->"<<C<<endl;
		return ; 
	}
	hanoi(n-1,A,C,B);//先A通过C转到B 
	cout<<A<<"->"<<C<<endl;//然后A最底下的转到C 
	hanoi(n-1,B,A,C);//然后B的所有东西都转到C 
	return ;
}

然后tmdG老师的回答给我看笑了，人在什么都看不懂的情况下是真的会笑。

询问了四次，到这里我就理解到了，通过后面带的0的数量可以把开局的数确定掉。

我居然看懂了？

然后代码实现还有个小瑕疵：

#include<iostream>
#define i64 long long
using namespace std;
i64 q,n,len=0,op=0,t=1;
char shun[3]={'A','B','C'},ni[3]={'A','C','B'};
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>q;
	while(q--){
		cin>>n>>s;
		op=0,t=0;
		len=s.length();
		for(i64 i=len-1;i>=0&&s[i]=='0';i--){
			op++;
		}
		op++;
		for(i64 i=0;i<=len-op;i++){
			t=((t<<1)+(s[i]-'0'))%6;
		}
		i64 tmp=0;
		if(t==5) tmp=2;
		else if(t==3) tmp=1;
		else if(t==1) tmp=0;
		//cout<<op<<' '<<t<<endl;
		 
		if(op%2==n%2){
			cout<<ni[tmp]<<' '<<ni[(tmp+1)%3]<<endl; 
		}else{
			cout<<shun[tmp]<<' '<<shun[(tmp+1)%3]<<endl; 
		}
	}
	return 0;
}

B题 难度系数：一星 知识点：for循环

C题 难度系数：四星 知识点：大根堆小根堆

这是除了B签到最简单的一题。

用快速排序是不行的，会TLE。

但是你如果维护两个堆，一个从小往大排，一个从大往小排，那么他们的队列顶部top值就是整个队列最中间的两个元素，中间偏左的当然就是大根堆里的啦。

#include<iostream>
#include<vector>
#include<queue>
#define i64 long long
using namespace std;
i64 q,x;
char ch;
priority_queue<i64, vector<i64>, less<i64> > big;
priority_queue<i64, vector<i64>, greater<i64> > small;
int main()
{
	cin>>q;
	for(i64 i=1;i<=q;i++){
		cin>>ch;
		if(ch=='+'){
			cin>>x;
			if(big.empty() || x<=big.top()){
				big.push(x);
			}
			else{
				small.push(x);
			}
			
			if(big.size()>small.size()+1){
				//大根堆跑小跟堆
				i64 tmp=big.top();
				small.push(tmp);
				big.pop();
			}
			else if(small.size()>big.size()){
				//小跟堆跑大根堆 
				i64 tmp=small.top();
				big.push(tmp);
				small.pop();
			}
		}	
		else{
			cout<<big.top()<<endl;
		}
	}
	return 0;
}

D题 难度系数：四星 知识点：区间DP

之前练过一堆的dp题，这次很显然看出了门道。

https://blog.csdn.net/xinghuayu_lin/article/details/155207032

但是输在不知道怎么做初始化上。还是需要AI提示。

这题的突破口在于时间，你可能觉得这是慢慢卖出去，区间缩小的过程，但是如果说逆着看当成一个区间放大的问题呢？那就好办了。

初始化，所有的dp[i][i]都等于a[k]*n，也就是假设自己是最后卖出的装备。

然后做两个for循环，第一个是长度，第二个是左边界，从而能确定右边界和天数两个参数。

那么状态转移方程就是dp[l][r]=max(dp[l][r-1]+a[r]*times, dp[l+1][r]+a[l]*times);

#include<iostream>
#define i64 long long
using namespace std;
i64 n,a[5005],dp[5005][5005];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	for(i64 i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(i64 i=1;i<=n;i++){
		dp[i][i]=a[i]*n;
	}
	for(i64 len=2;len<=n;len++){
		i64 times=n-len+1;
		for(i64 l=1;l+len-1<=n;l++){
			i64 r=l+len-1;
			dp[l][r]=max(a[l]*times+dp[l+1][r],a[r]*times+dp[l][r-1]);
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}

妈的，区间dp在这次比赛都算是个萝莉题。

E题 难度系数：六星 知识点：双指针+单调队列

AI告诉我，把问题转化成这样：

第一，无重复，第二，最大值等于子长度数组。

所以双指针就来了，这个时间复杂度压缩到O(1)，太强大了。

操作思路是：开一个计数cnt数组和一个dup标志状态，这个是为了遍历，如果cnt>=2说明数组内部存在重复，那么dup++。遇见了重复值就需要立马处理：l下标右移。但是仅仅改变l下标还不够。我们还要讨论一部分情况。

现在要用到一个队列deque，它与queue的区别在于队首队尾都能出去。dq是存放a数组的下标！下标！下标！不是值。我们要的是能立马观察和操作下标对应的值。

现在，我们遍历右指针r，那么：如果这个a[r]比进队里面的尾巴元素大，那么就要出队尾，知道没有为止。这就是单调队列。这里保证了在某个范围（就是在上一个下标的后面），a[r]是这一块的最大值。

然后来处理dup的值和cnt的值。如果dup>0，那么重复，如果a[dq.front()]>r-l+1，也就是最大值超过了长度len，那么不满足上面的条件2，也得出队。

出队：cnt[l]--，最左边不在队列了，那么计数清回去。如果在之前cnt[l]>=2，那么dup--，就不会重复了。如果dq.front()==l，也就是l到r这一段的最大值的下标位于l处，由于最大值要被移出去了，那么队首也要跟着出队。

最后就是l++。

神奇吧？

然后调试代码半天，死在了这里：while(dup>0||(!dq.empty()&&a[dq.front()]>r-l+1))，这个a[]可能导致，3 1 2 4的序列，你3入队之后发现自己比自己大，然后出队了。。。

好的，现在进入到了一个非常怪异的圈：

给两组例子

7

7 1 2 3 4 5 6

7

7 1 2 3 4 5 7

。。。我放弃了好吧，残废代码在这

#include<iostream>
#include<deque>
#define i64 long long
using namespace std;
i64 n,ans=0,l=1,dup=0;
i64 a[10005],cnt[10005];
deque<i64> dq;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(i64 i=1;i<=n;i++){
		cin>>a[i]; 
	}
	for(i64 r=1;r<=n;r++){
		cnt[a[r]]++;
		if(cnt[a[r]]==2)
			dup++; 
		
		while(!dq.empty()&&a[dq.back()]<a[r]){
			dq.pop_back();//在这里需要加进a[r]单调减，尾巴更小的出队
		}
		dq.push_back(r);
		//cout<<r<<' '<<dq.front()<<' '<<dq.back()<<endl;
		while(dup>0){
			//(!dq.empty()&&a[dq.front()]>r-l+1)
			//现在l要右移，之前跟着的dup状态量也得变化
			//cout<<dq.front()<<endl;
			if(cnt[a[l]]==2)
				dup--;
			cnt[a[l]]--;
			if(!dq.empty()&&dq.front()==l){
				dq.pop_front();
			}
			//cout<<"他妈的出队情况"<<dq.empty()<<' '<<dq.front()<<endl; 
			l++;
		}
		if(!dq.empty()&&a[dq.front()]==(r-l+1)){
			ans=max(ans,r-l+1);
			//cout<<l<<' '<<r<<' '<<ans<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}
/*6
7 1 2 3 4 5*/

F题 难度系数：？？？ 知识点：线性代数

请输入文本。屁都看不懂。

各位自行阅读吧，反正我理解不了。也不打算理解了。

G题 难度系数：九星 知识点：计算几何+剪枝+组合数+模逆元+快速幂

这是一道看似人畜无害，做起来细思极恐的题目。

这题题面比较好理解，就是一个几何题：走路只能斜上或者斜下，然后求多少种不经过x轴的可能性。那么模拟吗少年？这个答案取模给你开玩笑呢？

我们先剪枝排除一些情况：

x2<x1的排除；y2-y1绝对值比x2-x1还大的排除；y2y1有一个以上在x轴排除；y2与y1异号排除。

在这里就可以摸索出一点端倪：x2-x1可以表示“微信步数”，那么y1到y2实际上就是若干次上下分的组合作用了。（此时还有个地方可以剪枝：x2-x1+y2-y1必然是偶数）

那么这个题要求的就是：无约束减去碰到x轴的

无约束的意思很明确。但是碰到x轴的怎么算，就很巧妙了。

好的，当你成功地走到这一步，代码应该是这样的。

#include<iostream>
#include<cmath>
#define mod 998244353
#define i64 long long
using namespace std;
i64 t,xa,ya,xb,yb,ans=0;
i64 C(i64 n,i64 k);
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	while(t--){
		ans=0;
		cin>>xa>>ya>>xb>>yb;
		if(xb<xa){
			cout<<0<<endl;
			continue;
		}
		if(ya<=0||yb<=0){
			cout<<0<<endl;
			continue;
		}
		
		i64 dx=xb-xa;
		i64 dy=yb-ya;
		
		if(abs(dy)>dx){
			cout<<0<<endl;
			continue;
		}
		
		if((dx+dy)%2==1){
			cout<<0<<endl;
			continue;
		}
		
		i64 k1=(dx+dy)/2,k2=(dx+ya+yb)/2;
		ans=C(dx,k1)-C(dx,k2);
		
		cout<<ans<<endl;
	}
	return 0;
}
i64 C(i64 n,i64 k){
	if(k>n||k<0) return 0;
	else{
		i64 res=1;
		for(i64 i=n;i>=n-k+1;i--){
			res=(res*i)%mod;
		}
		for(i64 i=k;i>=1;i--){
			res=(res/i)%mod;
		}
	}
}

但是会发现，远远没完。第一，组合数计算会TLE，第二，能算出来的组合数也是错的。

为什么？还记得模的运算规则吗？离散数学表示我来了，在模运算的前提下，除法是错误的。

所以可以得出一点：我们先提前把每个阶乘的值及其逆元值计算出来，然后查表

C(n,k) = fact[n] * invfact[k] % mod * invfact[n-k] % mod

这个思路太牛逼了，山路十八弯。

但是预处理阶乘和逆阶乘为什么这么操作呢？为什么invfact是从上往下推导的呢？

本人不才，决定不靠AI，自己动手推导一遍

数学上的推导真是能满足人的高级情感需求！！！

所以我们只需要借助快速幂，算第一个inv，剩下的都能自动出来。

#include<iostream>
#include<cmath>
#define mod 998244353
#define i64 long long
using namespace std;
i64 t,xa,ya,xb,yb,ans=0;
i64 fact[200005],inv[200005];
i64 C(i64 n,i64 k);
void init();
i64 quickpower(i64 a,i64 b);
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>t;
	init();
	while(t--){
		ans=0;
		cin>>xa>>ya>>xb>>yb;
		if(xb<xa){
			cout<<0<<endl;
			continue;
		}
		if(ya==0||yb==0){
			cout<<0<<endl;
			continue;
		}
		if((ya<0&&yb>0)||(ya>0&&yb<0)){
			cout<<0<<endl;
			continue;
		}
		
		i64 dx=xb-xa;
		i64 dy=yb-ya;
		
		if(abs(dy)>dx){
			cout<<0<<endl;
			continue;
		}
		
		if((dx+dy)%2==1){
			cout<<0<<endl;
			continue;
		}
		
		i64 k1=(dx+dy)/2,k2=(dx+ya+yb)/2;
		ans=C(dx,k1)-C(dx,k2);
		if(ans<0)
			ans+=mod;
		cout<<ans<<endl;
	}
	return 0;
}
i64 C(i64 n,i64 k){
	if(k>n||k<0) return 0;
	else{
		i64 res=1;
		res=(((fact[n]*inv[k])%mod)*inv[n-k])%mod;
		return res;
	}
}
i64 quickpower(i64 a,i64 b){
	i64 r=1;
	while(b){
		if(b%2==1) r=(r*a)%mod;
		a=(a*a)%mod;
		b/=2;
	}
	return r;
}
void init(){
	fact[0]=1;
	for(i64 i=1;i<=200000;i++){
		fact[i]=(fact[i-1]*i)%mod;
	}
	inv[200000]=quickpower(fact[200000],mod-2);
	for(i64 i=200000;i>=1;i--){
		inv[i-1]=(inv[i]*i)%mod;
	}
	return ;
}

H题 难度系数：？？？ 知识点：计数组合

我不知道这题有多难，因为我看不懂。

人在太菜的时候是真的会把自己菜笑的，我看到这题的解析就是这样，从f(n,k)这里往下一步都看不懂。

I题 难度系数：七星 知识点：BFS、虚拟点、带权图

题目名为“火车站2”

这道题一眼看过去，哎，你终于会啦！但是这个集合AB的数据怎么给的这么怪啊，不管了上dfs！

喜提内存爆炸。

所以说这次校赛最杀人诛心的是，你一个屁都不会的算法萌新和一个勤奋练习过一点算法的同学是一样的结果——都是0分。。。因为每个题考的都不止一个点，那咋打？

说人话，虚拟点就是在二分图中间引入一个点，起名n+1往上。

现在的问题是：虚拟点会不会重复利用？二分图会不会翻倍计数？

虚拟点用一次就没，不会重复利用。bfs就类似遍地开花，你从其他地方走过来了一次，接下来所有的点都给你开放了。

如果没有虚拟节点：从上半区到上半区他需要走2次，从上半区到下半区只要走1次。但是如果有了bfs，那么无差别走两次。

我在这里问爆了GPT，问了半小时才问出来一个东西：01带权。

但是这个带权也是错的呀？

A集合到A集合长度2，B集合到B集合长度2，AB互通长度1，但是实际上按照上面的结果，同一个集合之内的距离是1，算不对。

再经过一段时间的折磨之后，我灵光一现：

然后再次喜提WA。几个人机不约而同的理解不到我的精髓，觉得-1会出事。

我反驳：这个所谓的-1一定是会消掉的大哥，这完全就是两个辅助节点，你怕啥。

#include<iostream>
#include<vector>
#include<queue>
#define i64 long long
using namespace std;
i64 n,m,qu,x,vir,ans[1000005]={0};
i64 anum,bnum,a[1000005]={0},b[1000005]={0};
bool s[1000005];
vector<pair<i64,i64> > g[1000005];
queue<i64> q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>qu;
	vir=n;
	for(i64 j=1;j<=m;j++){
		//j套数据 
		cin>>anum;
		for(i64 i=1;i<=anum;i++){
			cin>>a[i];
		}
		cin>>bnum;
		for(i64 i=1;i<=bnum;i++){
			cin>>b[i];
		}
		 
		vir++;
		
		for(i64 i=1;i<=anum;i++){
			g[a[i]].push_back({vir,1});
			g[vir].push_back({a[i],1});
		}
		
		vir++;
		
		for(i64 i=1;i<=bnum;i++){
			g[b[i]].push_back({vir,1});
			g[vir].push_back({b[i],1});
		}	
		g[vir].push_back({vir-1,-1});
		g[vir-1].push_back({vir,-1});
	}
	
	i64 len=1;
	q.push(1);
	s[1]=1;
	while(!q.empty()){
		i64 lst=q.front();
		q.pop();
		for(i64 i=0;i<g[lst].size();i++){
			i64 nxt=g[lst][i].first;
			i64 len=g[lst][i].second;
			
			if(s[nxt]==1) continue;
			
			s[nxt]=1;
			ans[nxt]=ans[lst]+len;//ans[1]=0默认 
			q.push(nxt);
		}
	}
	
	while(qu--){
		cin>>x;
		if(s[x]==0)
			cout<<-1<<endl;
		else
			cout<<ans[x]<<endl;
	}
	return 0;
}

不管怎么样WA了。

然后我给GPT试最后一次机会，他告诉我，用两个虚拟点，做单向图。单向图我懒得再解释怎么实现了，这真的给我恶心到了。

仍然WA，遂放弃。

代码半成品：

#include<iostream>
#include<vector>
#include<queue>
#define i64 long long
using namespace std;
i64 n,m,qu,x,virA,virB,ans[1000005]={0};
i64 anum,bnum,a[1000005]={0},b[1000005]={0};
bool s[1000005];
vector<pair<i64,i64> > g[1000005];
queue<i64> q;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m>>qu;
	virA=n,virB=2*n;
	for(i64 j=1;j<=m;j++){
		//j套数据 
		cin>>anum;
		for(i64 i=1;i<=anum;i++){
			cin>>a[i];
		}
		cin>>bnum;
		for(i64 i=1;i<=bnum;i++){
			cin>>b[i];
		}
		//单向行动总可以了吧tmd 
		virA++;
		for(i64 i=1;i<=anum;i++){
			g[a[i]].push_back({virA,0});
		}
		for(i64 i=1;i<=bnum;i++){
			g[virA].push_back({b[i],1});
		}	
		
		virB++;
		for(i64 i=1;i<=anum;i++){
			g[b[i]].push_back({virB,0});
		}
		for(i64 i=1;i<=bnum;i++){
			g[virB].push_back({a[i],1});
		}	

	}
	
	i64 len=1;
	q.push(1);
	s[1]=1;
	while(!q.empty()){
		i64 lst=q.front();
		q.pop();
		for(i64 i=0;i<g[lst].size();i++){
			i64 nxt=g[lst][i].first;
			i64 len=g[lst][i].second;
			
			if(s[nxt]==1) continue;
			
			s[nxt]=1;
			ans[nxt]=ans[lst]+len;//ans[1]=0默认 
			q.push(nxt);
		}
	}
	
	while(qu--){
		cin>>x;
		if(s[x]==0)
			cout<<-1<<endl;
		else
			cout<<ans[x]<<endl;
	}
	return 0;
}

G题 难度系数：？？？ 知识点：双指针+DP

好了，校赛就这么结束了，博主打不动了。。。

希望线下赛除了签到题不要爆零。。。