2023-02-02 比赛题目以及题解

测试题面链接：problems.pdf

比赛由 Sqrtyz 学长主持。深表敬意！

总结

这次测试可以说是一场娱乐赛。采用的是ACM赛制。

这一次测试成绩如下，是我与冯译宽一起合作出来的成绩。

其中，有两道题 (G, H) 其实都不是很正确的解法，只是因为数据比较水……

其中，G题是fyk想出的，A,C,H题都是我写的（其实只花了5+20+10分钟，其他时间都耗在了D题上，关键是还没有有想出来……）

所以说，HFu说的我们的策略很好其实是不正确的……QwQ （被Sqrtyz学长全图炮骂了）

其实我和fyk还是比较互补的，他的思路非常的独特，而我的又相对死板……

废话也不多说了，我们看题

A.Curse

签到题之二……是一个最优构造题。

我们只要使得 \(A\) 是严格递增的，此时，求出对应的 \(B'\) 序列的 \(LIS\)。

那么，答案就是 \(n + LIS(B')\)

证明

由于我们保证了 \(LIS(A)\) 已经是最大了，考虑对其进行一次操作，绑定交换其中两个数。

那么此时 \(LIS(A)\) 会减少一个，而 \(LIS(B)\) 要么不变，要么增加一个。也就是说 \(LIS(A) + LIS(B)\) 实际上是不会再变多了。换句话来说，这就是最优解了。

其实这道题在考场上我是没有过多思考的……

说来也惊险，在 12:09 我才开始思考这道题 （12:20结束比赛），随便口胡了这个思路，验证了一下样例，发现没有问题，于是在 12:15 就写出来了，于是就 AC 了……一发入魂

第一次提交的代码太难看了……仓促之下写的，下面的是把格式优化了一下的……

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e6 + 7;

#define lowbit(i) (i & -i)
class BIT {
private:
    int b[N];
public:
    int update(int i, int x) {
        for (; i < N; i += lowbit(i)) b[i] = max(b[i], x);
    }
    int query(int i, int r = 0) {
        for (; i; i -= lowbit(i)) r = max(r, b[i]);
        return r;
    }
};

struct Item {
    int a, b;
    bool operator<(const Item & i) {
        return a < i.a;
    }
};

int main() {
    static BIT bit;
    static Item items[N];

    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> items[i].a;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> items[i].b;
    }
    sort(items + 1, items + 1 + n);

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        int k = items[i].b;
        int ans = bit.query(k);
        bit.update(k, ans + 1);
        res = max(res, ans + 1);
    }
    cout << res + n << endl;
    return 0;
}

B.Cover

我现在还没有写出来，候补

C.Chess

其实说来也多亏了 Sqrtyz 学长的解释，我才终于看懂了样例……然后花了7分钟写了一个暴力（结果就过了……）

所谓暴力，也就是说深搜寻找到所有的输赢情况，并且统计……

其实正解就是暴力搜索。其复杂度的保证在进攻的方式上。

每一次进攻就必定有一个随从死亡。经过一点点分析，其复杂度不会超过 \(O(n!)\) 。考虑 \(n\) 最大也才7……

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
#include <iomanip>

using namespace std;

#define double long double
const int N = 10;
double W[2], E; // A win, B win, No win
int n[2];
int atk[2][N]; // 攻击力
int hp[2][N]; // 血量
int ats[2][N]; // 攻击次数

// a 打 b,当前状态的可能性为 P 
double calc(int a, int b, double P) {
    // 找到攻击次数最少的存活者 
    int minAts = INT_MAX, at, alive(0);
    for (int i = n[a]; i; --i) {
        if (hp[a][i] > 0) { ++alive; // 统计a存活人数 
            if (ats[a][i] <= minAts) minAts = ats[a][i], at = i;
        }
    }

    int blive(0);
    for (int i = 1; i <= n[b]; ++i) {
        if (hp[b][i] > 0) ++blive; // 统计b存活人数 
    }

    if (alive == 0 && blive == 0) { // 平局
        return E += P;
    } else if (alive == 0) { // b win
        return W[b] += P;
    } else if (blive == 0) { // a win
        return W[a] += P;
    }

    // at 攻击随机一个
    ++ats[a][at];
    for (int i = 1; i <= n[b]; ++i) {
        if (hp[b][i] > 0) { // at 可以攻击这个狗
            hp[a][at] -= atk[b][i];
            hp[b][i] -= atk[a][at];
            calc(b, a, P / blive); 
            hp[a][at] += atk[b][i];
            hp[b][i] += atk[a][at]; // trace back
        }
    }
    --ats[a][at]; // trace back
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n[0] >> n[1];
    for (int i = 1; i <= n[0]; ++i) {
        cin >> atk[0][i];
        hp[0][i] = atk[0][i];
    }
    for (int i = 1; i <= n[1]; ++i) {
        cin >> atk[1][i];
        hp[1][i] = atk[1][i];
    }

    double init = 1.0;
    if (n[0] == n[1]) init = 0.5;
    if (n[0] >= n[1]) { // 0 first
        calc(0, 1, init);
    }
    if (n[1] >= n[0]) { // 1 first
        calc(1, 0, init);
    }

    cout << fixed << setprecision(11);
    cout << W[0] << '\n' << W[1] << '\n' << E << endl;
    return 0;
}

D.Robot

真的毒瘤……我深搜了4个小时，结果只得了60分……太可恶了

DP解法

Sqrtyz 学长给出的正解是DP，奇奇怪怪的那种……其实思路理清楚非常简单。

我们令 dp[i][0/1] 表示前 i-1 行清理完之后到达 0/1 至少需要清理的次数

我们让机器人一步一步走。假设我们当前位置为 dp[i][j]

那么我们分两种情况：

  • dp[i][j ^ 1] == 0，也就是说当前列没有需要清理的了。那么我们让机器人向右走一步，到达 dp[i+1][j] 即可（花费代价为0）

  • dp[i][j ^ 1] == 1，也就是说当前列还有一个需要清理的。我们又要分两种情况讨论

    • dp[i + 1][j] == 1，两个需要清理的地方发生了冲突，我们必须要清理一个。那么我们有两种选择：

      • 人为清理同列的。那么我们让机器人走到 dp[i + 1][j] 即可，花费代价为1

      • 人为清理同行的。意味着我们让机器人向上走让后再向右即可。这个时候如图
        2023-02-02 比赛试题及题解-小白菜博客
        （红色为机器人的位置，蓝色为我们人为清理的位置，绿色为机器人需要清理的位置）经过观察我们可以知道，机器人不走已经被清理过的格子是最优的。那么显而易见，我们让机器人走到 dp[i+2][j^1] 的位置，就非常的优秀了（花费代价为1）

    • dp[i + 1][j] == 0，也就是说没有冲突了。此时我们仍然有两种选择

      • 人为清理这个格子。那么机器人就直接向右走转移到 dp[i+1][j]，花费代价为1 （就是因为我没有考虑到这个点，所以错了……QwQ）

      • 机器人清理这个格子，那么机器人就向上然后向右，转移到 dp[i + 1][j ^ 1] 即可，花费代价为0

为了方便DP，我们使用刷表法。定义刷新函数：

int flush(int i, int k) {
    if (mp[i][k ^ 1]) { // 上面有脏东西
        if (mp[i + 1][k]) { // 右边也有 
            // 略过右边的
            update(dp[i + 2][k ^ 1], dp[i][k] + 1); 
        } else {
            // 没有冲突 
            update(dp[i + 1][k ^ 1], dp[i][k]);
        }
        // 略过上面的 
        update(dp[i + 1][k], dp[i][k] + 1);
    } else { // 没有脏东西
        update(dp[i + 1][k], dp[i][k]); 
    }
    return 0;
}

初始化并用每一个值刷表：

memset(dp, 0x7F, sizeof(dp));
dp[1][0] = 0; // 初始位置
for (int i = 1; i <= n; ++i) {
    flush(i, 0);
    flush(i, 1);
}

那么这道题就做出来了……（考场上这道题我得分最高……60分……可是还是没有AC）

记忆化搜索写法

考场上我就是用这个方法写的，就是因为忽略了一种情况，痛失40分……

而且我当时的写法很奇怪……思路还是有一点区别。见代码，有注释。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int N = 1e6 + 7, INF = 0x7F7F7F7F;

int n, f[N][2];
char mp[N][2];

// 状态定义为清理完了前i列，并且在k行的答案
// impa指前面的操作有没有对这里的答案产生影响
// 记忆化一下就ok了
inline int dfs(int i, int k, int impa = false) {
    if (i == n) return 0;
    if (!impa && ~f[i][k]) return f[i][k];

    int ans = 0, backup = mp[i][k], j;
    mp[i][k] = 0;

    // 寻找第一个需要清理的地方 
    for (j = i; j <= n; ++j) {
        if (mp[j][0] || mp[j][1]) break;
    }

    // 如果是i,j同一列的话……就会对其产生影响  
    if (j >= n) ans = 0;
    else if (mp[j][k]) {
         // 唯一解
        ans = dfs(j, k, i == j ? true : false); 
    } else if (mp[j + 1][k]) { // 有冲突
        // 选择清理不同行的
        ans = dfs(j + 1, k) + 1; // 对其答案没有影响
        // 清理同行的
        mp[j + 1][k] = 0;
        ans = min(ans, dfs(j + 1, k ^ 1, true) + 1); // 对其答案有影响 
        mp[j + 1][k] = 1;
    } else { // 没有冲突
        ans = dfs(j, k ^ 1, i == j ? true : false);
        // 或者我们清理这个点，进入后面一个点 
        ans = min(ans, dfs(j + 1, k) + 1); 
    }

    // trace back
    mp[i][k] = backup;
    if (!impa) f[i][k] = ans;
    return ans;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    memset(f, 0xFF, sizeof(f));

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> mp[i][0], mp[i][0] -= '0';
    }
    for (int i = 1; i <= n; ++i) {
        cin >> mp[i][1], mp[i][1] -= '0';
    }

    cout << dfs(0, 0, false) << endl;
    return 0;
}

