A - Echo
题目大意
把一个字符串的每个字符输出两遍
解题思路
签到题不多嗦了;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
signed main() {
cin >> n;
string s;
cin >> s;
for (char str : s) {
cout << str << str;
}
return 0;
}
B - Base 2
题目大意
给定64个由0和1组成的序列, 如果第i个是1, 结果就加上2的(i-1)次方
解题思路
签到题不多嗦了; 就是注意一点, long long虽然是64位, 但是有一位是符号位, 所以只能取到2^63-1; 而本题最大为2^64-1, 所以要用unsigned long long;
神秘代码
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
signed main() {
n = 1;
int res = 0;
for (int i = 1; i <= 64; i++) {
cin >> m;
if (m) res += n;
n = n * 2;
}
cout << res;
return 0;
}
C - Centers
题目大意
给定一个3*n长度的数列, 其中1~n中每个数字都出现了三次, 其中第二次出现的位置就是他们的权值, 把1~n按权值排序;
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
int n, m;
vector<int> v[N];
map<int, int> mp;
signed main() {
cin >> n;
for (int i = 1; i <= 3 * n; i++) {
int x;
cin >> x;
v[x].push_back(i);
}
for (int i = 1; i <= n; i++) {
int a = v[i][1];
mp[a] = i;
}
for (auto t : mp) {
cout << t.second << ' ';
}
return 0;
}
D - Poisonous Full-Course
题目大意
小莫去一家特殊的餐馆吃饭, 按顺序给定n到菜, 对于每道菜有两个属性, 有毒or解毒以及他的美味值. 而对于每道菜, 小莫选择吃或者跳过; 如果在中毒状态下又吃到了有毒的食物就会out; 而解毒的食物即使没中毒也可以吃; 问小莫能获得的最大美味值为多少
解题思路
读完题就会发现是一个dp问题, 处理起来也不算复杂; 状态表示f(i, j)表示处理完第j到菜之后, 小莫此时是i状态, i=1则表示中毒, 0表示无毒; 状态计算时每道菜根据有毒or解毒进行分类, 每一类里面小莫都有中毒和无毒两种状态需要计算; 利用吃或不吃来进行状态转移即可;
注意 初始情况下是无毒状态, 故f(1, 0)要初始化为负无穷;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
vector<PII> v;
int f[2][N];
signed main() {
cin >> n;
v.push_back({ 0,0 });
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
v.push_back({ a,b });
}
f[1][0] = -1e15;
for (int i = 1; i < v.size(); i++) {
int a = v[i].first;
int b = v[i].second;
if (a == 1) {
f[1][i] = max(f[1][i - 1], f[0][i - 1] + b);
f[0][i] = f[0][i - 1];
}
else {
f[1][i] = f[1][i - 1];
f[0][i] = max(f[0][i - 1], max(f[1][i - 1], f[0][i - 1]) + b);
}
}
cout << max(f[0][n], f[1][n]);
return 0;
}
E - Best Performances
题目大意
给定一个数量为n且初识均为0的数列A; 接着定义了一个数列B和一个函数f(B), B是A降序排列后的结果, f(B)是指数列B前m个数的和; 然后给出了k个操作, 每次操作输入两个数a,b; 意为将A中第a个数替换为b, 对于每次操作输出更新后的f(B);
解题思路
这个题的题意很简单, 主要就是看怎么优化; 因为涉及到排序, 我们可以用两个multiset s1和s2来存储B的前m个数和后(n-m)个数; 用一个数组g来代表A; 一开始别忘了先往s1和s2里插入对应数量的0; 然后对于每次操作, 我们先从g里面取出a位置上原先的数c, 然后对c进行讨论; 如果c在s1中, 那么先删除c, 然后比较b和s2中最大数, 从而判断应该把谁插入到s1中; 如果c在s2中, 那么先删除c, 然后比较b和s1中最小的数, 看是否能把b插入到s1中; 最后别忘了替换g中a位置的数;
注意本题操作的关键是维护s1和s2中元素的个数, 必须一直保持m和(n-m)个;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, k;
int g[N];
multiset<int, greater<int>> s1;
multiset<int, greater<int>> s2;
signed main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) s1.insert(0);
for (int i = 1; i <= n - m; i++) s2.insert(0);
int res = 0;
for (int i = 1; i <= k; i++) {
int a, b;
cin >> a >> b;
int c = g[a];
if (s1.count(c)) {
s1.erase(s1.find(c));
int m1 = *s2.begin();
if (b >= m1) {
s1.insert(b);
res = res - c + b;
}
else {
s2.erase(s2.begin());
s2.insert(b);
s1.insert(m1);
res = res - c + m1;
}
}
else {
s2.erase(s2.find(c));
int m2 = *s1.rbegin();
if (b<=m2) {
s2.insert(b);
}
else {
s2.insert(m2);
s1.erase(s1.find(m2));
s1.insert(b);
res = res - m2 + b;
}
}
g[a] = b;
cout << res << endl;
}
return 0;
}