ABC309(A-F)

Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder

G的 容斥 + dp 不会捏，鸽了...

A - Nine

有一个 \(3 \times 3\) 的网格：\(\begin{matrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{matrix}\) ，给你两个数，判断这两个数是否同一行且相邻。

求出行列即可...

#include <iostream>

using namespace std;

int main()
{
    int a, b, ra, rb, ca, cb;
    cin >> a >> b;
    a--, b--;
    ra = a / 3, rb = b / 3;
    ca = a % 3, cb = b % 3;
    if(ra == rb && abs(ca-cb) <= 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

---

B - Rotate

给你一个 \(N \times N\) 的矩阵，将矩阵四周的元素顺时针转动一步，输出转动后的矩阵。

直接模拟即可

#include <iostream>

using namespace std;

const int maxn = 110;
int n;
char g[maxn][maxn];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> g[i];
    int t = g[0][n-1];
    for(int j = n-1; j; j--)
        g[0][j] = g[0][j-1];
    for(int i = 0; i < n-1; i++)
        g[i][0] = g[i+1][0];
    for(int j = 0; j < n-1; j++)
        g[n-1][j] = g[n-1][j+1];
    for(int i = n; i; i--)
        g[i][n-1] = g[i-1][n-1];
    g[1][n-1] = t;
    for(int i = 0; i < n; i++)
        cout << g[i] << endl;
    return 0;
}

---

C - Medicine

有 \(N\) 种药，每一种药有两个属性 \(a_i\) 和 \(b_i\) ，表示从第 \(1\) 天到第 \(a_i\) 天都需要服用 \(b_i\) 片这种药。问，从哪一天开始，每天服用药的数量小于等于 \(K\) ？

先求出 \(sum = \sum a_i\) 然后按照 \(a_i\) 排序。从小到大扫一遍，同一天结束的药就同时减掉，直到 \(sum ≤ K\)，输出答案。

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

using namespace std;

typedef long long LL;
const int maxn = 3E5 + 10;
LL sum, ans, k, n;
struct Node
{
    LL a, b;
    bool operator < (const Node &y) const
    {return a < y.a;}
}m[maxn];

int main()
{
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        scanf("%lld %lld", &m[i].a, &m[i].b), sum += m[i].b;
    sort(m, m+n);
    int i = 0;
    while(i < n && sum > k)
    {
        ans = m[i].a;
        while(i < n && m[i].a == ans)
            sum -= m[i++].b;
    }
    cout << ans + 1 << endl;
    return 0;
}

---

D - Add One Edge

有一个 \(N_1 + N_2\) 个点，\(M\) 条边的无向图，这个图有如下特点：

• 该图由子图 \(A\) 和 子图 \(B\) 组成，子图 \(A\) 中点的编号为 \(1 ≤ u ≤ N_1\)， 子图 \(B\) 中点的编号为 \(N_1 + 1 ≤ v ≤ N_1 + N_2\)
• 子图 \(A\) 是一个联通图，子图 \(B\) 也是一个联通图。
• 子图 \(A\) 与子图 \(B\) 不连通

现在，请你在子图 \(A\) 中选择一个点 \(u\) ，在子图 \(B\) 中选择一个点 \(v\) ，然后添加一条边 \((u, v)\) ，使得点 \(1\) 到 点 \(N_1 + N_2\) 之间的距离最大化。

对点 \(1\) bfs一次，然后对点 \(N_1 + N2\) bfs 一次， \(d\) 表示距离数组，答案就是 \(max(d_1, d_2, \ ...\ d_{N_1}) + max(d_{N_1 + 1}, d_{N_1+2}, \ ...\ d_{N_1 + N_2}) + 1\)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int maxn = 3E5 + 10;
const int maxm = 6E5 + 10;
const int inf = 0x3f3f3f3f;
int n1, n2, m;
int head[maxn], ne[maxm], edge[maxm], idx = 1, dis[maxn];
void add(int u, int v)
{
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}

void bfs(int s)
{
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        int d = dis[u];
        q.pop();
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            if(dis[v] == inf)
                dis[v] = d + 1, q.push(v);
        }
    }
}

int main()
{
    cin >> n1 >> n2 >> m;
    for(int u, v; m--;)
        scanf("%d %d", &u, &v), add(u, v), add(v, u);
    memset(dis, 0x3f, sizeof dis);
    bfs(1);
    for(int i = 1; i <= n1; i++)
        m = max(m, dis[i]);
    int ans = m + 1;
    bfs(n1+n2);
    m = 0;
    for(int i = n1+1; i <= n1 + n2; i++)
        m = max(m, dis[i]);
    ans += m;
    cout << ans << endl;
    return 0;
}

---

E - Family and Insurance

一个家族有 \(N\) 个人，这个家族的关系可以看作一棵树，根结点是 \(1\) ，对于 \(i ≥ 2\) ，\(i\) 的父亲是 \(p_i\) 。这个家族买了 \(M\) 份保险，每份保险的参数是 \(x_i\) 和 \(y_i\) ，表示 \(x_i\) 给他自己以及他的 \(y_i\) 代后代购买了保险。问：这个家族中有多少人有保险？

