usaco月赛，2017.1总结

T1：跳舞的奶牛

大致题意：一个体积为k的舞台能够同时容纳k只奶牛一起跳舞，他们每头奶牛的跳舞时间不同，如果有一只奶牛跳完了第k+1头奶牛就会立刻上场跳舞，当所有奶牛跳完舞以后我们认为这次表演结束。现在给出奶牛个数，最多用时，每头奶牛的跳舞时间。求舞台最小为多大。

思路：本来写了个程序以为这道题很简单，刚开始排一下序然后就行了，结果交了以后发现只过了五组，然后才发现这道题不能改变顺序（所以说为什么我改变顺序了还是能过五组，usaco的数据也好水......），所以说我想到了堆，然后就用堆写了一下。

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

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

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

 int a[];

 int n,t;

 int main()

 {

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

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

     cin>>n>>t;

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

         cin>>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<<endl;return ;}

     }

     fclose(stdin);fclose(stdout);

     return ;

 }

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

T2:传统游戏石头剪刀布

题目大意：两只奶牛玩石头剪刀布，第一只奶牛很笨，只会出自己想出的，而第二只奶牛能够预测出第一只奶牛要出的，所以第二只能稳赢第一只。但是第二只奶牛很懒，他在一轮比赛中只想换一次手势，现在给出：

一轮中会有多少次出拳的机会；第一只奶牛出拳的顺序。

求第二只奶牛最多能胜利多少场。

思路：数据量为十万，所以必须思考一下线性的做法，但其实这道题也很简单（总觉得这回铜组的T2比较难，要手写一堆if），因为我们已经知道第一只奶牛的出拳的顺序。

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

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int n;

int a[];

int maxx=-;

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()

{

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

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

    cin>>n;

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

    {

        char c;

        cin>>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,s2,p2);

        if(ans>maxx) maxx=ans;

    }

    cout<<maxx<<endl;

    fclose(stdin);fclose(stdout);

    return ;

}

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

T3：神奇的奶牛的代码

题目大意：奶牛们想选用一个基本的字符串，然后进行无数次的复制，复制规则如下：把已有字符串的最后一个字符放到最后，再把这串字符加到原有字符的后边，e.g.cow->cowwco->cowwcoocowwc->......

输入数据包含：基本字符串；一个整数n（n<=10^18）；

求：经过无数次变换后第n个字符是什么。

思路：n<=10^18......绝对long long。然后就开始考虑了，这个怎么搞呢，首先不是按照他的套路搞一个字符串然后一直加（本人亲测，这个只能过4组，应该有优化可以多过一点，但是我本来就是写个暴力玩玩，所以没想那么多）。还是要找规律的。

就用输入样例来说：

COW -> COWWCO -> COWWCOOCOWWC
　　　　　　　　　　　 1 2 3 4 5678 凑合看一下吧QWQ

然后我们把最后的结果分一下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；然后再继续往下分。

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<ctime>

#include<cstring>

#include<cmath>

using namespace std;

long long n;

string a;

long long k[];

int main()

{

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

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

    cin>>a>>n;

    k[]=;

    for(int i=;i<=;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<=;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<=;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-]<<endl;

    fclose(stdin);fclose(stdout);

    return ;

}

巴特西

usaco月赛，2017.1总结

最新文章

热门文章