CF1594C Make Them Equal
2021/10/13 6:14:43
本文主要是介绍CF1594C Make Them Equal,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
在想只有一个数的时候混乱了,先思考再开码很重要。
https://codeforces.com/contest/1594/problem/C
题意
给定一个字符串和目标字符 \(c\),每次操作可以选中一个 \(i\),并将所有 \(j,\ j\mod i \not= 0\) 位置处的字符变为\(c\),问最少多少次操作可以将整个字符串上的每个数都变成目标字符。
Turotial
首先容易发现第一次选 \(n\), 第二次选 \(n-1\) 一定可以将整个串变成目标串。
接下来只需要考虑能不能选择一个数就将串变成目标串。自然想到可以枚举 \(i,\ i \in [2,n]\),对于每个 \(i\) 检查是否存在 \(a_j \not = c,\ j \equiv 0 \mod i\),如果存在,则说明选当前的 \(i\) 时 \(a_j\) 不会被消除,那么当前 \(i\) 是无效的。直接枚举 \(i\) 的倍数处字符,复杂度为调和级数 \(O(n\log n)\).
点击查看代码
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <vector> typedef long long ll; #define endl '\n' #define P pair<int, int> #define IOS \ ios::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); using namespace std; const int N = 3e5 + 5; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; // int visit[N]; bool isprime[N], vis[N]; int prime[N]; string s; void Prime() { memset(isprime, true, sizeof isprime); isprime[0] = isprime[1] = false; for (int i = 2; i <= N; i++) { if (!isprime[i]) continue; prime[++prime[0]] = i; for (int j = 2; i * j <= N; j++) { isprime[i * j] = false; } } } void divide(int x) { for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= x; i++) { if (x % prime[i] == 0) vis[prime[i]] = 1; while (x % prime[i] == 0) { x /= prime[i]; } } if (x >= 1) vis[x] = 1; } int num[N], tot; int main() { IOS int T; cin >> T; int n; char to; while (T--) { tot = 0; cin >> n >> to >> s; for (int i = 0; i < n; i++) if (s[i] != to) tot++; if (tot == 0) { cout << 0 << endl; } else if (tot == 1) { cout << 1 << endl; if (s[n - 2] == to) cout << n - 1 << endl; else cout << n << endl; } else { bool f = 0; s = "-" + s; for (int i = 1; i <= n; i++) { bool ff = 1; for (int j = i; j <= n; j += i) { if (s[j] != to) { ff = 0; break; } } if (ff) { cout << 1 << endl << i << endl; f = 1; break; } } if (f) continue; cout << 2 << endl << n - 1 << " " << n << endl; } } }
这篇关于CF1594C Make Them Equal的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享