ABC352(A-F)

A - AtCoder Line

题目大意

给你四个整数 \(N, X, Y, Z\) 判断是否有 \(X \le Z \le Y\) 或者 \(Y \le Z \le X\)

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    int n, x, y, z;
    cin >> n >> x >> y >> z;
    if(x > y)
        swap(x, y);
    if(x <= z && z <= y)
        puts("Yes");
    else
        puts("No");
    return 0;
}

---

B - Typing

题目大意

给你两个字符串 \(S\) 和 \(T\)，其中 \(S\) 是 \(T\) 的子序列。问：在 \(T\) 中保留哪些位置的字符可以获得 \(S\) ？

参考代码

C++

#include <iostream>

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    int n = s.size();
    for(int i = 0, j = 0; i < n; j++)
    {
        if(s[i] == t[j])
        {
            cout << j + 1 << ' ';
            i++;
        }
    }
    return 0;
}

---

C - Standing On The Shoulders

题目大意

有 \(N(2 \le N \le 2 \times 10^5)\) 个巨人，在平地上，第 \(i\) 个巨人的肩膀的高度是 \(A_i\)，头的高度是 \(B_i(A_i \le B_i)\)。一个巨人可以站在另一个巨人的肩膀上，例如，巨人 \(x\) 站在巨人 \(y\) 的肩膀上，假设此时巨人 \(y\) 肩膀离地的高度是 \(H\)，则当巨人 \(x\) 站在巨人 \(y\) 的肩膀上之后，巨人 \(x\) 的肩膀的离地高度变为 \(A_x + H\)，头的离地高度变为 \(B_x + H\)。

这 \(N\) 个巨人想要一个接一个的站成直线，同时最大化最上面的巨人的头的高度，输出这个最大值。

解题思路

设站在最上面的巨人编号为 \(x\)，则此时答案为 \(\sum\limits_{i = 1} ^ N A_i - A_x + B_x\)，而 \(\sum\limits_{i = 1} ^ N A_i\) 是定值，因此找出 \(B_x - A_x\) 的最大值即可。

参考代码

C++

#include <iostream>

using namespace std;

typedef long long LL;

int main()
{
    int n;
    LL sum = 0, a, b, M = -2E9;
    cin >> n;
    while(n--)
    {
        cin >> a >> b;
        sum += a;
        M = max(M, b-a);
    }
    cout << sum + M << endl;
    return 0;
}

---

D - Permutation Subsequence

题目大意

给你一个 \(1\) 到 \(N(1 \le N \le 2 \times 10^5)\) 的排列 \(P = (P_1, P_2, \cdots, P_N)\)，同时给你一个整数 \(K(1 \le K \le N)\)，在 排列 \(P\) 中找出一个最短的区间，使得这个区间中包含 \(K\) 个连续的整数。

解题思路

记录每个数字的位置，然后采用类似滑动窗口的思路，从数字 \(1\) 到 \(K\) 开始，将数字的坐标存到 set 中，计算时取出 set 中的最小值和最大值。

参考代码

C++

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main()
{
    int n, k, x;
    cin >> n >> k;
    vector<int> p(n+1);
    for(int i = 1; i <= n; i++)
    {
        cin >> x;
        p[x] = i;
    }
    set<int> ps;
    for(int i = 1; i < k; i++)
        ps.insert(p[i]);
    int ans = n;
    for(int i = k; i <= n; i++)
    {
        ps.insert(p[i]);
        ans = min(ans, *ps.rbegin() - *ps.begin());
        ps.erase(p[i+1-k]);
    }
    cout << ans << endl;
    return 0;
}

---

E - Clique Connect

题目大意

给你一个无向图，图中有 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个点，初始时，图中没有边。

接下来，你需要执行 \(M(1 \le M \le 2 \times 10^5)\) 轮加边的操作，每一轮操作给你两个整数 \(K_i\) 和 \(C_i\) 以及一个点的集合 \(S_i = \{A_{i, 1}, A_{i, 2}, \cdots, A_{i, K_i}\}\)，你需要给集合 \(S_i\) 中的任意两点都添加一条权值为 \(C_i\) 的边。

