当前位置:Gxlcms > html代码 > CodeforcesRound#FF(Div.1)-A,B,C_html/css_WEB-ITnose

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

时间:2021-07-01 10:21:17 帮助过:2人阅读

A:DZY Loves Sequences

一开始看错题了。。sad。

题目很简单,做法也很简单。DP一下就好了。

dp[i][0]:到当前位置,没有任何数改变,得到的长度。

dp[i][1]:到当前位置,改变了一个数,得到的长度

不过需要正向求一遍,然后反向求一遍。

#include#include#include#include#includeusing 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])        {            if(dp[i][1]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]
B:DZY Loves Modification

我们可以发现选择一个横行,竖行的大小顺序不变,只是每一个竖行都下降了p。

所以我们可以枚举选择了x个横行,y个竖行。

#include#include#include#include#include#includeusing namespace std;#define maxn 1100#define LL __int64int mp[maxn][maxn];int hh[maxn];int ll[maxn];LL ph[1100000];LL pl[1100000];priority_queueque;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

主要是两个性质:

1,两个斐波那契数列相加依然是一个斐波那契数列。

2,根据斐波那契数列的前两项可以O(1)的时间内得出任意一个位置的斐波那契数,和任意长度的斐波那契数列的合。

剩下的东西就是简单的区间求和问题了。

#include#include#include#include#include#include#include#include#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)r||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=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

人气教程排行