A - Echo (abc306 a)
题目大意
给定一个字符串，将每个字符输出两次。
解题思路
模拟即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
string s;
cin >> n >> s;
for(auto &i : s)
cout << i << i;
cout << 'n';
return 0;
}
B - Base 2 (abc306 b)
题目大意
给定一个从低位开始的二进制串，将其转为十进制。
解题思路
注意有(64)位，得用 unsigned long long。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
unsigned long long ans = 0;
unsigned long long ji = 1;
for(int i = 0; i < 64; ++ i){
int x;
cin >> x;
if (x)
ans += ji;
ji <<= 1;
}
cout << ans << 'n';
return 0;
}
C - Centers (abc306 c)
题目大意
给定一个(1 sim n)都出现三次的数组 (a)。
定义 (f(x))表示 (x)第二次出现在 (a)的位置。
按照位置的升序输出 (x)。
解题思路
按照题意求出位置后，排序即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<int> pos(n, -2);
for(int i = 0; i < 3 * n; ++ i){
int x;
cin >> x;
-- x;
if (pos[x] == -2){
pos[x] = -1;
}else if (pos[x] == -1)
pos[x] = i;
}
vector<int> ans(n);
iota(ans.begin(), ans.end(), 0);
sort(ans.begin(), ans.end(), [&](int a, int b){
return pos[a] < pos[b];
});
for(auto &i : ans)
cout << i + 1 << ' ';
cout << 'n';
return 0;
}
D - Poisonous Full-Course (abc306 d)
题目大意
有(n)个疗程，分为两种：
- 解毒疗程，增加美味值 (y)
- 中毒疗程，增加美味值 (y)
高桥一开始很健康，他接受了解毒疗程后还是很健康，接受中毒疗程就会中毒。中毒状态下接受解毒疗程就恢复健康，如果又接受中毒疗程则会挂。
高桥可以跳过一些疗程，问最后在他没挂的前提下，接受疗程的美味值的和的最大值。
解题思路
注意(y)可能会有负数。比较简单的(dp)，由于中毒下接受中毒疗程会挂，为保证最后我们活着，我们只需保留最后的状态这个信息就好了。
设 (dp[i][0/1])表示考虑前 (i)个疗程后，当前是健康/中毒状态下的最大美味值。
根据当前状态转移即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
array<LL, 2> dp{0, 0};
for(int i = 0; i < n; ++ i){
array<LL, 2> dp2{0, 0};
LL x, y;
cin >> x >> y;
if (x == 0){
dp2[0] = max(dp[0] + max(y, 0ll), dp[1] + y);
dp2[1] = dp[1];
}else{
dp2[0] = dp[0];
dp2[1] = max(dp[0] + y, dp[1]);
}
dp.swap(dp2);
}
cout << *max_element(dp.begin(), dp.end()) << 'n';;
return 0;
}
E - Best Performances (abc306 e)
题目大意
给定一个数组(A)，定义其价值为前(k)大的数的和。
有 (q)次操作，每次操作令(A_x = y) 。
每次操作后，回答其价值。
操作是持久化的。
解题思路
用两个(set)，分别维护前 (k)大的和剩余的数。
每次操作则修改对应的 (set)的值，然后比较 左边的最小值和右边的最大值，如果小于则交换一下这两个数。
每次操作最多就交换两个数，因此复杂度是(O(qlog n))
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, k, q;
cin >> n >> k >> q;
array<set<pair<int, int>>, 2> num;
for(int i = 0; i < k; ++ i){
num[1].insert({0, i});
}
for(int i = k; i < n; ++ i){
num[0].insert({0, i});
}
LL ans = 0;
vector<int> a(n, 0);
while(q--){
int x, y;
cin >> x >> y;
-- x;
auto token = make_pair(a[x], x);
if (num[1].count(token)){
num[1].erase(token);
num[1].insert({y, x});
ans += y - a[x];
}else{
num[0].erase(token);
num[0].insert({y, x});
}
a[x] = y;
while(num[1].size() < k){
auto l = *num[0].rbegin();
ans += l.first;
num[1].insert(num[0].extract(l));
}
while(num[1].size() > k){
auto r = *num[1].begin();
ans -= r.first;
num[0].insert(num[1].extract(r));
}
while(!num[0].empty() && num[0].rbegin() -> first > num[1].begin() -> first){
auto l = *num[0].rbegin(), r = *num[1].begin();
ans += l.first - r.first;
num[1].insert(num[0].extract(l));
num[0].insert(num[1].extract(r));
}
cout << ans << 'n';
}
return 0;
}
F - Merge Sets (abc306 f)
题目大意
对于两个交集为空的集合(A,B)，定义(f(A, B))为， (A)中每个元素在 (A cup B)的位置的和。(A cup B)的位置即为将其所有数升序排序后的下标（从(1)开始）。
现给定俩俩交集均为空的(n)个集合 (s_i) ，求(sum_{1 leq i < j leq n} f(s_i, s_j))。
解题思路
由于(sum_{1 leq i < j leq n} f(s_i, s_j) = sum pos(s_{i,x}, s_j))，分析答案的贡献，发现可以转换成求每个数的贡献。因此我们的视角从枚举集合转移到枚举每个数。
对于第(i)个集合的升序排列的第 (x)个数 (s_{i,x})（此处下标均从(0)开始，同代码一致），我们考虑它会对答案贡献多少。
注意 (i < j)，这意味着我们只有选择 (j > i)的集合 (s_j)时，(s_{i,x}) 才有贡献。
然后考虑选择了(s_j)后， (s_{i,x})的是排第几位。假设 (s_j)中有 (y_j)个小于 (s_{i,x})的，那么此时 (s_{i,x})的贡献是 (x + y_j + 1)。然后将所有(j > i)的 (s_j)的这些贡献累加，就是 (s_{i,x})对答案的贡献。
直接累加的复杂度是 (O(n^2))，很显然不能这样算。
我们分析这个贡献式子，它可以拆成三部份 (x, y_j, 1)。第一项和最后一项会贡献 (n - i - 1)次（注意从第(0)集合算起）。
而第二项的(y_j)， 我们可以把(n times m)个数全部丢到数组(Q)里排个序，假设(s_{i,x})排在第 (a)位，那么 (sum_{j > i} y_j)的值就是在数组(Q)中，所有位置(pos < a)，且位于集合下标 (j > i)的数的个数。
显然这是一个二维偏序问题，同abc283f一样。我们可以用树状数组维护关于集合下标的数的个数，然后从小到大遍历(Q)数组，依次把每个数加进树状数组中。这样查询一下后缀和，就是(sum_{j > i} y_j)。进而 (s_{i, x})的贡献就是 (sum_{j > i}y_j + (x + 1) times (n - i - 1))，对于每个数依次这么计算即可。
时间复杂度为(O(nm log n))
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
template <typename T>
class fenwick {
public:
vector<T> fenw;
int n;
fenwick(int _n) : n(_n) {
fenw.resize(n);
}
void modify(int x, T v) {
while (x < n) {
fenw[x] += v;
x |= (x + 1);
}
}
T get(int x) {
T v{};
while (x >= 0) {
v += fenw[x];
x = (x & (x + 1)) - 1;
}
return v;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<array<int, 2>> a(n * m);
int pos = 0;
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m; ++ j){
cin >> a[pos][0];
a[pos][1] = i;
pos ++;
}
}
sort(a.begin(), a.end(), [](const auto &x, const auto &y){
return x[0] < y[0];
});
fenwick<int> cnt(n);
LL ans = 0;
int sum = 0;
for(int i = 0; i < n * m; ++ i){
int belong = a[i][1];
int pre = cnt.get(belong - 1);
int cur = cnt.get(belong);
ans += sum - cur + 1ll * (n - belong - 1) * (cur - pre + 1);
cnt.modify(belong, 1);
sum ++;
}
cout << ans << 'n';
return 0;
}
G - Return to 1 (abc306 g)
题目大意
给定一张有向图，问能否从(1)号点出发，经过 (10^{10^{100}})条边后，回到 (1)号点。
解题思路
<++>
神奇的代码
Ex - Balance Scale (abc306 h)
题目大意
给定一个数组(A)。
进行 (m)次操作，每次操作从 (A)中取两个数，然后将它们的大小结果 (> = <)之一加入字符串 (s)的最后。
问字符串(s)可能的情况数量。
解题思路
<++>
神奇的代码
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
