div3-950

DIV3_950

A

Problem Generator_950A

题意：

输入n，m和字符串s，s包含’A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, 和 ‘G’.

要求我们需要添加的最少的字符个数，使得s中的各个字符都至少有m个

Sol:

遍历计数，不够的添加，够了就不加

Code:

void solve()
{
    int n, m;;
    cin>>n>>m;
    string s;
    cin>>s;
    vector<int> vis(7,0);
    for(auto c:s) {
        vis[c-'A']++;
    }
    int ans = 0;
    for(int i = 0; i < 7; i++) {
        //cout << m - vis[i] << " ";
        if(vis[i] >= m) {
            continue;
        } else {
            ans += m - vis[i];
        }
    }
    cout<<ans<<endl;
}

B

Choosing Cubes_950B

题意：

给你一个长度为n的数组，和一个下标f，按从大到小排序，删掉k个值，看f是否会被删掉

Sol：

统计大于下标f的值的个数count1和大于等于下标f的值的个数count2，如果count1>=k，那么f就一定不会被删除。如果count1<k&&count2<k，那么f就可能被删除。否则，f一定会被删除。

Code:

void solve()
{
    int n, f, k;
    cin>>n>>f>>k;
    vi a(n);   
    for(int i=0; i<n; i++) cin>>a[i];
    int fav = a[f-1];
    int cnt1 = 0,cnt2 = 0;
    for(auto num:a) {
        if(num > fav) cnt1++;
        if(num >= fav) cnt2++;
    }
    //cout << cnt1 << " " << cnt2 << endl;
    if(cnt2 <= k) {
        cout << "YES" <<endl;
    } else if (cnt1 < k && cnt2 > k) {
        cout << "MAYBE" << endl;
    } else {
        cout << "NO" << endl;
    }
}

C

Sofia and the Lost Operations_950C

题意解释：

Sofia有一个包含𝑛个整数的数组𝑎1,𝑎2,…,𝑎𝑛。她对它感到厌倦，于是决定对它进行𝑚个修改操作。
每个修改操作由一对数字⟨𝑐𝑗,𝑑𝑗⟩描述，意味着数组中索引为𝑐𝑗的元素应赋值为𝑑𝑗，即执行赋值𝑎𝑐𝑗=𝑑𝑗。在依次应用所有修改操作后，Sofia丢弃了得到的数组。
最近，你发现了一个包含𝑛个整数的数组𝑏1,𝑏2,…,𝑏𝑛。你想知道这个数组是否是Sofia的数组。你知道原始数组的值，以及值𝑑1,𝑑2,…,𝑑𝑚。值𝑐1,𝑐2,…,𝑐𝑚被遗失了。
是否存在一个序列𝑐1,𝑐2,…,𝑐𝑚，使得将修改操作⟨𝑐1,𝑑1,⟩,⟨𝑐2,𝑑2,⟩,…,⟨𝑐𝑚,𝑑𝑚⟩依次应用到数组𝑎1,𝑎2,…,𝑎𝑛能将其转换为数组𝑏1,𝑏2,…,𝑏𝑛？

输入
第一行包含一个整数𝑡（1≤𝑡≤104）——测试用例的数量。
然后是每个测试用例的描述。
每个测试用例的第一行包含一个整数𝑛（1≤𝑛≤2⋅105）——数组的大小。
每个测试用例的第二行包含𝑛个整数𝑎1,𝑎2,…,𝑎𝑛（1≤𝑎𝑖≤109）——原始数组的元素。
每个测试用例的第三行包含𝑛个整数𝑏1,𝑏2,…,𝑏𝑛（1≤𝑏𝑖≤109）——找到的数组的元素。
第四行包含一个整数𝑚（1≤𝑚≤2⋅105）——修改操作的数量。
第五行包含𝑚个整数𝑑1,𝑑2,…,𝑑𝑚（1≤𝑑𝑗≤109）——每个修改操作的保留值。
保证所有测试用例中𝑛的值之和不超过2⋅105，同样保证所有测试用例中𝑚的值之和不超过2⋅105。

输出
输出𝑡行，每行是对应测试用例的答案。作为答案，如果存在合适的序列𝑐1,𝑐2,…,𝑐𝑚，则输出“YES”，否则输出“NO”。
你可以以任何形式输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案）。

示例
输入
7
3
1 2 1
1 3 2
4
1 3 1 2
4
1 2 3 5
2 1 3 5
2
2 3
5
7 6 1 10 10
3 6 1 11 11
3
4 3 11
4
3 1 7 8
2 2 7 10
5
10 3 2 2 1
5
5 7 1 7 9
4 10 1 2 9
8
1 1 9 8 7 2 10 4
4
1000000000 203 203 203
203 1000000000 203 1000000000
2
203 1000000000
1
1
1
5
1 3 4 5 1
输出
YES
NO
NO
NO
YES
NO
YES

