首页 > 其他分享 >ZZJCACM个人训练赛23题解

ZZJCACM个人训练赛23题解

时间：2024-12-23 20:43:19浏览次数：8  
标签：2ll ZZJCACM int 题解 tt cin -- 训练赛 using

原题链接
A
https://codeforces.com/contest/1999/problem/A 800
B
https://qoj.ac/contest/1794/problem/9310
C
https://codeforces.com/problemset/problem/2008/D 1100
D
https://qoj.ac/contest/1485/problem/8081
E
https://codeforces.com/contest/2002/problem/B 1000
F
https://codeforces.com/contest/1950/problem/F 1700
G
https://codeforces.com/contest/1954/problem/B 1200
H
https://codeforces.com/contest/1991/problem/D 1900
I
https://codeforces.com/contest/2020/problem/C 1400

A

太简单，直接看代码吧

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int a; cin >> a;
        cout << a / 10 + a % 10 << "\n";
    }
}

B

由于题目求的是方案数取余2的值，即求方案数的奇偶性。

尝试画一个矩阵来描述

\(M[i][j] = [j \in [l_i, r_i]] (即当 j \in [l_i, r_i],时M[i][j] = 1,否则为0)\)

以第一个样例为例：

\( \left[ \begin {array}{} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \end{array} \right] \)

我们把第二列除了最后一行的1全改为0，值是不变的，这由于第五行只能选择2

手模一下可以推广，初等行变换不会影响最后的奇偶性

注意到，当有行全为0的时候，那么答案就是偶数，反之为奇数

即判断这个矩阵是否行满秩即可

我们考虑区间覆盖，问题转化为判断是否存在一个区间能被其他若干个区间覆盖

我们把l和r + 1建边，如果图中有环，则说明存在一个区间能被其他若干个区间覆盖

下面我用拓扑排序判环

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<vector<int>> adj(n + 2, vector<int>(0));
        vector<int> d(n + 2);
        auto addEdge = [&](int u, int v) {
            adj[u].emplace_back(v);
            adj[v].emplace_back(u);
            d[u]++; d[v]++;
        };
        auto toposort = [&](vector<vector<int>> &adj, vector<int> &d) {
            vector<int> tp;
            queue<int> q;
            for (int i = 1; i <= n + 1; ++ i) {
                if (d[i] == 1) q.push(i);
            }
            while (q.size()) {
                int x = q.front(); q.pop();
                tp.push_back(x);
                for (auto y : adj[x]) {
                    d[y] --; d[x] --;
                    if (d[y] == 1) q.push(y);
                }
            }
            return (int)tp.size() == n + 1;
        };
        for (int i = 1; i <= n; ++ i) {
            int l, r;
            cin >> l >> r;
            addEdge(l, r + 1);
        }
        cout << toposort(adj, d) << "\n";
    }
}

C

由于原数组是排列，每一个点经过若干次，一定可以到本身，那么 \(F(i)\) 其实就是 \(i\) 所在的联通块的黑色的个数

我们用并查集合并即可得到连通块，把并查集的中的每个的点的权提前赋好再去合并

最后输出对应的连通块的值即可

#include <bits/stdc++.h>
using namespace std;
class DSU {
public:
    int n;
    vector<int> dsu, dsus;
    // dsu[i]存是 i 的祖宗结点
    // dsus[i]存 i 所在图的大小
    DSU() {}
    DSU(int n) { init(n); }
    void init(int n) {
        this -> n = n;
        dsu.resize(n + 1);
        dsus.resize(n + 1, 1);
        iota(dsu.begin(), dsu.end(), 0);
    }
    int find(int a) {
        if (a == dsu[a]) {
            return a;
        } else {
            dsu[a] = find(dsu[a]);
            return dsu[a];
        }
    }
    void merge(int a, int b) {
        int x = find(a);
        int y = find(b);
        if (x != y) {
            if (dsus[x] < dsus[y]) { swap(x, y); }
            dsu[y] = x; dsus[x] += dsus[y];
        }
    }
    //由于未必路径压缩好了，所以求祖宗结点需调用find函数或者使用reboot()函数路径压缩
    void reboot() {
        for (int i = 1; i <= n; ++ i) {
            int fa = find(dsu[i]);
            dsu[i] = fa; dsus[i] = dsus[fa];
        }
    }
};

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

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> p(n + 1);
        for (int i = 1; i <= n; ++ i) cin >> p[i];
        DSU a(n);
        for (int i = 1; i <= n; ++ i) {
            char c;
            cin >> c;
            a.dsus[i] = (c - '0') ^ 1;
        }
        for (int i = 1; i <= n; ++ i) {
            a.merge(i, p[i]);
        }
        a.reboot();
        for (int i = 1; i <= n; ++ i) {
            cout << a.dsus[i] << " \n"[i == n];
        }
    }
}

