A. Distance and Axis
題目連結
題目原文
題目大意
在 O X OX OX軸上，給出點 A A A的坐标 x = n x=n x=n，給出一個值 k k k，求問能不能在 O X OX OX軸上找一個點 B B B，使得你 ∣ O A − A B ∣ = k |OA-AB|=k ∣OA−AB∣=k。如果不能找到，你每次可以将 A A A點的坐标 + 1 +1 +1或 − 1 -1 −1，求至少移動點 A A A多少次，使得可以找到點 B B B （如果以開始就能找到，那麼輸出 0 0 0 ）。
解題思路
由題意得 O A = n OA=n OA=n，設 B B B的坐标為 y y y，那麼 ∣ A B ∣ = ∣ n − y ∣ |AB|=|n-y| ∣AB∣=∣n−y∣，那麼 ∣ O A − A B ∣ = ∣ 2 n − y ∣ |OA-AB|=|2n-y| ∣OA−AB∣=∣2n−y∣，是以就是求是否存在 2 n − y 2n-y 2n−y等于 k k k。
解法
如果 n < k n<k n<k，那麼一定解出來 y y y是負數，是以一定要将點 A A A移動到 x = k x=k x=k處，答案為 n − k n-k n−k。
如果 n − k n-k n−k為奇數，那麼除以2之後為小數，是以應該 + 1 +1 +1或 − 1 -1 −1，答案為 1 1 1。
代碼
#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
題目連結
題目原文
題目大意
有兩個數組 a a a和 b b b，這兩個數組都隻會有3個值：0或1或2。現在告訴你這兩個數組中這三個值的數量。請你構造 a , b a,b a,b數組，并且由下面規則生成 c c c數組，并且使得 c c c數組每一項的和最大，求這個最大值。
規則：
c i = { a i b i if a i > b i 0 if a i = b i − a i b i if a i < b i 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} ci=⎩⎪⎨⎪⎧aibi0−aibiif ai>biif ai=biif ai<bi
解題思路
這種題看過去不是貪心就是dp。
解法
我們貪心地想，首先要使得 a i = 2 , b i = 1 a_i=2, \; b_i=1 ai=2,bi=1的數量盡可能地多，然後盡可能地使得其他都為0，最後實在不行再使得值為 a i = 1 , b i = 2 a_i=1, \; b_i=2 ai=1,bi=2。
代碼
#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
題目連結
題目原文
題目大意
給出長度為 n n n的數組，每個數都大于1。記數組中最小的數為minn，現在你可以将數組中任意兩個 g c d = m i n n gcd=minn gcd=minn的數進行交換。求有沒有可能使得整個數組變成不下降序列。
解題思路
顯然minn可以和所有數進行交換，那就将minn作為交換的中間值。
解法
将數組中是minn的倍數的數提出來，直接排序（因為他們都可以通過minn進行交換）。然後從小到大插入提出來的位置。最後check一下數組，如果這個數組滿足要求，那麼就ok。
代碼
#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
題目連結
題目原文
題目大意
給出一棵樹，但沒有邊權。
給出一個數的因數形式（給出的數的乘積為k）。
現在你需要給每一條邊指派，使得所有每兩個點之間通過的路徑和最大，且邊權需要滿足以下要求：
- 每條邊的邊權必須大于0
- 所有邊的邊權之積為k
- 邊權為1的邊的數量盡可能地少
解題思路
顯然我們需要将通過最多的邊指派最大，通過次數最低的邊指派最小。于是我們想到貪心。
解法
用樹形dp求出每條邊的通過次數，對于一條邊i，它的通過次數等于它的子樹大小*(n-它的子樹大小)。然後再貪心求解。
注意m>n-1的情況！
代碼
#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;
}