BruceJay's Blog

Bruce之NOIP模拟考梦靥系列四

| Comments

扯淡

第二次NOIP全真模拟。
对于二试只有40分的Bruce,不垫底就是逆天。

Day1

Gcd

[Description]

定义f(a,b)为a,b通过辗转相除法得到最大公约数的计算次数。
给定N,求a<=b<=n,使得f(a,b)最小,且在b尽量小的情况下让a尽量小。

[Hint]

[Solution]

斐波那契数列,高精度压位搞起。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int LEN = 1510;
const int mod = 1e9;
int a[LEN]; int b[LEN<<3];
int f[2][LEN];

inline void read()
{
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9'){
        b[++b[0]]=ch-'0'; ch=getchar();
    }
    int x=1,now=0,t=0;
    for(int i=b[0];i;i--){
        now+=x*b[i]; x*=10; t++;
        if(t==9) a[++a[0]]=now,x=1,now=0,t=0;
    }
    if(now) a[++a[0]]=now;
    memset(b,0,sizeof(b));
}

bool Cmp(int x[],int y[])
{
    if(x[0]<y[0]) return false;
    else if(x[0]>y[0]) return true;
    for(int i=x[0];i;i--){
        if(x[i]<y[i]) return false;
        else if(x[i]>y[i]) return true;
    }
    return false;
}

void Plus(int x[],int y[])
{
    int k=0;
    b[0]=max(x[0],y[0]);
    for(int i=1;i<=max(x[0],y[0]);i++){
        b[i]=x[i]+y[i]+k;
        k=b[i]/mod; b[i]%=mod;
    }
    if(k) b[++b[0]]=k;
}

void print(int x[])
{
    printf("%d",x[x[0]]);
    for(int i=x[0]-1;i;i--) printf("%09d",x[i]);
}

int main()
{
    freopen("gcd.in","r",stdin);
    freopen("gcd.out","w",stdout);
    read();
    f[0][0]=f[0][1]=f[1][0]=f[1][1]=1;
    while(true){
        Plus(f[0],f[1]);
        if(Cmp(f[0],f[1])){
            if(Cmp(b,a)){
                print(f[1]);
                puts("");
                print(f[0]);
                break;
            }
            else memcpy(f[1],b,sizeof(f[1]));
        }
        else{
            if(Cmp(b,a)){
                print(f[0]);
                puts("");
                print(f[1]);
                break;
            }
            else memcpy(f[0],b,sizeof(f[0]));
        }
    }
    return 0;
}

Sequence

[Description]

给定一个长为n的序列a[1~n],定义f[i,j]为a[i~j]中最大值与最小值的差。
求a的所有子序列的f的和。

[Hint]

[Solution]

单调栈。最大值与最小值对答案的贡献分开算。
对于最大值,维护一个权值递减的单调栈,标记栈中元素进栈时间t[i],出栈时,计算出栈元素i对最大值的贡献。
最小值反之处理。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 300100;
int st[N]; ll a[N]; int t[N];
int n,top=0; ll ans=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

ll Calc(int x,int l,int r)
{
    return (ll)a[x]*(x-l+1)*(r-x+1);
}

int main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        t[i]=i;
        while(top && a[st[top]]<=a[i]){
            ans+=Calc(st[top],t[st[top]],i-1);
            t[i]=t[st[top]]; top--;
        }
        st[++top]=i;
    }
    while(top) ans+=Calc(st[top],t[st[top]],n),top--;
    for(int i=1;i<=n;i++){
        t[i]=i;
        while(top && a[st[top]]>=a[i]){
            ans-=Calc(st[top],t[st[top]],i-1);
            t[i]=t[st[top]]; top--;
        }
        st[++top]=i;
    }
    while(top) ans-=Calc(st[top],t[st[top]],n),top--;
    printf("%lld",ans);
    return 0;
}

Sort

[Description]

定义这么一种排序:
每次从前往后扫,扫到第一个a[i]>a[i+1],就将a[i+1]置于序列首位,称这个过程为一次计算。
对于一个序列a,t(a)为对a排序的计算次数。
给定n,求n的所有全排列的t值的和与n!的比值(mod 10^9+7)。

[Hint]

[Solution]

标记f(i)为i的全排列的t值总和。
考虑全排列r(1~n)={1,2,3,...,x-1,x+1,...,x},则。(不要问我为什么)
对于全排列r(1~n)={r(1~x-1,x+1~n),x},则这些所有排列r的t值总和为
所以可以得到递推式
$$f(n)=(2^{n-1}-1)*(n-1)!+n*f(n-1)$$
同J房同学都用这种方法秒了这一题,Bruce听了,感觉很有道理。
Bruce考试时实力画了3和4的树(全排列在这种排序下可以形成树结构,你可以当我扯淡),然后水出规律,水平差距不小啊。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100100;
const int mod = 1e9+7;
ll f[N]; int n; ll ans;

ll PowerMod(ll x,ll y)
{
    ll res=1;
    for(ll i=y;i;i>>=1,x=x*x%mod)
        if(i&1) res=res*x%mod;
    return res;
}

int main()
{
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d",&n);
    f[1]=0; ll bin=1,fac=1;
    for(int i=2;i<=n;i++){
        bin=(bin<<1)%mod; fac=fac*(i-1)%mod;
        f[i]=((bin-1)*fac%mod+(ll)f[i-1]*i%mod)%mod;
    }
    ans=f[n]*PowerMod((ll)fac*n%mod,mod-2)%mod;
    printf("%lld",ans);
    return 0;
}

Day2

Trampolin

[Description]

有n幢摩天大楼,Magnificent在第k幢,他可以飞到相邻的且高度不高于当前所在摩天楼高度的摩天楼,某些摩天楼上有蹦床,Magnificent可以通过蹦床飞到任意一座摩天楼,求Magnificent最多可以飞到多少座摩天楼。

[Hint]

[Solution]

贪心。
不难想到如果能让Magnificent飞到一个蹦床,那么就可以让Magnificent飞到所有蹦床。
沿着这个思路,再想想,就能想到如果起点能到达蹦床,那么就能到达所有能到达某个蹦床的摩天楼。
所以,可以先处理哪些摩天楼可以到达一个蹦床。
如果起点可以到蹦床,就可以到所有能到蹦床的摩天楼,答案最后加上不能到蹦床的摩天楼中能连续飞的最长一段。
如果不能,直接找从起点能连续飞的最长一段。
连续的一段高度相同的摩天楼看起来不好处理,要将这些摩天楼缩成一个。

[Code]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 300100;
int a[N]; char s[N];
int w[N]; bool vis[N];
int pos[N];
int nn,n=0,m;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Mark(int x)
{
    int L=x,R=x; vis[x]=true;
    while(L && a[L-1]>a[L] && !vis[L-1])
        vis[--L]=true;
    while(R<n && a[R+1]>a[R] && !vis[R+1])
        vis[++R]=true;
}

int Solve()
{
    if(!vis[m]){
        int x,ans1=w[m],ans2=w[m];
        x=m; while(x && a[x-1]<a[x]) ans1+=w[--x];
        x=m; while(x && a[x+1]<a[x]) ans2+=w[++x];
        return max(ans1,ans2);
    }
    else{
        int ans=0,tmp=0,now;
        for(int i=1;i<=n;i++) if(vis[i]) ans+=w[i];
        now=0;
        for(int i=1;i<=n;i++){
            if(!vis[i]){
                if(a[i]>a[i-1]) now+=w[i];
                else now=w[i];
            }
            else now=0;
            tmp=max(tmp,now);
        }
        now=0;
        for(int i=n;i;i--){
            if(!vis[i]){
                if(a[i]>a[i+1]) now+=w[i];
                else now=w[i];
            }
            else now=0;
            tmp=max(tmp,now);
        }
        return ans+tmp;
    }
}

int main()
{
    freopen("trampolin.in","r",stdin);
    freopen("trampolin.out","w",stdout);
    nn=read(); m=read();
    for(int i=1;i<=nn;i++) a[i]=read();
    for(int i=1;i<=nn;i++){
        if(a[i]!=a[n]) a[++n]=a[i];
        w[n]++; pos[i]=n;
    }
    scanf("%s",s+1);
    for(int i=1;i<=nn;i++) if(s[i]=='T') Mark(pos[i]);
    m=pos[m]; printf("%d",Solve());
    return 0;
}

Code

[Description]

Codeplay0314发明了一种语言:Jx。
Jx语言具有程序嵌套程序的功能。
一对大括号见就是一层程序,每一层程序都是普通语句在前,嵌套程序在后,而且只有一个嵌套程序。
他为了展示这种畸形的语言,他要在不改变嵌套层次的情况下用三块板子,将第一块板子的程序抄到第三块板子上(同一层的普通语句可以调换顺序)。
抄写时,可以把一块屏幕的最下面一条语句抄到另一块屏幕的最下面(从上往下写),并且将这条语句从原来的地方擦掉。大括号可以任意擦除或写入。
请求出最小的抄写次数(mod 10^9+7)。

[Hint]

程序层数不超过1000.

[Solution]

