本文主要是介绍think-cell Round 1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
think-cell Round 1
A. Maximise The Score
题意：给出2n个数，每次选两个取较小值加到分数里，分数最大为多少。
思路：排序，奇数位和。
AC code：
void solve() {cin >> n;int ans = 0;int a[N];for (int i = 0; i < 2*n; i ++) {cin >> a[i];}sort(a, a + 2 * n);for (int i = 0; i < 2 * n; i += 2) ans += a[i];cout << ans << endl;
}
B. Permutation Printing
题意：求长度为n的一个排列，该排列不存在两个不同的索引i,j使得pi平分pj，pi+1平分pj+1。
思路：奇偶交叉排列即可，注意n为偶数时先排偶数位，否则先排奇数位。
AC code：
void solve() {cin >> n;int t = 2;if (n % 2 == 0) {for (int i = 1; i <= n; i ++) {if (i % 2) a[t] = i, t += 2;}t = 1;for (int i = n; i >= 1; i --) {if (i % 2 == 0) {a[t] = i;t += 2;}}} else {t = 1;for (int i = 1; i <= n; i ++) {if (i % 2) a[t] = i, t += 2;}t = 2;for (int i = n; i >= 1; i --) {if (i % 2 == 0) {a[t] = i;t += 2;}}}for (int i = 1; i <= n; i ++) cout << a[i] << " ";cout << endl;
}
C. Lexicographically Largest
题意：给出长度为n的数组a，可以任意取出数组a中的元素，每次取出元素+当前下标存入一个栈中，然后比当前取出元素下标大的元素下标-1，注意堆栈是个排列，即堆栈中元素不能重复，求堆栈最大词典序。
思路：每次取出当前最大元素+下标即可，需要处理的是取到重复元素的处理，若取到重复元素，则所加下标递减1即可。这里可以用一个set来存已经入栈的元素，新元素+下标若重复，则在已经入栈的元素中选最小的-1再压入即可。选已经压入的元素中最小的元素-1可以最大化最终字典序，且不会在栈中重复。
AC code:
void solve() {priority_queue<int> q;cin >> n;for (int i = 1; i <= n; i ++) {int x; cin >> x;q.push(x + i);}set<int> s;while (!q.empty()) {auto t = q.top();q.pop();if (s.find(t) != s.end()) {t = *s.begin() - 1;}s.insert(t);cout << t << " ";}cout << endl;
}
D. Sum over all Substrings
题意：有点抽象，尽量理解。
首先是题目中的长度相同的字符串p和q的good，即对与p中的每一个字符pi，在q中都会存在一个子串符合pi模式；
然后是XX模式，即一个字符在一个子串中出现的次数为众数，则称字符串q为pi模式；
那么对于二进制字符串p，题目需要我们创造1最少的符合条件的good串q，每一子串都要符合good条件；
要最小化q中1的数量，最佳情况可以看出，当p中出现1是，q中每三个字符至少存在一个1，则可以符合当前子串good条件。
思路：
- 对于D1，可以直接暴力，即当字符串p出现字符1时，那么q当前位标记为1，包括该字符以及之后两位的三位字符均可以通过当前一位1来保证子串good。
- 对于D2，可以用dp来计算当前后缀连续子串的答案，由D1可知，影响1的数量的为每三位出现字符1的情况：
- 当前位为0时，dp[i] = dp[i + 1];
- 当前位为1时，dp[i] = dp[i + 3] + (n - i + 1);
AC code :
- D1
void solve() {cin >> n;int ans = 0;string s; cin >> s;for (int i = 0; i < n; i ++) {string now = "";for (int j = i; j < n; j ++) {now += s[j];int pos = 0;while (pos < now.size()) {if (now[pos] == '1') {ans ++;pos += 2;}pos ++;}}}cout << ans << endl;
}
- D2
void solve() {cin >> n;string s; cin >> s;s = " " + s;vector<int> dp(n + 10, 0);int ans = 0;for (int i = n; i >= 1; i --) {if (s[i] == '0') {dp[i] = dp[i + 1];} else {if (i + 3 > n) dp[i] = n - i + 1;else dp[i] = n - i + 1 + dp[i + 3]; }ans += dp[i];}cout << ans << endl;
}
这篇关于think-cell Round 1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
