Codeforces Round #627(Div.3) 解题报告

发布于 2020-03-13  88 次阅读



A - Yet Another Tetris Problem
这题一开始看错题了啊啊啊啊啊
总的来说就是看所有 $a_i$ 的奇偶性相不相同就行......

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[105];
int b[105][105];
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>n;
        int mx=0;
        for(int i=1;i<=n;++i)cin>>a[i];
        int op=(a[1]&1);
        bool flag=1;
        for(int i=1;i<=n;++i)
        {
            if(op!=(a[i
                flag=0;
        }
        if(flag)puts("YES");else puts("NO");
    }
    return 0;
}

B - Yet Another Palindrome Problem
做法比较多,$O(n)$ 或者 $O(n^2)$ 的都可以。我用的 $O(n^2)$,直接枚举每个数,看这个数出现在最左边或者最右边的位置,不相邻就行。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int a[5005];
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        bool flag=0;
        for(int i=1;i<=n;++i)
        {
            int L=-1,R=-1;
            for(int j=1;j<=n;++j)
            {
                if(a[j]==i)
                {
                    L=j;
                    break;
                }
            }
            for(int j=n;j;--j)
            {
                if(a[j]==i)
                {
                    R=j;
                    break;
                }
            }
            if(R-L>=2)
            {
                flag=1;break;
            }
        }
        if(flag)puts("YES");
        else puts("NO");
    }
    return 0;
}

C - Frog Jumps
直接统计最长的连续L就行,答案就是长度+1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
char s[200050];
int main()
{
    int Test;cin>>Test;
    while(Test--)
    {
        scanf(
        s[n+1]=s[n+2]=0;
        int ans=0,tmp=0;
        for(int i=1;i<=n+1;++i)
        {
            if(s[i]=='L')tmp++;
            else ans=max(ans,tmp),tmp=0;
        }
        cout<<ans+1<<'\n';
    }
    return 0;
}

D - Pair of Topics
写了个离散化+BIT......cjj写了个Treap2333

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[200050],b[200050];
ll ans;
ll t[500050];
map <int,int> h;
vector <ll> vec;int tot;
inline int lowbit(int x){return x&(-x);}
inline void change(int x,int val){while(x<=400000){t[x]+=val;x+=lowbit(x);}}
inline int query(int x){int ret=0;while(x){ret+=t[x];x-=lowbit(x);}return ret;}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)scanf(
    for(int i=1;i<=n;++i)scanf(
    for(int i=1;i<=n;++i)
    {
        vec.push_back(a[i]-b[i]);
        vec.push_back(b[i]-a[i]+1);
    }
    sort(vec.begin(),vec.end());
    for(auto i:vec)
    {
        if(h[i])continue;
        h[i]=++tot;
    }
    for(int i=1;i<=n;++i)
    {
        ans+=query(h[a[i]-b[i]]);
        change(h[b[i]-a[i]+1],1);
    }
    cout<<ans<<endl;
    return 0;
}

E - Sleeping Schedule
一道比较裸的dp...
设 $dp(i,j)$ 表示当前到第 $i$ 个数,总和对 $h$ 取模为 $j$ 的最大值,然后转移就两种情况取最大值。当 $j$ 在 $[l,r]$ 内时 $dp(i,j)++$ 。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,h,l,r;
int dp[2050][2050],f[2050][2050];
int ans;
int a[2050];
int main()
{
    scanf(
    for(int i=1;i<=n;++i)cin>>a[i];
    f[1][0]=1;
    for(int i=1;i<=n+1;++i)
    {
        for(int j=0;j<h;++j)
        {
            if(f[i][j]==0)continue;
            if(i>1&&j<=r&&j>=l)dp[i][j]++;
            dp[i+1][(j+a[i]
            dp[i+1][(j+a[i]-1+h
            ans=max(ans,dp[i][j]);
            f[i+1][(j+a[i]
        }
    }
    cout<<ans<<endl;
    return 0;
}

F - Maximum White Subtree
比较板的换根dp辣
我们将这棵树转成有根树,以 $1$ 为根
设 $f_u$ 表示 $u$ 从 $u$ 开始往下的 $u$ 的子树的最大值,$g_u$ 表示从 $u$ 往父亲走(不包括 $u$ )的最大值。
翻译一下就是把含 $u$ 的子树搞成两部分,一部分是 $u$ 的子树内(含 $u$ ),一部分是 $u$ 的子树外(不含 $u$ ),然后两次dfs,第一次统计 $f_u$,即 $f_u=\sum max(0,f_v)$ ,然后第二次dfs就统计 $g_u$,即 $g_u=max(f_{fa}+g_{fa}-max(f_u,0),0)$
最后答案就是 $f_u+g_u$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200050;
int f[N],g[N];
int n;
struct edge
{
    int v,nxt;
}e[N<<1];
int a[N];
int head[N],ecnt;
inline void ad(int u,int v)
{
    e[++ecnt].v=v;e[ecnt].nxt=head[u];
    head[u]=ecnt;
}
void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs1(v,u);
        if(f[v]>=0)f[u]+=f[v];
    }
}
void dfs2(int u,int fa)
{
    if(fa)g[u]=max(f[fa]-f[u]*(f[u]>=0)+g[fa],0);
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs2(v,u);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)scanf(
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf(
        ad(x,y);ad(y,x);
    }
    for(int i=1;i<=n;++i)
    {
        if(a[i]==0)f[i]=-1;
        else f[i]=1;
    }
    dfs1(1,0);
    dfs2(1,0);
//    for(int i=1;i<=n;++i)
//    {
//        printf("f
//        printf("g
//    }
    for(int i=1;i<=n;++i)
    {
        printf(
    }
    return 0;
}