看懂题意就知道这是汉诺塔模型。f[i]表示完成第i~n层程序抄写的最小步数,a[i]表示第i层程序普通语句的个数。
$$f[i]=f[i+1]*2+a[i]$$
Bruce本题爆零。(不仅仅是读入被坑)

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 1010;
const int mod = 1e9+7;
int a[N]; ll f[N]; int n;

int main()
{
    char s[210];
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    while(true){
        fgets(s,25,stdin);
        if(s[0]=='{') n++;
        else if(s[0]=='}') break;
        else a[n]++;
    }
    for(int i=n;i;i--) f[i]=((f[i+1]<<1)+a[i])%mod;
    printf("%lld",f[1]);
    return 0;
}

Diamond

[Description]

给定n*m的棋盘,每个格子有个颜色(1~9)。
一共进行q次交换,每次交换相邻的颜色不同的格子(x1,y1),(x2,y2)。
求每次交换后(x1,y1)和(x2,y2)所在同色矩阵的大小较大值。

[Hint]

[Solution]

Bruce看错了题意。
如果左右交换,位于左边的格子,其右边与其颜色是不会相同的,所以同色矩阵一定在该格子左边。
分别记录每个格子上下左右连续同色格子的个数,每次交换只需修改被交换格子所在行和列。
对于求(x,y)所在同色矩阵,确定方向直接枚举矩阵宽度(从大到小),再从(x,y)向两边扩展矩阵长度。

[Code]

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 510;
int a[N][N]; int f[5][N][N];
int n,m,q;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void pre()
{
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        if(a[i][j]==a[i][j-1]) f[1][i][j]=f[1][i][j-1]+1;
        else f[1][i][j]=1;
        if(a[i][j]==a[i-1][j]) f[2][i][j]=f[2][i-1][j]+1;
        else f[2][i][j]=1;
    }
    for(int i=n;i;i--)
    for(int j=m;j;j--){
        if(a[i][j]==a[i][j+1]) f[3][i][j]=f[3][i][j+1]+1;
        else f[3][i][j]=1;
        if(a[i][j]==a[i+1][j]) f[4][i][j]=f[4][i+1][j]+1;
        else f[4][i][j]=1;
    }
}

void Update(int x,int y)
{
    for(int i=1;i<=m;i++){
        if(a[x][i]==a[x][i-1]) f[1][x][i]=f[1][x][i-1]+1;
        else f[1][x][i]=1;
    }
    for(int i=m;i;i--){
        if(a[x][i]==a[x][i+1]) f[3][x][i]=f[3][x][i+1]+1;
        else f[3][x][i]=1;
    }
    for(int i=1;i<=n;i++){
        if(a[i][y]==a[i-1][y]) f[2][i][y]=f[2][i-1][y]+1;
        else f[2][i][y]=1;
    }
    for(int i=n;i;i--){
        if(a[i][y]==a[i+1][y]) f[4][i][y]=f[4][i+1][y]+1;
        else f[4][i][y]=1;
    }
}

int Calc(int dir,int x,int y)
{
    int k,res=0;
    if(dir&1){
        int L=x,R=x;
        for(int i=f[dir][x][y];i;i--){
            while(f[dir][L-1][y]>=i && a[L-1][y]==a[x][y]) L--;
            while(f[dir][R+1][y]>=i && a[R+1][y]==a[x][y]) R++;
            res=max(res,(R-L+1)*i);
        }
    }
    else{
        int L=y,R=y;
        for(int i=f[dir][x][y];i;i--){
            while(f[dir][x][L-1]>=i && a[x][L-1]==a[x][y]) L--;
            while(f[dir][x][R+1]>=i && a[x][R+1]==a[x][y]) R++;
            res=max(res,(R-L+1)*i);
        }
    }
    return res;
}

int Solve(int x1,int y1,int x2,int y2)
{
    if(x1==x2){
        if(y1>y2) swap(y1,y2);
        return max(Calc(1,x1,y1),Calc(3,x2,y2));
    }
    else{
        if(x1>x2) swap(x1,x2);
        return max(Calc(2,x1,y1),Calc(4,x2,y2));
    }
}

int main()
{
    int x1,y1,x2,y2;
    freopen("diamond.in","r",stdin);
    freopen("diamond.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        a[i][j]=read();
    pre();
    q=read();
    for(int i=1;i<=q;i++){
        x1=read(); y1=read();
        x2=read(); y2=read();
        swap(a[x1][y1],a[x2][y2]);
        Update(x1,y1); Update(x2,y2);
        printf("%d\n",Solve(x1,y1,x2,y2));
    }
    return 0;
}

Comments

comments powered by Disqus