这场比赛似乎又让我感觉我又行了，2333

A. Distance and Axis

题意：
很简单的A题，给定一个n和k，定义一种操作可以使n加一或者减一，让我们找到一个点B使得从0到B的距离减去从B到n的距离的绝对值等于k，问我们最少需要多少次操作？

思路：
试一下就知道了，当k大于等于n的时候不难看出当B在0的时候一定成立所以结果为0，当k小于n的时候就要看k和n的奇偶性是否一致了，其实也是根据n的性质来说的
比如n等于4的时候 0 1 2 3 4，当B在0的时候绝对值4，在1的时候绝对值为2，在2的时候绝对值为0, 在3，4的时候对称。

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin>>T;
	while(T--) 
	{
		int n,k;
		cin>>n>>k;
		if(n<=k) cout<<k-n<<'\n';
		else {
			if(n&1) {
				if(k&1) puts("0");
				else puts("1");
			}
			else {
				if(k&1) puts("1");
				else puts("0");
			}
		}
	}	
	return 0;
} 

B. Ternary Sequence

题意：
每次遇见B题就感觉思维会有点，然后我有很喜欢钻牛角，所以很多时候就很烦，还是要多换角度去考虑的，往往B题题意很无法，定义一堆操作，最后分析下来发现都没有或者可以从一个很简单的角度去构造出一种解。
正文：
给定两个个只包含0,1,2的序列A、B,我们定义 分别代表 A序列中0的个数1,1的个数，2的个数。同理 为B序列的0的个数、1的个数、2的个数。
然后定义C序列：

题目让我们最大化:

分析：
好烦对吧，你要是对A、B序列中0、1、2的个数分别进行讨论的话，情况太多换句话来说不是正解，况且你也讨论不出来，，，我们考虑一件事 最大化什么情况会最大化？肯定拿A序列的2和B序列的1去组合才是对答案有贡献的，而什么对答案没有贡献，不难发现无论是A序列的0、1还是B序列的0、1去组合的话无论谁多谁少都不影响，对答案有影响的只有B序列的2，所以我们还要用A序列的0和A序列剩下的2去抵消掉B序列的2，若不能抵消就只有和1组合了。

#include<bits/stdc++.h>

using namespace std;

int main()
{
	int T;
	cin>>T;
	while(T--) {
		int x1,y1,z1;
		int x2,y2,z2;
		
		cin>>x1>>y1>>z1;
		cin>>x2>>y2>>z2;
		
		//先让第一个2配
		int ans=min(z1,y2);
		z1-=y2;
		z1=max(0,z1);
		
		//用剩余的0和2再和第二个2配
		ans-=max(z2-z1-x1,0);
		ans*=2;
		cout<<ans<<'\n'; 
		
	}
	return 0;
}

C. Mere Array

题意：

给定一个长度为n的序列，定义了一种操作：你可以选择两个值进行交换，当他们的最大公约数等于整个序列的最小值的时候，问我们是否可以经过若干次操作让这个序列变成一个非递减序列。

思路：
从全局的角度进行考虑，最大公约数有一定的性质的，假设任意两个数可以交换，那么再取任意两个数，他们的最大公约数一定相等且等于最小数。但是对于这个题如果取判断所有需要交换的数的最大公约数是否等于最小数的话是有一定问题的，它可以能先和最小数进行交换，然后再交换，所以只要是最小数的倍数即可。

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+10;

