Codeforces Round #627 (Div. 3)

A. Yet Another Tetris Problem
$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,t;
int main(){
    cin>>t;
    while(t--){
        sc("%d",&n);
        int b[2]={0};
        for(int i=1,x;i<=n;i++){
            sc("%d",&x);
            b[x&1]++;
        }
        if(b[0]&&b[1])O("NO");
        else O("YES");
    }
}

B. Yet Another Palindrome Problem
$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,t;
int a[5005];
int main(){
    cin>>t;
    while(t--){
        sc("%d",&n);
        vector<int>v[n+2];
        for(int i=1;i<=n;i++){
            sc("%d",&a[i]);
            v[a[i]].push_back(i);
        }
        int f=0;
        for(int i=1;i<=n;i++){
            int l=0,r=(int)v[i].size()-1;
            if(r>0&&v[i][r]>v[i][l]+1)f=1;
        }
        if(f)O("YES");else O("NO");
    }
}

C. Frog Jumps
二分或者找 $R$ 间隔最大的。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n;
char s[N];
int main(){
    int t;cin>>t;
    while(t--){
        sc("%s",s+1);
        n=strlen(s+1);
        int l=0,ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='R')ans=max(ans,i-l),l=i;
        }
        ans=max(ans,n+1-l);
        pr("%d\n",ans);
    }
}

D. Pair of Topics
$a_i-b_i>b_j-a_j,(i<j)$ 。对 $b_j-a_j$ 离散化建树状数组 ,查询 $a_i-b_i$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,t=0;
int a[N],b[N],c[N];
int sum[N];
int getid(int x){return lower_bound(c+1,c+1+t,x)-c;}
void up(int x,int vl){for(int i=x;i<=t;i+=i&-i)sum[i]+=vl;}
int q(int x){
    int ans=0;
    for(int i=x;i;i&=i-1)ans+=sum[i];
    return ans;
}
int main(){
    sc("%d",&n);
    for(int i=1;i<=n;i++)sc("%d",&a[i]);
    for(int i=1;i<=n;i++)sc("%d",&b[i]);
    for(int i=1;i<=n;i++){
        c[++t]=b[i]-a[i];
        c[++t]=a[i]-b[i];
    }
    sort(c+1,c+1+t);
    t=unique(c+1,c+1+t)-c-1;
    for(int i=1;i<=n;i++)up(getid(b[i]-a[i]),1);
    ll ans=0;
    for(int i=1;i<=n;i++){
        up(getid(b[i]-a[i]),-1);
        ans+=q(getid(a[i]-b[i])-1);
    }
    O(ans);
}

E. Sleeping Schedule
简单dp,从上一个状态递推下来即可。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,h,l,r;
int dp[2005][2005];
int main(){
    sc("%d%d%d%d",&n,&h,&l,&r);
    me(dp,-1);dp[0][0]=0;
    for(int i=1;i<=n;i++){
        int x;
        sc("%d",&x);
        for(int j=0;j<h;j++){
            int a=(j+x)%h;
            int b=(j+x-1)%h;
            if(~dp[i-1][j]){
                dp[i][a]=max(dp[i][a],dp[i-1][j]+(a>=l&&a<=r));
                dp[i][b]=max(dp[i][b],dp[i-1][j]+(b>=l&&b<=r));
            }
        }
    }
    int ans=0;
    for(int i=0;i<h;i++)ans=max(ans,dp[n][i]);
    O(ans);
}

F. Maximum White Subtree
$dp$ 换根，对于 $u$ 节点可以从父节点转移, $dp[u]+dp[fa]-dp[u]$ 。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,a[N];
int dp[N]={0};
vector<int>g[N];
void dfs1(int u,int fa){
    for(int v:g[u]){
        if(v==fa)continue;
        dfs1(v,u);
        if(dp[v]>0)dp[u]+=dp[v];
    }
    dp[u]+=a[u]?1:-1;
}
void dfs2(int u,int fa){
    if(fa!=0){
        if(dp[u]>=0)dp[u]=max(dp[u],dp[fa]);
        else dp[u]=max(dp[u],dp[fa]-1);
    }
    for(int v:g[u]){
        if(v==fa)continue;
        dfs2(v,u);
    }
}
int main(){
    sc("%d",&n);
    for(int i=1;i<=n;i++)sc("%d",&a[i]);
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0);
    db(dp+1,dp+1+n);
}