CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!) 「A - F」

· 题解

这场打的有点下饭 D竟然也是简单的分类讨论一下 只能说是不够冷静 没有仔细分析了

这几天没什么动力 也不想写什么东西 但这场比赛会补好 写完 因为白天闲时的一个念头

A. Good Pairs

找到最大的数和最小的数的位置 注意顺序 输出

code 
#include<bits/stdc++.h>
using namespace std;
int main() {
	int tt;cin>>tt;
	while(tt--){
		int n;cin>>n;
		int Max=-1,Min=INT_MAX,p1,p2;
		for(int i=1;i<=n;i++) {
			int tem;cin>>tem;
			if(tem>Max) Max=tem,p1=i;
			if(tem<Min) Min=tem,p2=i;
		}
		if(p1>p2) p1^=p2^=p1^=p2;
		cout<<p1<<' '<<p2<<'\n';
	}
	return 0;
}

B. Subtract Operation

经过 n-1 次操作最后的答案值是最后两个减数的差 set维护一下就好

code 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int tt;cin>>tt;
	while(tt--){
		int n,k;cin>>n>>k;
		vector a(n,0);
		for(int i=0;i<n;i++) cin>>a[i];
		set<int>s{a.begin(),a.end()};
		bool flag=false;
		for(auto it:s) if(s.find(it+k)!=s.end()) {flag=true; break;}
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}

C. Make Equal With Mod

考虑构造的方式： 找到最大的数k %k得到0 %k-1得到1

可以知道同时含有0 1的情况是处理不了的

那么如果1有出现过 就尝试把别的数变到1 就不能有连续的数字k和k+1

如果没有1 那么全部变到0 从大到小依次%当前的Max就可以做到

code 
#include<bits/stdc++.h>
using namespace std;
int main(){
	int tt;cin>>tt;
	while(tt--){
		int n;cin>>n; vector<int>a(n);
		bool f1=false;
		for(int i=0;i<n;i++) {cin>>a[i]; if(a[i]==1) f1=true;}
		multiset<int>s{a.begin(),a.end()};
		bool F1=false;
		if(f1) for(auto it:s) if(s.count(it+1)>=1) {F1=true; break;}
		if(F1) {puts("NO"); continue;}
		puts("YES");
	}
	return 0;
}

D. K-good

给定一个数nn 判断是不是kk个数之和 并且这kk个数mod  k\mod k构成kk的完全剩余系

如果是 输出k 不是输出-1

事实上还是分类讨论 是我想歪了.. 首先很容易得到一个东西

  1. n=[2g+(k−1)]∗k2  if(kmod  2=0)n=[2g+(k-1)]*\frac{k}{2}\ \ if(k\mod 2=0)

  2. n=[g+k−12]∗k  if(kmod  2=1)n=[g+\frac{k-1}{2}]*k\ \ if(k\mod 2=1)

g=∑i=0n−1aig=\sum_{i=0}^{n-1}{a_i} 假设bi=ai∗k+ib_i=a_i*k+i且n=∑i=0n−1bin=\sum_{i=0}^{n-1}b_i

额 然后我这里十分sb的去分解因数找k去了 结果不是边界搞错就是T.. 还在想101810^{18}估计是要Pollard Rho..

事实上注意到肯定有一个因数是奇数 那么如果是2的次幂 就可以输出-1了

但是有了答案也不能草率的输出奇数或者对应的除数作为k 不然可能会有g等于0的情况

题设要求正整数 因此不能有0的出现 因此我们要求1 2式里乘号右边那东西尽量小

code 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt;cin>>tt;
	while(tt--){
		ll n;cin>>n; ll k=1;
		while(n%2==0) n/=2,k*=2;
		if(n==1) cout<<"-1\n";
		else cout<<min(n,2*k)<<'\n';
	}
}

E. Equal Tree Sums

给定n个点的树的连接情况 要求给每个点赋值aia_i 使得删除任意一个点之后 剩余的联通块权值和相等

要求1≤ai≤1051\leq a_i\leq 10^5

看了知乎几个回答 除了小岛的有分析之外别的就直接上染色+度数的方法了 然后再balabala事后分析一波 感觉不太好

这种事后分析感觉没什么帮助