Sol:

遍历原始数组和找到的数组，如果对应位置的元素不相等，则在mp1中记录找到的数组元素出现的次数，并增加计数器cnt。

遍历修改操作的保留值数组d，如果在mp1中找到对应的值，则减少对应值的出现次数，并减少计数器cnt。

如果计数器cnt为0，并且修改操作的保留值数组d的最后一个值在mp2中出现，则输出“YES”，否则输出“NO”。

Code:

void solve()
{
    int n,k,l;
    cin>>n>>k>>l;
    vi a(n*k);
    for(int i = 0;i < n*k;i++) cin>>a[i];
    sort(a);
    int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin());
    if (rg < n) {
        cout << "0" << endl;
        return;
    }
    int u = 0;
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += a[u++];
        for(int j = 0;j < k - 1; j++) {
            if (rg - u > n - i - 1) {
                u++;
            } else {
                break;
            }
        }
    }
    cout << ans << endl;
}

D

GCD-sequence_950D

题意：

判断是否可以从数组𝑎中移除一个数字，使得计算得到的GCD序列𝑏是非递减的。也就是说，𝑏𝑖≤𝑏𝑖+1始终成立。

Sol:

计算数组a中相邻两个数的最大公约数，将结果存入数组b中。
判断数组b是否是非递减序列，如果是则输出”YES”，否则进行下一步。
遍历数组a，尝试移除其中的一个数字，然后重新计算GCD序列，判断是否能得到非递减序列，如果能则输出”YES”，否则输出”NO”。

Code:

void solve()
{
    int n;
    cin>>n;
    vi a(n);
    for(int i = 0; i < n; i++) cin>> a[i];   
    vi b;
    for (int i = 0; i < n - 1; i++) {
        b.push_back(gcd(a[i], a[i + 1]));
    }
    int inv = 0, pos = -1;
    for (int i = 0; i + 1 < b.size(); i++) {
        if (b[i] > b[i + 1]) inv++, pos = i;
    }
    if (inv == 0 || pos == -1) {
        cout<<"YES"<<endl;
        return;
    }
    int good = 0;
    for (int remove_pos = max(0, pos - 3); remove_pos < min(n, pos + 3); ++remove_pos) {
      int rvp = remove_pos;
      auto c = a;
      c.erase(c.begin() + rvp);
      vector<int> bb;
      for (int i = 0; i + 1 < c.size(); ++i) {
        bb.push_back(gcd(c[i], c[i + 1]));
      }
      if (is_sorted(all(bb))) {
        good = 1;
        break;
      }
    }
    cout << (good ? "YES" : "NO") << '\n';
}

E

Permutation of Rows and Columns_950E

题意：

给定t组测试用例。
每个测试用例包括两行，第一行包含两个整数n和m，表示矩阵的大小。
接下来的n行包含m个整数，表示矩阵a的元素。
再接下来的n行包含m个整数，表示矩阵b的元素。
输出对于每个测试用例，如果可以通过交换矩阵a的行或列来得到矩阵b，则输出”YES”，否则输出”NO”。

Sol:

规律：按照每行的最小元素进行排序，然后再定义对应的转置矩阵，同样按照每行的最小元素进行排序，最后比较该矩阵的元素，若存在不相等的情况，则无法转换，否则满足。

Code：

void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int> > a(n, vector<int>(m));
    vector<vector<int> > b(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cin >> a[i][j];
      }
    }
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        cin >> b[i][j];
      }
    }
    int bad = 0;
    sort(all(a), [](const vector<int>& i, const vector<int>& j) {
      return *min_element(all(i)) < *min_element(all(j));
    });
    sort(all(b), [](const vector<int>& i, const vector<int>& j) {
      return *min_element(all(i)) < *min_element(all(j));
    });
    vector<vector<int> > c(m, vector<int>(n));
    vector<vector<int> > d(m, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        c[j][i] = a[i][j];
        d[j][i] = b[i][j];
      }
    }
    sort(all(c), [](const vector<int>& i, const vector<int>& j) {
      return *min_element(all(i)) < *min_element(all(j));
    });
    sort(all(d), [](const vector<int>& i, const vector<int>& j) {
      return *min_element(all(i)) < *min_element(all(j));
    });
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (c[i][j] != d[i][j]) {
          bad = 1;
          break;
        }
      }
    }
    cout << (bad ? "NO" : "YES") << '\n';
}