int a[N];
int b[N];
int c[N];

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main()
{
	int T;
	cin>>T;
	while(T--) {
		int n;
		scanf("%d",&n);
		int mi=0;
		//cout<<mi<<'\n';
		for(int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			if(mi==0) mi=a[i];
			mi=min(mi,a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+1+n);
		
		int cnt=0;
		
		for(int i=1;i<=n;i++) {
			int x=a[i];
			int y=b[i];
			if(x!=y) {
				c[++cnt]=x;
				c[++cnt]=y;	
			}
		}
		
		int g=c[1];
		bool flag=false;
		for(int i=2;i<=cnt;i++) {
			g=gcd(g,c[i]);
			//if(g==mi) flag=true;
		} 
		if(g%mi==0||cnt==0) puts("YES");
		else puts("NO"); 
	} 
	return 0;
}

D. Maximum Distributed Tree

题意：
这个题还是好烦的，他居然在优先队列上卡我，也怪我自己不注意，其实当我把取模问题解决以后数据跑到了13组样例的时候我就觉得自己思路是没问题的，可能就是取模的问题，没想到最后是因为优先队列没注意到。

正文

给我们n个节点的一棵树，然后给定m个素数，让我们把这m个素数放到n-1条边上，有可能m>n也有可能m<n，我们要保证整棵树的边权乘积等于这m个素数的乘积，还要保证1尽可能的少，因为当m<n的时候我们只能补1，然后题目让我们最大化这样一个东西：
其中f(i,j)代表节点i到节点j的边权之和。其实就是距离。

思路:

刚看的时候感觉是个贪心或者树形Dp都有可能，然后数据范围1e5可能牵扯到并查集的操作，这是大概的方向，然后再分析发现不可能对每个点都跑一遍的必然TLE，然后我们看是否存在一种方式可以局部最大化以后得到全局最大化。不难发现每条边的重复次数是可以算出来的。我们只需要让值比较大的边权放到重复次数多的上面就好了，而边的重复次数，我是这样算的，感觉不太像是正解，但是还说的过去，最起码能保证正确性，刚开始想着是否可以拿并查集进行维护，因为这是一颗数，我们看任意一条边，它重复的次数就是边两边点的个数的乘积。关键就是如何算出来这条边两边的个数。因为对每个点向左向右跑dfs的话肯定会超时，不如就从树形结构来看，连接的一定是儿子节点，我们预处理出来每个节点包含自己本身和儿子节点的个数，即从该节点向下一共有多少个节点。

当我们看一条边的时候，u——v可以发现，u可以看成是v的儿子节点，v也可以看成是u的儿子节点，所以我们预处理的时候从任意一点出发跑一遍dfs即可得到，然后就是如何算个数了，两个点中较少的那个点就是答案乘积的一种，因为较多的那个点包含了较少的点，而较多的那个点含有的个数就是n-min(size[u],size[v]),这里还是需要想想的，我也是多画出了几个图推出来的。

最后就是有个坑点，我拿大根堆进行维护的时候，当k的个数大于n的个数的时候我依次取出队首元素，然后相乘，然后我取余放了进去，，22333卡了我好长时间，应该单独把队首元素拿出来然后开个变量记录的，不能取余后放进去，因为大根堆维护可能会影响答案的正确性的。好坑，，，而当k的个数小于n的时候就补1然后依次取就好了。

#include<bits/stdc++.h>

using namespace std;

const int N=4e6+10,mod=1e9+7;

typedef long long LL;

LL p[N];
int h[N],e[N],ne[N];
LL size[N];
int idx;

void add(int a,int b) {
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

struct Edge{
	int u,v;
	LL cnt;
	bool operator <(const struct Edge &W)const {
		return cnt>W.cnt;
	}
}edge[N];

LL dfs(int u,int f)
{
	//LL sum=1;
	for(int i=h[u];~i;i=ne[i]) {
		int j=e[i];
		if(j!=f) {
			size[u]+=dfs(j,u);
		}
	}
	//size[u]=sum;
	return size[u];
}

int main()
{
	int T;
	cin>>T;
	while(T--) {
		
		int n;
		scanf("%d",&n);
		
		memset(h,-1,sizeof h);
		idx=0;
		
		for(int i=1;i<=n;i++) {
			size[i]=1;
		}
		
		for(int i=0;i<n-1;i++) {
			int u,v;
			scanf("%d%d",&u,&v);
			edge[i]={u,v}; 
			add(u,v);
			add(v,u);
		}
		
		dfs(1,-1);
		
		int cnt=n-1;
		
		//cnt为边的个数 
		
		for(int i=0;i<cnt;i++) {
			int u=edge[i].u;
			int v=edge[i].v;
			LL bp=min(size[u],size[v]);
			edge[i].cnt=1LL*bp*(n-bp);
		}
		
		sort(edge,edge+cnt);
		
		//处理能填的数字 
		
		int m;
		scanf("%d",&m);
		for(int i=0;i<m;i++) scanf("%lld",&p[i]);
		
		priority_queue<LL>heap;
		
		for(int i=0;i<m;i++) heap.push(p[i]);
		
		//m<cnt, 不够的边拿1顶替 
		for(int i=m;i<cnt;i++) {
			heap.push(1LL); 
		}
		
		//m>n需要把两个p最大的相乘以后 
		
		LL kw=heap.top();
		heap.pop();
//		m--;
		
		if(m>cnt) {
			while(m>cnt) {
				LL x=heap.top();
				heap.pop();
				kw=(kw*x)%mod;
				m--;
			} 
		}
		
		//cout<<heap.size()<<'\n';
		
		//为每个边赋值 按照边重复的次数 
		LL ans=kw*edge[0].cnt%mod;
		for(int i=1;i<cnt;i++)
		{
			LL top=heap.top();
			top%=mod;
			heap.pop();
			ans=(ans+1LL*top*edge[i].cnt%mod)%mod;
		}
		
		printf("%lld\n",ans);
	}
	return 0;
}

总结:

其实我也不知道自己水平啥地步，反正就是很菜，但是我一直想构建出来知识体系的，实验证明现在写代码必须要达到思维上的精确，然后写出来就很少出来wa了即使出现了也可以从逻辑上进行修改，而不是调试，调试只是输出我们想要的答案，他并不是改错的好方式，此外就是需要多分析题目本身具有的性质，比如这次的D题，开的时候还是有点没自信，不过自己写出来的时候感觉好简单，就贪心维护搞一下就好了，但是我不想注重排名或者过题什么的，更需要注重的是题目本身牵扯到的知识点，或者它本身思维的有趣性。大概用到的方法这次比赛：

1、构造
2、最大公约数的性质
3、从有到无分析问题，即从最后解的形式去分析
4、舍去一些无关的操作
5、树、dfs、取模