Codeforces Round #FF (Div. 1)-A,B,C_html/css_WEB-ITnose

A:DZY Loves Sequences

I read the wrong question at first. . sad.

The question is very simple and the method is also very simple. Just DP it.

dp[i][0]: The length obtained without any number change to the current position.

dp[i][1]: Go to the current position, change a number, and get the length

But you need to find it once in the forward direction, and then in the reverse direction.

#include<iostream>#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<string.h>using namespace std;#define maxn 110000int dp[maxn][3];int num[maxn];int a[maxn];int n;void dos(int maxx){    memset(dp,0,sizeof(dp));    memset(num,-1,sizeof(num));    for(int i=n; i>=1; i--)    {        if(a[i]<a[i+1])        {            dp[i][0]=dp[i+1][0]+1;        }        else        {            dp[i][0]=1;        }        dp[i][1]=dp[i][0];        num[i]=a[i];        if(a[i]<num[i+1])        {            if(dp[i][1]<dp[i+1][1]+1)            {                dp[i][1]=dp[i+1][1]+1;                num[i]=a[i];            }        }        if(a[i]>=a[i+1])        {            if(dp[i][1]<dp[i+1][0]+1)            {                dp[i][1]=dp[i+1][0]+1;                num[i]=a[i+1]-1;            }        }    }    for(int i=1; i<=n; i++)    {         //cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;        maxx=max(maxx,dp[i][0]);        maxx=max(maxx,dp[i][1]);    }    cout<<maxx<<endl;}int main(){    while(~scanf("%d",&n))    {        for(int i=1; i<=n; i++)        {            scanf("%d",&a[i]);        }        memset(dp,0,sizeof(dp));        memset(num,-1,sizeof(num));        for(int i=1; i<=n; i++)        {            if(a[i]>a[i-1])            {                dp[i][0]=dp[i-1][0]+1;            }            else            {                dp[i][0]=1;            }            dp[i][1]=dp[i][0];            num[i]=a[i];            if(a[i]>num[i-1])            {                if(dp[i][1]<dp[i-1][1]+1)                {                    dp[i][1]=dp[i-1][1]+1;                    num[i]=a[i];                }            }            if(a[i]<=a[i-1])            {                if(dp[i][1]<dp[i-1][0]+1)                {                    dp[i][1]=dp[i-1][0]+1;                    num[i]=a[i-1]+1;                }            }        }        int maxx=-1;        for(int i=1; i<=n; i++)        {            // cout<<dp[i][0]<<" "<<dp[i][1]<<" "<<num[i]<<endl;            maxx=max(maxx,dp[i][0]);            maxx=max(maxx,dp[i][1]);        }        dos(maxx);    }    return 0;}

B: DZY Loves Modification

We can find that when selecting a horizontal row, the size order of the vertical rows remains unchanged, but each vertical row decreases by p .

So we can enumerate and select x horizontal rows and y vertical rows.

#include<iostream>#include<stdio.h>#include<algorithm>#include<stdlib.h>#include<string.h>#include<queue>using namespace std;#define maxn 1100#define LL __int64int mp[maxn][maxn];int hh[maxn];int ll[maxn];LL ph[1100000];LL pl[1100000];priority_queue<int>que;int n,m,k,p;void chu(){    ph[0]=pl[0]=0;    while(!que.empty())que.pop();    for(int i=1;i<=n;i++)    {        que.push(hh[i]);    }    for(int i=1;i<=k;i++)    {        int x=que.top();        que.pop();        ph[i]=ph[i-1]+(LL)x;        x=x-p*m;        que.push(x);    }    while(!que.empty())que.pop();    for(int i=1;i<=m;i++)    {        que.push(ll[i]);    }    for(int i=1;i<=k;i++)    {        int x=que.top();        que.pop();        pl[i]=pl[i-1]+(LL)x;        x=x-p*n;        que.push(x);    }}int main(){    while(~scanf("%d%d%d%d",&n,&m,&k,&p))    {        memset(hh,0,sizeof(hh));        memset(ll,0,sizeof(ll));        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                scanf("%d",&mp[i][j]);                hh[i]+=mp[i][j];                ll[j]+=mp[i][j];            }        }        chu();        LL ans=pl[k];        for(int i=1;i<=k;i++)        {            LL x=(LL)i*(LL)(k-i);            x=(LL)x*(LL)p;            ans=max(ans,pl[k-i]+ph[i]-x);        }        cout<<ans<<endl;    }    return 0;}

