Codeforces Round 946 (Div. 3) A~G

A.Phone Desktop (枚举)

题意：

小 $A$ 的手机有一个桌面（或称启动器）。桌面可以由多个屏幕组成。每个屏幕表示为大小为 $\times 3$ 的网格，即五行三列。

有 $x$ 个应用程序的图标大小为 $\times 1$ 个单元格；这样的图标只占屏幕的一个单元格。还有 $y$ 个应用程序的图标大小为 $\times 2$ 个单元。；这样的图标在屏幕上占据了 $4$ 个单元格的个方格。每个屏幕的每个单元格最多只能有一个图标。

小 $A$ 希望在最少的屏幕上放置应用程序图标。请帮她找出所需的最少屏幕数。

分析：

我们直接枚举需要放几个屏幕，再判断是否合法即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    int t;
    cin >> t;
    while (t--) {
        LL x, y;
        cin >> x >> y;
        for (int i = 0; i <= 200; i++) {
            if (i * 2LL < y)
                continue;
            LL ans = 7LL * i + (2LL * i - y) * 4LL;
            if (ans >= x) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

B.Symmetric Encoding (模拟)

题意：

给出一个由小写字母组成的字符串 $s$ 。使用以下算法对这个字符串进行编码：

首先，构建一个新的辅助字符串 $r$ ，该字符串由字符串 $s$ 中所有不同的字母组成，按字母顺序书写；
然后进行如下编码：将字符串 $s$ 中的每个字符替换为字符串 $r$ 中的对称字符（字符串 $r$ 中的第一个字符将被最后一个字符替换，第二个字符将被从头开始的第二个字符替换，以此类推）。

例如， $s$ = $co d e f orces$ 字符串的编码过程如下：

字符串 $r$ 得到 $c d e f ors$ ；
第一个字符 $s_1$ = $c$ 被替换为 $s$ ；
第二个字符 $s_2$ = $o$ 被替换为 $e$ ；
第三个字符 $s_3$ = $d$ 被替换为 $r$ ；
…
最后一个字符 $s_{10}$ = $s$ 被替换为 $c$ 。
因此，对字符串 $s$ = $co d e f orces$ 进行编码的结果是字符串 $sero f e d soc$ 。
编写一个程序来执行解码，即从编码结果中还原出原始字符串 $s$ 。

分析：

我们首先对字符串去重，再用 $ma p$ 存储映射关系，按照题意模拟即可。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        string a;
        cin >> a;
        map<char, int> mp;
        vector<char> tmp;
        for (auto t: a) {
            if (!mp[t]) {
                mp[t] = 1, tmp.push_back(t);
            }
        }
        sort(tmp.begin(), tmp.end());
        for (int i = 0; i < tmp.size(); i++) mp[tmp[i]] = i;
        for (auto &t: a) cout << tmp[tmp.size() - mp[t] - 1];
        cout << endl;
    }
    return 0;
}

C. Beautiful Triple Pairs (数学)

题意：

给出由 $n$ 个整数组成的数组 $a$ 。每个 $j$ ( $\le j \le n - 2$ ) 都有一个由 $a_j, a_{j + 1}, a_{j + 2}]$ 组成的三元组。

如果一对三元组 $b$ 和 $c$ 在一个位置上完全不同，即满足以下条件之一，那么它们就是美丽的：

$b_1 \ne c_1$ 和 $b_2 = c_2$ 和 $b_3 = c_3$ ；
$b_1 = c_1$ 和 $b_2 \ne c_2$ 和 $b_3 = c_3$ ；
$b_1 = c_1$ 和 $b_2 = c_2$ 和 $b_3 \ne c_3$ 。

求写成的三元组 $a_j, a_{j + 1}, a_{j + 2}]$ 中优美的三元组对数。

分析：

假设三元组为 $(x, y, z)$ ，当保证 $x$ 不同时， $y, z$ 相同时，结果为 $[?, y, z]$ 的数量减去 $[x, y, z]$ 的数量。另外两种情况类似，所以我们只要用计算出三种情况的数量再减去 $3$ 倍的[x, y, z]$的数量即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        map<array<int, 3>, LL> mp;
        map<array<int, 2>, LL> mp1, mp2, mp3;
        LL ans = 0;
        for (int i = 3; i <= n; i++) {
            ans += mp1[{a[i - 2], a[i - 1]}];
            ans += mp2[{a[i - 2], a[i]}];
            ans += mp3[{a[i - 1], a[i]}];
            ans -= 3ll * mp[{a[i - 2], a[i - 1], a[i]}];
            mp1[{a[i - 2], a[i - 1]}]++;
            mp2[{a[i - 2], a[i]}]++;
            mp3[{a[i - 1], a[i]}]++;
            mp[{a[i - 2], a[i - 1], a[i]}]++;
        }
        cout << ans << endl;
    }
    return 0;
}

D.Ingenuity-2 (思维)

题意：

