Codeforces Round #670 (Div. 2)
A - Subset Mex
知道NIM游戏应该都知道Mex。那就直接贪心分组,保证尽可能每组都存在每一个自然数,然后按照Mex定义直接求答案即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int n;
int cnt1[N],cnt2[N];
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
memset(cnt1,0,sizeof cnt1);
memset(cnt2,0,sizeof cnt2);
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
if(cnt1[a])
cnt2[a]++;
else
cnt1[a]++;
}
int res=0;
for(int i=0;i<=100;i++)
if(!cnt1[i])
{
res+=i;
break;
}
for(int i=0;i<=100;i++)
if(!cnt2[i])
{
res+=i;
break;
}
cout<<res<<endl;
}
return 0;
}
B - Maximum Product
由于最终选出的数非常少,因此可以枚举选出多少个负数,剩下的选非负数。
如果最终结果可以为正数那么就选择绝对值尽量大的数,否则选择绝对值尽量小的数。
最终结果一定是负数的条件:①没有正数②
n
=
5
n=5
n=5并且负数个数是奇数个
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const int N=100010;
int n;
ll a[N];
ll b[N],c[N];
int cntb,cntc;
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
cntb=cntc=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(a[i]<0) b[++cntb]=a[i];
else c[++cntc]=a[i];
}
sort(b+1,b+1+cntb);
sort(c+1,c+1+cntc);
reverse(c+1,c+1+cntc);
ll res=-1e18;
if(cntc==0||(cntc==2&&n==5)||(cntc==4&&n==5))
{
reverse(c+1,c+1+cntc);
reverse(b+1,b+1+cntb);
}
for(int i=0;i<=min(cntb,5);i++)
{
int j=5-i;
if(j>cntc) continue;
ll now=1;
if(i)
{
for(int k=1;k<=i;k++) now*=b[k];
}
if(j)
{
for(int k=1;k<=j;k++) now*=c[k];
}
res=max(res,now);
}
cout<<res<<endl;
}
return 0;
}
C - Link Cut Centroids
- 如果重心只有一个,随便断一条边再连上。
- 如果重心有两个,那么必定相邻,
不难猜想出只要把其中的一个重心连接的叶子接到另一个重心去即可。(貌似把其他一个重心的子树接到另一个重心也可以)
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int n;
int h[N],e[2*N],ne[2*N],idx;
int sz[N];
vector<int> cnt;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
int fa[N];
void dfs1(int u,int p)
{
fa[u]=p;
sz[u]=1;
int mx=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==p) continue;
dfs1(j,u);
sz[u]+=sz[j];
mx=max(sz[j],mx);
}
mx=max(mx,n-sz[u]);
if(2*mx<=n) cnt.push_back(u);
}
int now;
int x,y;
void dfs2(int u,int c)
{
if(now) return;
int d=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(j==fa[u]||j==c) continue;
d++;
dfs2(j,c);
}
if(d==0)
{
x=u;
y=fa[u];
now++;
return;
}
}
int main()
{
IO;
int T=1;
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) h[i]=-1;
cnt.clear();
idx=now=0;
for(int i=1;i<n;i++)
{
int a,b;
cin>>a>>b;
add(a,b),add(b,a);
}
dfs1(1,0);//找重心
if(cnt.size()==1)
{
dfs2(cnt[0],cnt[1]);//找叶子
cout<<x<<' '<<y<<endl;
cout<<x<<' '<<y<<endl;
}
else
{
dfs2(cnt[0],cnt[1]);
cout<<x<<' '<<y<<endl;
cout<<x<<' '<<cnt[1]<<endl;
}
}
return 0;
}
就做了上面三个题1h,竟然还上分了!可能我分数比较低把。。B w了2次,C w了1次。。
D - Three Sequences
大佬题解
{
b
2
=
b
1
+
Δ
1
(
Δ
1
≥
0
)
b
1
+
c
1
=
a
1
b
2
+
c
2
=
a
2
c
1
≥
c
2
\begin{cases} b_2=b_1+\Delta_1(\Delta_1 \ge0) \\ b_1+c_1=a_1 \\ b_2+c_2=a_2 \\ c_1\ge c_2\end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧b2=b1+Δ1(Δ1≥0)b1+c1=a1b2+c2=a2c1≥c2由上述条件可以推出
Δ
1
\Delta_1
Δ1与
a
1
a_1
a1 、
a
2
a_2
a2的关系即
a
1
+
Δ
1
≥
a
2
a_1+\Delta_1 \ge a_2
a1+Δ1≥a2
肯定是希望
∑
Δ
\sum \Delta
∑Δ 尽可能小,所以
Δ
\Delta
Δ 取到等号最优,即
Δ
i
=
a
i
+
1
−
a
i
\Delta_i=a_{i+1}-a_i
Δi=ai+1−ai
对于
b
n
=
b
1
+
∑
Δ
b_n=b_1+\sum \Delta
bn=b1+∑Δ,而
c
1
c_1
c1我们希望最好和
b
n
b_n
bn接近,分析可知
c
1
c_1
c1和
b
n
b_n
bn是地位相同的即
c
1
c_1
c1和
b
n
b_n
bn可以互推,因而最优解能够保证存在一组解是他们两个最接近。
c
1
=
b
1
+
∑
Δ
−
>
c
1
+
c
1
=
b
1
+
c
1
+
∑
Δ
=
a
1
+
∑
Δ
c_1=b_1+\sum \Delta->c_1+c_1=b_1+c_1+\sum\Delta=a_1+\sum\Delta
c1=b1+∑Δ−>c1+c1=b1+c1+∑Δ=a1+∑Δ
因此
m
a
x
(
b
n
,
c
1
)
=
⌈
a
1
+
∑
Δ
2
⌉
max(b_n,c_1)=\left \lceil \frac{a_1+\sum \Delta}{2} \right \rceil
max(bn,c1)=⌈2a1+∑Δ⌉即为最终答案。
注意负数上取整和正数不一样
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N],d[N];
int n,q;
ll calc(ll x)
{
if(x>=0) return (x+1)/2;
else return x/2;
}
int main()
{
IO;
int T=1;
//cin>>T;
while(T--)
{
ll now=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
d[i]=a[i]-a[i-1];
if(i>1) now+=max(0ll,d[i]);
}
cout<<calc(now+a[1])<<'\n';
cin>>q;
while(q--)
{
int l,r;
ll c;
cin>>l>>r>>c;
if(l==1) a[1]+=c;
r++;
if(l>1)
{
now-=max(0ll,d[l]);
d[l]+=c;
now+=max(0ll,d[l]);
}
if(r<=n)
{
now-=max(0ll,d[r]);
d[r]-=c;
now+=max(0ll,d[r]);
}
cout<<calc(now+a[1])<<'\n';
}
}
return 0;
}
D题需要认真静下心来分析,需要多多练习
要加油哦~
本文地址:https://blog.csdn.net/Fighting_Peter/article/details/108560286
推荐阅读
-
Codeforces Round #595 (Div. 3)D1D2 贪心 STL
-
Codeforces Round #655 (Div. 2) A. Omkar and Completion
-
Codeforces Round #656 (Div. 3)D. a-Good String(递归+dfs)
-
Codeforces Round #487 (Div. 2)
-
CodeForces 1324 - Codeforces Round #627 (Div. 3)
-
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)