ABC308(A-G)

比较简单的一场，只有G题的小结论和边界处理花了一点时间。

A - New Scheme ¶

给你一个长度为 \(8\) 的序列 \(A = (A_1,A_2,...,A_8)\) ，判断序列是否满足以下条件

序列是否单调递增，即是否满足 \(A_1 ≤ A_2 ≤\ ... ≤ A_8\)

序列的每个值是否在 \([100, 675]\) 的范围内。

序列的每个值是否是 \(25\) 的倍数。

如果满足以上条件则输出 Yes，否则输出 No

直接模拟

#include <iostream>

using namespace std;

int main()
{
    int a[10], pre = 0;
    bool f = 1;
    for(int i = 0; i < 8; i++)
    {
        cin >> a[i];
        if(a[i] < pre || a[i] < 100 || a[i] > 675 || a[i] % 25)
            f = 0;
        pre = a[i];
    }
    if(f)
        puts("Yes");
    else
        puts("No");
    return 0;
}

B - Default Price ¶

你在餐厅点了 \(N\) 个菜，每个菜的名字用字符串 \(C_i\) 表示。菜单中有 \(M\) 种菜，第 \(i\) 种菜的名字是 \(D_i\) ，价格是 \(P_i\) ，有一些菜的名字没有在菜单中，价格是 \(P_0\) ，问：你需要支付多少钱。

哈希表即可

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
    int n, m, p0, x;
    cin >> n >> m;
    vector<string> a(n), b(m);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
        cin >> b[i];
    cin >> p0;
    unordered_map<string, int> p;
    for(int i = 0; i < m; i++)
    {
        cin >> x;
        p[b[i]] = x;
    }
    int sum = 0;
    for(int i = 0; i < n; i++)
    {
        if(p.count(a[i]))
            sum += p[a[i]];
        else
            sum += p0;
    }
    cout << sum << endl;
    return 0;
}

C - Standings ¶

有 \(N\) 个人，每人有 \(A_i\) 和 \(B_i\) 属性，按照每个人的 \(\large \frac{A_i}{A_i+B_i}\) 降序排序，如果 \(\large \frac{A_i}{A_i+B_i}\) 相同则按照编号升序排列，输出排列后的编号。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;

int n;

struct Node {
    int id;
    LL a, s;
    bool operator > (const Node &y) const
    {
        LL m1 = a * y.s, m2 = y.a * s;
        if(m1 != m2)
            return m1 > m2;
        return id < y.id;
    }
}p[maxn];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        p[i].id = i + 1;
        cin >> p[i].a >> p[i].s;
        p[i].s += p[i].a;
    }
    sort(p, p+n, greater<Node>());
    for(int i = 0; i < n; i++)
        cout << p[i].id << ' ';
    return 0;
}

D - Snuke Maze ¶

有一个 \(H \times M\) 的二维地图，地图上每个位置都有一个小写字母。你可以进行 上下左右 的移动，在移动时，需遵循 snuke 的顺序，即：如果你目前的所在字符是 s，下一个字符必须是 n，以此类推（可以循环，即 e 的下一个字符是 s）。

初始时你的位置是 \((1, 1)\) ，问：能不能走到 \((H, M)\) ，如果能则输出 Yes 否则输出 No

直接dfs

#include <iostream>

using namespace std;

const int maxn = 510;
char g[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
char ne[300];

int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

bool inlim(int r, int c)
{return r >= 0 && r < n && c >= 0 && c < m;}

void dfs(int r, int c)
{
    vis[r][c] = 1;
    char nch = ne[g[r][c]];
    for(int i = 0; i < 4 && !vis[n-1][m-1]; i++)
    {
        int nr = r + dr[i], nc = c + dc[i];
        if(!inlim(nr, nc))
            continue;
        if(!vis[nr][nc] && g[nr][nc] == nch)
            dfs(nr, nc);
    }
}

int main()
{
    ne['s'] = 'n';
    ne['n'] = 'u';
    ne['u'] = 'k';
    ne['k'] = 'e';
    ne['e'] = 's';
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> g[i];
    dfs(0, 0);
    if(vis[n-1][m-1])
        puts("Yes");
    else
        puts("No");
    return 0;
}

E - MEX ¶

给你一个长度为 \(N\) 的序列 \(A\) ，\(A\) 中的值是 \(0\) ，\(1\) ，\(2\) ，同时给你一个长度为 \(N\) 的字符串 \(S\) ，\(S\) 中的字符是 \(M\) ，\(E\) ，\(X\)

求出所有满足以下条件的三元组 \(mex(A_i, A_j, A_k)\) 值的和，

\(1 ≤ i < j < k ≤ N\)

\(S_iS_jS_k=\) MEX

\(mex(A_i, A_j, A_k)\) 表示没有出现在 \((A_i, A_j, A_k)\) 中的最小非负整数值。

分0, 1, 2处理一个前缀和记录 M 的数量，M[i][0] 表示前 i 个字符中对应数字是 0 的字符 M 的数量，其余同理，再处理出 X 的后缀和。然后枚举中间的 E ，分情况累加就可以了。

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
int mex[3][3][3], n, a[maxn], M[maxn][3], X[maxn][3];
char s[maxn];

int main()
{
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            for(int k = 0; k < 3; k++)
                for(int x = 0; x <= 3; x++)
                    if(x != i && x != j && x != k)
                    {
                        mex[i][j][k] = x;
                        break;
                    }
    cin >> n;
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    scanf("%s", s+1);
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < 3; j++)
            M[i][j] = M[i-1][j];
        if(s[i] == 'M')
            M[i][a[i]]++;
    }
    for(int i = n; i; i--)
    {
        for(int j = 0; j < 3; j++)
            X[i][j] = X[i+1][j];
        if(s[i] == 'X')
            X[i][a[i]]++;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(s[i] == 'E')
        {
            int y = a[i];
            for(int x = 0; x < 3; x++)
                for(int z = 0; z < 3; z++)
                    ans += (LL)mex[x][y][z] * M[i][x] * X[i][z];
        }
    }
    cout << ans << endl;
    return 0;
}