F1

Field Division_950F1

Alice和Bob正在划分一个田地。田地是一个大小为𝑛×𝑚（2≤𝑛,𝑚≤109）的矩形，行从上到下编号为1到𝑛，列从左到右编号为1到𝑚。位于第𝑟行第𝑐列的单元格表示为(𝑟,𝑐)。

Bob有𝑘（2≤𝑘≤2⋅105）个喷泉，它们都位于田地的不同单元格中。Alice负责划分田地，但她必须满足几个条件：

要划分田地，Alice将从田地的左侧或顶部的任何空闲单元格开始她的路径，并且每次移动都向下或向右相邻的单元格。她的路径将在田地的右侧或底部结束。
Alice的路径将把田地分成两部分——一部分属于Alice（这部分包括她的路径的单元格），另一部分属于Bob。
Alice将拥有包括单元格(𝑛,1)的部分。
Bob将拥有包括单元格(1,𝑚)的部分。

Alice希望以尽可能多的单元格来划分田地。 Bob希望保留所有的喷泉，但他可以把其中一个喷泉给Alice。首先输出整数𝛼——如果Bob不给她任何喷泉（即所有喷泉都将留在Bob的部分），则Alice的地块的最大可能大小。然后输出𝑘个非负整数𝑎1,𝑎2,…,𝑎𝑘，其中：

如果Bob给Alice第𝑖个喷泉后，Alice的地块的最大可能大小不增加（即保持等于𝛼），则𝑎𝑖=0；
如果Bob给Alice第𝑖个喷泉后，Alice的地块的最大可能大小增加（即变大于𝛼），则𝑎𝑖=1。

输入

第一行包含一个整数𝑡（1≤𝑡≤104）——测试用例的数量。
每个测试用例的第一行包含三个整数𝑛,𝑚和𝑘（2≤𝑛,𝑚≤109，2≤𝑘≤2⋅105）——田地的大小和喷泉的数量。
然后是𝑘行，每行包含两个数字𝑟𝑖和𝑐𝑖（1≤𝑟𝑖≤𝑛，1≤𝑐𝑖≤𝑚）——第𝑖个喷泉所在单元格的坐标。保证所有单元格都不同，并且它们中没有一个是(𝑛,1)。

保证所有测试用例中𝑘的总和不超过2⋅105。

输出对于每个测试用例，首先输出𝛼——如果Bob不给她任何喷泉，Alice的地块的最大可能大小。然后输出𝑘个非负整数𝑎1,𝑎2,…,𝑎𝑘，其中：

如果Bob给Alice第𝑖个喷泉后，Alice的地块的最大可能大小不增加（即保持等于𝛼），则输出0；
如果Bob给Alice第𝑖个喷泉后，Alice的地块的最大可能大小增加（即变大于𝛼），则输出1。

如果您输出任何其他正数而不是1，只要它适合64位有符号整数类型，它也将被识别为1。

Sol：

Alice只能向下或向右移动，如果在第𝑖行有𝑥个单元格属于她，那么在第(𝑖−1)行她最多只能有𝑥个单元格。最大地块的构建可以表示如下：我们将从下到上遍历行，并跟踪我们在下面一行收集了多少单元格。在当前行，我们将收集相同数量的单元格，或者收集直到该行最左边的喷泉的所有单元格，如果这样的单元格更少。

相对于Alice的地块边界，喷泉有三种可能的位置：

喷泉没有相邻的单元格属于Alice的地块；
喷泉有一个相邻的单元格属于Alice的地块；
喷泉有两个相邻的单元格属于Alice的地块。

只有在移除第三种喷泉位置时，即所谓的角落，Alice的地块面积才会改变。因为角落已经形成，在下面一行Alice有更多的单元格，当移除这个喷泉时，她将能够至少带走一个单元格，并且对它的答案将是1。对于其他两种位置，移除喷泉不会改变地块的大小，它们的答案将是0（您可以自行证明）。

为了确保解决方案不依赖于田地的大小，我们将按照𝑥坐标的降序对喷泉进行排序，如果𝑥相等，则按𝑦坐标的升序排序。我们将按照这个顺序遍历喷泉，跟踪最后一个角落的坐标，并在找到新的角落时更新答案。

