总结：赛时状态很好，做出了感觉平常会赛时寄掉但是赛后补题的E，但是也因此花费时间太多，没时间去做更简单的F和G，赛后G用时十分钟AC，F码的有点麻烦，用时40分钟左右，感觉三个小时能AK？
A. Phone Desktop
题意：给定3*5的平面，有a个1*1的格子和b个2*2的格子，求完全放下所有的格子最少需要几面平面
思路：首先想到一面平面最多放两个2*2的格子，所以先求放下所有2*2格子所需要的平面，然后算一下剩余的1*1的空格数量，如果小于b就添加新的平面、
void solve(){
int x, y;
cin >> x >> y;
int ans = y / 2 + y % 2;
int kong = y / 2 * 7;
if(y % 2){
kong += 15 - 4;
}
if(kong < x){
ans += (x - kong) / 15 + ((x - kong) % 15 != 0);
}
cout << ans << '\n';
}
B. Symmetric Encoding
题意：给定字符串，按照出现过的字母的字典序排序来反向对应，比如如果字符串是aadccef，那么出现过的字母就是acdef，反过来就是fedca，所有a换成f，c换成e，以此类推
思路：读懂即可做
void solve(){
int n;
string s;
cin >> n >> s;
map<char, int> mp;
vector<char> v;
for(int i = 0; i < n; i ++){
if(!mp[s[i]]){
mp[s[i]] = 1;
v.push_back(s[i]);
}
}
sort(v.begin(), v.end());
auto v1 = v;
sort(v1.begin(), v1.end(), greater<char>());
map<char, char> ans;
for(int i = 0; i < v.size(); i ++){
ans[v[i]] = v1[i];
}
for(int i = 0; i < n; i ++){
cout << ans[s[i]];
}
C. Beautiful Triple Pairs
题意：定义一对优美三元组为存在且仅存在一对对应的字母不相同，求有多少个优美三元组
思路：枚举哪一位不同即可，另外两位都相同，实现起来比较抽象
void solve(){
int n;
cin >> n;
vector<ll> a(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
map<PII, map<int, int>> mp1, mp2, mp3;
map<PII, int> sum1, sum2, sum3;
for(int i = 3; i <= n; i ++){
mp1[{a[i - 2], a[i - 1]}][a[i]] ++;
sum1[{a[i - 2], a[i - 1]}] ++;
mp2[{a[i - 2], a[i]}][a[i - 1]] ++;
sum2[{a[i - 2], a[i]}] ++;
mp3[{a[i - 1], a[i]}][a[i - 2]] ++;
sum3[{a[i - 1], a[i]}] ++;
}
int ans = 0;
for(auto [x, y] : mp1){
auto [i, j] = x;
int sum = sum1[x], res = 0;
for(auto [x1, y1] : y){
res += (sum - y1) * y1;
}
ans += res / 2;
}
for(auto [x, y] : mp2){
auto [i, j] = x;
int sum = sum2[x], res = 0;
for(auto [x1, y1] : y){
res += (sum - y1) * y1;
}
ans += res / 2;
}
for(auto [x, y] : mp3){
auto [i, j] = x;
int sum = sum3[x], res = 0;
for(auto [x1, y1] : y){
res += (sum - y1) * y1;
}
ans += res / 2;
}
cout << ans << '\n';
}
D. Ingenuity-2
题意：有上下左右四种指令，每个机器至少执行一次指令，分配指令让两个机器行动结束后在同一地点，且二者至少执行一次指令，求一种分配方案
思路：分类讨论，如果所有指令的个数全是偶数那各一半即可，如果有奇数，就看上下/左右是不是都是奇数，若果是那就可以相互抵消，否则做不到在同一终点，要注意二者必须至少执行一次指令
void solve(){
int n;
string s;
cin >> n >> s;
vector<int> idx(6);
for(auto c : s){
if(c == 'N') idx[1] ++;//右
if(c == 'S') idx[2] ++;//左
if(c == 'E') idx[3] ++;//上
if(c == 'W') idx[4] ++;//下
}
map<int, int> a, b;
if(idx[1] % 2 == 0 && idx[2] % 2 == 0){
a[1] = b[1] = idx[1] / 2;
a[2] = b[2] = idx[2] / 2;
}
else if(idx[1] % 2 == 1 && idx[2] % 2 == 1){
idx[1] --;
idx[2] --;
a[1] ++;
a[2] ++;
a[1] += idx[1] / 2;
b[1] += idx[1] / 2;
a[2] += idx[2] / 2;
b[2] += idx[2] / 2;
}
else{
cout << "NO\n";
return;
}
if(idx[3] % 2 == 0 && idx[4] % 2 == 0){
a[3] = b[3] = idx[3] / 2;
a[4] = b[4] = idx[4] / 2;
}
else if(idx[3] % 2 == 1 && idx[4] % 2 == 1){
idx[3] --;
idx[4] --;
b[3] ++;
b[4] ++;
a[3] += idx[3] / 2;
b[3] += idx[3] / 2;
a[4] += idx[4] / 2;
b[4] += idx[4] / 2;
}
else{
cout << "NO\n";
return;
}
if(a[1] + a[2] + a[3] + a[4] == 0 || b[1] + b[2] + b[3] + b[4] == 0){
cout << "NO\n";
return;
}
for(auto c : s){
int u = 0;
if(c == 'N') u = 1;//右
if(c == 'S') u = 2;//左
if(c == 'E') u = 3;//上
if(c == 'W') u = 4;//下
if(a[u]){
a[u] --;
cout << 'R';
}
else{
b[u] --;
cout << 'H';
}
}
cout << '\n';
}
E. Money Buys Happiness
题意：给定n个物品，该物品只能在第 i 月购买，花费 hi 获得 ci 的幸福感，只有在每个月的月底可以获得 x 元，求能获得的最大幸福感
思路：体重的 hi 总和不超过 1e5 就是一个提示，定义dp[i][j] 为前 i 个物品获得 j 幸福感的最大剩余钱数，那么转移就是
最后找一下剩余钱数不为0的最大价值即可
void solve(){
int n, x, sum = 0;
cin >> n >> x;
vector<int> c(n + 1), h(n + 1);
for(int i = 1; i <= n; i ++){
cin >> c[i] >> h[i];
sum += h[i];
}
vector<vector<int>> dp(n + 10, vector<int>(sum + 10, -1));
if(c[1] == 0){
dp[1][h[1]] = x;
}
dp[1][0] = x;
for(int i = 1; i <= sum; i ++) dp[0][i] = 0;
for(int i = 2; i <= n; i ++){
for(int j = 0; j <= sum; j ++){
if(dp[i - 1][j] != -1){
dp[i][j] = max(dp[i][j], dp[i - 1][j] + x);
}
if(dp[i - 1][j] >= c[i]){
dp[i][j + h[i]] = max(dp[i][j + h[i]], dp[i - 1][j] - c[i] + x);
}
}
}
for(int i = sum; i >= 0; i --){
if(dp[n][i] != -1){
cout << i << '\n';
return;
}
}
}
F. Cutting Game
题意：给定a*b的格子，每次会给命令删去前k或者后 k 行/列，并且获得其中的所有有价值的点，轮流操作求各自获得的价值
思路：用两个map分别用x和y排序，然后从前/后删点，并且再开一个map存点是否存在，每次不存在就加上
void solve(){
ll a, b, n, m;
cin >> a >> b >> n >> m;
map<PII, ll> mp1, mp2, mp;
for(int i = 1; i <= n; i ++){
ll x, y;
cin >> x >> y;
mp1[{x, y}] ++;
mp2[{y, x}] ++;
mp[{x, y}] ++;
}
ll ans1 = 0, ans2 = 0;
int u = 1, d = a, l = 1, r = b;
for(int i = 1; i <= m; i ++){
char c;
int k, res = 0;
cin >> c >> k;
vector<PII> del;
if(c == 'U'){
u += k;
for(auto q = mp1.begin(); q != mp1.end(); q ++){
auto [x, y] = *q;
if(x.first < u){
if(mp[x]){
res ++;
mp[x] --;
del.push_back(x);
}
}
else break;
}
for(auto d : del) mp1.erase(d);
}
if(c == 'D'){
d -= k;
for(auto q = mp1.rbegin(); q != mp1.rend(); q ++){
auto [x, y] = *q;
if(x.first > d){
if(mp[x]){
res ++;
mp[x] --;
del.push_back(x);
}
}
else break;
}
for(auto d : del) mp1.erase(d);
}
if(c == 'L'){
l += k;
for(auto q = mp2.begin(); q != mp2.end(); q ++){
auto [x, y] = *q;
PII x1 = {x.second, x.first};
if(x.first < l){
if(mp[x1]){
res ++;
mp[x1] --;
del.push_back(x);
}
}
else break;
}
for(auto d : del) mp2.erase(d);
}
if(c == 'R'){
r -= k;
for(auto q = mp2.rbegin(); q != mp2.rend(); q ++){
auto [x, y] = *q;
PII x1 = {x.second, x.first};
if(x.first > r){
if(mp[x1]){
res ++;
mp[x1] --;
del.push_back(x);
}
}
else break;
}
for(auto d : del) mp2.erase(d);
}
if(i & 1) ans1 += res;
else ans2 += res;
}
cout << ans1 << ' ' << ans2 << '\n';
}
G. Money Buys Less Happiness Now
题意：给定n个物品，每次可以在第 i 月花费 ci 获得 1 幸福感，月底获得 x 元，求最多获得多少幸福感
思路：用优先队列维护即可，每次如果当前费用足够直接购买，否则查看先前购买的最贵的是不是比当前的还贵，如果是的就不要前面那个，选择当前的幸福感，否则就放弃当前的物品
void solve(){
ll n, x, sum = 0;
cin >> n >> x;
priority_queue<ll> q;
for(int i = 1; i <= n; i ++, sum += x){
ll sal;
cin >> sal;
if(sum >= sal){
q.push(sal);
sum -= sal;
}
else if(q.size()){
ll pre = q.top();
q.pop();
if(pre > sal){
sum += pre;
sum -= sal;
q.push(sal);
}
else q.push(pre);
}
}
cout << q.size() << '\n';
}
标签：idx,946,auto,Codeforces,++,int,mp2,mp,Div From： https://www.cnblogs.com/RosmontisL/p/18203636