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;
}
