B.Ternary Sequence
题目传送门
Ternary Sequence
题目大意
有两个由0,1,2组成的数组a和b，分别给你a数组和b数组中0,1,2的个数，其中满足
求C的和的最大值
思路
贪心
1、通过观察我们发现正的贡献只有a(2)*b(1)=2,负的贡献只有a(1)*b(2)= -2，其他的情况则都为0。按照贪心的思想，a(1)*b(2)应该尽可能的少，而a(2)*b(1)尽可能多。
2、于是我们优先用a数组中的0，然后再用a数组中的2，去和b数组中的2匹配，使得贡献为0，最后再用a中的1去匹配，贡献-2。
3、如果上述操作后a中的2仍有剩余，再计算a(2)*b(1)=2的情况。
AC Code
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int x1,y1,z1;
int x2,y2,z2;
scanf("%d%d%d",&x1,&y1,&z1);
scanf("%d%d%d",&x2,&y2,&z2);
int maxn=0,k;
if(x1+z1>=z2)
{
k=z2-x1;
if(k<0) k=z1;
else k=z1-k;
k=min(k,y2);
printf("%d\n",2*k);
}
else
{
k=z2-x1-z1;
printf("%d\n",-1*k*2);
}
}
//system("pause");
return 0;
}
C.Mere Array
题目传送门
Mere Array
题目大意
给你一个长度为n的数组，如果数组中两个元素的gcd等于数组中的最小值，那么就可以将两者调换。问这个数组能否达到单调非减序列。
思路
其实gcd(a,b)等于最小值，说明a和b都是最小值mi的倍数。而且通过观察发现，所有mi的倍数之间，我们都可以通过和mi进行交换，达到这些数任意交换的效果。
我们可以复制一个数组a进行排序，对于排序后的数组，与原数组元素不同的那些元素ai进行判断，若ai%mi==0，则说明ai可以通过交换到达排序后位置。
AC Code
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+10;
const LL inf=1e12;
LL a[N],b[N];
bool cmp(LL a,LL b)
{
return a<b;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
LL maxn=inf;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
maxn=min(maxn,a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1,cmp);
int flag=0;
for(int i=1;i<=n;i++)
{
if(a[i]!=b[i])
{
if(a[i]%maxn!=0)
{
printf("NO\n");
flag=1;
break;
}
}
}
if(flag==0) printf("YES\n");
}
//system("pause");
return 0;
}
D.Maximum Distributed Tree
题目传送门
Maximum Distributed Tree
题目大意
给定一个n个点n-1条边的连通图（其实就是树），我们要给它的边赋值，必须满足以下条件：
- 边权必须大于0；
- 所有边权的乘积必须等于k（输入直接给出了k分解质因子数后的质因数）；
- 边权为1的边尽可能少
定义f（u，v）为从点u到点v的路径的边权和，
问
最大是多少？答案对10^9+7取模。
思路
假定树的根为1，每个点的点权等于连向它父结点的边的边权。我们对所有的子树求出子树大小siz（包括自己这个点），则对于每一条边（每一个结点连向父结点的边，siz是这个结点所在子树的大小），它在求和中出现的次数就是siz*（n-siz）。把每一条边的siz*（n-siz）求出来，从小到大排序，因为要使得求和尽量大，所以我们尽可能把质数中最大的给siz*（n-siz）最大的边。但是注意质数的数量可能多于n-1，这个时候我们就把最大的多出的质数乘起来，变成一个数，把它赋给siz*（n-siz）最大的边即可。若质数少于n-1，则不够的部分补1。
AC Code
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MOD=1e9+7,N=1e5+10,M=6e4+10;
int t,n,k;
int cent,head[N];
LL siz[N],prime[N];
struct node{
int to;
int next;
}rode[N*2];
void add(int a,int b)
{
rode[cent].to=b;
rode[cent].next=head[a];
head[a]=cent++;
}
bool cmp(LL a,LL b)
{
return a<b;
}
void dfs(int now,int fa)
{
siz[now]=1;
for(int i=head[now];~i;i=rode[i].next)
{
int to=rode[i].to;
if(to==fa) continue;
else
{
dfs(to,now);
siz[now]+=siz[to];
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
cent=0;
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
scanf("%d",&k);
for(int i=1;i<=k;i++)
scanf("%d",&prime[i]);
if(k<n-1)
{
for(int i=k+1;i<n;i++) prime[i]=1;
k=n-1;
}
sort(prime+1,prime+k+1,cmp);
while(k>n-1)
{
prime[k-1]=prime[k-1]*prime[k]%MOD;
k--;
}
dfs(1,0);
for(int i=1;i<=n;i++)
siz[i]=siz[i]*(n-siz[i]);
sort(siz+1,siz+1+n,cmp);
LL res=0;
for(int i=1;i<n;i++)
res=(res+siz[i+1]*prime[i]%MOD)%MOD;
printf("%lld\n",res);
}
//system("pause");
return 0;
}
