首页 > 代码库 > USACO Chapter 1 Section 1.1
USACO Chapter 1 Section 1.1
USACO的题解和翻译已经很多了。。。
我只是把自己刷的代码保存一下。
1、PROB Your Ride Is Here
1 /* 2 ID:xiekeyi1 3 PROG:ride 4 LANG:C++ 5 */ 6 7 #include<bits/stdc++.h> 8 using namespace std ; 9 10 int main() 11 { 12 freopen("ride.in","r",stdin); 13 freopen("ride.out","w",stdout) ; 14 string s1 , s2 ; 15 cin >> s1 >> s2 ; 16 int ans1 = 1 , ans2 = 1 ; 17 for( int i = 0 ; i < s1.size() ; i++) 18 ans1 *= (s1[i] - ‘A‘ + 1 ) % 47 ; 19 for( int i = 0 ; i < s2.size() ; i++) 20 ans2 *= (s2[i] - ‘A‘ + 1 ) % 47 ; 21 ans1 %= 47 , ans2 %= 47 ; 22 if( ans1 == ans2 ) 23 cout << "GO" << endl ; 24 else 25 cout << "STAY" << endl ; 26 return 0 ; 27 }
2、PROB Greedy Gift Givers
1 /* 2 ID:xiekeyi1 3 PROG:gift1 4 LANG:C++ 5 */ 6 7 #include<bits/stdc++.h> 8 using namespace std ; 9 10 map<string,int> na; 11 struct 12 { 13 string name ; 14 int account = 0 ; 15 int begiven = 0 ; 16 }a[1000]; 17 int main() 18 { 19 freopen("gift1.in","r",stdin); 20 freopen("gift1.out","w",stdout); 21 int n ; 22 cin >> n; 23 for( int i = 1 ; i <= n ; i++) 24 { 25 cin >> a[i].name ; 26 na[ a[i].name] = i ; 27 } 28 string tempname ; 29 30 int tempmoney , ng ; 31 while( cin >> tempname >> tempmoney >> ng ) 32 { 33 int tem = 0 ; 34 a[ na[tempname] ].account -= tempmoney ; 35 if( ng != 0 ) 36 { 37 tem = tempmoney / ng ; 38 a[ na[tempname] ].account = a[ na[tempname] ].account - ( a[ na[tempname] ].account + tem * ng ) ; 39 } 40 41 for( int i = 1 ; i <= ng ; i++) 42 { 43 44 string t ; 45 cin >> t ; 46 a[ na[t] ] . begiven += tem ; 47 } 48 } 49 50 for( int i = 1 ; i <= n ; i++) 51 { 52 cout << a[i].name << ‘ ‘ << a[i].account + a[i].begiven << endl ; 53 } 54 return 0 ; 55 }
3、PROB Friday the Thirteenth
1 /* 2 ID:xiekeyi1 3 PROG:friday 4 LANG:C++ 5 */ 6 7 #include<bits/stdc++.h> 8 using namespace std ; 9 int a[10] = {0} ; 10 11 bool isleapyear( int n ) 12 { 13 if( n % 4 == 0 && n % 100 != 0 ) 14 return true ; 15 else if( n % 400 == 0 ) 16 return true ; 17 else 18 return false ; 19 } 20 21 int days_month( int y , int m ) 22 { 23 switch(m){ 24 case 1 : 25 case 3 : 26 case 5 : 27 case 7 : 28 case 8 : 29 case 10: 30 case 12: 31 return 31 ; 32 case 4 : 33 case 6 : 34 case 9 : 35 case 11 : 36 return 30 ; 37 case 2: 38 if( isleapyear(y) ) 39 return 29 ; 40 else 41 return 28 ; 42 } 43 } 44 45 int days( int y , int m , int d ) 46 { 47 int ans = 0 ; 48 for( int i = 1900 ; i < y ; i++) 49 { 50 if( isleapyear( i ) ) 51 ans+=366; 52 else 53 ans+=365; 54 } 55 56 for( int i = 1 ; i < m ; i++) 57 { 58 ans+= days_month( y , i ) ; 59 } 60 61 ans += d ; 62 63 return ans - 1 ; 64 } 65 66 67 int main() 68 { 69 freopen("friday.in" , "r" , stdin) ; 70 freopen("friday.out" , "w" , stdout) ; 71 int n ; 72 cin >> n ; 73 for( int i = 1900 ; i < ( n + 1900 ) ; i++) 74 { 75 for( int j = 1 ; j <= 12 ; j++) 76 a[ days(i,j,13) % 7 + 1 ]++ ; 77 } 78 79 cout << a[6] << ‘ ‘ << a[7] << ‘ ‘ << a[1] << ‘ ‘ << a[2] << ‘ ‘ << a[3] << ‘ ‘ << a[4] 80 << ‘ ‘ << a[5] << endl ; 81 return 0 ; 82 }
4、PROB Broken Necklace
前面三道题都是1A,我还说怪不得大家的说USACO简单。
我虽然感觉做起来对初学者有点难,但是感觉数据都比较水, 1A美滋滋。
结果卡在这道题上好久
本来是准备模拟剪断,后来发现是个环,然后就想复制一遍再模拟,结果写的很挫,代码很多很崩。
后来看了题解,发现这个方法很巧妙。
无需考虑w的。进行分类讨论,只有rb和br两种情况。 但是如果是rrrrwbbbbrb呢??
问:如何解决w的重复运算与漏算问题? w的漏算很容易考虑,至于重算的情况那得到的总长度必然超过n,这种情况下显然是可以把所有珠子都取出来的。直接输出n就可以了。
这是USACO中提到的一个思路(应该四种思路,其中还有DP)
代码如下:
1 /* 2 ID:xiekeyi1 3 PROG:beads 4 LANG:C++ 5 */ 6 #include<bits/stdc++.h> 7 using namespace std ; 8 int main() 9 { 10 freopen("beads.in","r",stdin); 11 freopen("beads.out","w",stdout); 12 13 int n ; 14 string s ; 15 cin >> n >> s ; 16 s+=s; 17 int a = 0 , b = 0 , w = 0 , c = 0 , ans = 0 ; 18 for( int i = 0 ; i < n*2 ; i++) 19 { 20 if( s[i] == ‘w‘ ) b++,w++; 21 else if( s[i] == c ) b++,w=0; 22 else 23 { 24 ans = max( a+b,ans) ; 25 26 a = b - w ; b = w + 1 ; w = 0 ; c = s[i] ; 27 } 28 29 } 30 ans = max( a+b , ans ) ; 31 32 cout << min( ans , n ) << endl ; 33 return 0 ; 34 } 35 36
这个很巧妙,不断的试,
当时 a = b - w b = w + 1 这里我一直不理解,我认为换成 a = b , b = 1 也可以。
后来发现前者实际上是把 w和前面 后面都计算了一次,而后者不行。
这道题也让我学到了对于环的处理可以复制一次再处理。
USACO Chapter 1 Section 1.1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。