C: DZY Loves Fibonacci Numbers

Mainly two properties:

1, the addition of two Fibonacci numbers It’s still a Fibonacci sequence.

2. According to the first two terms of the Fibonacci sequence, the Fibonacci number at any position and the sum of the Fibonacci sequence of any length can be obtained in O(1) time.

The rest is a simple interval summation problem.

#include<stdio.h>#include<iostream>#include<stdlib.h>#include<string.h>#include<algorithm>#include<vector>#include<math.h>#include<map>#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;#define mem(a,b) (memset(a),b,sizeof(a))#define lmin 1#define rmax n#define lson l,(l+r)/2,rt<<1#define rson (l+r)/2+1,r,rt<<1|1#define root lmin,rmax,1#define now l,r,rt#define int_now int l,int r,int rt#define INF 99999999#define LL __int64#define mod 1000000009#define eps 1e-6#define zero(x) (fabs(x)<eps?0:x)#define maxn 330000LL sum[maxn<<2];LL f1[maxn<<2];LL f2[maxn<<2];LL fib[maxn];LL look(int a,int b,int n){    if(n==1)return a;    if(n==2)return b;    return (a*fib[n-2]+b*fib[n-1])%mod;}LL suan(int a,int b,int n){    if(n==1)return a;    if(n==2)return (a+b)%mod;    return ((look(a,b,n+2)-b)%mod+mod)%mod;}void push_up(int_now){    sum[rt]=sum[rt<<1]+sum[rt<<1|1];    sum[rt]=sum[rt]%mod;}void push_down(int_now){    if(f1[rt]!=0)    {        LL ll,rr;        ll=(l+r)/2-l+1;        rr=r-(l+r)/2;        LL x,y;        x=f1[rt];        y=f2[rt];        f1[rt<<1]=(f1[rt<<1]+x)%mod;        f2[rt<<1]=(f2[rt<<1]+y)%mod;        sum[rt<<1]=(sum[rt<<1]+suan(x,y,ll))%mod;        LL px,py;        px=x;py=y;        x=look(px,py,ll+1);        y=look(px,py,ll+2);        //cout<<x<<" "<<y<<" +"<<rr<<endl;        f1[rt<<1|1]=(f1[rt<<1|1]+x)%mod;        f2[rt<<1|1]=(f2[rt<<1|1]+y)%mod;        sum[rt<<1|1]=(sum[rt<<1|1]+suan(x,y,rr))%mod;        f1[rt]=f2[rt]=0;    }}void creat(int_now){    sum[rt]=f1[rt]=f2[rt]=0;    if(l!=r)    {        creat(lson);        creat(rson);        push_up(now);    }    else    {        scanf("%I64d",&sum[rt]);    }}void updata(int ll,int rr,int_now){    if(ll>r||rr<l)return;    if(ll<=l&&rr>=r)    {        f1[rt]+=fib[l-ll+1];        f2[rt]+=fib[l-ll+2];        sum[rt]+=suan(fib[l-ll+1],fib[l-ll+2],r-l+1);        sum[rt]=(sum[rt]+mod)%mod;        f1[rt]=f1[rt]%mod;        f2[rt]=f2[rt]%mod;        return;    }    push_down(now);    updata(ll,rr,lson);    updata(ll,rr,rson);    push_up(now);}LL query(int ll,int rr,int_now){    if(ll>r||rr<l)return 0;   /// cout<<l<<"-"<<r<<" "<<sum[rt]<<endl;    if(ll<=l&&rr>=r)return sum[rt];    push_down(now);    return (query(ll,rr,rson)+query(ll,rr,lson))%mod;}int main(){    fib[1]=1;fib[2]=1;    for(int i=3;i<maxn;i++)    {        fib[i]=fib[i-1]+fib[i-2];        fib[i]=fib[i]%mod;    }    int n,m,k,l,r;    while(~scanf("%d%d",&n,&m))    {        creat(root);        while(m--)        {            scanf("%d%d%d",&k,&l,&r);            if(k==1)updata(l,r,root);            else            {                printf("%I64d\n",query(l,r,root));            }        }    }    return 0;}