比赛链接： https://vjudge.net/contest/178158#overview
A： Binary Protocal
题目描述： 规定一个数转化成“二进制”， 各个数位上的数字为1的个数， 两个数位之间相隔一个0， 如果数位本身为0， 相当于输出0个1再输出一个0， 现在知道了“二进制”， 让你反推这个数
解题思路： 一开始我又犯蠢了， 这么一道简单题浪费了很多时间， 快半个点儿吧， 实际上是只需要结束的时候特判一下最后一位是否为0 就可以
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <map> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; int main() { int n; string s; cin >> n >> s; int ans = 0; for( int i = 0; i < n; i++ ) { if( s[i] == '1' ) ans++; if( s[i] == '0'|| i == n-1 ) { cout << ans; ans = 0; } } if( s[n-1] == '0' ) cout << "0"; cout << endl; return 0; }
思考：一道水题自己也写了好长时间......想不到点子上面......
B: Five in a row
题目描述： 给你一个棋盘， 让你判断能不能再放一个黑子使之成为五连， 棋盘很小
解题思路： 暴力就可以， 将黑子转换为1， 空闲转换为0， 在八个方向中都加一遍（其实仅仅需要四个方向）， 如果 == 4就输出 yes
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; char graph[20][20]; int turn[20][20]; int main() { memset( graph, 0, sizeof(graph) ); memset( turn, 0, sizeof(turn) ); for( int i = 1; i <= 10; i++ ) { for( int j = 1; j <= 10; j++ ) { cin >> graph[i][j]; if( graph[i][j] == 'X' ) turn[i][j] = 1; else if( graph[i][j] == 'O' ) turn[i][j] = -1; else if( graph[i][j] == '.' ) turn[i][j] = 0; } } // for( int i = 1; i <= 10; i++ ) { // for( int j = 1; j <= 10; j++ ) { //// cout << graph[i][j] << " "; // cout << turn[i][j] << " "; // } // cout << endl; // } int ans = 0; for( int i = 1; i <= 10; i++ ) { for( int j = 1; j <= 10; j++ ) { if( turn[i][j] == 1 || turn[i][j] == 0 ){ int a, b, c, d, e, f, g, h; a = b = c = d = e = f = g = h = 0; for( int k = 0; k < 5; k++ ) { if( j <= 6 ) a += turn[i][j+k]; // right if( i <= 6 ) b += turn[i+k][j]; // down if( j <= 6 && i <= 6 ) c += turn[i+k][j+k]; // eastsouth if( i >= 5 && j >= 5 ) d += turn[i-k][j-k]; // westnorth if( i >= 5 && j <= 6 ) e += turn[i-k][j+k]; // eastnorth if( i <= 6 && j >= 5 ) f += turn[i+k][j-k]; // westsouth } ans = max(a,max(b,max(c,max(d,max(e,f))))); //cout<<ans<<endl; if( ans == 4 ) { cout << "YES" << endl; return 0; } } } } cout<<"NO"<<endl; return 0; }
思考： 以前做过好多遍了......
C： Multi judge solving
题目描述： 这个题看了好久.....就是给你一组数， 和一个K， 只要小于等于2 * k都可以立刻被忽略掉并且k被取代成k与这个数之间更大的数，但是k * 2需要代价， 问最小代价是多少
解题思路： 排序， 设置cnt记录k * 2的次数， 每次更新k为k 与 a[i]的最大值
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; int a[1000+50]; int main() { int n, k; cin >> n >> k; for( int i = 1; i <= n; i++ ) { cin >> a[i]; // if( a[i] <= k*2 ) a[i] = 0; } sort( a+1, a+n+1 ); // for( int i = 1; i <= n; i++ ) { // cout << a[i] << " "; // } // cout << endl; int ans = 0; for( int i = 1; i <= n; i++ ) { while( a[i] > k*2 ) { k *= 2; ans++; } k = max( k, a[i] ); } cout << ans << endl; }
思考： 自己一开始读错题了.....并没有更新K， WA了一发， 好好读题....
D： Suitable replacement
题目描述： 给你连个字符串， 第一个字符串内可能有问号， 现在让你用任意的字母替换问号， 使得第一个字符串能够出现最多次数的字符串二， 不重叠（还有串s可以随意排序）
解题思路： 首先特判问号个数为0或者len2 > len1的情况，抠掉。 然后直接看字符串t中各个字母，如果各个字母出现在s中就可以抵消掉一部分， 否则只能用问号抵消。 所以我们直接遍历字符串t各个字母， 如果出现在字符串s ， 不去管它， 当然s中的该字符的次数要--， 否则出现一个没有出现过的字符就直接用它替换问号。
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; map<char, int> ms; map<char, int> mt; stack<char> ans; int main() { ms.clear(); mt.clear(); string s; string t; cin >> s >> t; int len1 = (int)s.length(); int len2 = (int)t.length(); int cnt = 0; for( int i = 0; i < len1; i++ ) { if( s[i] == '?' ) cnt++; ms[s[i]]++; } for( int i = 0; i < len2; i++ ) { mt[t[i]]++; } if( cnt == 0 || len2 > len1 ) { cout << s << endl; return 0; } while( cnt ) { for( int i = 0; i< len2; i++ ) { if( ms[t[i]] ) ms[t[i]]--; else { ans.push(t[i]); cnt--; if( cnt == 0 ) break; } } } for( int i = 0; i < len1; i++ ) { if( s[i] == '?' ) { char res = ans.top(); ans.pop(); s[i] = res; } } cout << s << endl; return 0; }
思考： 这种思维题有的没有那么复杂， 很大一部分靠贪心就能解出来
比赛总结： 以后多做点儿这种题吧， 挺有意思的， 再说自己的手速码力和思维都有待提高.......