跳转至

ABC373(A-G)

A - September

题目大意

给你 \(12\) 个字符串 \(S_1, S_2, \cdots, S_{12}\)，求有多少个字符串 \(S_i\) 满足 \(|S_i| = i\)

参考代码 
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    int ans = 0;
    for (int i = 1; i <= 12; i++)
    {
        cin >> s;
        ans += (int)s.size() == i;
    }
    cout << ans << endl;
    return 0;
}

B - 1D Keyboard

题目大意

有 \(26\) 个方格从左到右排成一行，方格的内容是字母 A 到 Z 的一个排列。你将从字母 A 开始依次访问 B，C ... 直到 Z，在访问时移动到相邻方格视为走了 \(1\) 步。问：访问到 Z 时走了多少步？

参考代码 
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string s;
    cin >> s;
    vector<int> pos(26);
    for(int i = 0; i < 26; i++)
        pos[s[i]-'A'] = i;
    int sum = 0;
    for(int i = 1; i < 26; i++)
        sum += abs(pos[i] - pos[i-1]);
    cout << sum;        
    return 0;
}

C - Max Ai+Bj

题目大意

给你两个长度均为 \(N\) 的数组 \(A\) 和数组 \(B\)，求出 \(\max\limits_{i \in [1, N], j\in[1, N]}A_i + B_j\)

参考代码 
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    cout << *max_element(a.begin(), a.end()) + *max_element(b.begin(), b.end()) << endl;
    return 0;
}

D - Hidden Weights

题目大意

给你一个 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个点 \(M(1 \le M \le 2 \times 10 ^ 5)\) 条边的有向图。对于每条边 \((u_i, v_i, w_i)\) ，\(w_i\) 的范围在 \([-10^9, 10^9]\) 之间。你需要给每个点都赋一个值 \(x_i\)，\(x_i\) 需要满足以下条件:

  • \(|x_i| \le 10^{18}\)
  • 对于每条边 \((u_i, v_i, w_i)\)，都需要满足 \(x_{v_i} - x_{u_i} = w_i\)

保证答案一定存在。输出任意一种方案即可。

解题思路

一开始想到为了尽可能节省值域空间，应该首先将所有的负边反向，然后构造出一个 DAG 拓扑排序。

但是由于 \(|x_i| \le 10^{18}\)，而每条边的范围只有 \(10^9\)，实际不需要这样，在每个连通分量中从任意一个点开始搜索就可以了。

参考代码 
#include <iostream>

using namespace std;

using LL = long long;
const int MAXN = 2E5 + 10;
const int MAXM = 2 * MAXN;
int head[MAXN], edge[MAXM], ne[MAXM], idx = 1;
LL cost[MAXM], val[MAXN];
bool vis[MAXN];

void Add(int u, int v, LL w)
{
    edge[idx] = v;
    ne[idx] = head[u];
    cost[idx] = w;
    head[u] = idx++;
}

void dfs(int u, LL k)
{
    vis[u] = true;
    val[u] = k;
    for (int i = head[u]; i; i = ne[i])
    {
        int v = edge[i], w = cost[i];
        if (!vis[v])
            dfs(v, k + w);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Add(u, v, w);
        Add(v, u, -w);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, 0);
    for (int i = 1; i <= n; i++)
        cout << val[i] << ' ';
    return 0;
}

E - How to Win the Election

题目大意

有 \(N(1 \le N \le 2 \times 10 ^ 5)\) 个候选人正在竞选议员，一共有 \(K(1 \le K \le 10 ^ {12})\) 选票。目前，第 \(i\) 个候选人已经收到了 \(A_i\) 张选票。还剩下 \(K - \sum\limits_{i = 1}^N\) 张选票没有投出。

这场选举将选出至少 \(M(1 \le M \le N)\) 个议员。投票结束时，将所有候选人的票数从大到小排序，前 \(M\) 个候选人当选，如果有多个候选人票数一样，则相同票数的候选人也能当选。

问：对于每个候选人 \(i\)，至少还需要获得多少票才能保证一定当选？每个候选人输出一个答案，如果候选人即使获得剩下的所有票也不能当选，输出 -1。

解题思路

显然是一个二分。首先将所有的 \(A_i\) 排序，对于每个候选人，在 \([0, K - \sum\limits_{i = 1}^N+1]\) 之间枚举出一个值 \(mid\)，接下来考虑怎么检验。

将 \(A_i + mid\) 放到原数组中比较，获得当前的位次（即有多少人的选票大于 \(A_i + mid\)），对于这部分，剩下的选票不应该分配给他们，因为这些人已经比 \(A_i + mid\) 大了。假设有 \(X\) 个人比 \(A_i + mid\) 大。

对于小于等于 \(A_i + mid\) 的人，求出剩下的 \(M-X\) 个人，看看剩下的票数能不能将这 \(M-X\) 个人补到 \(A_i + mid + 1\) 票，如果可以，则 \(A_i + mid\) 还不够安全。