我们把火星表面想象成一个无限坐标平面。最初，"毅力-2 号 "漫游车和 "智慧-2 号 "直升机位于坐标为 $(0, 0)$ 的点上。现在为它们专门开发了一套指令 $s$ ，由以下类型的 $n$ 指令组成：

$N$ ：向北移动一米（从点 $(x, y)$ 到 $(x, y + 1)$ ）；
$S$ ：向南移动一米（从点 $(x, y)$ 到 $(x, y - 1)$ ）；
$E$ ：向东移动一米（从点 $(x, y)$ 移至点 $(x + 1, y)$ ）；
$W$ ：向西移动一米（从点 $(x, y)$ 移至 $(x - 1, y)$ ）。

每条指令必须由漫游车或直升机执行。此外，漫游车或直升机都必须至少执行一条指令。你的任务是分配指令，使直升机和漫游者在执行所有 $n$ 条指令后，最终到达相同的点，或者确定这是不可能的。

分析：

我们首先考虑不可能的情况：

$n$ 为奇数

$N$ 和 $S$ ， $E$ 和 $W$ 的奇偶性不一致
$n = 2$ ，但两次行动不相同

除掉上述情况，我们可以按照以下顺序执行目标：
将 $N$ 和 $S$ 先分配给直升机，再分配给探测车。 $E$ 和 $W$ 的分配顺序则相反，这样我们可以保证符合题意。

代码：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<char> a(n);
        map<char, int> m;
        for (auto &t: a) {
            cin >> t;
            m[t]++;
        }
        if (n % 2 || m['N'] % 2 != m['S'] % 2 || m['E'] % 2 != m['W'] % 2) {
            cout << "NO" << endl;
            continue;
        }
        if (n == 2 && a[0] != a[1]) {
            cout << "NO" << endl;
            continue;
        }
        vector<char> ans(n);
        for (auto tmp: {'N', 'S', 'E', 'W'}) {
            int flag = 0;
            if (tmp == 'N' || tmp == 'S') flag = 1;
            for (int i = 0; i < n; i++) {
                char it = a[i];
                if (it == tmp) {
                    if (flag) {
                        ans[i] = 'R';
                    } else {
                        ans[i] = 'H';
                    }
                    flag ^= 1;
                }
            }
        }
        for (auto &tmp: ans) cout << tmp;
        cout << endl;
    }
    return 0;
}

E.Money Buys Happiness（动态规划）

题意：

作为一名物理学家，查理喜欢用简单精确的语言来规划自己的生活。

在接下来的 $m$ 个月里，从没有钱开始，查理将努力工作，每月赚取 $x$ 英镑。在第 $i$ 月 $(1\le i \le m)$ 里，将有一次机会，付出 $c_i$ 英镑的代价，获得幸福 $h_i$ 。

不允许借贷。在第 $i$ 月赚到的钱只能在之后的第 $j$ 月（ $j\gt i$ ）花掉。

既然物理学家不会编程，帮查理找出幸福的最大值吧。

分析：

从数据范围可以得知天数和可以得到的所有的幸福值数据范围很小，考虑 $d p$ 。

状态 $i$ 表示第几天，状态 $j$ 表示幸福值。

$dp_{ij}$ 代表 $i$ 天获得 $j$ 点幸福值所剩的最多钱。

每次把这个月剩的钱数和这个月新赚的的钱数加到下一个月。如果当前的钱数可以购买今天的幸福值的时候，购买之后下个月对应的幸福度所剩的钱数和和我当前的钱数+本月的钱数-买本月幸福度所花费的钱取个最大值即可。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;
const LL N = 2e5 + 10;
const LL MIN = -1e18;
LL a[N], b[N];
LL dp[100][N];

