[SinGuLaRiTy] 高一下半期测试

对于所有的题目: Time Limit: 1s | Memory: 256 MB

第一题：跳舞

题目描述

奶牛舞会开始了。一共有n（n<=10000）头奶牛，编号为1,2，……，n，它们将要按照顺序登台表演。每头奶牛的跳舞时间是给定的，第i头奶牛的舞蹈需要的时间为dur[i]。舞台可以容纳k头奶牛同时跳舞。开始的时候，编号为1,2，……k的奶牛都上台同时跳。当某头奶牛的舞蹈结束以后，它就立刻下台，下一头奶牛立刻登台开始跳。奶牛上台和下台可以认为是瞬间的，不消耗时间。现在给定奶牛们跳舞的总时间为T，即在T以内，所有奶牛的都必须结束舞蹈。请你确定k的最小值。数据保证当k=n时，一定可以在T以内完成所有舞蹈。

输入

第一行给出两个整数N和T。T不超过1百万。

接下来N行，表示奶牛们的舞蹈所花的时间，dur[i]是一个[1,100000]的整数。

输出

一个整数，表示最小的k。

样例数据

样例输入

样例输出

5 8

题目分析

第一题......并没有什么好说的，好吧，还是说说好了。

枚举舞台的大小i（从小往大枚举，方便输出），首先舞台的大小不会大于奶牛的个数。开始时老老实实的把前i个奶牛给存进堆里，然后开一个变量（这里用bowl来说），找到堆的最小值j，让bowl=bowl+（j-bowl），j-bowl表示这头奶牛剩余的时间；然后再把下一个奶牛存进堆，这时候存的时候应该存的值是bowl+原来奶牛跳舞的时间（因为弹出奶牛的时候要j-bowl），如果到最后bowl（bowl存的其实就相当于跳舞用的总时间，但是最后一个奶牛进去堆后，别忘了台上还是有奶牛的，所以应该在想办法吧台上的奶牛跳舞所用的时间也加进去）还是小于timemaxx，那就直接输出。

STD Code

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<queue>

#include<iostream>

#include<algorithm>

#define MAXN 10100

using namespace std;

priority_queue<int,vector<int>,greater<int> >q;

int a[MAXN];

int n,t;

int main()

{

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

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

    {

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

    }

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

    {

        int j;

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

            q.push(a[j]);

        int bowl=;

        while(j<=n&&bowl<=t)

        {

            bowl+=(q.top()-bowl);

            q.pop();

            q.push(a[j++]+bowl);

        }

        while(!q.empty())

        {

            bowl+=(q.top()-bowl);

            q.pop();

        }

        if(bowl<=t)

        {

            cout<<i;

            return ;

        }

    }

    return ;

}

第二题：石头剪刀布

题目描述

小明和小新玩石头剪刀布的游戏。小明在这方面是专家，他可以猜到小新下一次出什么。但是他很懒，他几乎每次都出一样的动作。具体来讲，在整个游戏过程中，他最多只变换一次，即可以从始至终只出一种手势，或是在前几次一种手势，在剩下的次数中出另一种手势。现在他们玩N次游戏，告诉你每次小新出什么。问小明最多能赢几次。

输入

第一行一个整数n，表示游戏进行的次数。（1<=n<=100000）

接下来n行，为H,P,或S中的一个。表示小新出的动作。H表示石头，P表示布，S表示剪刀。

输出

一个整数，表示小明最多能赢几次。

样例数据

样例输入

样例输出

题目分析

数据量为十万，所以必须思考一下线性的做法，但其实这道题也很简单，因为我们已经知道小新的出拳的顺序。

把数据给的字母换成数字。然后用六个变量分别记录换手势前和后石头，剪刀，布个能赢多少次。扫一遍，边扫边判断，改变六个变量的值，然后就很简单了。

STD Code

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#define MAXN 100100

#define INF 10000

using namespace std;

int n;

char c[];

int a[MAXN];

int maxx=-INF;

int h1,s1,p1,h2,s2,p2;

int MAX(int a,int b,int c)

{

    int w=b;

    if(a>b)

        w=a;

    if(c>w)

        w=c;

    return w;

}

int main()