Code：

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<pii> a(k);
    map<pii, int> idx;
    for (int i = 0; i < k; i++) {
        cin >> a[i].F >> a[i].S;
        idx[a[i]] = i;
    }
    sort(all(a), [](const pii &a, const pii &b) {
        if (a.F != b.F) return a.F > b.F;
        return a.S < b.S;
    });
    vi ans(k);
    int total = 0;
    int cur = m + 1;
    int last = n;
    for (auto e : a) {
        if (cur > e.S) {
            ans[idx[e]] = 1;
            total += (cur - 1) * (last - e.F);
            cur = e.S;
            last = e.F;
        }
    }
    total += (cur - 1) * last;
    cout << total << endl;
    for (int e : ans) cout << e << " ";
    cout << '\n';
}

F2

Field Division_950F2

题意参照F1,困难版本，输出的不是是否增加，而是增加面积数

Sol：

让我们使用简单版本的解决方案来预先计算存储在前缀上的信息。只有当喷泉被移除时，它才会停止成为一个角落，因为前缀上最左边的角落在移除后不会再向左移动。为了计算面积的变化，让我们做一个重要的观察：如果喷泉𝑗不是一个角落，那么它要么无法成为一个角落，要么只有在按排序顺序在它之前的最后一个角落被移除后才会成为一个角落。它是在喷泉𝑗之前出现的最左边的角落，按排序顺序下一个角落的行号会严格更高。因此，我们需要做以下事情：对于每个角落，计算在不考虑它的情况下直到下一个角落的面积，这将有助于我们在计算面积时进行预计算。每个喷泉只会被处理一次，因此时间复杂度为𝑂(𝑛)。

Code：

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<pii> a(k);
    map<pii, int> idx;
    for (int i = 0; i < k; i++) {
        cin >> a[i].x >> a[i].y;
        idx[a[i]] = i;
    }
    idx[{0,0}] = k++;
    a.emplace_back(0,0);
    sort(all(a), [](const pii &a, const pii &b) {
        if (a.x != b.x) return a.x > b.x;
        return a.y < b.y;
    });
    vector<int> ans(k);
    vector<int> total(k + 1), cur(k + 1, m + 1), last(k + 1, n);
    for(int i = 1; i <= k; ++i){
        auto e = a[i - 1];
        total[i] = total[i - 1];
        cur[i] = cur[i - 1];
        last[i] = last[i - 1];
        if(cur[i] > e.y) {
            ans[idx[e]] = 1;
            total[i] += (cur[i] - 1) * (last[i] - e.x);
            cur[i] = e.y;
            last[i] = e.x;
        }
    }
    cout << total[k] << "\n";
    for(int i = 1; i <= k; ++i){
        auto e = a[i - 1];
        if(ans[idx[e]] == 0)continue;
        int tot = total[i - 1];
        int cr = cur[i - 1];
        int lst = last[i - 1];
        for(int j = i + 1; j <= k; ++j){
            auto ee = a[j - 1];
            if(cr > ee.y){
                tot += (cr - 1) * (lst - ee.x);
                cr = ee.y;
                lst = ee.x;
            }
            if(ans[idx[ee]] == 1){
                ans[idx[e]] = tot - total[j];
                break;
            }
        }
    }
    ans.pop_back();
    for(int e: ans) cout << e << " ";
    cout << '\n';
}

G

Yasya and the Mysterious Tree_950G

题意：

Yasya在森林中漫步时意外发现了一棵具有𝑛个顶点的树。树是一个无环的连通无向图。在树旁边，女孩发现了一份古老的手稿，上面写着𝑚个查询。查询可以有两种类型。第一种查询由整数𝑦描述。树中每条边的权重被替换为该边的权重与整数𝑦的按位异或。第二种查询由顶点𝑣和整数𝑥描述。Yasya选择一个顶点𝑢（1≤𝑢≤𝑛，𝑢≠𝑣），并在树中从𝑣到𝑢画一条权重为𝑥的双向边。然后Yasya在结果图中找到一个简单环，并计算其中所有边的按位异或值。她希望选择一个顶点𝑢，使得计算出的值最大。在给定的约束条件下可以证明这样的环存在且唯一（不依赖于𝑢的选择）。如果𝑣和𝑢之间已经存在一条边，那么简单环就是路径𝑣→𝑢→𝑣。请帮助Yasya回答所有的查询。

输入

第一行包含一个整数𝑡（1≤𝑡≤104）——测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数𝑛，𝑚（2≤𝑛≤2⋅105，1≤𝑚≤2⋅105）——树中顶点的数量和查询的数量。

每个测试用例的接下来𝑛−1行包含三个整数𝑣，𝑢，𝑤（1≤𝑣,𝑢≤𝑛，1≤𝑤≤109）——树中某条边的端点和权重。保证给定的边构成一棵树。

每个测试用例的接下来𝑚行描述了查询：

^ 𝑦（1≤𝑦≤109）——第一种查询的参数；

