1994(div1+div2)

A. Diverse Game

佩特看了谢尔盖的数据流,得出了一个 n×m 的矩阵 a1ain×m,aiaj 构造矩阵 b ,使得 b 对于任意 1in,1jmai,jbi,j 都成立。

给你一个矩阵 a ,请构造出满足 Petr 要求的矩阵 b ,或者确定这是不可能的。

只有 n=1,m=1 的时候不可能,其他一定可以构造。

直接暴力构造会有一个问题:若 an,m=n×m,则最后一个数字不会变,随便和前面的数字交换即可。

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];b[i][j] = a[i][j];
        }
    }
    if (n == 1 && m == 1) {
        cout << "-1\n";return;
    }
    vector<int> vis(n * m + 1);
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            for (int k = 1;k <= n * m;k++) {
                if (a[i][j] != k && !vis[k]) {
                    b[i][j] = k;vis[k] = 1;break;
                }
            }
        }
    }
    if (b[n][m] == a[n][m])swap(b[1][1], b[n][m]);

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << b[i][j] << " \n"[j == m];
        }
    }
}

标准答案:

直接输出 a[(i + 1) % n][(j + 1) % m] 即可,没有想到...

B. Fun Game

游戏开始时,沃瓦选择长度为 n 的两个二进制序列 st ,并把它们交给万亚。二进制序列是仅由数字 01 组成的序列。凡亚可以选择整数 l,r ,使得 1lrn ,并且对于所有 lir 同时将 si 替换为 sisil+1 ,其中 si 是序列 s 中的第 i 个元素。

判断序列 s 能不能变为 t

当字符串 s 有前置 0 时,t 字符串前面必须也是 0,不然无法变为 t,其他情况都能变为 t

void solve() {
    int n;cin >> n;
    string s, t;cin >> s >> t;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '0') {
            if (t[i] != s[i]) {
                cout << "NO\n";
            }
        } else {
            break;
        }
    }
    cout << "YES\n";
}

C. Hungry Games

雅罗斯拉夫正在玩一款电脑游戏,在其中一个关卡中,他遇到了 n 个排列成一排的蘑菇。每种蘑菇都有自己的毒性级别;从一开始的第 i 个蘑菇的毒性级别为 ai 。雅罗斯拉夫可以选择两个整数 1lrn ,然后他的角色就会从左到右轮流逐个吃掉这个分段中的蘑菇,也就是数字为 l,l+1,l+2,,r 的蘑菇。

角色的毒性等级为 g ,最初等于 0 。电脑游戏由数字 x 定义--即任何时候的最大毒性级别。当食用毒性等级为 k 的蘑菇时,会发生以下情况:

  1. 角色的毒性等级会增加 k
  2. 如果 gx ,过程继续;否则, g 变为零,过程继续。

雅罗斯拉夫感兴趣的是,有多少种方法可以选择 lr 的值,使得 g 的最终值不为零。帮助雅罗斯拉夫找到这个数字!

Solution

DP

新知识:

想要直接将某个数组做前缀和直接:partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
(针对下标 1~n)

对于下标 l,找到后面的最小下标 k 使得 al+al+1++ak>xprekprel1>x

al+al+1++ak1xprek1prel1x,则有 kl 种满足要求。

prekprel10,这个时候下标 lk 之后结果为 0 ,若继续吃还有可能会有结果,即为 fk+1

fi 代表左边界为 i 的满足条件的区间个数。

DP 动态转移方程:fl=(kl)+fk+1

#define int long long
void solve() {
    int n, x;cin >> n >> x;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
    vector<int> f(n + 2);
    for (int i = n - 1;i >= 0;i--) {
        int j = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
        f[i] = f[j] + j - i - 1;
    }
    cout << accumulate(f.begin(), f.end(), 0ll) << '\n';
}

D. Funny Game

Vanya 有一个包含 n 个顶点(编号从 1n )和 an 个整数的数组的图形;最初,图形中没有边。万尼亚觉得无聊,为了找点乐子,他决定进行 n1 次运算。

操作数 x (操作数从 1 开始依次编号)如下:

使用 n1 运算帮助凡亚得到一个连通的图,或者确定这是不可能的。

Solution

抽屉原理

操作需要倒着进行(对答案没有影响):从操作数 n1 开始(后面依次递减),需要找到 x||auav|,即 auav(modx)

根据抽屉原理,每一次操作都一定能够找到两个点 u,v 满足要求。

void solve() {
    int n;cin >> n;
    vector<int> a(n), p(n);
    iota(p.begin(), p.end(), 0);
    vector<pair<int, int>> ans;
    for (auto& i : a)cin >> i;
    for (int i = n - 1;i >= 1;i--) {
        vector<int> occ(i, -1);
        for (auto j : p) {
            if (occ[a[j] % i] != -1) {
                ans.push_back({j, occ[a[j] % i]});
                p.erase(find(p.begin(), p.end(), j));
                break;
            }
            occ[a[j] % i] = j;
        }
    }
    cout << "YES\n";
    reverse(ans.begin(), ans.end());
    for (auto [x, y] : ans)cout << x + 1 << " " << y + 1 << "\n";
}