D

题目求 \(C_2\) 上的点到 \(C_1\) 上所有点的最小期望曼哈顿距离

设 \(C_2\) 上的点 \((x_0, y_0)\) 为使得 \(C_2\) 上的点到 \(C_1\) 上所有点的最小期望曼哈顿距离的点

设 \(EMD\) 为 \(C_1\) 到 \((x_0, y_0)\) 期望曼哈顿距离
设 \(MD(x, y)\) 为 \((x, y)\) 到 \((x_0, y_0)\) 曼哈顿距离

对于 \(C_1\) 上的点 \((x_1 + \Delta x, y_1 + \Delta y)\) 必然有 \((x_1 - \Delta x, y_1 - \Delta y)\) 使得

\(MD(x_1 + \Delta x, y_1 + \Delta y) = MD(x_1 - \Delta x, y_1 - \Delta y)\)

所以 \(EMD = MD(x_1, y_1)\)

即到 \((x_0, y_0)\) 期望曼哈顿距离就是 \(C_1\) 的圆心到 \((x_0, y_0)\) 的曼哈顿距离

那么我们只需要最小化这个曼哈顿距离即可

不妨反过来思考，我们在 \(C_2\) 上找一个点使得曼哈顿距离最小

在 \(C_1\) 的圆心为圆心画曼哈顿圆 \(MC_1\) ，当 \(MC_1\) 与 \(C_2\) 相切时，切点就是 \((x_0, y_0)\)

然后计算 \(MD(x_1, y_1, x_0, y_0)\) 即可

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll x11, y11, x12, y12;
        ll x21, y21, x22, y22;
        cin >> x11 >> y11 >> x12 >> y12;
        cin >> x21 >> y21 >> x22 >> y22;
        double x10 = (double)(x11 + x12) / 2.0, y10 = (double)(y11 + y12) / 2.0;
        double x20 = (double)(x21 + x22) / 2.0, y20 = (double)(y21 + y22) / 2.0;
        double d = sqrt(2ll * ((x22 - x21) * (x22 - x21) + (y22 - y21) * (y22 - y21))) / 4.0;
        double x0, y0;
        if (x10 < x20 && y10 < y20) {
            x0 = x20 - d;
            y0 = y20 - d;
        } else if (x10 < x20 && y10 > y20) {
            x0 = x20 - d;
            y0 = y20 + d;
        } else if (x10 > x20 && y10 < y20) {
            x0 = x20 + d;
            y0 = y20 - d;
        } else if (x10 > x20 && y10 > y20) {
            x0 = x20 + d;
            y0 = y20 + d;
        }
        double ans = abs(x0 - x10) + abs(y0 - y10);
        cout << fixed << setprecision(10) << ans << "\n";
    }
}

E

推理可得，答案和Alice的选择无关，那么我们只需要遍历Alice的数组，每次判断当前的首尾是不是也是Bob数组的首尾即可

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= n; ++ i) cin >> a[i];
        for (int i = 1; i <= n; ++ i) cin >> b[i];
        bool flag = 1;
        int l = 1, r = n;
        for (int i = 1; i <= n; ++ i) {
            if (a[i] == b[l] && a[n] == b[r]) {
                l ++;
            } else if (a[i] == b[r] && a[n] == b[l]) {
                r --;
            } else {
                flag = 0;
                break;
            }
        }
        if (flag) {
            cout << "Bob\n";
        } else {
            cout << "Alice\n";
        }
    }
}

F

根据二叉树的性质， \(n0 == n2 + 1\) ,若不符合则输出 \(-1\)

考虑贪心，优先把度为2的用完，再用1的

我们用队列模拟这个贪心的过程，队首为 \(x\) ，表示当前在第 \(x\) 层

所以如果需要往队列里添加节点的话 需要添加 \(x + 1\)

