Codeforces Round 665 赛后解题报告
A. Distance and Axis
我们设 \(B\) 点 坐标为 \(x(x\leq n)\)。由题意我们知道
\]
\]
因此 \(n,k\) 同奇偶。我们分类来讨论，如果 \(n<k\)，那么最优方案一定是让 \(k'=n,x=n\)。这一定是最小的，因为再要满足条件就 \(k'>n\) 了，肯定不优。若 \(n\geq k\)。则我们只需要满足同奇偶的条件，判断一下即可
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int n,k;
signed main() {
int T=read();
while(T--) {
n=read();k=read();
if(n<k) {
cout<<k-n<<endl;
}
else {
cout<<(n-k)%2<<endl;
}
}
return 0;
}
B. Ternary Sequence
这个题就是直接贪心讨论即可。
我们来分析一下，其实这个题目 \(c_i\) 的计算根本没那么麻烦.我们只需贪心计算。我们先尽可能让 \(b\) 中的 \(2\) 产生最小负面影响。我们第一选择是拿 \(a\) 中的 \(0\) 一个一个去送死抵消。再拿 \(2\) 去抵消。最后才是 \(1\) 因为只有此时每一对都会产生 \(-2\) 的负面 BUFF。然后我们尽可能多的让 \(a\) 中的 \(2\) 产生正面 BUFF，和 \(b\) 中的 \(1\) 一个一个配对，剩下的随意排布都不会产生贡献或负贡献，算法就结束了。
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int x[2],y[2],z[2];
signed main() {
int T=read();
while(T--) {
for(int i=0;i<=1;i++) {
x[i]=read();y[i]=read();z[i]=read();
}
int ans=0;
int tmp=min(z[1],x[0]);
z[1]-=tmp;
x[0]-=tmp;
if(z[1]) {
int t1=min(z[1],z[0]);
z[1]-=t1;
z[0]-=t1;
if(z[1]) {
ans-=z[1]*2;
y[0]-=z[1];
}
}
ans+=min(z[0],y[1])*2;
cout<<ans<<endl;
}
return 0;
}
C. Mere Array
虽然比赛的时候我写挂了一次，但我还是蛮喜欢这道题的
这个题的思路很妙，我们先来看题目中的条件：
In one operation, you can choose two different indices \(i\) and \(j\) (\(1\leq i\),\(j\leq n\)). If \(\gcd(a_i,a_j)\) is equal to the minimum element of the whole array a, you can swap \(a_i\) and \(a_j\)
这证明我们可以先找出这个最小值，即为 \(divi\)（全称divisor，注意 div 在头文件中出现过，不能用！）。我们只要判断一个数 \(a_i\)，若 \(divi\nmid a_i\)，我们要判断他是否在正确的位置上，即有多少的数比它小。若不在正确位置上，直接 \(\text{NO}\)，否则继续判断。
一开始我是这样写的，但是由于写挂了，于是怀疑这个是错误的
其实这个怀疑很正常，因为我们认为的是两个都能被 \(divi\) 整除的数可以直接交换位置，但是如果 \(divi=2\)，那么 \(4,8\) 不能直接交换位置。这边是我一开始的疑惑。但是后来，我们可以发现，\(4,8\)，不能直接交换位置，我们可以间接交换呀。我们先把 \(2,4\) 换一下，再换一下 \(2,8\)，最后再换一下 \(2,4\) 就完成了。因此原算法正确。只是我写挂了而已qwq
特别注意一下如果 \(a_i\)=\(a_{i-1}\)，我们的要特殊处理
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=1e5+10;
int n,a[maxn],divi,b[maxn];
signed main() {
int T=read();
while(T--) {
n=read();
divi=1e9+10;
for(int i=1;i<=n;i++) {
a[i]=read();
b[i]=a[i];
divi=min(divi,a[i]);
}
sort(b+1,b+n+1);//排序
bool flag=1;
int pos=0;
for(int i=1;i<=n;i++) {
if(a[i]%divi!=0) {
pos=upper_bound(b+1,b+i+1,a[i])-b;
if(!(pos-1==i&&b[pos-1]==a[i])) {//如果 $a_i$=$a_{i-1}$，我们的要特殊处理
printf("NO\n");
flag=0;
break;
}
}
}
if(flag) {
printf("YES\n");
}
}
return 0;
}
D. Maximum Distributed Tree
贪心题石锤。
这个题有一个突破口，就是我们可以先用一遍 \(\text{dfs}\) 来求出所有边在答案 \(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n} f(i,j)\) 中的贡献次数。所以我们可以有以下的式子：
\]
其中 \(con_{(u,v)}\) 表示 \((u,v)\) 这条边被经过次数，\(w_{(u,v)}\) 表示 \(u,v\) 这条边的边权。
如果我们以 \(1\) 为根，\(size_u\) 表示以 \(u\) 为根的子树的大小。那么连接 \(u,v\)，且 \(u\) 为 \(v\) 的父亲的这条边对答案的贡献就是 \(con_{(u,v)}=size_u\times (n-size_u)\)。
我们再来维护边权。有两种情况，我们分别讨论
- 如果 \(m<n-1\) 那么一定会有边权为 \(1\) 的边出现。那么为了让 \(1\) 最少（题目要求），我们只有唯一解
- 否则我们可以让一些质因子合并，构造出 \(n-1\) 个边权。那么我们为了让答案最大，一定是把最大的 \(m-n+2\) 个边权堆在一起。证明很简单，就是因为如果我们有 \(a>b,k>0\)，那么 \(k\cdot a>k\cdot b\)。最后给 \(w,con\) 数组排个序即可。
注意，对于 \(con\) 数组，先排序在取模；对于 \(w\) 数组，按顺序处理，由于数字太大在处理时就要取模，千万别排序！！！
//Don't act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read() {
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9') {
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int maxn=1e5+10,mod=1e9+7;
int n,m;
int p[maxn],a[maxn],h[maxn],cnt,w[maxn],sz[maxn],con[maxn],tot;
struct edge {
int v,next;
}e[maxn<<1];
void addedge(int u,int v) {
e[++cnt].v=v;
e[cnt].next=h[u];
h[u]=cnt;
}
void insert(int u,int v) {
addedge(u,v);
addedge(v,u);
}
void dfs(int u,int fa) {
sz[u]=1;
for(int i=h[u];i;i=e[i].next) {
int v=e[i].v;
if(v!=fa) {
dfs(v,u);
sz[u]+=sz[v];
}
}
if(fa!=0) {
con[++tot]=sz[u]*(n-sz[u]);//不着急取模
}
}
signed main() {
int T=read();
while(T--) {
n=read();
fill(h+1,h+n+1,0);
cnt=0;
for(int i=1;i<n;i++) {
insert(read(),read());
}
m=read();
fill(w,w+n+1,0);
for(int i=1;i<=m;i++) {
p[i]=read();
}
sort(p+1,p+m+1);//这里要先排序
if(n-1<m) {//第一种
for(int i=1;i<n-1;i++) {
w[i]=p[i];
}
w[n-1]=p[n-1];
for(int i=n;i<=m;i++) {
w[n-1]=w[n-1]*p[i]%mod;
}
}
else {//第二种
for(int i=1;i<=m;i++) {
w[i]=p[i];
}
for(int i=m+1;i<n;i++) {
w[i]=1;
}
sort(w+1,w+n);
}
tot=0;
dfs(1,0);//维护con
int ans=0;
sort(con+1,con+n);
for(int i=1;i<n;i++) {
ans+=con[i]%mod*w[i]%mod;//贪心
ans%=mod;
}
cout<<ans<<endl;
}
return 0;
}
这里放一个拓展。因为在比赛时我有一个朋友把 product 理解为 sum，所以浪费了很多时间。不是无中生友qwq。大家看到这篇题解可以想一想如果是 sum 怎么做，可以在评论里交流一下~