大于 \(A_i + mid\) 的部分可以二分找出来，而小于等于 \(A_i + mid\) 的部分手动加的话时间复杂度仍然是线性的。因此在排序之后，预处理出一个前缀和，就能 \(O(1)\) 求解出来了。

实现的时候注意两个点:

  • 注意把 \(A_i\)（也就是在增加 \(mid\) 之前的值）从 \(M-X\) 个人中排除。
  • 特判一下 \(M = N\) 的情况（所有人都能当选，输出 0）
参考代码 
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

struct Candidate
{
    int id;
    LL a;
    bool operator>(const Candidate &other) const { return a > other.a; }
};

int main()
{
    int n, m;
    LL k;
    cin >> n >> m >> k;
    vector<Candidate> c(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i].a;
        c[i].id = i;
        k -= c[i].a;
    }
    if (m == n)
    {
        for (int i = 1; i <= n; i++)
            cout << 0 << ' ';
        return 0;
    }
    sort(c.begin() + 1, c.end(), greater<Candidate>());
    vector<LL> s(n + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + c[i].a;
    vector<LL> ans(n + 1);
    for (int i = 1; i <= n; i++)
    {
        LL l = 0, r = k + 1;
        while (l < r)
        {
            LL mid = (l + r) / 2;
            Candidate after{i, c[i].a + mid};
            int rk = lower_bound(c.begin() + 1, c.end(), after, greater<Candidate>()) - c.begin();
            if (rk - 1 >= m)
                l = mid + 1;
            else
            {
                LL right_cnt = m - rk + 1;
                LL right_sum = s[m] - s[rk - 1];
                if(i <= m)
                    right_sum += c[m+1].a - c[i].a;
                if(right_cnt * (c[i].a + mid + 1) - right_sum <= k - mid)
                    l = mid + 1;
                else
                    r = mid;
            }
        }
        ans[c[i].id] = l == k + 1 ? -1 : l;
    }
    for(int i = 1; i <= n; i++)
        cout << ans[i] << ' ';
    return 0;
}

F - Knapsack with Diminishing Values

题目大意

有 \(N(1 \le N \le 3000)\) 种物品，第 \(i\) 种物品的价值是 \(v_i\)，重量是 \(w_i\)，每种物品都有无限个。

你拥有一个可容纳 \(W(1 \le W \le 3000)\) 重量的背包。你可以拿取任意物品装进背包，同种物品拿太多个会降低价值，具体来说，假设你拿了 \(k_i\) 个第 \(i\) 种物品，则这 \(k_i\) 个物品共同的价值为 \(k_i * v_i - k_i^2\)。

问：最多能获得多少价值？

解题思路

常规的背包思路是做不出来的。这里参考了官方题解的思路。

考虑将所有重量相同的物品分到一组。接下来，对于每一个分组，我们预处理出一个数组 \(f\)，其中 \(f[j]\) 表示凑出重量为 \(j\) 的组合能获得的最大价值。由于同组重量相同，假设重量为 \(w\)，对于每个分组，实际上只有 \(f[w], f[2w], f[3w], \cdots\) 这些值是有意义的，其他地方都等于 \(0\)。

考虑如何构造出 \(f[w], f[2w], f[3w], \cdots\)，这实际上可以维护一个优先队列，队列中维护每种物品多拿 \(1\) 个产生的收益。

预处理出所有的分组，然后只需要按照分组进行常规的背包过程即可。

参考代码 
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
using LL = long long;

struct Node
{
    LL v, k, benefit;

    Node(LL v) : v(v), k(1), benefit(v-1) {}

    bool operator<(const Node &other) const { return benefit < other.benefit; }

    void add()
    {
        k++;
        benefit = v  - k * k + (k-1) * (k-1);
    }

    bool valid() const { return benefit > 0; }
};
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<LL>> group(m + 1);
    vector<LL> dp(m + 1);
    for (int i = 0; i < n; i++)
    {
        LL w, v;
        cin >> w >> v;
        if (v > 1)
            group[w].emplace_back(v);
    }
    for (int w = 1; w <= m; w++)
    {
        if (group[w].empty())
            continue;
        priority_queue<Node> heap;
        for (auto v : group[w])
            heap.push({v});
        vector<LL> vk{0};
        for (int j = 1; j * w <= m && !heap.empty(); j++)
        {
            Node p = heap.top();
            heap.pop();
            vk.emplace_back(vk[j - 1] + p.benefit);
            p.add();
            if (p.valid())
                heap.push(p);
        }
        int len = vk.size();
        if (len == 1)
            continue;
        for (int j = m; j >= w; j--)
            for (int k = 1; k < len && j >=  k * w; k++)
                dp[j] = max(dp[j], dp[j-k*w] + vk[k]);                
    }
    cout << dp[m];
    return 0;
}

