ACM训练记录|Codeforces Round #747 (Div. 2) c++|acm竞赛|数据结构|编程语言

Codeforces Round #747 (Div. 2) 写在前面：这场比赛个人觉得出的题蛮不错的，很有质量，真的推荐能够看到这个我的这个补题记录的人可以去试着做一做
Problem - 1594A - Codeforces-Consecutive Sum Riddle 题目大意：
给定T组数据，然后找到一个l和r，l是负数到0，r可以理解为是从1到r
实现思路：
1的时候特判，其他时候输出-(n - 1), n
代码实现：

/* * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了 * @Write Up: https://github.com/godhandsjoker/ACM- * @Author: godhands * @LastEditors: godhands * @LastEditTime: 2021-10-08 23:10:02 */ #include #include #include #include #include #include using namespace std; #define int long long signed main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while(T--) {int n; cin >> n; if (n == 1) cout << "0 1\n"; else {cout << -(n - 1) << " " << n << "\n"; } } return 0; }

Problem - 1594B - Codeforces-Special Numbers 题目大意：
给定T组数据，然后每组一个n一个k，n代表底数，然后找n的非负整数之和，找第k个
实现思路：
【ACM训练记录|Codeforces Round #747 (Div. 2)】直接看他二进制就可以，二进制为1就是可以进行一个qpow(n, i, mod)的运算，这里可以自己手动模拟，也可以学习一下bitset，这个容器用处很不错
代码实现：

#include #include #include #include #include #include #include using namespace std; #define int long longconst int mod = 1e9 + 7; int qpow(int a, int b) { int res = 1; while(b) {if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } int qpow(int a, int b, int mod) { int res = 1 % mod; a %= mod; while(b) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }signed main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while(T--) {int n, k; cin >> n >> k; bitset<30> bs(k); int res = 0; for (int i = 0; i < 30; i++) {if (bs[i] == 1) {res = (res % mod + qpow(n, i, mod) % mod) % mod; } } cout << res << "\n"; } return 0; }

Problem - 1594C - Codeforces-Make Them Equal 题目大意：
首先是T组数据，然后我们输入一个n代表字符串的长度，然后这里我们要注意一个问题，就是我们的这个字符串的下标是从1开始的，然后我们输入一个字符，接下来就是一个字符串，我们的目的就是把这个字符串里面的所有字符都给变成跟我们一开始给定的字符一样的字符，问需要多少次，然后把数字输出，这里的数字是你自由选择的，从1到n，这个数字的作用就是让不是这个数字的倍数的地方全都变成我们的那个字符
实现思路：
我一下子想到了一个假的做法，就是我们搞最后的n和n - 1，但是其实仔细想想是不对的，然后这里给出一个正解的做法，其实这个也不算是假的做法，只不过他对一一种情况的判断少了点东西，我们这里给出一个正解，首先我们是可以对我们这里的每一个x都进行一个计算，如果我们发现了这么一个问题，就是发现对于一个x，他的倍数所对应的地方都是跟我们要求的那个特殊的c是一模一样的话，咱们其实就是可以直接选择这个x，用一次操作就可以了，如果不可以的话，我们就肯定是至少需要两次，那我们就是可以直接选择n - 1和n，这里其实仔细想想，这里经过第一步其实已经是保证了一个问题就是，他俩的这个位置是一定不会是等于我们要的这个数的
代码实现：

#include #include #include #include #include #include using namespace std; void solve() { int n; char c; string s; cin >> n >> c >> s; int cnt = 0; for (auto &it : s) if (it != c) cnt++; if (cnt == 0) {cout << "0\n"; return ; } for (int i = 1; i < n; i++) {bool flag = true; for (int j = i; j < n; j += i + 1) {if (s[j] != c) {flag = false; break; } } if (flag) {cout << "1\n" << i + 1 << "\n"; return; } } cout << "2\n" << n - 1 << " " << n << "\n"; } signed main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while(T--) {solve(); } return 0; }

