第十八届东北CCPC程序设计竞赛题解

A: Paper Watering

解题思路：

​ 该题很简单，但有一个需要考虑到的，就是当一个数 n 不是完全平方数的时候，那么他执行 1 操作之后再执行 2 操作之后，所得到的值和之前的不同，那么就需要再进行处理。

解题代码：

void Solved() {	int n, k; cin >> n >> k;int ans = 0;if(n == 1){cout << 1 << endl;return ;}int temp = 0;while(n != 1 && temp < k) {temp ++;int t = (int)sqrt(n);ans ++;if(t * t != n && t != 1) ans += k - temp;n = t;}cout << ans + k + 1 << endl;
}

E: Checksum

解题思路：

​ 该题看到时间复杂度可以看出来是用的遍历，对k进行枚举，然后进行判断就行了。该题可以用到bitset，代码更简洁。

解题代码：

void solve() {int n,k;cin >> n >> k;int len = 0;for(int i = 1; i<= n; i++){char a; cin >> a;if(a == '1') len ++;}for(int i = 0; i <= k; i++){int sum = len + i;bitset<32> d(sum);int dd = 0;for(int j = 0; j < k; j ++ )  if(d[j] == 1) dd ++;if(dd == i) {for(int j = k - 1; j >= 0; j -- ) {cout << d[j];} cout << endl;return ;}		}cout << "None" << endl;
}

L: Bracket Generation

解题思路：

​ 该题赛时没写出来。。。当时就想着怎么进行排列了，没想到顺序这回事。

因为这只有两种情况：

1. 在序列后加一个括号
2. 选取合法的括号，将其中括号包裹住。

那么括号的排列是有一定的顺序的，就比如那个最小的括号一定是在包裹它的括号后面，如下图所示：

​

​ 就上图，该图中那前两个1一定是在第一个2的后面，前四个1一定是在第二个2的前面，这个顺序是固定的，那么只要满足前面1的顺序，后面的2在后面的顺序就可以随便放了。

解题代码：

void solve() {string str;cin >> str;vector<int> vec;vector<int> a;for(int i = 0; i < str.size(); i++){if(str[i] == ')' && str[i - 1] == '('){a.push_back(1);}else if(str[i] == ')'){a.push_back(2);}}reverse(a.begin(),a.end());int res = 1,cnt = 0;for(int i = 0; i < a.size(); i++){cnt ++;if(a[i] == 2){res = res * cnt % mod;}}cout << res << endl;
}

I: password(待补)

解题思路:
解题代码: