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

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]>0$，就应该是$c[i]=c[i-1]+d[i]$，否则是$b[i]=b[i-1]+d[i]$
有等式$b[1]+c[1]=d[1]$且为了让最大值最小，让$b[1]=c[n]$.
设$pos$表示${\sum }_{d[i]>0}d[i]$,有$c[n]=c[1]+pos$
于是$c[1]=\frac{d[1]-pos}{2},b[1]=\frac{d[1]+pos}{2}$，答案即是$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

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

#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