哎……这种写法表现极其不优秀……DP写法是214ms，这种写法512ms

E.Xorloop

都是套路……

我们一点点剖析需求。

首先，我们肯定需要找到所有回路的异或和，同时，还需要求出这些异或和的最大值……考虑到 a ^ a = 0 的性质，我们用可以通过拼接两个环形成一个全新的环。

为了让每一条边都在一个环内，我们可以先找一棵生成树。然后遍历每一条非树边，形成一个只有一条非树边的环。这样，我们就可以通过拼接这些环，构造出所有的回路了。

由于有了每一种环的异或值，我们考虑如何凑出最大值。那么就需要用到线性基……

那么恭喜你，这道题就做出来了……都是套路啊

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 5e4 + 7, M = 1e5 + 7;

int n, m;

class MergeFindSet {
private:
    int grp[N];
public:
    MergeFindSet(int n) { init(n); }
    void init(int n) {
        for (int i = 1; i <= n; ++i) grp[i] = i;
    }
    int find(int x) {
        if (grp[x] == x) return x;
        return grp[x] = find(grp[x]);
    }
    void merge(int x, int y) {
        grp[find(x)] = find(y);
    }
};

struct Edge {
    int from, to, w;
} edge[M], ver[M];
int head[N], tot = 0, vtot = 0;
int W[N]; // 生成树上点到根的路径权值异或和 
int xorRing[M];
void add(int u, int v, int w) {
    edge[++tot] = {head[u], v, w}, head[u] = tot;
}

