Problem A Counting Sticks
题意:给一个有棍子组成的加法等式现在只允许你移动一根棍子,是等式成立。
思路:比赛时候脑子卡壳直接暴力枚举,然后还有一个小地方错了,最后挂了。结束后改了过来。枚举两个加数判断是不是能从原来状态一步移到。
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-20 23:25 5 * Filename : Codeforce_231_2_A.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 34 int main() 35 { 36 // freopen("in.txt", "r", stdin); 37 38 char str[1010]; 39 int num[3], top, a, b, tsum; 40 while(cin >> str){ 41 int len = strlen(str); 42 top = 0;memset(num, 0, sizeof num); 43 tsum = 0; 44 for(int i=0; i<len; i++){ 45 if(str[i] == '|') { 46 num[top]++; 47 tsum++; 48 } 49 else top++; 50 } 51 int f = 1; 52 for(int i=1; i<101; i++){ 53 for(int j=1; j<101; j++){ 54 int tmp = abs(num[0]-i) + abs(num[1]-j) +abs(num[2]-(tsum-i-j)); 55 if((tmp == 2 || !tmp) && i+j==tsum-i-j){ 56 f = 0;a = i;b = j;break; 57 } 58 } 59 if(!f) break; 60 } 61 if(f) cout << "Impossible" << endl; 62 else { 63 for(int i=0; i<a; i++) cout << "|"; 64 cout << "+"; 65 for(int i=0; i<b; i++) cout << "|"; 66 cout << "="; 67 for(int i=0; i<a+b; i++) cout << "|"; 68 cout << endl; 69 } 70 71 } 72 return 0; 73 }
Problem B Very Beautiful Number
题意:求一个长度为p的数使得p的最后一个数字移到第一个变成的新数是原数的x倍。
思路:枚举原数最后一位,然后新数最高位就知道了用新数除以x我们可以发现虽然新数只知道最高位,但是最高位除x的结果其实就是次高位,这样我们就能模拟整个除法的过程推出原数。最后验证新数最后一位与枚举的数是否相等。由于新数最高位是从小到大枚举的,所以求出来的一定是最小的。
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-20 23:26 5 * Filename : Codeforce_231_2_B.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1000000+10; 34 int num[LEN], p, x, ans[LEN]; 35 36 int main() 37 { 38 // freopen("in.txt", "r", stdin); 39 40 while(scanf("%d%d", &p, &x) != EOF){ 41 int tt, f = 1; 42 for(int i=x; i<10; i++){ 43 tt = i; 44 for(int j=0; j<p; j++){ 45 ans[j] = tt/x; 46 tt = (tt%x)*10+ans[j]; 47 } 48 if(i == ans[p-1] && tt==i) { 49 f = 0; 50 break; 51 } 52 } 53 if(f) printf("Impossible "); 54 else { 55 for(int i=0; i<p; i++) printf("%d", ans[i]); 56 } 57 58 printf(" "); 59 } 60 return 0; 61 }
Problem C Dominoes
题意:有许多骨牌(00,01,10,11)放在一个n*2m的矩阵中,01和10可以通过翻转互换。然后让你求所有列上和最大的最小值。
思路:贪心+模拟 只要先把11平均放在每一行再放01和10最后剩下来的都是00。最后就是答案,至于01与10我们可以设置一个标记上一行放的01那下一行就放10。
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-02-20 23:26 5 * Filename : Codeforce_231_2_C.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 1010; 34 int n, m, Map[LEN][LEN], top[LEN], sum[LEN], cnta, cntb; 35 36 int main() 37 { 38 // freopen("in.txt", "r", stdin); 39 40 char str[10]; 41 while(scanf("%d%d", &n, &m)!=EOF){ 42 memset(Map, 0, sizeof Map); 43 memset(top, 0, sizeof top); 44 memset(sum, 0, sizeof sum); 45 cnta = cntb = 0; 46 for(int i=0; i<n; i++){ 47 for(int j=0; j<m ;j++){ 48 scanf("%s", str); 49 if(!strcmp(str, "11")) cnta++; 50 if(!strcmp(str, "01") || !strcmp(str, "10")) cntb++; 51 } 52 } 53 int pos; 54 for(int i=0; i<n; i++){ 55 for(int j=0; j<m; j++){ 56 if(cnta==0) { 57 pos = j; 58 break; 59 } 60 Map[i][j] = 2; 61 sum[j]+=2; 62 top[j] ++; 63 cnta--; 64 } 65 if(cnta == 0) 66 break; 67 } 68 if(cntb-m>=m){ 69 for(int j=0; j<(cntb-m)/m; j++) 70 for(int i=0; i<m; i++){ 71 Map[top[i]++][i] = 1; 72 sum[i]++; 73 } 74 while(cntb-m>=m)cntb-=m; 75 } 76 for(int j=0; j<cntb; j++){ 77 int min = INF, minpos; 78 for(int i=0; i<m; i++){ 79 if(top[i] < n && sum[i] < min){ 80 min = sum[i]; 81 minpos = i; 82 } 83 } 84 Map[top[minpos]++][minpos] = 1; 85 sum[minpos] ++; 86 } 87 int tag[LEN]; 88 memset(tag, -1, sizeof tag); 89 for(int i=0; i<n; i++){ 90 for(int j=0; j<m; j++){ 91 if(Map[i][j] == 0)printf("00"); 92 else if(Map[i][j] == 2)printf("11"); 93 else if(Map[i][j] == 1){ 94 if(tag[j]<0) printf("01"); 95 else printf("10"); 96 tag[j] = -tag[j]; 97 } 98 printf(" "); 99 } 100 printf(" "); 101 } 102 } 103 return 0; 104 }