假设 \(x_i\) 给他自己以及他的 \(y_i\) 代后代购买了保险，相当于 \(x_i\) 的所有儿子都买了 \(y_i-1\) 保险，开一个数组 \(g\) ，\(g[u]\) 表示 \(u\) 购买的保险的代数，\(-1\) 表示没有购买保险，多个保险冲突时，肯定是保留代数较多的那一份。

读取完数据后，从根结点开始 dfs，如果 \(g[u] ≥ 0\) 则向下传播时可以把 \(g[u]-1\) 传播给儿子结点，只需一遍 dfs 即可，时间复杂度 \(O(N)\)

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 3E5 + 10;
const int inf = 0x3f3f3f3f;
int n, m, ans;
int head[maxn], ne[maxn], edge[maxn], idx = 1, g[maxn];
void add(int u, int v)
{
    edge[idx] = v;
    ne[idx] = head[u];
    head[u] = idx++;
}

void dfs(int u)
{
    if(g[u] == -1)
    {
        for(int i = head[u]; i; i = ne[i])
            dfs(edge[i]);
    }
    else
    {
        ans++;
        for(int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            g[v] = max(g[v], g[u]-1);
            dfs(v);
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(g, -1, sizeof g);
    for(int i = 2, p; i <= n; ++i)
        scanf("%d", &p), add(p, i);
    for(int x, y; m--; )
        scanf("%d %d", &x, &y), g[x] = max(g[x], y);
    dfs(1);
    cout << ans << endl;
    return 0;
}

---

F - Box in Box

有 \(N\) 个长宽高为 \(x_i \times y_i \times z_i\) 的箱子，你可以任意转动箱子，问：是否存在一个箱子严格比另一个箱子大？

显然，每个箱子都要转成 \(x_i ≤ y_i ≤ z_i\) 的形式。

先考虑二维的形式怎么做，等价于，平面内每个点 \((x_i, y_i)\) 满足 \(x_i ≤ y_i\) ，问是否有一个点在另一个点的右上方。

将点按 \(x\) 坐标排序，然后从左往右扫，这样能保证新扫到的点的 \(x\) 坐标一定比之前的大，同时记录之前扫过的 \(y\) 的最小值 \(y_i\)，直接比较最小值就可以保证 \(y\) 坐标也比他大，边扫边更新 \(y_i\) 即可。

但这样还需考虑 \(x\) 坐标相等的问题，也就是说 \(x_i = x_j\) 且 \(y_i < y_j\) 的情况，情况下 \(y_i\) 不能直接用于 \(y_j\) 的比较。但如果排序的时候我们对于相同的 \(x\) 时，按照 \(y\) 的降序来排，那么访问的时候就一定不会有 \(x_i = x_j\) 且 \(y_i < y_j\) 的情况发生了。

二维本质就是维护一个“最右下”的点，三维同理，随着 \(x\) 坐标的增长，我们需要维护一个左下的凸包。凸包实际是点的集合，在凸包中同样的 \(y\) 坐标我们选择 \(z\) 较小的那个点，并且由于是左下的凸包，不存在 \(y_i ≤ y_j\) 且 \(z_i ≤ z_j\) 的情况，因为这样的话选前一个点更优。

扫到某个点 \(j\) 的时候，因为我们先按 \(x\) 排序，所以凸包中的点一定满足 \(x_i < x_j\) ，接下来在凸包中二分出第一个 \(y_i < y_j\) ，根据凸包的性质， \(y_i\) 对应的 \(z_i\) 也是最小的，可以直接比较，如果不满足条件，就用 \(y_j\) 和 \(z_j\) 的值更新凸包即可。用一个 map<int, int> 维护凸包就能实现以上操作，key 对应 \(y\) 的值，value 对应 \(z\) 的值。 同样的，为了防止相同的 \(x\) 的情况，当 \(x\) 相同时按照 \(y\) 的降序来排即可。

需要注意的是更新凸包时，对后续的点也要检查，保证map满足凸包的性质，由于每个点至多被删除一次，每次二分的时间复杂度为 \(O(logn)\) ，总的时间复杂度就是 \(O(nlogn)\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

bool cmp(const vector<int> &x, const vector<int> &y)
{
    if(x[0] != y[0])
        return x[0] < y[0];
    return x[1] > y[1];
}

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(3));
    for(int i = 0; i < n; i++)
    {
        scanf("%d %d %d", &a[i][0], &a[i][1], &a[i][2]);
        sort(a[i].begin(), a[i].end());
    }
    sort(a.begin(), a.end(), cmp);
    bool f = 0;
    map<int, int> h;
    h[0] = 1E9;
    h[1E9+1] = 0;

    for(int i = 0; i < n && !f; i++)
    {
        int y = a[i][1], z = a[i][2];
        auto it = h.lower_bound(y), pre = it;
        pre--;
        if(z > pre -> second)
        {
            f = 1;
            break;
        }
        else if(z == pre -> second)
            continue;
        else if(it -> first != y || it -> second > z)
        {
            h[y] = z;
            pre++;
            it = pre;
            it++;
            while(it -> second >= z)
            {
                pre = it;
                it++;
                h.erase(pre);
            }
        }
    }
    if(f)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

---

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