CF1594C Make Them Equal

发布时间:2022-07-03 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了CF1594C Make Them Equal脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

在想只有一个数的时候混乱了,先思考再开码很重要

https://codeforces.COM/contest/1594/PRoblem/C

题意

给定一个字符串和目标字符 (c),每次操作可以选中一个 (i),并将所有 (j, jmod 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(nLOG 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全部内容,希望文章能够帮你解决CF1594C Make Them Equal所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。