本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-23 12:37:40

思路

用动态数组记录下所有的字母的位置，每一次搜索到的字符都从记录的下标中找到距离最小的字符（直接循环遍历），如果没有记录就加上 $S$ 的长度。

超级简单的代码

主函数前三行没有太大用处可以不写。

#include<bits\/stdc++.h>
using namespace std;
string c;
vector<int> v[1005];
int n,m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	cin>>c;
	for(int i=0;i<c.size();i++)v[c[i]-'a'].push_back(i);
	while(n--){
		long long ans=0;
		string s;
		cin>>s;
		for(int i=0;i<s.size();i++){
			int minn=0x3f3f3f3f;
			if(v[s[i]-'a'].size()==0){
				ans+=s.size();
				continue;
			}
			for(int j=0;j<v[s[i]-'a'].size();j++){
				minn=min(minn,abs(v[s[i]-'a'][j]-i));
			}
			ans+=minn;
		}
		cout<<ans<<"\n";
		ans=0;
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-23 13:51:07

分析亿下

数组需要开很大所以不能开二维数组，询问的次数很多，所以不能通过遍历去求和。

打个表可以发现在原始状态下，第 $i$ 行或列的值为：

n*i+n*(n+1)\/2

所以每一行或列的值都是固定的，那么就只需要统计出减少的值。模拟一下可以发现，每一次行的减少，会对所有的列减少当前的行数加上这一列的列数，所以就可以用一个变量统计下所有行减少的当前行数，在统计一下一共减去了多少行，再在输出时将它乘上当前的列数。列的算法同样如此。

重点（代码）

#include<bits\/stdc++.h>
using namespace std;
long long n,q,C,R,sumr,sumc,visr[1000005],visc[1000005];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;i++) {
		char s;
		int x;
		cin>>s>>x;
		if(s=='R'){
			if(visr[x]){
				cout<<0<<'\n';
				continue;
			}
			cout<<n*(n+1+2*x)\/2-sumc*x-R<<"\n";
			visr[x]=1;
			C+=x;
			sumr++;
		}
		else {
			if(visc[x]){
				cout<<"0\n";
				continue;
			}
			cout<<n*(n+1+2*x)\/2-sumr*x-C<<"\n";
			visc[x]=1;
			R+=x;
			sumc++;
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-08-28 20:06:43

骗分还得是模拟退火

思路

了解了模拟退火算法后，本题几乎成为了一道板子题，但是还有一些细节需要去解决一下。

模拟退火算法本来是用来求最值的，所以对于本题来说其中退火的环节确实有点多余，所以我们为了本人更好地偷懒解法的正确性，我们要舍去多余的退火。

舍去了退火之后会发现，如何解决是否交换的问题呢？其实只需要全部交换就可以了，因为异或这种运算没什么太大的规律。

之后是我们总体的思路，首先预处理一下要用的 $lg$ 数组，然后对于每一个 $n$ 准备好的原数组和它的前 $m$ 个异或和，还有要比较的数。之后跑模拟退火直到出结果或者无解就好了。

更多的代码细节还是直接看代码吧。

Code

#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 flag=0,lg[1000005];
int a[1000005],n,m,t,pos=1,sum;
void SA(){
	for(int i=1;i<=10000;i++){
		int l=rand()%m+1,r=m+rand()%(n-m)+1;
		sum^=a[l];
		sum^=a[r];
		swap(a[l],a[r]);
		if(sum==pos){
			flag=1;
			return ;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(0));
	cin>>t;
	for(int i=1;i<=1000000;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	while(t--){
		cin>>n>>m;
		if(n==m){
			for(int i=1;i<=n;i++) a[i]=i;
			flag=sum=0;
			for(int i=1;i<=m;i++) sum^=i;
			pos=1;
			for(int i=1;i<=lg[n];i++) pos*=2;
			pos--;
			if(sum==pos) {
				for(int i=1;i<=n;i++) cout<<i<<" ";
				cout<<"\n";
				continue;
			}
			else {
				cout<<"-1\n";
				continue;
			}
		}
		for(int i=1;i<=n;i++) a[i]=i;
		flag=sum=0;
		for(int i=1;i<=m;i++) sum^=i;
		pos=1;
		for(int i=1;i<=lg[n];i++) pos*=2;
		pos--;
		for(int i=1;i<=90;i++){
			SA();
			if(flag){
				for(int j=1;j<=m;j++){
					cout<<a[j]<<" ";
				}
				cout<<"\n";
				break;
			}
		}
		if(!flag){
			cout<<"-1\n";
		}			
	}
	return 0;
}

温馨提示

本代码不一定可以一遍过，如果答案错误的话，多提交几遍就可以了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-03 09:28:41

前置知识

首先看到要取出最小值，那么一定就是优先队列了。

优先队列

思路

由于输出的是最小值，所以我们要用到的是小根堆，定义有稍许不同。

priority_queue<int,vector<int>,greater<int>>q;

解决了优先队列看到他还有修改操作，要是整体修改肯定是会超时的，所以我们可以想到一个类似于前缀和的算法。

如果把每一次添加的数当做一个数组，那么我们可以得出一个数所增加的值一定是它添加之后增加的数到他取出前的数的前缀和，那么我们可以找到规律，如果一个数添加上目前增加的所有的数，那么它比真正的值所大的就是他之前的数的总和，那么由此我们可以判断出，每一次添加一个数的时候，我们可以添加这个数减去之前增长的值，这样一来可以快速记录当前的值，同时我们也更好地维护优先队列中数的顺序。（如果没有看懂就看代码吧）

CODE：

#include<bits\/stdc++.h>
using namespace std;
\/\/十年OI一场空，不开long long见祖宗 
priority_queue<long long,vector<long long>,greater<long long>> q;
long long cnt,n,x;\/\/cnt统计一共加了多少数 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	\/\/前三行是加快cincout速度的
	\/\/本人懒得写scanf与快读 
	cin>>n;
	for(int i=1,h;i<=n;i++){
		cin>>h;
		if(h==1){
			cin>>x;
			q.push(x-cnt);
		}
		else if(h==2){
			cin>>x;
			cnt+=x;
		}
		else {
			cout<<q.top()+cnt<<"\n";
			\/\/换行使用'\n'速度更快 
			q.pop();
		}
	}
	return 0;
	\/\/return 0;是好习惯 
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-05 22:55:34

看到好多大佬都在写，我也来写一发

根据其他大佬的思路，我们可以想到用以下字符串作为基本串。

ccccccccccccccccccccc……

之后我们要找到一个等价于相同长度连续 $c$ 的字符串，那么首先就可以找到 $dD$。

过程： $c$ 的值是 $99$，所以 $cc$ 的贡献是 $99×31+99×1=3168$，而我们可以通过写一个暴力代码求出与他相同的字符串：

for(char i='a';i<='z';i++){
	for(char j='A';j<='Z';j++){
		if(i*31+j==3168){
			cout<<i<<j<<endl;
		}
	}
	for(char j='a';j<='z';j++){
		if(i*31+j==3168){
			cout<<i<<j<<endl;
		}
	}
}
for(char i='A';i<='Z';i++){
	for(char j='A';j<='Z';j++){
		if(i*31+j==3168){
			cout<<i<<j<<endl;
		}
	}
	for(char j='a';j<='z';j++){
		if(i*31+j==3168){
			cout<<i<<j<<endl;
		}
	}
}

之后我们就要想办法构造出每一种的字符串。可以发现总共 $n$ 的值与最长的字符串的值相同，所以我们可以按照 $n$ 的大小构造字符串的长度。然后把所有的字符串每一次选取两个字符修改为 $dD$，在输出。为了防止越界，需要把 n==1000 时字符串的长度控制在规定长度内，然后剩下的输出一个含有两个 $dD$ 的字符串即可。

CODE：

#include<bits\/stdc++.h>
using namespace std;
string c;
int n;
int main(){
	cin>>n;
	for(int i=0;i<n+1;i++) c+="c";
	if(n==1000){
		c=c.substr(0,1000);
		printf("dDdD");
		for(int i=5;i<=1000;i++) putchar('c');
		putchar('\n');
	}
	for(int i=1;i<=999*(n==1000)+n*(n!=1000);i++){
		string s=c;
		s[i-1]='d';s[i]='D';
		cout<<s<<"\n";
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-19 21:53:08

优先队列与动态数组！

首先我们看到了第三种操作，需要我们输出最大的数的最早的插入位置。最大我们不免想到可以用优先队列也就是堆，最早又可以想到动态数组 vector，所以我们就可以得出两者相结合的方法完成第三种操作。

之后第二种操作就显得简单了许多，大家都知道队列的特点是先进先出，正好可以做到把先插入的先删除。

十分详细的代码：

#include<bits\/stdc++.h>
using namespace std;
queue<int> q1;
priority_queue<int> q2;
vector<int> v[1000005];
int a[1000005],vis[1000005],cnt;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1) {
			int m;
			cin>>m;
			a[++cnt]=m;
			q1.push(cnt);
			q2.push(m);
			v[m].push_back(cnt);
			\/\/存储所有要用到的数据 
		}
		else if(op==2) {
			while(vis[q1.front()]) q1.pop();
			\/\/删除已经使用过的数据 
			vis[q1.front()]=1;
			cout<<q1.front()<<" ";
			q1.pop();
		}
		else{
			while(vis[v[q2.top()][0]]) v[q2.top()].erase(v[q2.top()].begin()),q2.pop();
			\/\/对于一个值找到他最早的插入时间，依然将使用过的先删除 
			vis[v[q2.top()][0]]=1;
			cout<<v[q2.top()][0]<<" ";
			v[q2.top()].erase(v[q2.top()].begin());
			\/\/vector的erase函数中填入的是元素地址 
			q2.pop();
		}
	} 
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-09-24 15:49:12

题目大意

A 题 链接

C 题 链接

在本比赛 A 题的基础上，查找第 $n$ 个符合要求的数。

模拟

根据题目我们可以找到一个暴力方法就是从头开始枚举，直到找到 $n$ 个（这样肯定会超时）。

例如 $977654321$ 这个数一定是不符合要求的，但是此时如果从个位一点点加起会稍好很多时间。所以可以看到在这个数的第二位开始就已经能判断出它不符合要求，所以我们可以用一个数组按位存储要判断的数，然后找到第一个不合法的位数，从那一位开始修改。

代码：

#include<bits\/stdc++.h>
using namespace std;
int a[15];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int cnt=1;
	a[1]=1;
	int sum=0;
	while(sum<n){
		int flag=0;
		for(int i=1;i<cnt;i++){
			if(a[i]>=a[i+1]) {
				flag=i;
				break;
			}
		}
		if(flag) {
			a[flag]++;
			for(int i=1;i<flag;i++) a[i]=0;
			while(a[flag]>=10) {
				a[flag]-=10;
				a[++flag]++;
				cnt=max(cnt,flag);
			}
			continue;
		}
		else {
			sum++;
			if(sum==n) break;
			flag=1;
			a[1]++;
			while(a[flag]>=10) {
				a[flag]-=10;
				a[++flag]++;
				cnt=max(cnt,flag);
			}
		}
	}
	for(int i=cnt;i>=1;i--) cout<<a[i];
	return 0;
}

AC截图

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

得分

得分太少，不想说了……

T1

歪解

本来想要贪心，但是自己随便写了一组数就挂了，所以了一点点 rand，自己的数据对了不少，但是好像没有得分。

正解

DP！！！

首先应该将数组排序，当只有一个或者零个数时，无法组成一组数，所以把 $dp[0][1~n]$ 和$dp[1][1~n]$ 赋成最大值。 对于 $dp[i][j]$ 有两种情况

1： 本身不被选，那么 $dp[i][j]$ 就等于 $dp[i-1][j]$。

2： 本身被选，那么 $dp[i][j]$ 就等于 $dp[i-2][j-1]$,因为与这个数最近的数一定是它的前一个，并且之前有 $j-1$ 组时才能变成 $j$ 组。

代码（正确的）：

#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 a[1000005];
int n,m;
int dp[5005][5005];
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++) dp[0][i]=0x3f3f3f3f3f3f3f3f,dp[1][i]=0x3f3f3f3f3f3f3f3f;
	for(int i=2;i<=n;i++){
		dp[i][0]=0;
		for(int j=1;j<=m;j++){
			dp[i][j]=dp[i-1][j];
			dp[i][j]=min(dp[i][j],min(dp[i-2][j-1]+a[i]-a[i-1],dp[i-1][j]));
		}
	}
	cout<<dp[n][m];
	return 0;
}

T2

错误的做法：贪心

也不知道哪里贪的不对，但是就是不对。

正确的做法：贪心

也不知道哪里贪对了，但是就是贪对了。

思路（我自己的）

大体分为两种情况。

第一种是在原先的数列中已经有了 1。这时考虑是否要把 1 提前，如果把 1 提前，那么就把 1 提前，不然就删去上升序列中的最后一个数。

第二种是在原先的队列中没有 1，那么就加上 1，然后删去上升序列中的最后一个数（如果 $n>2$，那么一定不能是 1）。

最后一步就是 WA 了。

错误的代码：

#include<bits\/stdc++.h>
#define int long long
using namespace std;
int t,n,a[2000005];
set<int> s;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n;
		int uu=0,flag=n+1;
		a[n+1]=0;
		for(int i=1;i<=n;i++) s.insert(i);
		for(int i=1;i<=n;i++){
			cin>>a[i];
			if(a[i]==1) flag=i;
			if(a[i]==0&&uu==0) uu=i;
			s.erase(a[i]);
		}
		if(s.count(1)){
			s.erase(1);
			a[uu]=1;
			for(int i=1;i<=n;i++){
				if(i==uu) continue;
				if(a[i]>a[i+1]){
					s.insert(a[i]);
					a[i]=-1;
					break;
				}
			}
		}
		else if(uu<flag&&uu!=0){
			if(a[uu-1]>*s.begin()){
				s.insert(a[uu-1]);a[uu-1]=-1;
			}
			else  {
				a[flag]=-1;
				s.insert(1);				
			}
		}
		else {
			for(int i=1;i<=n;i++){
				if(a[i+1]==0){
					if(a[i]>*s.begin()){
						s.insert(a[i]);
						a[i]=-1;
						break;
					}
				}
				else if(a[i]>a[i+1]){
					s.insert(a[i]);
					a[i]=-1;
					break;
				}
			}
		}
		int flagg=0;
		for(int i=1;i<=n;i++){
			if(flagg==0&&i==n) continue;
			if(a[i]>0) cout<<a[i]<<" ";
			else if(a[i]==0){
				cout<<*(s.begin())<<" ";
				s.erase(*(s.begin())) ;
			}
			else flagg=1;
		}
		cout<<"\n";
	}
	return 0;
}