注意双层for循环的那里，我们一定要注意好下标，我们底下的时候要+1，因为不+1会出错，大家可以仔细思考一下这个问题
Problem - 1594D - Codeforces-The Number of Imposters 题目大意：
首先还是T组数据，然后每组都是n个人，m句话，然后我们可以进行这么一个操作，就是一个人说另一个人说的话是真的还是假的，然后我们问最多的说假话的数量
实现思路：
首先我们得先把问题转换，我们可以发现这么一个问题，就是我们如果从图的角度来考虑这个问题，那么我们看这么一个问题，就是我们说真话和说假话的如果点定为1和0，那么我们会发现他们的边就是他们的一个异或值，然后不论谁对谁都是一样的，那么我们这时候应该怎么办呢，我们是不是就可以抽象出来这么的一个问题，就是现在有一张无向图，我们要让说假话的人尽可能的多，我们可以用维护到根节点的并查集来解决这个问题，然后cf的官方题解给了这么两种写法，第一个，我们构建这么一个图，然后如果A说B是假，那么我们添加从A到B的边，如果A说B是好的，那么我们添加一个从A到一个假的节点的边，然后从同一个假节点到B的边，然后对于每一个我们检查他是否是矛盾的，如果矛盾-1，否则我们就是可以让其中一个节点为真，一个节点为假，然后找到一个最大值，然后cf官方给的第二种方法就是，我们用这种办法来构建我们的这个图形，如果A和B在同一个团队里面，我们就是可以添加权重为0的边，否则就是添加权重为1的边，然后我们可以用dfs来把节点染色成为0或者1，然后保证异或可以满足我们上述的条件
代码实现：

#include #include #include #include #include #include using namespace std; #define int long long const int N = 2e6 + 10; int f[N], dis[N], val[N][10]; int find(int u) { if (f[u] == u) return u; int tmp = f[u]; f[u] = find(f[u]); dis[u] = dis[u] ^ dis[tmp]; return f[u]; }void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) {f[i] = i, dis[i] = 0, val[i][0] = val[i][1] = 0; } bool flag = true; for (int i = 1; i <= m; i++) {int a, b; string s; cin >> a >> b >> s; int fa = find(a), fb = find(b); if (s == "imposter") {if (fa == fb && (dis[a] ^ dis[b] == 0)) flag = false; if (fa == fb) continue; dis[fa] = 1 ^ dis[a]; f[fa] = b; } else {if (fa == fb && (dis[a] ^ dis[b] == 1)) flag = false; if (fa == fb) continue; dis[fa] = 0 ^ dis[a]; f[fa] = b; } } if (flag) {long long res = 0; for (int i = 1; i <= n; i++) val[find(i)][dis[i]]++; for (int i = 1; i <= n; i++) res += max(val[i][0], val[i][1]); cout << res << "\n"; } else {cout << "-1\n"; } } signed main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int T; cin >> T; while(T--) {solve(); } return 0; }

Problem - 1594E1 - Codeforces-Rubik’s Cube Coloring (easy version) 题目大意：
输入一个n，然后输出有多少种染色情况，就是一颗二叉树然后相邻不能染色，然后因为他是魔方类比过来的，然后按照题目给的描述，限定颜色是怎么染色的
实现思路：
直接根节点的时候有6种情况，其他的时候就是每一个节点就是只剩下了4种情况，然后用快速幂跑一遍就可以了
代码实现：

/* * @Description: 电影和人生不一样，电影太仁慈了，人生太辛苦了 * @Write Up: https://github.com/godhandsjoker/ACM- * @Author: godhands * @LastEditors: godhands * @LastEditTime: 2021-10-09 03:57:59 */ #include #include #include #include #include #include using namespace std; #define int long long const int mod = 1e9 + 7; int qpow(int a, int b) { int res = 1; while(b) {if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } int qpow(int a, int b, int mod) { int res = 1 % mod; a %= mod; while(b) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }signed main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout); #endif ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int n; while(cin >> n) {if (n == 1) {cout << "6\n"; continue; } int res = 6ll; res = res % mod * qpow(4, (1ll << n) - 2, mod) % mod; cout << res << "\n"; } return 0; }

这个题让我想到了之前的一个题，就是不可以使用对次幂直接取模，得减去一个1来再取模，但是我忘记具体是哪一个了