Cycle

Cycle

关注
发信
关注(28)粉丝(399)

9.29noip模拟试题

环上的游戏（cycle）

有一个取数的游戏。初始时，给出一个环，环上的每条边上都有一个非负整数。这些整数中至少有一个0。然后，将一枚硬币放在环上的一个节点上。两个玩家就是以这个放硬币的节点为起点开始这个游戏，两人轮流取数，取数的规则如下：

（1）选择硬币左边或者右边的一条边，并且边上的数非0；

（2）将这条边上的数减至任意一个非负整数(至少要有所减小)；

（3）将硬币移至边的另一端。

如果轮到一个玩家走，这时硬币左右两边的边上的数值都是0，那么这个玩家就输了。

如下图，描述的是Alice和Bob两人的对弈过程，其中黑色节点表示硬币所在节点。结果图(d)中，轮到Bob走时，硬币两边的边上都是0，所以Alcie获胜。

现在，你的任务就是根据给出的环、边上的数值以及起点（硬币所在位置），判断先走方是否有必胜的策略。

【输入格式】

第一行一个整数N（N≤20），表示环上的节点数。

第二行N个数，数值不超过30，依次表示N条边上的数值。硬币的起始位置在第一条边与最后一条边之间的节点上。

【输出格式】

仅一行。若存在必胜策略，则输出“YES”，否则输出“NO”。

【样例】

cycle.in cycle.out

4

2 5 3 0 YES

cycle.in cycle.out

3

0 0 0 NO

最后取到数的人获胜

博弈

