1930(div1+div2)
A. Maximise The Score
#define int long long
void solve() {
int n;cin >> n;
vector<int> a(2 * n);
for (int i = 0;i < 2 * n;i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int ans = 0;
for (int i = 0;i < 2 * n;i += 2) {
ans += min(a[i], a[i + 1]);
}
cout << ans << '\n';
}
B. Permutation Printing
构造一个数组,满足
void solve() {
int n;cin >> n;
vector<int> a(n);
int m = 0;
for (int i = 0;i < n;i += 2) {
a[i] = n - m;
a[i + 1] = 1 + m;m++;
}
for (auto i : a)cout << i << " ";cout << '\n';
}
C. Lexicographically Largest
堆栈有一个长度为
他将进行以下三步操作恰好
- 选择一个索引
,使得 . - 将
插入 插入 。 - 从
中删除 。注意, 右边所有元素的索引将减少 。
注意,
现在,Stack 将构造一个新数组
求 Stack 字典序最大的
Solution
我的想法是用
map<int, vector<int>>
存储a[i] + 1 + i
一样的序列,如果各不相同,直接从最后往前面贪心,对于相同的序列就将序列倒过来,都加上最小的序号 (待更)(看来应该是做不了 )
由题目给出的样例,可以知道,肯定不会有数字和别的重合,不然不可能是字典序最大,因此答案数组的大小一定是
从最大值到最小值贪心,先得到最大值,如果后面出现两个相等的情况,则将较小的数减一即可。(即将这个数字向前一位后再取走)
void solve() {
int n;cin >> n;vector<int> a(n), b(n);
for (int i = 0;i < n;i++) {
cin >> a[i];a[i] += i + 1;
}
sort(a.rbegin(), a.rend());
cout << a[0] << " ";
for (int i = 1;i < n;i++) {
a[i] = min(a[i], a[i - 1] - 1);
cout << a[i] << " \n"[i == n - 1];
}
}
D1/D2 Sum over all Substrings
int f(string s) {
int ans = 0;
for (int i = 0;i < s.size();i++) {
if (s[i] == '1') {
ans++;i += 2;
}
}
return ans;
}
void solve() {
int n;cin >> n;
string s;
cin >> s;
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
sum += f(s.substr(i, j - i + 1));
cout << sum << '\n';
}