void solve() {
    LL m, x;
    cin >> m >> x;
    LL sum = 0;
    for (LL i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        sum += b[i];
    }
    for (LL i = 0; i <= m + 1; i++) {
        for (LL j = 0; j <= sum; j++) {
            dp[i][j] = MIN;
        }
    }
    dp[1][0] = 0;
    for (LL i = 1; i <= m; i++) {
        for (LL j = 0; j <= sum; j++)
            dp[i + 1][j] = dp[i][j] + x;
        for (LL j = 0; j <= sum; j++) {
            if (dp[i][j] >= a[i]) {
                dp[i + 1][j + b[i]] = max(dp[i + 1][j + b[i]], dp[i][j] + x - a[i]);
            }
        }
    }
    for (LL i = sum; i >= 0; i--) {
        if (dp[m + 1][i] >= 0) {
            cout << i << endl;
            return;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

F.Cutting Game（模拟、数据结构）

题意：

爱丽丝和鲍勃又在玩一个游戏。他们有一个大小为 $a\times b$ ( $1\le a,b\le 10^9$ )的网格，网格上有 $n$ 个筹码，每个单元格中最多有一个筹码。位于第 $x$ 行和第 $y$ 列交点的单元格坐标为 $(x, y)$ 。

爱丽丝先下一步棋，然后棋手们轮流下棋。在每一步棋中，棋手可以从剩余网格的开头或末尾切掉几行或几列（但不是全部），并为网格切掉部分的每一个筹码赢得一分。每一步棋都可以用字符"U"、“D”、"L"或"R"以及整数 $k$ 来描述：

如果字符为"U"，那么将剪切剩余的前 $k$ 行；
如果字符为"D"，则将剪切剩余的最后 $k$ 行；
如果字符为"L"，则将剪切剩余的前 $k$ 列；
如果字符为"R"，则将剪切剩余的最后 $k$ 列。

根据网格的初始状态和玩家的移动，确定爱丽丝和鲍勃分别获得的点数。

分析：

以横坐标正序，横坐标倒序，纵坐标正序和纵坐标倒序分别对于所有点建立优先队列。

对于询问，这里以"U"操作为例，首先可以计算出新的矩形上边界，然后就可以在优先队列中得到横坐标在被截取范围内的所有点。然后，只需要判断该点的纵坐标是否在当前未被截去的纵坐标范围内即可。

实现的时候用 $ma p$ 维护每个点是否被取走，实现方式是类似的。因为每个点只会被取到四次，总时间复杂度为
$O (n l o g n)$ 。

代码：

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
map<pair<LL,LL>,LL>mp;
void solve(){
    mp.clear();
    LL u,d,l,r,a,b,n,m;
    cin>>a>>b>>n>>m;
    u=1,d=a,l=1,r=b;
    priority_queue<pair<LL,LL>>q1,q2,q3,q4;
    for(LL i=1;i<=n;++i){
        LL x,y;cin>>x>>y;mp[make_pair(x,y)]=1;
        q1.push(make_pair(x,y));
        q2.push(make_pair(-x,y));
        q3.push(make_pair(y,x));
        q4.push(make_pair(-y,x));
    }
    LL ans[2]={};
    for(LL i=1;i<=m;++i){
        char op;
        LL t;
        cin>>op>>t;
        if(op=='U'){
            u+=t;
            while(!q2.empty()){
                auto U=q2.top();
                if(-U.first>=u)
                    break;
                if(mp[make_pair(-U.first,U.second)]){
                    mp[make_pair(-U.first,U.second)]=0;
                    ++ans[i%2];
                }
                q2.pop();
            }
        }
        if(op=='D'){
            d-=t;
            while(!q1.empty()){
                auto u=q1.top();
                if(u.first<=d)
                    break;
                if(mp[u]){
                    mp[u]=0;
                    ++ans[i%2];
                }
                q1.pop();
            }
        }
        if(op=='L'){
            l+=t;
            while(!q4.empty()){
                auto u=q4.top();
                if(-u.first>=l)
                    break;
                if(mp[make_pair(u.second,-u.first)]){
                    mp[make_pair(u.second,-u.first)]=0;
                    ++ans[i%2];
                }
                q4.pop();
            }
        }
        if(op=='R'){
            r-=t;
            while(!q3.empty()){
                auto u=q3.top();
                if(u.first<=r)
                    break;
                if(mp[make_pair(u.second,u.first)]){
                    mp[make_pair(u.second,u.first)]=0;
                    ++ans[i%2];
                }
                q3.pop();
            }
        }
    }
    cout<<ans[1]<<' '<<ans[0]<<endl;
}

int main(){
    LL t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

G.Money Buys Less Happiness Now（数据结构）

题意：

在这个版本的题目中，每个月只能购买 $h_i=1$ 幸福，但月数却大大增加了。我们进入了量子幸福和时间膨胀的领域。

作为一名物理学家，查理喜欢用简单精确的语言来规划自己的生活。

在接下来的 $m$ 个月里，查理将从没有钱开始，努力工作，每月赚取 $x$ 英镑。在第 $i$ 个月 $(1\le i \le m)$ 里，只有一次机会，付出 $c_i$ 英镑的代价来获得一个单位的幸福。每月不能购买超过一个单位。

不允许借贷。在第 $i$ 月赚到的钱只能在之后的第 $j$ 月花掉（ $j\gt i$ ）。

帮查理找出可达到的最大幸福值吧。

分析：

本题用优先队列维护即可，每次如果当前费用足够直接购买，否则查看先前购买的最贵的是不是比当前的还贵，如果是的就不要前面那个，选择当前的幸福感，否则就放弃当前的物品。

代码：

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

void solve() {
    LL n, x, sum = 0;
    cin >> n >> x;
    priority_queue<LL> q;
    for (int i = 1; i <= n; i++, sum += x) {
        LL tmp;
        cin >> tmp;
        if (sum >= tmp) {
            q.push(tmp);
            sum -= tmp;
        } else if (q.size()) {
            LL pre = q.top();
            q.pop();
            if (pre > tmp) {
                sum += pre;
                sum -= tmp;
                q.push(tmp);
            } else
                q.push(pre);
        }
    }
    cout << q.size() << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}