CodeForces 1324 - Codeforces Round #627 (Div. 3)

第一次遇到这么水的div. 3。。。

本来想抢d一血的，结果失败了。。然后干脆就\(45\mathrm{min}\)ak了。。。

codeforces比赛页面传送门

a - yet another tetris problem

洛谷题目页面传送门 & codeforces题目页面传送门

给出\(n\)个数，第\(i\)个数为\(a_i\)。每次操作可以选择一个\(i\in[1,n]\)并令\(a_i=a_i+2\)，或令\(\forall i\in[1,n],a_i=a_i-1\)。问能否经过若干次操作，将\(a\)数组清零。本题多测。

结论显然，能将\(a\)数组清零当且仅当所有数奇偶性相同。

证明：若所有数奇偶性相同，显然可以通过若干次第\(1\)种操作把它们变成两两相等，再通过若干次第\(2\)种操作把它们都变成\(0\)；若存在\(2\)个数\(a_i,a_j\)奇偶性不相同，则若对\(a_i,a_j\)做第\(1\)种操作，那么它们奇偶性不变，若做第\(2\)种操作，它们奇偶性互换，所以它们奇偶性永远不可能相同，自然也无法都变成\(0\)。得证。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
void mian(){
    int n;
    cin>>n;
    int x;
    cin>>x;
    x&=1;//a[1]的奇偶性
    n--;
    bool ok=true;
    while(n--){
        int y;
        cin>>y;
        ok&=x==(y&1);//奇偶性要全部相同
    }
    puts(ok?"yes":"no");
}
int main(){
    int testnum;
    cin>>testnum;
    while(testnum--)mian();
    return 0;
}

b - yet another palindrome problem

洛谷题目页面传送门 & codeforces题目页面传送门

给出\(n\)个数，第\(i\)个数为\(a_i\)。问是否存在长度至少为\(3\)的回文子序列。本题多测。

\(n\in[3,5000],\sum n\leq5000\)。

显然，任何一个回文子序列的两端相等，又因为要求长度至少为\(3\)，所以两端的距离至少为\(2\)。于是存在\(2\)个距离至少为\(2\)且相等的数是存在长度至少为\(3\)的回文子序列的必要条件。若存在\(2\)个距离至少为\(2\)且相等的数，那么随便选择它们之间的任意一个数即可构成长度为\(3\)的回文子序列。于是存在\(2\)个距离至少为\(2\)且相等的数是存在长度至少为\(3\)的回文子序列的充分条件。综上，存在\(2\)个距离至少为\(2\)且相等的数是存在长度至少为\(3\)的回文子序列的充要条件。

直接暴力枚举数对，时间复杂度\(\mathrm o\!\left(\sum n^2\right)\)。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
const int n=5000;
int n;
int a[n+1];
void mian(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)for(int j=i+2/*距离至少为2*/;j<=n;j++)if(a[i]==a[j])/*相等*/{puts("yes");return;}
    puts("no");
}
int main(){
    int testnum;
    cin>>testnum;
    while(testnum--)mian();
    return 0;
}

c - frog jumps

洛谷题目页面传送门 & codeforces题目页面传送门

有\(n+2\)个格子，编号\(0\sim n+1\)。\(\forall i\in[1,n]\)，格子\(i\)上有一个字母\(a_i\in\{\texttt l,\texttt r\}\)，分别表示在格子\(i\)上只能往左、右跳。青蛙一开始站在格子\(0\)，\(a_0=\texttt r\)。求一个最小的\(d\)，表示青蛙一次能跳\(1\sim d\)格且不能出格，使得青蛙能到达格子\(n+1\)。保证总有符合要求的\(d\)。本题多测。

首先，不难发现对于任意一个\(d\)，能到达的格子组成前缀。证明：反证法。若不组成前缀，即存在\(i\in[1,n]\)使得\(i\)不能到达且\(i+1\)能到达。此时必存在一个\(x\in[0,i)\)使得\(a_x=\texttt r\)且\(x\)能到达\([i+1,n+1]\)中任意一个格子\(y\)。根据青蛙跳的规则，\([x+1,y]\)内任意一个格子都能从\(x\)到达，又\(x<i,y>i\rightarrow i\in[x+1,y]\)，与\(i\)不能到达矛盾。得证。

接下来，又双叒叕不难发现往左跳的格子不起丝毫作用，即任意一个能到达的格子都可以只往右跳来到达。证明：数学归纳法。设对于某一个\(d\)，能到达的格子组成的前缀为\([0,r](r\geq0)\)。

