欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Codeforces Round #670 (Div. 2) (A~E题解)

程序员文章站 2022-03-23 22:09:06
Link!Asb题B直接枚举求一遍#include#define int long long#define N 100015#define rep(i,a,n) for (int i=a;i<=n;i++)#define per(i,a,n) for (int i=n;i>=a;i--)#define inf 0x3f3f3f3f3f3f3f3f#define pb push_back#define mp make_pair#d...

Link!

A

sb题

B

直接枚举求一遍

#include<bits/stdc++.h>
#define int long long
#define N 100015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
using namespace std;
int t,n,a[N];
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	cin>>t;
 	while(t--){
 		int ans = -inf;
 		cin>>n;
 		rep(i,1,n) cin>>a[i];
 		sort(a+1,a+n+1);
 		rep(i,1,n-4){
 			ans = max(ans,a[i]*a[i+1]*a[i+2]*a[i+3]*a[i+4]);
 		}
 		ans = max({ans,a[1]*a[2]*a[n]*a[n-1]*a[n-2],a[1]*a[2]*a[3]*a[4]*a[n]});
 		cout << ans << endl;
 	}
	return 0;
}

C

如果只有一个重心就不用管,否则把一个重心子树里的一个叶子移到另外一个里。

#include<bits/stdc++.h>
#define ll long long
#define N 100015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
using namespace std;
int t,n,head[N],f[N],siz[N],son[N],fat[N],cnt;
struct edge{
	int to,next;
	edge(){}
	edge(int a,int b){to = a;next = b;}
}e[N<<1];
void init(){
	cnt = 0;
	rep(i,1,n) head[i] = -1;
	rep(i,1,n) f[i] = fat[i] = son[i] = siz[i] = 0;
}
void add(int u,int v){
	e[++cnt] = edge(v,head[u]);
	head[u] = cnt;
}
void dfs(int u,int fa){
	siz[u] = 1;fat[u] = fa;
	for(int i = head[u];~i;i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v,u);siz[u] += siz[v];
		if(siz[v] > siz[son[u]]){
			son[u] = v;
		}
	}
	f[u] = siz[son[u]];
	if(n-siz[u] > siz[son[u]]){
		son[u] = fa;f[u] = n-siz[u];
	}
}
int get_leaf(int u,int fa){
	fat[u] = fa;
	int flag = 0;
	for(int i = head[u];~i;i = e[i].next){
		int v = e[i].to;
		if(v == fa) continue;
		int ans = get_leaf(v,u);
		if(ans) return ans;
		flag = 1;
	}
	if(flag == 0) return u;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	scanf("%d",&t);
 	while(t--){
 		scanf("%d",&n);
 		init();
 		rep(i,2,n){
 			int u,v;
 			scanf("%d%d",&u,&v);
 			add(u,v);add(v,u);
 		}
 		dfs(1,0);
 		int val = *min_element(f+1,f+n+1);
 		VI temp;
 		rep(i,1,n) if(f[i] == val) temp.pb(i);
 		if(temp.size() > 1){
 			int u = temp[0],v = temp[1],tu = get_leaf(u,v);
			printf("%d %d\n",tu,fat[tu]);
			printf("%d %d\n",tu,v);
 		}else{
 			int u = 1,v = e[head[u]].to;
 			printf("%d %d\n",u,v);
 			printf("%d %d\n",u,v);
 		}
 	}
	return 0;
}

D

先求出差分数组 d [ i ] d[i] d[i],如果 d [ i ] > 0 d[i] > 0 d[i]>0,就应该是 c [ i ] = c [ i − 1 ] + d [ i ] c[i] = c[i-1] + d[i] c[i]=c[i1]+d[i],否则是 b [ i ] = b [ i − 1 ] + d [ i ] b[i] = b[i-1] + d[i] b[i]=b[i1]+d[i]
有等式 b [ 1 ] + c [ 1 ] = d [ 1 ] b[1] + c[1] = d[1] b[1]+c[1]=d[1]且为了让最大值最小,让 b [ 1 ] = c [ n ] b[1] = c[n] b[1]=c[n].
p o s pos pos表示 ∑ d [ i ] > 0 d [ i ] \sum_{d[i] > 0} d[i] d[i]>0d[i],有 c [ n ] = c [ 1 ] + p o s c[n] = c[1] + pos c[n]=c[1]+pos
于是 c [ 1 ] = d [ 1 ] − p o s 2 , b [ 1 ] = d [ 1 ] + p o s 2 c[1] = \frac{d[1]-pos}{2} , b[1] = \frac{d[1]+pos}{2} c[1]=2d[1]pos,b[1]=2d[1]+pos,答案即是 b [ 1 ] b[1] b[1],对于区间修改在差分数组上单点修改即可。