T3

上来写了一大堆，然后样例都没有过，调了半个小时，然后还是没有过样例。

正解

好像是找到虚点所连接在集合中的点的个数，如果大于 3，就说明会出错。（还要把边权为 0 的点合并）

自己写的

先求集合中的最小生成树，再把原图中的点删除一部分，把剩下的再求一下最小生成树，比较是否相同（就是纯模拟了一遍题意）。然后就错了。

错误的代码

#include<bits\/stdc++.h>
#define int long long
using namespace std;
struct nd{
	int y,z;
};
int cnt;
struct nt{
	int x,y,z;
}s[1000005],c[1000005];
int fa[1000005],minn=0x3f3f3f3f;
vector<nd> v[105];
int a[105],n,m;
set<int> ss;
int mp[105][105];
queue<int> q;
bool cmp(nt x,nt y){
	return x.z<y.z;
}
void bfs(int r){
	q.push(r);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();i++){
			int xx=v[x][i].y;
			if(xx==r||mp[r][xx]) continue;
			mp[r][xx]=mp[r][x]+v[x][i].z;
			q.push(xx);
		}
	}
}
int find(int x) {
	while (x != fa[x]) x = fa[x];
	return x;
}
int kruskal(){
	int sum=0,t=0;
	for(int i=1;i<m;i++){
		s[++cnt]={mp[a[m]][a[i]],a[m],a[i]};
	}
	sort(s+1,s+1+cnt,cmp);
	for(int i=1;i<=n;i++) {
		fa[i]=i;
	}
	for(int i=1;i<=cnt;i++){
		int fx=find(s[i].x),fy=find(s[i].y);
		if(fx!=fy){
			fa[fy]=fx;
			sum+=s[i].z;
			++t;
			if(t==m-1) break;
		}
	}
	return sum;
}
int kruskals(){
	int cntt=0;
	for(auto i:ss){
		for(int j:ss){
			c[++cntt]={mp[i][j],i,j};
		}
	}
	int sum=0,t=0;
	sort(s+1,s+1+cnt,cmp);
	for(int i=1;i<=n;i++) {
		fa[i]=i;
	}
	for(int i=1;i<=cntt;i++){
		int fx=find(c[i].x),fy=find(c[i].y);
		if(fx!=fy){
			fa[fy]=fx;
			sum+=c[i].z;
			++cnt;
			if(t==m-1) break;
		}
	}
	return sum;
}
void match(int x){
	if(x==n+1) return ;
	minn=min(minn,kruskals());
	for(int i=x+1;i<=n;i++){
		if(ss.count(i)) continue;
		ss.insert(i);
		match(i);
		ss.erase(i);
	}
	match(x+1);
}
signed main() {
\/\/	freopen("steiner.in","r",stdin);
\/\/	freopen("steiner.out","w",stdout); 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y,z;
		cin>>x>>y>>z;
		v[x].push_back({y,z});
		v[y].push_back({x,z});
	}
	for(int i=1;i<=n;i++){
		bfs(i);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
		m=n;
		for(int j=1;j<=m;j++) ss.insert(a[j]);
		minn=0x3f3f3f3f;
		match(1);
		
		if(kruskal()!=minn){
			cout<<0;
		}
		else {
			cout<<1;
		}
	}