F - Vouchers ¶

有 \(N\) 个商品，第 \(i\) 个商品的价格是 \(P_i\) 元。有 \(M\) 张优惠券，第 \(i\) 张优惠券是满 \(L_i\) 减 \(D_i\) 元的。每一个商品只能用一张优惠券，每一张优惠券只能用一次，且只能对一个商品使用。问：将这 \(N\) 个商品全部买下，最少需要花多少钱？

贪心，将商品排序，然后将优惠券按照 \(L_i\) 排序，用一个大顶堆按照 \(D\) 的值维护当前可用的优惠券，从小到大扫描商品，每次购买商品时弹出优惠力度最大的优惠券即可，时间复杂度 \(O(NlogN + MlogM)\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;
const int maxn = 2E5 + 10;
int p[maxn], n, m;

struct Node{
    int l, d;
    bool operator < (const Node &y) const
    {return l < y.l;}
}c[maxn];

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        scanf("%d", &p[i]);
    for(int i = 0; i < m; i++)
        scanf("%d", &c[i].l);
    for(int i = 0; i < m; i++)
        scanf("%d", &c[i].d);
    sort(p, p+n);
    sort(c, c+m);
    priority_queue<int> heap;
    LL sum = 0;
    for(int i = 0, j = 0; i < n; i++)
    {
        while(j < n && c[j].l <= p[i])
            heap.push(c[j++].d);
        if(!heap.empty())
        {
            p[i] -= heap.top();
            heap.pop();
        }
        sum += p[i];
    }
    cout << sum << endl;
    return 0;
}

G - Minimum Xor Pair Query ¶

你需要维护一个集合，有三种操作:

1 x ：从集合中添加一个数 x

2 x ：从集合中删除一个数 x

3 ：查询集合中最小的异或点对的值。

结论题：数组中最小的异或点对，一定来自于将数组排序后某一对相邻的数。

证明如下：考虑三个数的情况 \(x ≤ y ≤ z\) ，只需要证明 \(min(x \oplus y, y \oplus z) < x \oplus z\)

假设 \(x\) 和 \(z\) 的最高的不同位是第 \(k\) 位（从右开始算，右边是第 \(0\) 位），由于 \(x ≤ z\) ，因此 \(z\) 的第 \(k\) 位是 \(1\) ，\(x\) 的第 \(k\) 位是 \(0\) ，此时有 \(x \oplus z ≥ 2^{k}\)

对于 \(y\) 的第 \(k+1\) 位开始的位置，\(y\) 的分布情况一定与 \(x\) 和 \(z\) 的情况相同（否则就与 \(x ≤ y ≤ z\) 矛盾）。

考虑 \(y\) 的第 \(k\) 位：

若 \(y\) 的第 \(k\) 位是 \(0\) ，则有 \(x \oplus y < 2^{k}\)
若 \(y\) 的第 \(k\) 位是 \(1\) ，则有 \(y \oplus z < 2^{k}\)

因此无论如何，都有 \(min(x \oplus y, y \oplus z) < x \oplus z\) ，证毕。

维护有序的数组，当然使用 set 实现了，当然本题有重复值，所以要用 multiset，开一个 num 维护数字的集合，然后开一个 val 维护所有相邻的异或值。对于三种操作：

添加 x ：假设添加后 num 中有 pre ≤ x ≤ ne，添加后 (pre, ne) 不再相邻，在 val 中删掉 (pre, ne) 的异或值，同时添加 (pre, x) 和 (x, ne) 的异或值。
删除 x ：假设删除前 num 中有 pre ≤ x ≤ ne，删除后 (pre, x) 和 (x, ne) 不再相邻，删除其异或值，同时添加 (pre, ne) 的异或值。
查询：由于 val 也是 multiset，直接输出 begin 迭代器值。

三种操作的时间复杂度都是 \(O(logN)\)，总的时间复杂度就是 \(O(qlogN)\)

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

multiset<int> num, val;

int main()
{
    int q, op, x;
    multiset<int>::iterator pre, ne;
    cin >> q;
    while(q--)
    {
        scanf("%d", &op);
        if(op == 1)
        {
            scanf("%d", &x);
            pre = ne = num.upper_bound(x);
            bool pf = 0, nf = 0;
            if(ne != num.end())
                val.insert(x ^ *ne), nf = 1;
            if(pre != num.begin())
            {
                pre--;
                val.insert(*pre ^ x);
                pf = 1;
            }
            if(pf && nf)
                val.erase(val.find(*pre ^ *ne));

            num.insert(x);
        }
        else if(op == 2)
        {
            scanf("%d", &x);
            pre = ne = num.find(x);
            bool pf = 0, nf = 0;
            if(pre != num.begin())
            {
                pf = 1;
                pre--;
                val.erase(val.find(*pre ^ x));
            }
            ne++;
            if(ne != num.end())
            {
                val.erase(val.find(x ^ *ne));
                nf = 1;
            }
            if(pf && nf)
                val.insert(*pre ^ *ne);
            num.erase(num.find(x));
        }
        else
            cout << *val.begin() << endl;
    }
    return 0;
}

最后更新: 2023-08-29
创建日期: 2023-08-29

ABC308(A-G)

A - New Scheme¶

B - Default Price¶

C - Standings¶

D - Snuke Maze¶

E - MEX¶

F - Vouchers¶

G - Minimum Xor Pair Query¶