1. 格子\(0\)显然满足可以只往右跳来到达；
2. \(\forall x\in[1,r]\)，假设\(\forall i\in[0,x)\)，格子\(i\)都满足可以只往右跳来到达。对于\(x\)的某一种到达方式，设最后一步是由\(y\)跳过来的，分\(2\)种情况：
   1. \(y<x\)。此时最后一步一定是往右跳。再加上\(\forall i\in[0,x)\)，格子\(i\)都满足可以只往右跳来到达，可以得出格子\(x\)满足可以只往右跳来到达；
   2. \(y>x\)。此时在\(y\)的到达方式中，必有一步是从\(z\in[1,x)\)跳到\(xx\in[x,n+1]\)。根据青蛙跳的规则，\([z+1,xx]\)内任意一个格子都能从\(z\)到达，又\(x>z,x\leq xx\rightarrow x\in[z+1,xx]\)，所以\(x\)能被\(z\)往右跳到达。再加上\(z\in[1,x)\subsetneq[0,x)\)且\(\forall i\in[0,x)\)，格子\(i\)都满足可以只往右跳来到达，可以得出格子\(x\)满足可以只往右跳来到达。
   综上，若\(\forall i\in[0,x)\)，格子\(i\)都满足可以只往右跳来到达，那么格子\(x\)满足可以只往右跳来到达。

综上，得证。

于是我们可以把所有\(a_i=\texttt r\)的\(i\)有序地抽出来组成序列\(pos\)，特殊地，\(pos_{|pos|}=n+1\)。显然，\(\forall i\in[1,|pos|),pos_i\to pos_{i+1}\)，这种跳法最省\(d\)。要满足每次跳，起点和终点的距离都在\(d\)以内，所以答案是\(d=\max\limits_{i=1}^{|pos|-1}\{pos_{i+1}-pos_i\}\)。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int n=200000;
int n;
char a[n+5];
void mian(){
    cin>>a+1;
    n=strlen(a+1);
    vector<int> pos;
    pos.pb(0);
    for(int i=1;i<=n;i++)if(a[i]=='r')pos.pb(i);
    pos.pb(n+1);
    int ans=0;
    for(int i=0;i+1<pos.size();i++)ans=max(ans,pos[i+1]-pos[i]);//取最大距离 
    cout<<ans<<"\n";
}
int main(){
    int testnum;
    cin>>testnum;
    while(testnum--)mian();
    return 0;
}

d - pair of topics

洛谷题目页面传送门 & codeforces题目页面传送门

给定\(2\)个长度为\(n\)的数组\(a,b\)，求有多少个有序对\((i,j)\)满足\(i<j\)且\(a_i+a_j>b_i+b_j\)。

\(n\in\left[2,2\times10^5\right],a_i,b_i\in\left[1,10^9\right]\)。

\(a_i+a_j>b_i+b_j\leftrightarrow a_i-b_i>b_j-a_j\)，这样左边仅关于\(i\)，右边仅关于\(j\)。于是我们把\(\forall i\in[1,n],a_i-b_i,b_i-a_i\)这\(2n\)个数一起离散化咯，然后类似bit求逆序对那样建一个值域bit，从后往前扫描，每扫到一个数\(i\)，给答案贡献值域区间\((-\infty,a_i-b_i)\)上的区间计数的结果，再将\(b_i-a_i\)插入bit。时间复杂度\(\mathrm o(n\log_2n)\)。

答案会爆int，记得开long long。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long//答案爆int
#define pb push_back
int lowbit(int x){return x&-x;}
const int n=200000;
int n;
int a[n+1];
int b[n+1];
vector<int> nums;
void discrete(){//离散化 
    sort(nums.begin(),nums.end());
    nums.resize(unique(nums.begin(),nums.end())-nums.begin());
    for(int i=1;i<=n;i++)
        b[i]=lower_bound(nums.begin(),nums.end(),-a[i])-nums.begin()+1,
        a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
}
struct bitree{//bit 
    int sum[2*n+1];
    void init(){memset(sum,0,sizeof(sum));}
    void add(int x){//添加x 
        while(x<=nums.size())sum[x]++,x+=lowbit(x);
    }
    int sum(int x){//前缀计数 
        int res=0;
        while(x)res+=sum[x],x-=lowbit(x);
        return res;
    }
}bit;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[i]-=x;
        nums.pb(a[i]);//a[i]-b[i]
        nums.pb(-a[i]);//b[i]-a[i]
    }
    discrete();
    int ans=0;
    bit.init();
    for(int i=n;i;i--){
        ans+=bit.sum(a[i]-1);//贡献答案 
        bit.add(b[i]);//添加 
    }
    cout<<ans;
    return 0;
}

e - sleeping schedule

洛谷题目页面传送门 & codeforces题目页面传送门