E. Wooden Game

有一片森林,里面有 k 棵有根的树木 。伐木工蒂莫菲想通过以下操作砍伐整片森林:

蒂莫菲喜欢位运算,因此他希望删除的子树的大小的 bitwise OR 是最大的。请帮助他,找出他能得到的最大结果。

Solution

这个题目所给出的树没有任何用处,只有顶点个数 ai 有用。

对于某个树,设每次删除的子树大小为 d1,d2,,dt ,易得: i=1di=n,且 d1|d2||dtn

若无子树大小为 k,可以将子树中的节点一个一个删除从而构造出 k

因此,对于这个树,可以构造 [1,n] 中的所有答案

对于某个树,n 的第 k 位是 1,则可以直接构造出 2k,若答案已经拥有了这个部分,则可以构造出 2k1,从而保证了最优。

非常妙!

void solve() {
    int k;cin >> k;
    vector<int> a(k);
    for (int i = 0;i < k;i++) {
        cin >> a[i];
        for (int j = 0;j < a[i] - 1;j++) {
            int x;cin >> x;
        }
    }
    sort(a.rbegin(), a.rend());
    int ans = 0;
    for (auto x : a) {
        for (int i = __lg(x);i >= 0;i--) {
            if ((x >> i) & 1) {
                int y = (ans >> i) & 1;
                if (y == 0) {
                    ans |= (1 << i);
                } else {
                    ans |= (1 << i) - 1;
                    break;
                }
            }
        }
    }
    cout << ans << '\n';
}

F. Stardew Valley

鹈鹕镇由 m 条双向道路连接着 n 座房屋。有些道路上站着 NPC。农民布巴需要在每条路上与 NPC 走一走,并与他们交谈。

帮助农夫找到一条符合以下属性的路线:

可以保证:只需在有 NPC 的道路上行走,就可以从任何其他房屋到达任何其他房屋。

Solution

欧拉图

类似的题目还有:F - Perils in Parallel

题目意思即这个图是 NPC 边的全集 加上 无 NPC 边的子集 (即删除一些无 NPC 的边) ,求这个图的欧拉回路。

拥有欧拉图的条件是每个顶点的度数都是偶数

对于删除单独的某一条边,可以使用代码中的技巧,g[u].push(i),edge[i]=u^v->int to=edge[i]^u

对于这个题,可能需要删除部分无 NPC 的边组成的图来做欧拉回路。只要图中的每个顶点的度数都是偶数,则一定存在欧拉回路,否则一定不存在欧拉回路。

将图中无 NPC 的边组成一个图,对于这个图进行处理,若能够使得所有顶点度数为偶,则继续求欧拉回路。

若有奇数个顶点有奇数的度数,则无法通过删边达到都为偶数度数,在搜索的过程中若某个顶点的度数为奇数,则需要将这个顶点和其连接的顶点之间的边删去一个

void solve() {
    int n, m;cin >> n >> m;
    vector<vector<int>> g(n + 1), blk(n + 1);
    vector<int> edge(m + 1);
    for (int i = 1;i <= m;i++) {
        int u, v, is;cin >> u >> v >> is;
        g[u].push_back(i);
        g[v].push_back(i);
        edge[i] = u ^ v;
        if (!is) {
            blk[u].push_back(i);
            blk[v].push_back(i);
        }
    }
    vector<int> deg(n + 1);
    for (int i = 1;i <= n;i++)deg[i] = g[i].size() & 1;
    vector<int> del(m + 1), vis(n + 1);
    auto dfs = [&](auto self, int u)->void {
        vis[u] = 1;
        for (auto x : blk[u]) {
            int to = edge[x] ^ u;
            if (vis[to])continue;
            self(self, to);
            if (deg[to]) {
                del[x] = 1;
                deg[to] ^= 1;
                deg[u] ^= 1;
            }
        }
        };
    int ok = 1;
    for (int i = 1;i <= n;i++) {
        if (vis[i])continue;
        dfs(dfs, i);
        ok &= !deg[i];
    }
    if (!ok) {
        cout << "NO\n";return;
    }
    cout << "YES\n";
    cout << m - accumulate(del.begin() + 1, del.end(), 0) << '\n';
    auto euler = [&](auto self, int u) ->void {
        while (g[u].size()) {
            int x = g[u].back();g[u].pop_back();
            int to = edge[x] ^ u;
            if (del[x])continue;
            del[x] = 1;
            self(self, to);
        }
        cout << u << " ";
        };

    euler(euler, 1);
    cout << '\n';
}