电子商务网站系统规划 案例分析,dremrever做网站流程,腾讯云wordpress插件下载,现货交易平台合法吗cf1555D. Say No to Palindromes
题意#xff1a;
给出一个字符串#xff0c;长度为n#xff0c;而且都是a,b,c三个字符构成的#xff0c;然后有m个询问 每个询问给出l r#xff0c;问要想这个区间内任意长度字串都不是回文子串#xff0c;至少要改多少个字符
题解
给出一个字符串长度为n而且都是a,b,c三个字符构成的然后有m个询问 每个询问给出l r问要想这个区间内任意长度字串都不是回文子串至少要改多少个字符
题解
我们思考一下什么样的字符是符合要求的
长度为2相邻两个字符不能相同长度为3间隔为1的字符不能一样长度为4只要不满足长度为2和长度为3的情况一定不是回文串
也就是只要不满足长度为2和长度为3的字符情况就是符合要求的。要符合这两个要求可以得知要求每三个字符都是不一样的一共就三个字符我们将三个字符全排列。 一个符合要求的字符串一定循环的且循环节有6种情况abc,acb,bac,bca,cab,cba 这样就可以实现三个位置都不相同 我们用前缀和预处理用前缀和来实现
代码
// Problem: D. Say No to Palindromes
// Contest: Codeforces - Educational Codeforces Round 112 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1555/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Data:2021-08-18 11:42:57
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 3e5 9;
string s1[10];
ll diff[10][maxn];
int main()
{//rd_test();ll n, m;read(n, m);string s;cin s;s # s; //为了下标从1开始s1[1] #;while (s1[1].size() n)s1[1] abc;s1[2] #;while (s1[2].size() n)s1[2] acb;s1[3] #;while (s1[3].size() n)s1[3] bac;s1[4] #;while (s1[4].size() n)s1[4] bca;s1[5] #;while (s1[5].size() n)s1[5] cab;s1[6] #;while (s1[6].size() n)s1[6] cba;//Time_test();for (int i 1; i 6; i) {diff[i][0] 0;for (int j 1; j n; j) {if (s1[i][j] s[j])diff[i][j] diff[i][j - 1];elsediff[i][j] diff[i][j - 1] 1;}}// cout -- endl;while (m--) {int l, r;read(l, r);ll ans INF_int;for (int i 1; i 6; i) {ans min(ans, diff[i][r] - diff[i][l - 1]);}printf(%lld\n, ans);}return 0;
}