用 \(ans\) 记录最大层数即可

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n2, n1, n0;
        cin >> n2 >> n1 >> n0;
        int ans = -1;
        if (n0 == n2 + 1) {
            queue<int> q;
            q.push(0);
            ans = 0;
            while (!q.empty()) {
                int x = q.front(); q.pop();
                ans = x;
                if (n2) {
                    n2 --;
                    q.push(x + 1);
                    q.push(x + 1);
                } else if (n1) {
                    n1 --;
                    q.push(x + 1);
                }
            }
        }
        cout << ans << "\n";
    }
}

G

分析题目可得，由于原数组是“美丽”的，那么数组的首尾一定是相等的，并且其中有其他数字，也只是一个孤立的，因为如果有两个及以上，那么该数组就不“美丽”，自然地，只有把两个孤立的数字合并就可以了

要使两个孤立的数字合并，那么只需要删掉他们之间的所有数字就行
问题就被转化成了，最小的连续为k的子段，k即是数组头部的位置
注意当全部为一种时，要输出-1

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n; 
        cin >> n;
        int ans = n, cur = 0;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++ i) cin >> a[i];
        for (int i = 1; i <= n; ++ i) {
            if (a[i] != a[1]) {
                ans = min(ans, cur);
                cur = 0;
            } else {
                cur ++;
            }
        }
        ans = min(ans, cur);
        if (ans == n) ans = -1;
        cout << ans << "\n";
    }
}

H

看到要使直接连接的两个顶点没有相同的颜色，可以想到著名的四色问题
猜测至多只需要四种颜色就能填满
自然的，(在结点较多时)
我们给结点 1 染色 1
我们给结点 2 染色 2
我们给结点 3 染色 3
我们给结点 4 染色 4
5 可以选择 1 3 4
6 可以选择 2
7 可以选择 1 3
8 可以选择 1 2 4

目前不能找到什么规律，但是由于建边是根据异或的，我们可以尝试把5 6 7 8与其可以建边的点进行异或看看
5:
1 4
3 6
4 1
6:
2 4
7:
1 6
3 4
8:
1 9
2 10
4 12
可以发现5 6 7的异或值都有4
进一步思考

$xor(4n_1+k, 4n_2+k) = 4n (k \in {0, 1, 2, 3}, n \in N^*) $

即 \(4n+k\) 可以选用同一种颜色，因为 \(4n\) 一定是一个非质数，即这类点不会直接相连
由于题目需要输出最小的，将颜色不需要4种的特判即可

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        if (n < 6) {
            cout << n / 2 + 1 << "\n";
            int ans = 1, t = 1;
            for (int i = 1; i <= n; ++ i) {
                cout << ans << " \n"[i == n];
                ans += t % 2;
                t = (t + 1) % 2;
            }
        } else {
            cout << 4 << "\n";
            for (int i = 1; i <= n; ++ i) {
                cout << (i - 1) % 4 + 1 << " \n"[i == n];
            }
        }
    }
}

I

我们将 \(a, b, c, d\) 全部二进制展开

对每一位有

a a a a a
b 0 0 1 1
c 0 1 0 1
ans a 0 1 !a

按照这个表算出 \(a\) 即可

更进一步，我们发现 \(a = xor(b, d)\)

然后判断 \(a\) 是否合法即可

下面给出两种解法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll a, b, c, d;
        cin >> b >> c >> d;
        a = b ^ d;
        if ((a | b) - (a & c) != d) a = -1;
        cout << a << "\n";
    }
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tt = 1;
    cin >> tt;
    while (tt--) {
        bool flag = 1;
        ll a = 0, b, c, d;
        cin >> b >> c >> d;
        ll B = b, C = c, D = d;
        vector<int> al(65);
        for (int i = 0; i < 65; ++ i) {
            if (b % 2ll == c % 2ll) {
                al[i] = (d % 2ll) ^ (b % 2ll);
            } else if (b % 2ll ==  0 && c % 2ll == 1) {
                al[i] = 1;
            } else if (b % 2ll ==  1 && c % 2ll == 0) {

            } else {
                flag = 0;
                break;
            }
            b /= 2ll;
            c /= 2ll;
            d /= 2ll;
            if (b == 0 && c == 0 && d == 0) break;
        }
        for (int i = 64; i >= 0; -- i) {
            a = a * 2ll + al[i];
        }
        if ((a | B) - (a & C) != D) a = -1;
        cout << a << "\n";
    }
}