{

    scanf("%d",&n);

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

    {

        scanf("%s",c);

        if(c[]=='H')

            a[i]=;

        else if(c[]=='S')

            a[i]=;

        else if(c[]=='P')

            a[i]=;

    }

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

    {

        if(a[i]==)

            h2++;

        if(a[i]==)

            s2++;

        if(a[i]==)

            p2++;

    }

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

    {

        if(a[i]==)

        {

            h1++;

            h2--;

        }

        if(a[i]==)

        {

            s1++;

            s2--;

        }

        if(a[i]==)

        {

            p1++;

            p2--;

        }

        int ans=MAX(h1,s1,p1)+MAX(h2,p2,s2);

        if(ans>maxx)

        {

            maxx=ans;

        }

    }

    printf("%d",maxx);

    return ;

}

第三题：奶牛密码

题目描述

奶牛们在玩密码游戏。他们拿到一个字符串，首先将它复制一份，然后将复制的字符串进行循环右移——即将最右边的字符放到该字符串的左边，成为第一个字符。然后将循环移位后的字符串接在原来的字符串的后面。这样，它们就得到了一个长度为原来两倍的字符串。

如果这样一直做下去，则字符串的长度会越来越大。现在，奶牛需要问你这个无穷长的字符串的第n个字符是什么？最左边的位置为第1个位置。

输入

一个字符串S和一个整数n。S由最多30个字母组成，n<=10^18。

输出

一个字符。

样例数据

样例输入	样例输出
COW 8	C

样例解释

COW——COWWCO——COWWCOOCOWWC

第8个字符是c。

题目分析

n<=10^18......绝对long long。然后就开始考虑了，这个怎么搞呢，首先不是按照样例的套路搞一个字符串然后一直加，看来还是要找规律的。

就用输入样例来说：

COW -> COWWCO -> C O W | W C O | O C O W W C

然后我们把最后的结果分一下COWWCOOCOWWC 表示生成的过程。这样我们发现第八个是在第三组里面（红色的一组，蓝色的一组，黑色的一组），也就是说，必须要进行2次才会出现第八的字符，这时候字符的总数有3*2^2，其中，3是原始字符的长度m，第一个2是一个在这道题中不会变得常数，第二个2表示要进行n次才会出现第八个字符，然后我们考虑怎么确定第八个字符在原始字符串里的位置。

根据题目我们知道，黑色字符串与蓝色字符串的区别就在于第一个O应该是在最后，那么我们设想一下，如果没有把最后一个字符放在最前边的规则，那么第八个字符在这个字符串中应该是第七个字符，而这时蓝色字符串与黑色字符串就应该是一样的，也就是说第七个字符就等于第7-6=1个字符，C。

如果让求的字符是第11个，那么根据刚才的思想这个在蓝色字符串中对应的就应该是第11-1=10-6=4个，这时候就把它转换到蓝色的字符串中了，但是因为它还是没有进到初始的字符串中，所以我们还需要继续往下分，那么又可以根据刚才的思想把它分到带红色的字符串里，但是这是我们转换到的第四个字符是非常特殊的，因为如果根据上一段的思想的话，这个字符在还原的时候应该是第六个，也就是说这时候我们需要特判一下，不应该是4-1，而应该是让它等于3*2^1=6；然后再继续往下分......

STD Code

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#define MAXN 66

using namespace std;

long long n;

string a;

long long k[MAXN];

int main()

{

    cin>>a>>n;

    k[]=;

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

    {

        k[i]=k[i-]*;

    }

    int m=a.size();

    long long u=n/m;

    long long w=(double)(log(u*1.0)/log(*1.0));

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

    {

        if(u==k[i]&&n%m==)

        {

            w--;

            break;

        }

    }

    long long q=;

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

    {

        q*=;

    }

    long long num=n;

    while(num>m)

    {

        bool flag=;

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

        {

            if(num==(m*k[i]+))

            {

                num=m*k[i+];

                flag=;

                break;

            }

        }

        if(!flag)

        {

            num--;

        }

        num-=m*k[w--];

        while(num<=m*k[w])

        {

            w--;

        }

    }

    cout<<a[num-];

    return ;

}

Time : 2017-04-18

巴特西

[SinGuLaRiTy] 高一下半期测试

第一题：跳舞

题目描述

输入

输出

样例数据

题目分析

STD Code

第二题：石头剪刀布

题目描述

输入

输出

样例数据

题目分析

STD Code

第三题：奶牛密码

题目描述

输入

输出

样例数据

样例解释

题目分析

STD Code

最新文章

热门文章