? 𝑣 𝑥（1≤𝑣≤𝑛，1≤𝑥≤109）——第二种查询的参数。

保证所有测试用例中𝑛的总和不超过2⋅105。对于𝑚也是一样的。

输出

对于每个测试用例，输出第二种查询的答案。

Sol

我们将把树放在顶点1上，并计算从顶点到根节点路径上每个顶点𝑑𝑣的异或值。这可以通过深度优先遍历在𝑂(𝑛)时间复杂度内完成。

现在让我们来学习如何在每个查询中以𝑂(𝑛)时间复杂度解决问题。第一类查询可以直接执行。注意由于异或运算的属性，数值只会在奇深度的顶点（根节点的深度为0）发生改变。同时，它们的改变很简单：与𝑦异或即可。为了回答第二类查询，需要意识到简单循环路径𝑣→lca(𝑣,𝑢)→𝑢→𝑣的异或值等于𝑑𝑣⊕𝑑𝑢⊕𝑥。实际上，从lca(v, u)到根节点的路径将被计算两次，所以最终异或值为0，并且不会包含任何其他额外的边。通过适当的技巧，你可以尝试使用AVX指令加速这种解决方案，但是时间限制设置得很严格。

对于问题的完整解决方案，可以使用前缀树（trie）数据结构。借助它，可以在𝑂(log𝑥)时间复杂度内找到集合中与𝑥异或后结果最大的𝑦。由于𝑑𝑣会不同地改变，你需要使用两个前缀树——分别用于偶数和奇数高度的顶点。第一类操作可以累积在变量𝑤odd中，并添加到异或表达式中。此外，在回答第二类查询时，不要忘记从所需的前缀树中删除𝑑𝑣，然后再插入回去。为此，可以在每个顶点中维护一个叶子节点的计数器，并在遍历过程中使用这些信息。

因此，最终的时间复杂度为𝑂((𝑛+𝑚)log109)。

Code：

struct trie {
    int l, c;
    vector<array<int, 2> > node;
    vector<int> cnt;
    trie(int l, int max_members) : l(l), c(0), node((l + 2) * max_members + 3), cnt((l + 2) * max_members + 3) {}
    void add(int x) {
        int cur = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (!node[cur][has_bit]) {
                node[cur][has_bit] = ++c;
            }
            cur = node[cur][has_bit];
            ++cnt[cur];
        }
    }
    void remove(int x) {
        int cur = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (!node[cur][has_bit]) {
                node[cur][has_bit] = ++c;
            }
            cur = node[cur][has_bit];
            --cnt[cur];
        }
    }
    int find_max(int x) {
        int cur = 0, ans = 0;
        for (int i = l; i >= 0; --i) {
            bool has_bit = (1 << i) & x;
            if (node[cur][!has_bit] && cnt[node[cur][!has_bit]]) {
                ans += 1 << i;
                cur = node[cur][!has_bit];
            }
            else {
                cur = node[cur][has_bit];
            }
        }
        return ans;
    }
};
const int N=2e5+10;
int x[N];
bitset<N> dp;
vector<array<int, 2> > e[N];
void dfs(int c, int p) {
    for (auto [i, w] : e[c]) {
        if (i == p) {
            continue;
        }
        dp[i] = !dp[c];
        x[i] = x[c] ^ w;
        dfs(i, c);
    }
}
 
void solve() {
    int n, m, gx = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        e[i].clear();
    }
    for (int i = 1, u, v, w; i < n; ++i) {
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0);
    vector<trie> t(2, trie(30, n));
    for (int i = 1; i <= n; ++i) {
        t[dp[i]].add(x[i]);
    }
    while (m--) {
        char c;
        cin >> c;
        if (c == '^') {
            int y;
            cin >> y;
            gx ^= y;
        }
        else {
            int a, b;
            cin >> a >> b;
            t[dp[a]].remove(x[a]);
            int same_group = t[dp[a]].find_max(x[a] ^ b);
            int diff_group = t[1 - dp[a]].find_max(x[a] ^ b ^ gx);
            t[dp[a]].add(x[a]);
            cout << max(same_group, diff_group) << " ";
        }
    }
    cout << '\n';
}

Conclusion

太久没打脑袋不灵光。。但是d和e如果写过的话是可以做的，确实不难。没想到三个题也能加几分，下次再练练。

codeforces

#math #sortings #constructive algorithms #number theory #implementation #data structures #dfs and similar #bitmasks #graphs

div3-950

https://www.polarishaw.top/2024/06/07/DIV3_950/

作者

Polaris

发布于

2024年6月7日

许可协议

茶6.10-6.14 上一篇

CMU15445-lecture3 下一篇