标签：2ll,ZZJCACM,int,题解,tt,cin,--,训练赛,using
From： https://www.cnblogs.com/Proaes/p/18624985

相关文章

  • 第36次ccf-csp题解（思维）
    比赛链接https://sim.csp.thusaac.com/contest/36/home 比赛感受这会刚打完上海icpc，比起区域赛的题，这个简单太多了。感受还不错，写的很顺手。除了第3题，其他3题都是一发过。刷题得长期刷。      A题移动 题意：f:y+1; b:y-1; ......
  • 期望问题+ybt题解
    算法理解对于随机变量\(X\)，有\(n\)个可能的取值，取值为\(x_i\)有\(P(x_i)\)的概率，则它的数学期望则为\(E(X)=\sum_{i=1}^nx_iP(x_i)\)性质其中期望的线性限制最重要，它可以将两个完全独立的期望拆分开来单独计算，详见例题T1：首先我们观察有\(n\)道题，我们根据期望的线......
  • 题解：CF2048F Kevin and Math Class
    Problemstatement给定长度为\(n\)的数组\(a,b\)，每次操作可以任意选择一个区间\([l,r]\)，记\(x=\displaystyle\min_{l\leqi\leqr}b_i\)，然后\(\foralla_i(i\in[l,r]),a_i\leftarrow\lfloor{\frac{a_i}{x}}\rfloor\)，求最终使得\(a_i\)均变为\(1\)的最小操作次......
  • 题解：P11411 兰奇的卡牌游戏
    题解：P11411兰奇的卡牌游戏今天来讲一个超级缝合题目，所以要先讲一些前置。前置知识\(1\)——单调栈[USACO06NOV]BadHairDayS题目入口题目描述农夫约翰有\(N\)头奶牛正在过乱头发节。每一头牛都站在同一排面朝右，它们被从左到右依次编号为\(1,2,\cdots,N\)。编号......
  • 2024年“华为杯”天津大学程序设计竞赛（新生赛）个人题解
    A.谁来自智算学部模拟#include<bits/stdc++.h>#defineintlonglong#definepiipiar<int,int>#definedbdoubleusingnamespacestd;intans[5];voidsolve(){ intn;cin>>n; while(n--){ stringstr;cin>>str; if(str.substr(4,......
  • AT_keyence2019_e Connecting Cities 题解
    题目传送门前置知识Boruvka算法解法考虑Boruvka算法。拆掉绝对值后得到\(a_{i}+id,a_{i}-id,a_{j}+id,a_{j}-id\)四个式子。vector启发式合并辅助线段树查询的常数过大，无法通过。上述做法的常数在于一条边会被计算两次，考虑优化。不妨直接钦定向前连、向后连的贡献，顺......
  • .net framework 4.7.2 winform框架项目升级到.net 8.0项目 界面比列失调问题解决
    一、问题发生前：在.netframework4.7.2winform框架开发的项目之前在.netframework4.7.2开发的winform项目，在visualstudio一打开的时候，虽然界面内有些控件也会失调，但是他会提示“使用100%缩放比例重新启动VisualStudio”点击“使用100%缩放比例重新启动VisualStudio”......
  • 题解 - 换位置游戏
    题目描述N个小朋友（编号为1到N）正在玩一个换位置游戏。从左到右依次排列着N个凳子（编号为1到N，最左边的为1号凳子，最右边的为N号凳子），每个凳子上都有一个数字（凳脚处红色数字），每个数字互不相同，且都是不超过N的正整数。游戏开始前，1号小朋友坐在1号凳子上，2号小......
  • push代码报错fatal: Authentication failed的问题解决
    在不使用pat之前，我的centos系统不能向github提交代码，然后我在github上申请了pat并且配置，可以成功提交代码了，而且还免除了输入用户名和密码的麻烦。如何申请pat（咨询文心快码就可以得到答案）：如何在git上配置pat（继续咨询文心快码）：配置完成之后，问题得到解决，现在可以正常的push代码......
  • 题解：P11410 闪耀之塔
    题解：P11410闪耀之塔https://www.luogu.com.cn/problem/P11410我们要想讲讲前置知识——蒙哥马利快速幂模求逆元。前置知识逆元定义何为逆元？逆元，又称数论倒数。若整数\(a\)、\(b\)满足同余方程\(a*b=1(mod\n)\)，那么\(a\)，\(b\)互为模\(n\)意义下的逆元。前置\(......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99