在vova的世界里，一天\(h\mathrm h\)。vova会睡\(n\)次觉，每次睡刚好\(1\)天。第\(i\)次会在第\(i-1\)次睡觉醒来后\((a_i-1)\mathrm h\)或\(a_i\mathrm h\)后入睡，特殊地，第\(0\)次睡觉在第\(0\mathrm h\)醒来。设一次睡觉是在入睡当天的第\(x\mathrm h\)入睡，若\(x\in[l,r]\)，则称此次睡觉是好的。问最多能有多少次好的睡觉。

\(n\in[1,2000],h\in[3,2000],0\leq l\leq r<h,a_i\in[1,h)\)。

可以说是基础dp。

设\(dp_{i,j}\)表示考虑到第\(i\)次睡觉，第\(i\)次睡觉在当天第\(j\mathrm h\)醒来时最多的好的睡觉次数。边界为\(dp_{i,j}=\begin{cases}0&j=0\\- \infty&j\neq0\end{cases}\)（\(j\neq0\)时状态不合法），目标为\(\max\limits_{i=0}^{h-1}\{dp_{n,i}\}\)，状态转移方程为\(dp_{i,j}=\max\!\left(dp_{i-1,(j-(a_i-1))\bmod h},dp_{i-1,(j-a_i)\bmod h}\right)+[j\in[l,r]]\)（选择在上一次睡觉醒来后\((a_i-1)\mathrm h\)还是\(a_i\mathrm h\)后入睡）。时间复杂度\(\mathrm o(nh)\)。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int n=2000,h=2000;
int dp[n+1][h];
int n,h,l,r;
int a[n+1];
bool in(int x){return l<=x&&x<=r;}//[x in [l,r]]
int main(){
    cin>>n>>h>>l>>r;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<h;i++)dp[0][i]=-inf;//不合法状态 
    for(int i=1;i<=n;i++)for(int j=0;j<h;j++)//dp 
        dp[i][j]=max(dp[i-1][(j-a[i]+1+h)%h],dp[i-1][(j-a[i]+h)%h])+in(j);//状态转移方程 
    cout<<*max_element(dp[n],dp[n]+h);//目标 
    return 0;
}

f - maximum white subtree

洛谷题目页面传送门 & codeforces题目页面传送门

给定一棵树\(t=(v,e),|v|=n,|e|=n-1\)，节点\(i\)有一个权值\(a_i\in\{0,1\}\)，分别表示是白点、黑点。\(\forall i\in[1,n]\)，找一个树上连通子图，设此图内白、黑点各有\(cnt1,cnt2\)个，要求最大化\(cnt1-cnt2\)。输出最大值。

\(n\in\left[1,2\times10^5\right]\)。

先吐槽一句：为什么我总共就打过\(4\)场div. 3，其中\(3\)场的f都是树形dp¿¿¿/yiw

非常显然的树形dp+二次扫描与换根。

首先，如果当前要求的这个点\(x\)是树根的话，那一切都好办了。设\(dp_i\)表示在以\(x\)为整棵树的根的情况下，在以\(i\)为根的子树内选连通子图，必须包含\(i\)时\(cnt1-cnt2\)的最大值。目标是\(dp_x\)，状态转移方程是\(dp_i=\sum\limits_{j\in son_i}\max(0,dp_j)+\begin{cases}-1&a_i=0\\1&a_i=1\end{cases}\)（累加以每个儿子为根的子树能给\(dp_i\)带来的贡献的最大值，如果为负就不选）。时间复杂度\(\mathrm o(n)\)。

然而题目要求对于所有点。不妨先令\(1\)为根求出所有点的dp值，再一遍二次扫描与换根求出所有点的答案。时间复杂度\(\mathrm o(n)\)。

总时间复杂度\(\mathrm o(n)+\mathrm o(n)=\mathrm o(n)\)。

下面是ac代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int n=200000;
int n;
bool a[n+1];//点权
vector<int> nei[n+1];
int dp[n+1];
void dfs(int x=1,int fa=0){//求出以1为根时所有点的dp值 
    dp[x]=a[x]?1:-1;
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa)continue;
        dfs(y,x);
        dp[x]+=max(0,dp[y]);
    }
}
int ans[n+1];
void dfs0(int x=1,int fa=0){//二次扫描与换根 
    ans[x]=dp[x];//记录答案 
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa)continue;
        dp[x]-=max(0,dp[y]);
        dp[y]+=max(0,dp[x]);
        dfs0(y,x);
        dp[y]-=max(0,dp[x]);
        dp[x]+=max(0,dp[y]);
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        nei[x].pb(y);nei[y].pb(x);
    }
    dfs();
    dfs0();
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
    return 0;
}