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$并且负数个数是奇数个

#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

大佬题解
$$\{\begin{array}{l}{b}_2=b_1+{\Delta }_1({\Delta }_1\ge 0)\\ b_1+c_1=a_1\\ b_2+c_2=a_2\\ c_1\ge c_2\end{array}$$由上述条件可以推出${\Delta }_1$与$a_1$ 、 $a_2$的关系即$a_1+{\Delta }_1\ge a_2$
肯定是希望$\sum \Delta$ 尽可能小，所以$\Delta$ 取到等号最优，即 ${\Delta }_i=a_{i+1}-a_i$
对于$b_n=b_1+\sum \Delta$，而$c_1$我们希望最好和$b_n$接近，分析可知$c_1$和$b_n$是地位相同的即$c_1$和$b_n$可以互推，因而最优解能够保证存在一组解是他们两个最接近。
$c_1=b_1+\sum \Delta ->c_1+c_1=b_1+c_1+\sum \Delta =a_1+\sum \Delta$
因此$max(b_n,c_1)=\lceil \frac{a_1+\sum \Delta }{2}\rceil$即为最终答案。
注意负数上取整和正数不一样

#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