欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-11-22 10:09:33
第一次遇到这么水的div. 3。。。 本来想抢D一血的,结果失败了。。然后干脆就$45\mathrm{min}$AK了。。。 "CodeForces比赛页面传送门" A Yet Another Tetris Problem "洛谷题目页面传送门" & "CodeForces题目页面传送门" 给出$n ......

第一次遇到这么水的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;
}