A. Distance and Axis

题目链接

题目原文

1401A

题目大意

在OXOX轴上，给出点AA的坐标x=nx=n，给出一个值kk，求问能不能在OXOX轴上找一个点BB，使得你∣OA−AB∣=k|OA-AB|=k。如果不能找到，你每次可以将AA点的坐标+1+1或−1-1，求至少移动点AA多少次，使得可以找到点BB （如果以开始就能找到，那么输出 00 ）。

解题思路

由题意得OA=nOA=n，设BB的坐标为yy，那么∣AB∣=∣n−y∣|AB|=|n-y|，那么∣OA−AB∣=∣2n−y∣|OA-AB|=|2n-y|，所以就是求是否存在2n−y2n-y等于kk。

解法

如果n<kn<k，那么一定解出来yy是负数，所以一定要将点AA移动到x=kx=k处，答案为n−kn-k。

如果n−kn-k为奇数，那么除以2之后为小数，所以应该+1+1或−1-1，答案为11。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n,k,ans;
int main()
{
 	#ifdef lemon
	freopen("A.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		ans=0;
		if(n<k) ans+=k-n,n=k;
		else if((n-k)&1) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

B. Ternary Sequence

题目链接

题目原文

1401B

题目大意

有两个数组aa和bb，这两个数组都只会有3个值：0或1或2。现在告诉你这两个数组中这三个值的数量。请你构造a,ba,b数组，并且由下面规则生成cc数组，并且使得cc数组每一项的和最大，求这个最大值。

规则：

ci={aibiif ai>bi0if ai=bi−aibiif ai<bi c_i = \begin{cases} a_i b_i &\text{if } a_i > b_i \\ 0 &\text{if } a_i = b_i \\ -a_i b_i &\text{if } a_i < b_i \end{cases}

解题思路

这种题看过去不是贪心就是dp。

解法

我们贪心地想，首先要使得ai=2,  bi=1a_i=2, \; b_i=1的数量尽可能地多，然后尽可能地使得其他都为0，最后实在不行再使得值为ai=1,  bi=2a_i=1, \; b_i=2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T;
long long x1,yy1,z1,x2,y2,z2;
int main()
{
 	#ifdef lemon
	freopen("B.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld%lld%lld",&x1,&yy1,&z1,&x2,&y2,&z2);
		long long t1=min(z1,y2),ans=0;
		z1-=t1;y2-=t1;
		ans+=2ll*t1;
		long long t2=min(z1,z2);
		z1-=t2;z2-=t2;
		long long t3=min(x1,z2);
		x1-=t3;z2-=t3;
		ans-=2ll*z2;
		printf("%lld\n",ans);
	}
	return 0;
}

C. Mere Array

题目链接

题目原文

1401C

题目大意

给出长度为nn的数组，每个数都大于1。记数组中最小的数为minn，现在你可以将数组中任意两个gcd=minngcd=minn的数进行交换。求有没有可能使得整个数组变成不下降序列。

解题思路

显然minn可以和所有数进行交换，那就将minn作为交换的中间值。

解法

将数组中是minn的倍数的数提出来，直接排序（因为他们都可以通过minn进行交换）。然后从小到大插入提出来的位置。最后check一下数组，如果这个数组满足要求，那么就ok。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int a[maxn],b[maxn],c[maxn],T,n;
int main()
{
 	#ifdef lemon
	freopen("C.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		int minn=0x7f7f7f7f;b[0]=0;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]),minn=min(minn,a[i]);
		for(int i=1;i<=n;i++) if(a[i]%minn==0) b[++b[0]]=a[i];
		sort(b+1,b+b[0]+1);
		int p=1;
		for(int i=1;i<=n;i++)
		{
			if(a[i]%minn) c[i]=a[i];
			else c[i]=b[p++];
		}
		bool flag=true;
		for(int i=2;i<=n;i++) if(c[i]<c[i-1]) flag=false;
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

D. Maximum Distributed Tree

题目链接

题目原文

1401D

题目大意

给出一棵树，但没有边权。
给出一个数的因数形式（给出的数的乘积为k）。

现在你需要给每一条边赋值，使得所有每两个点之间通过的路径和最大，且边权需要满足以下要求：

  1. 每条边的边权必须大于0
  2. 所有边的边权之积为k
  3. 边权为1的边的数量尽可能地少

解题思路

显然我们需要将通过最多的边赋值最大，通过次数最低的边赋值最小。于是我们想到贪心。

解法

用树形dp求出每条边的通过次数，对于一条边i，它的通过次数等于它的子树大小*(n-它的子树大小)。然后再贪心求解。

注意m>n-1的情况！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
const long long mod=1e9+7;
int T,n,head[maxn],k=0,size[maxn],tot,m;
struct node
{
	int to,next;
} edge[maxn<<1];
void add(int u,int v)
{
	edge[++k].to=v;
	edge[k].next=head[u];
	head[u]=k;
}
long long p[maxn],ans=0,b[maxn];
void dfs(int x,int fa)
{
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next)
	{
		if(edge[i].to==fa) continue;
		dfs(edge[i].to,x);
		size[x]+=size[edge[i].to];
		b[++tot]=(long long)size[edge[i].to]*(long long)(n-size[edge[i].to]);
	}
}
int main()
{
 	#ifdef lemon
	freopen("D.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		memset(head,0,sizeof(head));k=0;tot=0;ans=0;
		scanf("%d",&n);
		for(int i=1,x,y;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			add(x,y);add(y,x);
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++) scanf("%lld",&p[i]);
		dfs(1,1);
		sort(b+1,b+tot+1);
		sort(p+1,p+m+1);
		p[0]=1ll;
//		for(int i=1;i<=tot;i++) printf("%d ",b[i]);printf("\n");
		while(m>tot)
		{
			p[m-1]=(p[m-1]*p[m])%mod;
			m--;
		}
		int pp=m;
		for(int i=tot;i;i--)
		{
			b[i]%=mod;
			ans=(ans+(b[i]*p[pp])%mod)%mod;
			pp--;
			if(pp<0) pp=0;
		}
		printf("%lld\n",ans);
	}
	return 0;
}