首先随便画个链 可知需要设置负权 进一步能想到设置负权的原因是

假设都是正权 如果删除一个点之后 假设还剩两个联通块 如果权值能平衡 那么不删除这个这点 转而删除旁边的点

权值就势必不会平衡 进一步可知点权的贡献应该都视作-1或1

后面随便搞个Huffman树 完全二叉树 权值与度数关联这个比较好想 就是二分图染色可能是比较常用的套路 就是令一条边的影响为|1|

用度数和其相反数设置过去 一条边给两个点的贡献是-1+1=0 这样整张图的权值为0

在删除一个节点之后 设权值为k 会产生∣k∣|k|个联通块 那么每个联通块在失去了当前节点之后 就会产生一个−∣k∣k-\frac{|k|}{k}的权值

剩余的联通块于是就平衡了

code 
#include<bits/stdc++.h>
using namespace std;
int main() {
	int tt;cin>>tt;
	while(tt--){
		int n;cin>>n;
		vector e(n+1,vector<int>{});
		vector ans(n+1,0);
		for(int i=1;i<n;i++){ int u,v;cin>>u>>v; e[u].push_back(v),e[v].push_back(u); }
		auto dfs = [&](auto self,int u,int f,int k)->void{
			ans[u]=k*e[u].size();
			for(auto it:e[u]){
				if(it==f) continue;
				self(self,it,u,-k);
			}
		};
		dfs(dfs,1,0,1);
		for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
		cout<<endl;
	}
	return 0;
}

F. Parametric MST

给定a_i表示点权 设图G(t)由n个点和边(i,j) 边权为ai∗aj+t(ai+aj)a_i*a_j+t(a_i+a_j)组成

f(t)是G(t)的最小生成树的花费 要求找出f(t)的上界 或者是INF t在实数范围内

简单分析一下 边权只考虑t∗(ai+aj)t*(a_i+a_j) 即t→+∞∣t→−∞t \to +\infty | t\to -\infty

如果所有的形态都是花费>0 或者<0 那么配上t→∞t\to\infty就会趋向INF 不然就确保有解

之后的就不会了 有二分的感觉 但是好像不行.. 后面的内容就属于是搬运题解了..

考虑固定t之后快速求出MST.. 边权变换为(ai+t)∗(aj+t)−t2(a_i+t)*(a_j+t)-t^2 删掉常数t2t^2 答案就是新图的MST-(n−1)t2(n-1)t^2

这个时候连边的方式就是a1a_1和ana_n相连 然后>0>0的连向a1a_1否则ana_n 这个过程满足prime的要求 顺序无所谓

这个形态发生改变的过程在t取到−ai-a_i的时候 然后更新上界就好了 整个过程的瓶颈在于排序

code 
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define il inline
#define rg register
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef long long ll;
typedef double db;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const int MOD=998244353;
const int mod=1e9+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
// head
template<typename T>
inline void scan(T &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9')
		f=(ch=='-')?-1:1,ch=getchar();
	while (ch>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+ch-48,ch=getchar();
	x*=f;
}
void solve(){
	int n;scan(n);
	vector a(n+1,0LL),sum(n+1,0LL);
	rep(i,1,n+1) scan(a[i]);
	sort(a.begin()+1,a.begin()+1+n);
	rep(i,1,n+1) sum[i]=sum[i-1]+a[i];
	if(a[1]*(n-2)+sum[n]>0||a[n]*(n-2)+sum[n]<0){
		puts("INF");
		return;
	}
	ll ans=-2e18;
	auto calc=[&](int pos,ll val)->ll{
		return -(n-1)*val*val+(a[n]+val)*(pos*val+sum[pos])+(a[1]+val)*(sum[n-1]-sum[pos]+(n-1-pos)*val);
	};
	rep(i,1,n) ans=max(ans,calc(i,-a[i]));
	cout<<ans<<endl;
}
int main() {
	int tt;scan(tt);
	while(tt--){
		solve();
	}
	return 0;
}

之前看小岛的回答 说F的确有二分的做法 我没啥思路 网上找了一圈也没见着 小岛还删回答了 哎..

这感觉已经是Div. 1C的难度了 后面的题暂时不开了 补别的场次了..