// 点x, 到根的路径异或和s，父节点fa
void dfs(int x, int s, int fa) {
    W[x] = s;
    for (int y, i = head[x]; i; i = edge[i].from) {
        if ((y = edge[i].to) != fa) {
            dfs(y, s ^ edge[i].w, x);
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;
    static MergeFindSet mfs(n);
    int u, v, w;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        if (mfs.find(u) == mfs.find(v)) {
            ver[++vtot] = {u, v, w}; // 记录非树边
        } else {
            mfs.merge(u, v);
            add(u, v, w), add(v, u, w); // 建生成树 
        }
    }
    // 预处理树上路径异或和 
    dfs(1, 0, 0);

    static int xxj[40];
    #define marked(x, i) ((x>>i)&1)
    for (int i = 1; i <= vtot; ++i) {
        u = ver[i].from, v = ver[i].to, w = ver[i].w;
        int val = W[u] ^ W[v] ^ w;
        for (int k = 30; k >= 0; --k) {
            if (marked(val, k)) {
                if (!xxj[k]) {
                    xxj[k] = val; break;
                }
                val ^= xxj[k];
            }
        }
    }

    int ans = 0;
    for (int k = 30; k >= 0; --k) {
        ans = max(ans, ans ^ xxj[k]);
    }
    printf("%d\n", ans);
    return 0;
}

F.Line

虽然代码写出来了，但是……有一个点一直过不了。可恶

其实这道题就是优化建图的问题。建完图之后，跑一次DJK就行了。

那么如何建图？

我们记 W(x) 为点 x 的权值。

对于一条边 (u, v)，其编号为 i。我们在另外一张图里面加入边 (i, u, W(u) / 2) 以及 (i, v, W(v) / 2) （无向边！）

那么对于新的图……跑一次DJK就OK了

不要用 double，会出现这种错误情况

所以，我们建图的时候先不除以2，在答案的地方除以二就行了。

还有，最大值能有多大设多大

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <climits>

using namespace std;
const int N = 5e6;

struct Edge {
    int to, next;
    long long w;
} edge[N];
int head[N], tot = 0;
inline void add(int u, int v, long long w) {
    edge[++tot] = {v, head[u], w}, head[u] = tot;
}

long long Vw[N];
int n, m, S, T;

typedef pair<long long, int> Pr;
void djk(int s, long long * dis) {
    static int vis[N]; memset(vis, 0, sizeof(vis));

    priority_queue<Pr, vector<Pr>, greater<Pr> > pq;

    dis[s] = 0;
    pq.push(make_pair(0, s));

    while (pq.size()) {
        int x = pq.top().second; pq.pop();
        if (vis[x]) continue;
        vis[x] = true;

        long long w;
        for (int y, i = head[x]; i; i = edge[i].next) {
            y = edge[i].to, w = edge[i].w;
            if (!vis[y] && dis[y] > dis[x] + w) {
                dis[y] = dis[x] + w;
                pq.push(make_pair(dis[y], y));
            }
        }
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m >> S >> T;
    for (int i = 1; i <= n; ++i) cin >> Vw[i];

    int u, v;
    for (int i = 1; i <= m; ++i) {
        cin >> u >> v;
        add(i, u + m, Vw[u]);
        add(u + m, i, Vw[u]);
        add(i, v + m, Vw[v]);
        add(v + m, i, Vw[v]);
    }

    static long long dis[N];
    for (int i = 1; i <= m + n; ++i) dis[i] = LLONG_MAX;
    djk(S, dis);
    cout << dis[T] / 2 << endl;
    return 0;    
}

G.Sequence

感性理解一下，对于这个序列，相邻两个元素只差最大为 n - 1，而我们单次操作至多却是 n，也就是说，最终状态一定是单点不下降的序列……

这是一道构造题。总的来说，有两种构造方法

  • 我们先构造差分序列，记录每一二元组 (d, i)，d指差分的值，i指位置。以d为第一关键字，i为第二关键字排序，然后，我们将 i 依次输出即可
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5 + 7;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    static pair<int, int> dif[N];

    int px(0), n, x;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        dif[i] = make_pair(px - x, i);
        px = x;
    }

    sort(dif + 1, dif + 1 + n);
    for (int i = 1; i <= n; ++i) {
        cout << dif[i].second << ' ';
    } cout << endl;
    return 0;
}
  • Sqrtyz 学长给出了一种 O(n) 的构造法。考虑到元素是唯一的，我们尝试把每一个元素凑到 n + 1。也就是说，值为 x 的数，在第 n + 1 - x 次被操作。
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, x, ans[100007];
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        ans[n + 1 - x] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
    } cout << endl;
    return 0;
}

