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;
}
- Beginner AtCoder Contest 306 abcbeginner atcoder contest 306 306 beginner atcoder contest beginner atcoder contest abc atcoder beginer contest 306 atcoder abc 306 def contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335