完成 \(M\) 轮加边操作之后，求出这个图的最小生成树。

解题思路

参考克鲁斯卡尔算法的思路，将 \(M\) 轮操作的 \(C_i\) 进行排序，然后遍历每一轮加边操作，加边前对集合筛一遍，留下不在一个联通块的点，对这些点加边即可。

参考代码

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int p[maxn];

int find(int x)
{return x == p[x] ? x : p[x] = find(p[x]);}
bool same(int u, int v)
{return find(u) == find(v);}
void merge(int u, int v)
{u = find(u), v = find(v), p[u] = v;}

struct EdgeSet 
{
    int k, c;
    vector<int> v;
    bool operator < (const EdgeSet &y) const
    {return c < y.c;}
};

int main()
{
    int n, m;
    cin >> n >> m;
    vector<EdgeSet> es(m);
    for(int i = 0; i < m; i++)
    {
        cin >> es[i].k >> es[i].c;
        es[i].v.resize(es[i].k);
        for(auto &&u : es[i].v)
            cin >> u;
    }
    sort(es.begin(), es.end());
    for(int i = 1; i <= n; i++)
        p[i] = i;
    int cnt = n;
    LL ans = 0;
    for(int i = 0; i < m && cnt > 1; i++)
    {
        vector<int> a;
        for(auto u : es[i].v)
            a.push_back(find(u));
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
        int k = a.size();
        cnt -= k - 1;
        ans += (LL)(k-1) * es[i].c;
        for(int i = 1; i < k; i++)
            merge(a[0], a[i]);
    }
    if(cnt > 1)
        ans = -1;
    cout << ans << endl;
    return 0;
}

---

F - Estimate Order

题目大意

有一个 \(1\) 到 \(N(2 \le N \le 16)\) 的排列 \(P = (P_1, P_2, \cdots, P_N)\) ，但你并不知道这个排列是什么。给你 \(M(0 \le M \le \frac{N(N-1)}{2})\) 个提示，每一个提示包括三个数字 \(a_i, b_i, c_i\) ，表示 \(P_{a_i} - P_{b_i} = c_i\)。

问：排列中哪些位置的数字是唯一确定的？哪些位置是不确定的？不确定的位置输出 -1 。

解题思路

\(N\) 的范围只有 \(16\)，搜索加上一些剪枝肯定是能卡过去。但是我一直在思考如何优雅的搜索，导致我想了很久很久。。。最后终于想出了 \(\text{1ms}\) 的解法。

首先需要推几个性质：

• 性质 1：将每个位置当成点，每当有 \(a_i, b_i, c_i\)，就连一条 \((a_i, b_i, -c_i)\) 以及 \((b_i, a_i, c_i)\) 的边 。则最终图会被分割成若干个连通块。

  这个性质是显然的。

• 性质 2: 任意一个连通块中，只要有一个点（即某个位置）的数字确定，则同一个连通块中其他的点（即其他有关的位置）都确定。

  这个性质也是显然的。

• 性质 3: 同一个连通块中的任意两点关于小于号 \(<\) 是一种偏序关系（通俗来讲就是连通块中随便两个点进行比较都有大小关系）。

  因为这是一个排列，所以任意两点的数字一定不同，所以这个性质也是显然的。

性质 3 有什么用呢？这个性质表明，同一个连通块中的数字是有固定的相对大小的。举个例子，假设连通块中第二小的数字比最小的数字大 \(3\)，第三小的数字比第二小的数字大 \(2\)，则当最小的数字取 \(1\) 时，整个连通块的取值就是 \(\{1, 4, 6\}\)，那么下一个可能的取值就是 \(\{2, 5, 7\}\)。

为了利用这个性质，需要处理出同一个连通块中的偏序关系，可以用类似 \(\text{Floyed}\) 算法的实现。处理完成后我们得到了每个连通块中类似 \(\{1, 4, 6\}\) 这样的集合，用位运算来表示，计算下一个取值只需要右移一位。