真·田才

H.Puzzle

一道不是那么数学的数学题，从来没有做过的交互体……结果写了一个假的解……数据太假了。

考场思路：

我们令未确定的位置全集为 \(S\), 随机选取其中一个元素 \(i\) 作为基准，枚举其他元素 \(j\)，令 \(gcd(i, j)\) 最大值为 \(d\)，记录下所有 \(gcd(i, j) = d\) 的 \(j\)，作为新的全集 \(S\)。重复上述步骤，直到全集中只剩下 1 或 2 个数为止。

次数上限 \(3n - 1\) 是不符合要求的……但是，Sqrtyz 学长出了一堆 \(n = 10\) 的情况，而在 \(n = 10\) 的时候，其实刚好需要 \(2n\) 次……所以没有被Hack掉……QwQ

那么 Sqrtyz 学长对此给出了优化的方法，我们只需要寻找到一个不为 1 的基准开始即可。

枚举 \(i \in [1, n)\) ，直到 \(gcd(i, i+1) \ne 1\)，那么，\(i\) 与 \(i + 1\) 就一定都不为 \(1\)。钦定任一为基准即可。但是，为了不浪费寻找的那些次数，我们可以发现，如果 \(gcd(i, i+1) = 1\) 并且 \(gcd(i + 1, i + 2) == 1\) ，那么可以保证 \(i + 1\) 一定不为 \(0\)。（假定我们如此寻找了 \(k\) 次）也就是说，我们未确定的全集减少了 \(k - 1\) 个数。那么总的询问次数上限为 \(2(n - k + 1) + k = 2n - k + 1\) 次，又由于 \(k \ge 1\)，那么可以保证次数在 \(2n\) 次以内

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

