Codeforces Round 946 (Div. 3) (A-G)
A. Phone Desktop
在一个 大小的手机上面上摆放 个 大小和 个 大小的手机图标。问最小需要多少个屏幕
先摆大的,剩下的空间摆小的。
void solve() {int x, y;read(x, y);int occupy_full = y / 2;bool is_remain = y % 2;int remain_cell = occupy_full * 7 + is_remain * 11;int big = occupy_full + is_remain;int small = std::ceil(std::max(x - remain_cell, int(0)) * 1.0 /15);std::cout << occupy_full + (is_remain) + std::ceil(mmax((x - remain_cell), 0) * 1.0 / 15);}
B. Symmetric Encoding
输入一个字符串 ,将 进行排序去重后得到 。根据映射关系将中每个字符找到在 中对应的 并替换为替换为 ,其中
void solve() {int a;std::cin >> a;std::string x;std::cin >> x;std::string y = x;std::sort(all(y));y.erase(std::unique(all(y)), y.end());std::map<char, char> mp;for(int i = 0, end = y.size()-1; i < y.size(); i++, end--){mp[y[i]] = y[end];}for(auto ch: x){std::cout << mp[ch];}}
C. Beautiful Triple Pairs
给一个序列 ,构造三元组
求中有多少对三元组中只有一个元素不同
假设现在只求最后一个元素不同的元组有多少对。
设对于 ,前两个元素相同的数量减去三个元素相同的数量,即为和 相比最后一个元素不同的数量。
void solve() {i32 n;read(n);std::vector<int> a(n);reads(all(a));std::map<std::pair<int, int>, int> fst, snd, thi;std::map<std::array<int, 3>, int> cnt;i64 ans = 0;for (int i = 0; i < n - 2; i++) {int q = a[i], w = a[i + 1], e = a[i + 2];ans += fst[{w, e}] - cnt[{q, w, e}];ans += snd[{q, e}] - cnt[{q, w, e}];ans += thi[{q, w}] - cnt[{q, w, e}];fst[{w, e}]++;snd[{q, e}]++;thi[{q, w}]++;cnt[{q, w, e}]++;}std::cout << ans;}
D. Ingenuity-2
A和B都能向NSEW四个方向移动,现在给出一个操作序列,将序列中每个元素分给A或B,使A和B在同一个点出发时都能到达同一个终点,且A和B都进行了移动。
- 如果有两个相同的操作,可以将两个操作分别发给A和B
- 如果有两个相反的操作(比如N和S),可以将其两者发给A或B
- 将 NS 发给 A,EW 发给B可确保在可行时 A 和B 都能进行移动
思路很乱,写的又臭又长
void solve() {int len;std::cin >> len;std::string instr;std::cin >> instr;std::map<char, int> cnt;for(auto ch: instr){cnt[ch]++;}std::map<char, int> tmp = cnt;cnt['N'] %= 2;cnt['S'] %= 2;cnt['E'] %= 2;cnt['W'] %= 2;if(cnt['N'] != cnt['S'] || cnt['E'] != cnt['W']){std::cout << "NO";return;}std::map<char, int> p = tmp;p['N'] -= cnt['N'];p['S'] -= cnt['S'];p['E'] -= cnt['E'];p['W'] -= cnt['W'];char flipChar = 'N';if(p['N'] > 0 && p['N'] % 2 == 0){flipChar = 'N';}else if(p['S'] > 0 && p['S'] % 2 == 0){flipChar = 'S';}else if(p['E'] > 0 && p['E'] % 2 == 0){flipChar = 'E';}else if(p['W'] > 0 && p['W'] % 2 == 0){flipChar = 'W';}std::string seq;int Hcnt = 0, Rcnt =0;for(auto ch: instr){if(p[ch] != 0) {if(p[ch] % 2){if(flipChar == ch){seq.push_back('H');Hcnt++;}else{seq.push_back('R');Rcnt++;}}else{if(flipChar == ch){seq.push_back('R');Rcnt++;}else{seq.push_back('H');Hcnt++;}}p[ch]--;}else if(ch == 'N' || ch == 'S') {seq.push_back('R');Rcnt++;}else{seq.push_back('H');Hcnt++;}}if(Rcnt == 0 || Hcnt==0){std::cout << "NO";}else{std::cout << seq;}}
E. Money Buys Happiness
小 C 每个月赚 元,在 个月中每个月都可以花费 元获取 的快乐值,这种操作最多进行1次。
个月后小 C 的快乐值最大是多少
似乎是 PTA 上的原题
注意数据范围发现 和 出奇的小,故可以将背包的维度掉转一下。使 表示第 个月有 快乐的时候花了多少钱
那么就有
int dp[67][50017];void solve(){int m, x;read(m, x);std::vector<int> c(m + 1), h(m + 1);int max_h = 50010;for (int i = 1; i <= m; i++){read(c[i], h[i]);}std::memset(dp, -0x3f, sizeof(dp));dp[0][0] = 0;for (int i = 1; i <= m; i++){for (int j = 0; j <= max_h; j++){if (j - h[i] >= 0 && dp[i - 1][j - h[i]] >= c[i]){dp[i][j] = std::max(dp[i - 1][j - h[i]] - c[i] + x, dp[i-1][j] + x);}else{dp[i][j] = dp[i - 1][j] + x;}}}int ans = 0;for (int j = 0; j <= max_h; j++){if (dp[m][j] >= 0){ans = mmax(ans, j);}}std::cout << ans;}
F. Cutting Game
有 大小的格子,上面摆有 个物品。A 和 B 轮流从上、下、左或右侧删一定的行或列,每当他们删去的格子上有1个物品时得一分。给出格子、物品和操作,求得分
拿个 set 存位置打暴力即可,注意行列
复杂度
void solve() {int a, b, n, m;read(a, b, n, m);std::set<std::pair<int, int>> rchip, cchip, removed;for (int i = 0; i < n; i++) {int x, y;read(x, y);rchip.insert({x, y});cchip.insert({y, x});}int lbound = 1, rbound = b, tbound = 1, bbound = a;int point[2] = {0, 0};for (int i = 0; i < m; i++) {char op;int opnum;std::cin >> op >> opnum;if (op == 'U') {while (!rchip.empty() && rchip.begin()->first - tbound < opnum) {cchip.erase({rchip.begin()->second, rchip.begin()->first});rchip.erase(rchip.begin());point[i % 2]++;}tbound += opnum;} else if (op == 'D') {while (!rchip.empty() && bbound - rchip.rbegin()->first < opnum) {cchip.erase({rchip.rbegin()->second, rchip.rbegin()->first});rchip.erase(--rchip.end());point[i % 2]++;}bbound -= opnum;} else if (op == 'L') {while (!cchip.empty() && cchip.begin()->first - lbound < opnum) {rchip.erase({cchip.begin()->second, cchip.begin()->first});cchip.erase(cchip.begin());point[i % 2]++;}lbound += opnum;} else {while (!cchip.empty() && rbound - cchip.rbegin()->first < opnum) {rchip.erase({cchip.rbegin()->second, cchip.rbegin()->first});cchip.erase(--cchip.end());point[i % 2]++;}rbound -= opnum;}}std::cout << point[0] << " " << point[1];}
G. Money Buys Less Happiness Now
在 个月中每月收入 元,每个月都可以花费 元购买 1 点幸福
输出最大幸福
反悔贪心。由于每次购买的幸福都是1,所以在钱不够是反悔1次总能得到最优解
void solve() {int m, x;read(m, x);std::vector<int> c(m);reads(all(c));std::priority_queue<int> rec;int bag = 0;int happ = 0;for(auto v: c){if(bag < v && !rec.empty() && rec.top() > v){// regretbag += rec.top();rec.pop();bag -= v;rec.push(v);}else if(bag >= v){happ++;rec.push(v);bag-=v;}bag += x;}std::cout << happ;}