下面考虑枚举每个连通块可能的取值。首先需要优化枚举的顺序，显然，应该优先枚举更大的连通块。dfs 枚举的实现就是常规的位运算，具体参考代码。

接下来考虑大小为 \(1\) 的连通块（下面称之为孤立点），即没有任何提示关联的位置。这里仍然有一些性质。

• 性质 4：如果孤立点的个数大于 \(1\) 个，则所有的孤立点的取值都是不确定的。

  一个不太严谨的证明：设当前有 \(x\) 个孤立点，即使所有非孤立点都只有唯一的取值，仍然剩下 \(x\) 个数字是不确定的，这些数字每一个孤立点都可以取得，因此当 \(x > 1\) 时，这些孤立点的取值也不唯一。

• 性质 5：如果孤立点的个数只有 \(1\) 个，则这个孤立点的取值有可能是唯一确定的。

  参考样例 1 即可。

因此我们在枚举的时候，跳过所有的孤立点，同时统计孤立点的数量，对于一个合法的方案，将其记录到每个点可能的取值当中（用 set 存储）。

dfs 结束后，遍历所有的点，如果 set 中只有一个值，则里面的值就是唯一确定的值。

时间复杂度分析：由于跳过了所有的孤立点，所以最坏情况应该是没有孤立点，且每个连通块的大小都为 \(2\) 情形，此时相当于两个点绑一起，复杂度就是 \((\frac{N}{2})!\)

最终献上实现起来简单粗暴但运行起来仅需 1ms 的代码。

参考代码

C++

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

using namespace std;

const int maxn = 20;
int n, m;
int b[maxn][maxn];
void build()
{
    for (int k = 0; k < n; k++)
        for  (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (b[i][k] && b[k][j])
                    b[i][j] = b[i][k] + b[k][j];
}

int p[maxn], col[maxn], ncol = 0;
int find(int x)
{
    return x == p[x] ? x : p[x] = find(p[x]);
}
bool same(int u, int v)
{
    return find(u) == find(v);
}
void merge(int u, int v)
{
    u = find(u), v = find(v), p[u] = v;
}

map<int, vector<int>> group;
struct CG
{
    vector<int> v;
    int bit, comb;
    CG(const vector<int> &_v) : v(_v)
    {
        sort(v.begin(), v.end(), [](int i, int j) -> bool {return b[i][j] > 0;});
        bit = 1;
        for(int i = 1, n = v.size(); i < n; i++)
            bit |= 1 << b[v[0]][v[i]];
        comb = bit;
    }
    bool operator<(const CG &y) const
    {
        return v.size() > y.v.size();
    }
};

vector<CG> cg;
set<int> ans[maxn];
int last = -1;

void dfs(int cur, int can_used)
{
    if(cur == (int)cg.size())
    {
        for(auto &c : cg)
        {
            int j = 0;
            for(int i = 0; i < n; i++)
                if(c.comb >> i & 1)
                {
                    int id = c.v[j++];
                    ans[id].insert(i+1);
                }
        }
        if(last >= 0)
        {
            for(int i = 0; i < n; i++)
                if(can_used >> i & 1)
                    ans[last].insert(i+1);
        }
        return;
    }
    for(cg[cur].comb = cg[cur].bit; cg[cur].comb < 1 << n; cg[cur].comb <<= 1)
    {
        if((cg[cur].comb & can_used) != cg[cur].comb)
            continue;
        dfs(cur+1, can_used ^ cg[cur].comb);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        p[i] = i;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        b[u][v] = -w;
        b[v][u] = w;
        merge(u, v);
    }
    build();
    for (int i = 0; i < n; i++)
        group[find(i)].push_back(i);
    for (auto &[k, v] : group)
    {
        if(v.size() > 1)
            cg.push_back(CG(v));
        else if(last == -1)
            last = k;
        else
            last = -2;
    }
    sort(cg.begin(), cg.end());
    dfs(0, (1 << n) - 1);
    for(int i = 0; i < n; i++)
        cout << (ans[i].size() == 1 ? *ans[i].begin() : -1) <<  ' ';
    return 0;
}

---

---

最后更新: 2024-07-26
创建日期: 2024-05-15