G - No Cross Matching

题目大意

在平面上有 \(2N(1 \le N \le 300)\) 个点 \(P_1, P_2, \cdots, P_N, Q_1, Q_2, \cdots, Q_N\)，其中任意三个点都不共线。你需要构造一种匹配方案，让每个点 \(P_i\) 匹配一个点 \(Q_j\)，每个点 \(P_i\) 和 \(Q_j\) 都只能被匹配一次，每一对匹配的点连接一条线，你的匹配方案需要保证任意两条连线不相交。

输出匹配方案，题目保证存在这样的方案。

解题思路

一道非常巧妙地题。我们假设有连线 \((P_a, Q_x)\) 和 \((P_b, Q_y)\) 已经相交，此时如果我们交换成 \((P_a, Q_y)\) 和 \((P_b, Q_x)\)，此时这两条线是一定不相交的（很显然的几何性质）。

接下来巧妙的来了，交换之后连线的距离之和也会变小（同样非常显然），而一定存在一种方案能使得所有连线的距离之和最小，所以我们需要构造的是让所有连线的距离之和最小的方案，这就是在二分图上求一个最大（小）权匹配，跑费用流即可。

参考代码 
#include <cmath>
#include <cstring>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>

using namespace std;

const int MAXU = 310;
const int MAXN = 2 * MAXU;
const int MAXM = MAXU * MAXU * 2;
const int INF = 0x3f3f3f3f;

int head[MAXN], edge[MAXM], ne[MAXM], cap[MAXM], idx = 2;

double cost[MAXM];

void add(int u, int v, int c, double w)
{
    edge[idx] = v;
    ne[idx] = head[u];
    cap[idx] = c;
    cost[idx] = w;
    head[u] = idx++;
}
void add_edge(int u, int v, int c, double w)
{
    add(u, v, c, w);
    add(v, u, 0, -w);
}

int n, m, s, t;
int pre[MAXN];
double h[MAXN], dis[MAXN];
bool vis[MAXN];

void spfa()
{
    queue<int> q;
    for (int i = 0; i < 2 * n + 2; i++)
        h[i] = numeric_limits<double>::max();
    h[s] = 0;
    q.push(s);
    vis[s] = true;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for (int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            double w = cost[i];
            if (cap[i] && h[u] + w < h[v])
            {
                h[v] = h[u] + w;
                if (!vis[v])
                {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

struct Node
{
    int u;
    double dis;
    bool operator>(const Node &other) const { return dis > other.dis; }
};

bool dijkstra()
{
    for (int u = 0; u < 2 * n + 2; u++)
        dis[u] = numeric_limits<double>::max();
    memset(vis, 0, sizeof vis);
    priority_queue<Node, vector<Node>, greater<Node>> heap;
    heap.push({s, 0});
    dis[s] = 0;
    while (!heap.empty())
    {
        int u = heap.top().u;
        heap.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            double w = cost[i] + h[u] - h[v];
            if (cap[i] && dis[u] + w < dis[v])
            {
                dis[v] = dis[u] + w;
                pre[v] = i;
                heap.push({v, dis[v]});
            }
        }
    }
    return vis[t];
};

pair<int, double> mcmf()
{
    spfa();
    int min_cost = 0, max_flow = 0;
    while (dijkstra())
    {
        for (int u = 0; u < 2 * n + 2; u++)
            h[u] += dis[u];
        int flow = INF;
        for (int v = t, i = pre[t]; v != s; v = edge[i ^ 1], i = pre[v])
            flow = min(flow, cap[i]);
        for (int v = t, i = pre[t]; v != s; v = edge[i ^ 1], i = pre[v])
        {
            cap[i] -= flow;
            cap[i ^ 1] += flow;
        }
        max_flow += flow;
        min_cost += flow * h[t];
    }
    return {min_cost, max_flow};
}

int main()
{
    cin >> n;
    s = 0, t = 2 * n + 1;
    vector<int> x(2 * n + 1), y(2 * n + 1);
    for (int u = 1; u <= n; u++)
        cin >> x[u] >> y[u];
    for (int v = n + 1; v <= 2 * n; v++)
        cin >> x[v] >> y[v];
    for (int u = 1; u <= n; u++)
    {
        add_edge(s, u, 1, 0);
        add_edge(n + u, t, 1, 0);
        for (int v = n + 1; v <= 2 * n; v++)
        {
            double dis = sqrt((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]));
            add_edge(u, v, 1, dis);
        }
    }
    mcmf();
    vector<int> ans(n);
    for (int u = 1; u <= n; u++)
        for (int i = head[u]; i; i = ne[i])
        {
            int v = edge[i];
            if (v != s && cap[i] == 0)
            {
                cout << v - n << ' ';
                break;
            }
        }
    return 0;
}
最后更新: 2024-12-16
创建日期: 2024-12-16