首页 > 代码库 > usaco月赛,2017.1总结
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,那就直接输出。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 6 using namespace std; 7 8 priority_queue<int,vector<int>,greater<int> >q; 9 int a[12000]; 10 int n,t; 11 12 int main() 13 { 14 freopen("cowdance.in","r",stdin); 15 freopen("cowdance.out","w",stdout); 16 cin>>n>>t; 17 for(int i=1;i<=n;i++) 18 cin>>a[i]; 19 for(int i=1;i<=n;i++) 20 { 21 int j; 22 for(j=1;j<=i;j++) 23 q.push(a[j]); 24 int bowl=0; 25 while(j<=n && bowl<=t) 26 { 27 bowl+=(q.top()-bowl); 28 q.pop(); 29 q.push(a[j++]+bowl); 30 } 31 while(!q.empty()) 32 { 33 bowl+=(q.top()-bowl); 34 q.pop(); 35 } 36 if(bowl<=t){cout<<i<<endl;return 0;} 37 } 38 fclose(stdin);fclose(stdout); 39 return 0; 40 }
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2:传统游戏石头剪刀布
题目大意:两只奶牛玩石头剪刀布,第一只奶牛很笨,只会出自己想出的,而第二只奶牛能够预测出第一只奶牛要出的,所以第二只能稳赢第一只。但是第二只奶牛很懒,他在一轮比赛中只想换一次手势,现在给出:
一轮中会有多少次出拳的机会;第一只奶牛出拳的顺序。
求第二只奶牛最多能胜利多少场。
思路:数据量为十万,所以必须思考一下线性的做法,但其实这道题也很简单(总觉得这回铜组的T2比较难,要手写一堆if),因为我们已经知道第一只奶牛的出拳的顺序。
把数据给的字母换成数字。然后用六个变量分别记录换手势前和后石头,剪刀,布个能赢多少次。扫一遍,边扫边判断,改变六个变量的值,然后就很简单了。
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n; int a[100100]; int maxx=-10000; int h1=0,s1=0,p1=0,h2=0,s2=0,p2=0; 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=1;i<=n;i++) { char c; cin>>c; if(c==‘H‘)a[i]=3; else if(c==‘S‘)a[i]=1; else if(c==‘P‘)a[i]=2; } for(int i=1;i<=n;i++) { if(a[i]==1)h2++; if(a[i]==2)s2++; if(a[i]==3)p2++; } for(int i=1;i<=n;i++) { if(a[i]==1){h1++;h2--;} if(a[i]==2){s1++;s2--;} if(a[i]==3){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 0; }
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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[66]; int main() { freopen("cowcode.in","r",stdin); freopen("cowcode.out","w",stdout); cin>>a>>n; k[0]=1; for(int i=1;i<=65;i++) k[i]=k[i-1]*2; int m=a.size(); long long u=n/m; long long w=(double)(log(u*1.0)/log(2*1.0)); for(int i=1;i<=65;i++) { if(u==k[i] && n%m==0) {w--;break;} } long long q=1; for(int i=1;i<=w;i++) q*=2; long long num=n; while(num>m) { bool flag=0; for(int i=1;i<=65;i++) { if(num==(m*k[i]+1)) {num=m*k[i+1];flag=1;break;} } if(!flag) num--; num-=m*k[w--]; while(num<=m*k[w]) w--; //因为不一定你剪完以后就一定是下一个,就像样例的那样。 } cout<<a[num-1]<<endl; fclose(stdin);fclose(stdout); return 0; }
usaco月赛,2017.1总结