\/\/	fclose(stdin);
\/\/	fclose(stdout); 
	return 0;
}

T4

死于苹果（ios）……

高效的思路

输出 $1$，即可得 15 分，但是因为关了同步，所以 0。

未知的正解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-10-01 20:21:09

忘了得多少分了……

T1

考场上本来想多得一点分，所以没有打暴力，结果 0分。

正解

首先二分出 $a,b,c,d$ 四个数的总和，然后枚举 $a,d$(或者 $b,c$)，之后估算出 $b,c$ 的大致范围，再从这个范围中找到 $b$ 和 $c$ 的值。

没有代码了，凑活看吧

T2

赛时只做了小范围的数据和一条链的情况。

小数据：

直接暴力求解。

链：

发现每一个点移动到他的父节点时，其他的点会有 $2^n/2/2$ 种不同的排列，所以只要乘上方案数就行了。

正解（不会）

部分分的代码

T3

首先对于 $A$ 题目没有过多的限制，所以说我们可以将 $A$ 放在第一个位置，之后再交替放 $B$。

先考虑放完所有的 $A$，先将 $A$ 与 $B$ 尽可能更多地交替放置。然后剩下的 $A$ 每 $a$ 个就 $+1$。

之后考虑 &B&。对于当前，如果最后的一位是 $A$,那么在后面加上一个 $B$ 就能使价值加一，剩余的 $B$，每有 $b$ 个 $B$，就能使价值加一。

代码

T4

考场上实在是看不出来这是一个分段函数，所以只能做出暴力的 5 分。但是在暴力的基础上，加了一些优化，本来希望能做对之后查询的部分……但是失败了。

优化： 将修改操作中连续的操作进行合并，减少询问时操作的次数。

思路

测试点1

暴力模拟即可。

测试点 $23456$

根据题意可以得出整个变化的过程中可以归结成为一个分段函数，所以只需要二分找到它的两个断点，之后就可 O(1) 地进行查询。

之后的就不会了

本文章由 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;
}