Codeforces Round #670 (Div. 2) (A~E题解)
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[i−1]+d[i],否则是
b
[
i
]
=
b
[
i
−
1
]
+
d
[
i
]
b[i] = b[i-1] + d[i]
b[i]=b[i−1]+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
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #487 (Div. 2)
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
Codeforces Round #649 (Div. 2) C-Ehab and Prefix MEXs
-
Educational Codeforces Round 71 (Rated for Div. 2)E. XOR Guessing
-
Codeforces Round #659 (Div. 2) A. Common Prefixes(字符串,思维)
-
Codeforces Round #610 (Div. 2)
-
Codeforces Round #670 (Div. 2)
-
Codeforces Round #665 (Div. 2)