using namespace std;

int ask(int i, int j) {
    if (i > j) swap(i, j);
    static map<pair<int, int>, int> cache;
    pair<int, int> P = make_pair(i, j);
    if (cache[P] != 0) return cache[P];

    cout << "? " << i << ' ' << j << endl;
    int g;
    cin >> g;
    return cache[P] = g;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;

    vector<int> S;
    // 找到全集
    for (int gcd(0), i = 1; i < n; ++i) {
        gcd = ask(i, i + 1);
        if (gcd != 1) {
            for (int j = i; j <= n; ++j) S.push_back(j);
            break;
        }
    }
    if (S[0] != 1) S.push_back(1);

    if (S.size() == 1) {
        cout << "! 1 " << n << endl;
        return 0;
    }

    for (int id(1); id <= n; ++id) {
        if (S.size() == 2) {
            cout << "! " << S[0] << ' ' << S[1] << endl;
            return 0; 
        }

        vector<int> V;
        int i = S[0], gmax = -1;
        for (size_t si = 1; si < S.size(); ++si) {
            int j = S[si];
            int gcd = ask(i, j);  
            if (gcd > gmax) gmax = gcd, V.clear();
            if (gcd == gmax) V.push_back(j); 
        }

        if (V.size() == 1) {
            cout << "! " << i << ' ' << V[0] << endl;
            return 0;
        }

        S.swap(V);
    }

    return 0;
}

正解：

对于题目，我们有下述发现

\[\begin{cases}
gcd(a, c) = gcd(b, c) \implies c \ne 0 \\
gcd(a, c) < gcd(b, c) \implies b \ne 0 \\
gcd(a, c) > gcd(b, c) \implies a \ne 0 \\
\end{cases}
\]

也就是说，每两次询问，就一定能排除一个数。那么最多 \(2n\) 次，就确定为 \(0\) 的数。

这种思路的代码我就不放了，我没有写……QwQ