/*

比较简单的博弈题

手动模拟一下

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,a[],s;

int main()

{

    freopen("cycle.in","r",stdin);

    freopen("cycle.out","w",stdout);

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    for(int i=;i<=n;i++)

        if(a[i]==)break;

        else s++;

    for(int i=n;i>=;i--)

        if(a[i]==)break;

        else s++;

    if(s&)printf("YES\n");

    else printf("NO\n");

    return ;

}

舞蹈课(dancingLessons)

问题描述

有n个人参加一个舞蹈课。每个人的舞蹈技术由整数来决定。在舞蹈课的开始，他们从左到右站成一排。当这一排中至少有一对相邻的异性时，舞蹈技术相差最小的那一对会出列并开始跳舞。如果相差最小的不止一对，那么最左边的那一对出列。一对异性出列之后，队伍中的空白按原顺序补上（即：若队伍为ABCD，那么BC出列之后队伍变为AD）。舞蹈技术相差最小即是的绝对值最小。

你的任务是，模拟以上过程，确定跳舞的配对及顺序。

输入

第一行为正整数：队伍中的人数。下一行包含n个字符B或者G，B代表男，G代表女。下一行为n个整数。所有信息按照从左到右的顺序给出。在50%的数据中，。

输出

第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。

样例输入

4

BGBG

4 2 4 3

样例输出

2

3 4

1 2

样例输入

4

BGBB

1 1 2 3

样例输出

1

1 2

贪心

/*

贪心+堆优化

一开始把所有挨着的男女放进去

然后拿出Abs最小的 同时看看新生成的挨着的能不能组合成一组

注意一些细节的处理

开始wa了一个点

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

#define maxn 200010

#define inf 0x7fffffff

using namespace std;

int n,a[maxn],cnt,f[maxn],s1,s2;

char c[maxn];

struct node{

    int l,r,C;

    bool operator < (const node &x) const{

        if(x.C==C)return x.l<l;

        return x.C<C;

    }

}ans[maxn],t;

priority_queue<node>q;

int init(){

    int x=,f=;char s=getchar();

    while(s<''||s>''){if(s=='-')f=-;s=getchar();}

    while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

    return x*f;

}

int Abs(int x){

    return x<?-x:x;

}

int main()

{

//    freopen("dancingLessons.in","r",stdin);

    //freopen("dancingLessons.out","w",stdout);

    n=init();

    scanf("%s",c+);

    for(int i=;i<=n;i++)

        if(c[i]=='B')s1++;

        else s2++;

    for(int i=;i<=n;i++)

        a[i]=init();

    for(int i=;i<=n;i++)

        if(c[i-]!=c[i])

            q.push((node){i-,i,Abs(a[i]-a[i-])});

    while(!q.empty()){

        int falg=;

        while(){

            if(q.empty()){falg=;break;}

            t=q.top();q.pop();

            if(f[t.l]||f[t.r])continue;

            else break;

        }

        if(q.empty()&&falg)break;//这里多一个falg标记 表示q空时最后一个合不合法

        ans[++cnt].l=t.l;ans[cnt].r=t.r;

        f[t.l]=;f[t.r]=;

        int L=t.l-,R=t.r+;

        while(f[L])L--;

        while(f[R])R++;

        if(L&&R<=n&&c[L]!=c[R])

            q.push((node){L,R,Abs(a[R]-a[L])});

    }

    printf("%d\n",cnt);

    for(int i=;i<=cnt;i++)

        printf("%d %d\n",ans[i].l,ans[i].r);

    return ;

}

数位和乘积(digit.cpp/c/pas)

【题目描述】

一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意，这里的N位数是可以有前导零的。比如01，02视为二位数，但是他们的数位和乘积都是0。

【输入格式】

一行两个整数N，K

【输出格式】

一个行一个整数表示结果。

【样例输入】

2 3

【样例输出】

2

【样例输入2】

2 0

【样例输出2】

19

【数据范围】

对于20%：N <= 6。

对于50%：N<=16

存在另外30%：K=0。

对于100%：N  <= 50，0 <= K <= 10^9。

暴力50

/*

我是蒟蒻没有想出正解...

打了个暴力 当然也不是裸裸的

k==0 10^n-9^n

分成两段 每段分别暴力 在hash一下（不知为啥hash最小的数据不对 写了map）

还有一些小剪枝

目测n<=15的都能过

但是说好的%30<=16结果全尼玛是16 你故意的吧

然后就只拿到了基础的暴力分50

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<ctime>

#define mod 233333

using namespace std;

int n,k,N,falg,ans[],J[];

map<int,int>p;

void Add(int a[],int b[]){

    int c[];

    memset(c,,sizeof(c));

    int len=max(a[],b[]);

    for(int i=;i<=len;i++)

        c[i]=a[i]+b[i];

    for(int i=;i<=len;i++)

        if(c[i]>){

            c[i+]++;c[i]%=;

        }

    if(c[len+])len++;c[]=len;

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Jian(int a[],int b[]){

    int c[];

    memset(c,,sizeof(c));

    int len=max(a[],b[]);

    for(int i=;i<=len;i++)

        c[i]=a[i]-b[i];

    for(int i=;i<=len;i++)

        if(c[i]<){

            c[i+]--;c[i]+=;

        }

    for(int i=len;i>=;i--)

        if(c[i]){

            c[]=i;break;

        }

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Mul(int a[],int x){

    int c[];

    memset(c,,sizeof(c));

    int len=a[];

    for(int i=;i<=len;i++)

        c[i]=a[i]*x;

    for(int i=;i<=len;i++)

        if(c[i]>){

            c[i+]+=c[i]/;

            c[i]%=;

        }

    while(c[len+]>){

        len++;

        c[len+]+=c[len]/;

        c[len]%=;

    }

    if(c[len+])len++;c[]=len;

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Cal(int x){

    int a[];

    memset(a,,sizeof(a));

    while(x){

        a[++a[]]=x%;x/=;

    }

    Add(ans,a);

}

void Dfs(int now,int s,int r){

    if(r>k)return;

    if(now==N+){

        if(!falg)p[r]++;

        else{

            if(r){

                int t=k/r;

                if(t*r==k)Cal(p[t]);

            }

        }

        return;

    }

    for(int i=;i<=;i++)

        Dfs(now+,s*+i,r*i);

}

void Solve(){

    ans[]=;ans[]=;

    J[]=;J[]=;

    for(int i=;i<=n;i++)

        Mul(ans,);

    for(int i=;i<=n;i++)

        Mul(J,);

    Jian(ans,J);

}

int main()

{

    //freopen("digit.in","r",stdin);

    //freopen("digit.out","w",stdout);

    scanf("%d%d",&n,&k);

    if(k==)Solve();

    else{

        N=n/;Dfs(,,);

        falg=;

        N=n;Dfs(n/+,,);

    }

    for(int i=max(ans[],);i>=;i--)

        printf("%d",ans[i]);

    return ;

}

正解dp

/*

正解还是很机智的Orz

f[i][j][k][l][r]前i位选了j个2 k个3 l个5 r个7的方案数

然后+个高精就ok了

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,k,ans[],J[];

int f[][][][][];

void Add(int a[],int b[]){

    int c[];

    memset(c,,sizeof(c));

    int len=max(a[],b[]);

    for(int i=;i<=len;i++)

        c[i]=a[i]+b[i];

    for(int i=;i<=len;i++)

        if(c[i]>){

            c[i+]++;c[i]%=;

        }

    if(c[len+])len++;c[]=len;

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Jian(int a[],int b[]){

    int c[];

    memset(c,,sizeof(c));

    int len=max(a[],b[]);

    for(int i=;i<=len;i++)

        c[i]=a[i]-b[i];

    for(int i=;i<=len;i++)

        if(c[i]<){

            c[i+]--;c[i]+=;

        }

    for(int i=len;i>=;i--)

        if(c[i]){

            c[]=i;break;

        }

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Mul(int a[],int x){

    int c[];

    memset(c,,sizeof(c));

    int len=a[];

    for(int i=;i<=len;i++)

        c[i]=a[i]*x;

    for(int i=;i<=len;i++)

        if(c[i]>){

            c[i+]+=c[i]/;

            c[i]%=;

        }

    while(c[len+]>){

        len++;

        c[len+]+=c[len]/;

        c[len]%=;

    }

    if(c[len+])len++;c[]=len;

    for(int i=;i<=len;i++)a[i]=c[i];

}

void Cal(int x){

    int a[];

    memset(a,,sizeof(a));

    while(x){

        a[++a[]]=x%;x/=;

    }

    Add(ans,a);

}

void Solve(){

    ans[]=;ans[]=;

    J[]=;J[]=;

    for(int i=;i<=n;i++)

        Mul(ans,);

    for(int i=;i<=n;i++)

        Mul(J,);

    Jian(ans,J);

    for(int i=max(ans[],);i>=;i--)

        printf("%d",ans[i]);

}

void solve(){

    int t1=,t2=,t3=,t4=;

    while(k%==)k/=,t1++;

    while(k%==)k/=,t2++;

    while(k%==)k/=,t3++;

    while(k%==)k/=,t4++;

    if(k>){cout<<;return;}

    f[][][][][]=;

    f[][][][][]=;

    for(int i=;i<=n;i++)

        for(int j=t1;j>=;j--)

            for(int k=t2;k>=;k--)

                for(int l=t3;l>=;l--)

                    for(int r=t4;r>=;r--){

                        if(j>=)Add(f[j][k][l][r],f[j-][k][l][r]);//

                        if(k>=)Add(f[j][k][l][r],f[j][k-][l][r]);//

                        if(j>=)Add(f[j][k][l][r],f[j-][k][l][r]);//

                        if(l>=)Add(f[j][k][l][r],f[j][k][l-][r]);//

                        if(j>=&&k>=)Add(f[j][k][l][r],f[j-][k-][l][r]);//

                        if(r>=)Add(f[j][k][l][r],f[j][k][l][r-]);//

                        if(j>=)Add(f[j][k][l][r],f[j-][k][l][r]);//

                        if(k>=)Add(f[j][k][l][r],f[j][k-][l][r]);//

                    }

    for(int i=max(f[t1][t2][t3][t4][],);i>=;i--)

        printf("%d",f[t1][t2][t3][t4][i]);

}

int main()

{

    //freopen("digit.in","r",stdin);

    //freopen("digit.out","w",stdout);

    scanf("%d%d",&n,&k);

    if(k==)Solve();

    else solve();

    return ;

}
05-07 15:26
Powered by LMLPHP ©2024 Cycle 0.079799