Codeforces Round #636 (Div. 3) 题解的草稿

A. Candies

嘤～

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf;
//#define int ll
signed main(){
	for(int T=read();T--;){
		int n=read();
		int ans=0;
		repeat(i,1,60)
			if(n%((1ll<<i)-1)==0)ans=n/((1ll<<i)-1);
		cout<<ans<<endl;
	}
	return 0;
}

B. Balanced Array

嘤嘤～

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf;
//#define int ll
signed main(){
	for(int T=read();T--;){
		int n=read();
		if(n%4==2)cout<<"NO"<<endl;
		else{
			ll sum=0;
			cout<<"YES"<<endl;
			repeat(i,1,n/2+1)
				cout<<i*2<<‘ ‘,sum+=i*2;
			repeat(i,1,n/2)
				cout<<i*2-1<<‘ ‘,sum-=i*2-1;
			cout<<sum<<endl;
		}
	}
	return 0;
}

C. Alternating Subsequence

略略略～

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf;
//#define int ll
int a[N];
#define sgn(x) ((x)>0?1:-1)
signed main(){
	for(int T=read();T--;){
		int n=read();
		repeat(i,0,n)a[i]=read();
		int flag=sgn(a[0]);
		int m=-inf;
		ll ans=0;
		repeat(i,0,n){
			if(sgn(a[i])==flag){
				m=max(m,a[i]);
			}
			else{
				flag=-flag;
				ans+=m;
				m=a[i];
			}
		}
		ans+=m;
		cout<<ans<<endl;
	}
	return 0;
}

D. Constant Palindrome Sum

两个数 \(a,b\) 要改成 \(s\) 的代价是

\(cost_i[s]=\begin{cases}0&a+b=s\\1&a+b\not=s∧s∈[a,a+k]∪[b,b+k]\\2&otherwise\end{cases}\)

考虑把所有对称的两个数的代价加起来（即把所有 \(cost_i\) 加起来），可以得到下标为 \(s\) 的数组 \(cost[s]\)

上述操作中直接维护数组 \(cost[s]\) 是不行的，由于我们每次修改都是区间加，并且离线操作，可以考虑用差分数组，如果区间 \([l,r]\) 要加上 \(d\)，可以 \(a[l]+=d,a[r+1]-=d\)，最后求它的前缀和，还原成 \(cost[s]\)

这样我们对 \(s\) 的所有情况的代价都求出来了，min一下即可

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=400010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf;
//#define int ll
int a[N],s[N];
void add(int x,int y,int d){
	s[x]+=d;
	s[y+1]-=d;
}
signed main(){
	for(int T=read();T--;){
		int n=read(),k=read();
		fill(s,s+2*k+2,0);
		repeat(i,0,n)a[i]=read();
		repeat(i,0,n/2){
			int x=a[i],y=a[n-i-1];
			if(x>y)swap(x,y);
			add(0,x,2);
			add(x+1,x+y-1,1);
			add(x+y+1,y+k,1);
			add(y+k+1,k*2,2);
		}
		int ans=inf;
		repeat(i,1,k*2+1){
			s[i]+=s[i-1];
			ans=min(ans,s[i]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

E. Weights Distributing

傻逼题，我被套路了，原来这么简单

先求每个点到 \(A,B,C\) 最短路径（bfs即可），然后遍历所有点 \(v\)，计算 \(A→v→B→v→C\) 并 \(O(1)\) 更新答案

怎么更新答案？由于 \(v→B\) 要走两次，所以 \(len(v→B)\) 个最小边权要赋给它们，剩下 \(len(v→A)+len(v→C)\) 个最小边权赋给路径上其他边（至于对price排序求前缀和，就不多说了）

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=200010; typedef long long ll; const int inf=~0u>>2; const ll INF=~0ull>>2; ll read(){ll x; if(scanf("%lld",&x)==-1)exit(0); return x;} typedef double lf;
#define int ll
int dis1[N],dis2[N],dis3[N],price[N];
int n,m,s1,s2,s3;
vector<int> a[N];
queue<int> q;
void bfs(int s,int dis[]){
	q.push(s);
	fill(dis,dis+n+1,-1);
	dis[s]=0;
	while(!q.empty()){
		int x=q.front(); q.pop();
		for(auto p:a[x])
		if(dis[p]==-1){
			dis[p]=dis[x]+1;
			q.push(p);
		}
	}
}
ll ans;
signed main(){
	for(int T=read();T--;){
		n=read();
		repeat(i,0,n+1)a[i].clear();
		m=read(),s1=read(),s2=read(),s3=read();
		repeat(i,1,m+1)price[i]=read();
		sort(price+1,price+m+1);
		repeat(i,1,m+1)price[i]+=price[i-1];
		repeat(i,0,m){
			int x=read(),y=read();
			a[x].push_back(y);
			a[y].push_back(x);
		}
		bfs(s1,dis1);
		bfs(s2,dis2);
		bfs(s3,dis3);
		ans=INF;
		repeat(i,1,n+1){
			int t2=dis2[i];
			int t1=dis1[i]+dis3[i];
			if(t2+t1<=m)
				ans=min(ans,price[t2]+price[t2+t1]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

Codeforces Round #636 (Div. 3) 题解的草稿

原文：https://www.cnblogs.com/axiomofchoice/p/12749281.html