#include<bits/stdc++.h>
#define int long long
#define N 100015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
using namespace std;
int n,q,a[N],D[N],l[N],r[N],val[N],pos,neg,ans[N];
void change(int p,int x){
	if(p == 1||p>n) return;
	if(D[p] > 0){
 		if(D[p] + x < 0) pos -= D[p],neg += D[p] + x;
 		else pos += x;
 	}else{
 		if(D[p] + x > 0) neg -= D[p],pos += D[p] + x;
 		else neg += x;
 	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	ios::sync_with_stdio(false);
 	cin>>n;
 	rep(i,1,n) cin>>a[i];
 	cin>>q;
 	rep(i,1,q) cin>>l[i]>>r[i]>>val[i];
 	pos = neg = 0;
 	rep(i,1,n) D[i] = a[i]-a[i-1];
 	rep(i,2,n) {
 		if(D[i]>0) pos += D[i];
 		else neg += D[i];
 	}
 	rep(i,0,q){
 		if(i != 0) {
 			change(l[i],val[i]);change(r[i]+1,-val[i]);
 			D[l[i]] += val[i];D[r[i]+1] -= val[i];
 		}
 		ans[i] = (int)floor(1.0*(D[1]+pos+1)/2);
 	}
 	rep(i,0,q) cout << ans[i] << endl;
	return 0;
}

E

先筛出每个质数。
有一个显然的结论,至多有一个 > n > \sqrt{n} >n 的质因子,我们把 > n > \sqrt{n} >n 的因子分块,每次将一个整块内的质数删完,然后输出 A   1 A \ 1 A 1判断 x x x是否在这个块内。
对于 ≤ n \leq \sqrt{n} n 的数 p p p,我们暴力判断 p 1 , p 2 , p 3 . . . p^1,p^2,p^3... p1,p2,p3...是否存在即可。

#include<bits/stdc++.h>
#define ll long long
#define N 100015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
#define ff fflush(stdout)
#define L 98
using namespace std;
bool notprime[N];
int n,tot,p[N],maxn,res = 1;
void init(int x){
	rep(i,2,x){
		if(!notprime[i]) p[++tot] = i;
		for(int j = 1;p[j]*i <= x&&j <= tot;++j){
			notprime[i*p[j]] = 1;
			if(i%p[j] == 0) break;
		}
	}
}
void solve(int x){
	int cur = 1,temp;
	printf("B %d\n", x);
	ff;
	scanf("%d", &temp);
	while(1){
		cur *= x;
		if(cur > n) break;
		printf("A %d\n",cur);
		ff;
		scanf("%d",&temp);
		if(temp == 0) break;
		res *= x;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	scanf("%d",&n);
 	init(n);int a;
 	rep(i,1,tot) if(1ll*p[i]*p[i] <= 1ll*n) maxn = i;
 	int sum = n;
 	rep(i,1,L){
 		int l = (i-1)*L+1,r = min(i*L,tot);
 		rep(j,l,r){
 			if(j <= maxn) continue;
 			printf("B %d\n",p[j]);
 			ff;
 			scanf("%d",&a);
 			sum -= a;
 		}
 		printf("A 1\n");
 		ff;
 		scanf("%d",&a);
 		if(a != sum){
 			rep(j,l,r){
 				if(j <= maxn) continue;
 				printf("A %d\n",p[j]);
 				ff;
 				scanf("%d",&a);
 				if(a){
 					res = p[j];
 					break;
 				}
 			}
 			break;
 		}
 		if(r == tot) break;
 	}
 	rep(i,1,maxn) solve(p[i]);

 	printf("C %d\n", res);
 	ff;
	return 0;
}

手速不太行。
D没开long long WA*3
倒开yyds,以后继续CABDE

本文地址:https://blog.csdn.net/qq_44062973/article/details/108589823