本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-02 16:18:45

得分

只有第三题得了 75 分……

T1

考场上写的超级暴力的暴力，然后 0 分。

正解

首先考虑最后形成的数组，从最小值看起，发现只有有奇数个的时候先手必胜，所以可以用异或统计出是否是先手必胜。

对于两个点之间的路径，直接暴力的统计他们之间的路径是会超时的，所以可以发现。

本图意为从（5,6）之间的路径，（1,2）之间的路径重复两次，所以正好抵消。

如图的两个路径，从根节点到分叉点的路径相同，也就是说，在异或时正好可以抵消掉，并不会影响结果。剩下的就是原本的路径。所以可以一开始预处理出根节点到所有点的路径权值异或和。

最后用所有方案数减去权值向同的点之间的方案数，即为答案。

代码

#include<bits\/stdc++.h>
#define int long long
using namespace std;
inline long long read() {
	long long s = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(long long x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x \/ 10);
	putchar(x % 10 + '0');
}
int ds[500005];
int n,t;
struct nd{
	int y,z;
};
vector<nd> v[500005];
void dfs(int x,int fa){
	for(int i=0;i<v[x].size();i++){
		if(v[x][i].y==fa) continue;
		ds[v[x][i].y]=ds[x]^v[x][i].z;
		dfs(v[x][i].y,x);
	}
}
map<int,int> vis,tong,mp,ul;
int r;
signed main() {
	srand(time(0));
	int t;
	mp[0]=1;
	cin>>t;
	for(int i=1;i<=500000;i++){
		mp[i]=mp[i-1]*13331;
	}
	while(t--){
		vis.clear();
		tong.clear();
		cin>>n;
		for(int i=1;i<=n;i++) v[i].clear();
		for(int i=1;i<=n;i++) ds[i]=0;
		for(int i=1,x,y,z;i<n;i++){
			cin>>x>>y>>z;
			if(ul[z]==NULL) {
				ul[z]=++r;
			}
			z=ul[z];
			z=mp[z];
			v[x].push_back({y,z});
			v[y].push_back({x,z});
		}
		dfs(1,1);
		int ans=(n-1)*n\/2;
		for(int i=1;i<=n;i++){
			ans-=tong[ds[i]];
			tong[ds[i]]++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

T2

虽然理解了题意，但是没有听懂……

T3

考场写的还行，能得到 75 分，全是ifelse。

做法

首先把 1 和 2，先结合。如果剩下得到是2，就让2自己结合，之后再把 2 与 3 结合或者用 4 去补充，否则就把 1 与自己结合，剩下的与 3 结合，或者用 4 去补充它。

代码

#include<bits\/stdc++.h>
using namespace std;
inline long long read() {
	long long s = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(long long x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x \/ 10);
	putchar(x % 10 + '0');
}
int a[5],n;
int main() {
	while(cin>>n){
		int ans=0;
		a[1]=a[2]=a[3]=a[4]=0;
		for(int i=1;i<=n;i++) a[read()]++;
\/\/		if(a[1]+a[2]+a[2]+a[3]*3+a[4]*4==4||a[1]+a[2]+a[2]+a[3]*3+a[4]*4<3||a[1]+a[2]+a[2]+a[3]*3+a[4]*4==5) {
\/\/			cout<<-1<<"\n";
\/\/			continue;
\/\/		}
		if(a[1]>a[2]){
			ans+=a[2];
			a[1]-=a[2];
			a[3]+=a[2];
			a[2]=0;
			while(a[1]>=3) {
				ans+=2;
				a[1]-=3;
				a[3]++;
			}
			if(a[1]>a[3]) a[1]-=a[3],ans+=a[3],a[4]+=a[3],a[3]=0;
			else a[3]-=a[1],ans+=a[1],a[4]+=a[1],a[1]=0;
			while(a[1]&&a[4]>=2) a[4]-=2,a[1]--,a[3]++,ans+=2;
			if(a[1]) ans=-1;
		}
		else {
			ans+=a[1],a[2]-=a[1],a[1]=0;
			while(a[2]>=3) a[2]-=3,a[3]+=2,ans+=2;
			while(a[4]&&a[2]) a[4]--,a[2]--,a[3]++,ans++;
			if(a[2]==2) a[2]=0,a[4]++,ans+=2;
			while(a[2]&&a[3]>=2){
				a[3]-=2,a[4]+=2,a[2]--,ans+=2;
			}
			if(a[2]) ans=-1;
		}
		write(ans);
		putchar('\n');
	}
	return 0;
}

T4

考场本来写的是 O（qn） 复杂度的算法，但是不知到为什么，set里面总会少 6 这个数，所以直接 0 分。

我预想的做法

模拟修改的阶段，之后枚举三元组的中间值，用两个 set 维护所枚举到的当前的位置左右两边的值。

错误代码

（不知道有没有好心人帮我看看哪里写错了）

#include<bits\/stdc++.h>
using namespace std;
inline long long read() {
	long long s = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(long long x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x \/ 10);
	putchar(x % 10 + '0');
}
int n,l,r,k,q,a[1000005];
int b[1000005];
int main() {
\/\/	freopen("circulate.in","r",stdin);
\/\/	freopen("circulate.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>l>>r>>k;
		for(int j=l;j<=r;j++){
			if(j+k>r){
				b[j+k-r-1+l]=a[j];
			}
			else {
				b[j+k]=a[j];
			}
		}
		for(int j=l;j<=r;j++) a[j]=b[j];
		set<int> s,ss;
		for(int j=1;j<=n;j++) s.insert(a[j]);
		ss.insert(a[1]);
		s.erase(a[1]);
		int flag=0;
		cout<<s.count(6); 
		for(int j=2;j<n;j++){
			s.erase(a[j]);
			if(*ss.begin()<a[j]&&*s.end()>a[j]){
				flag=1;
				break;
			}
			ss.insert(a[j]);
			
		}
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}