山西网站开发公司,园林景观设计公司计划书,seo的主要分析工具,免费咨询医生在线解答CF1550E Stringforces
题意#xff1a;
设 s 是一个由前 k 个小写字母构成的字符串#xff0c;v 是前 k 个小写字母中的某一个。定义MaxLen(s,v)\mathrm{MaxLen}(s,v)MaxLen(s,v) 表示 s 所有仅由字母 v 构成的连续子串的最长长度。 定义 s 的价值为所有 MaxLen(s,v)\mathr…CF1550E Stringforces
题意
设 s 是一个由前 k 个小写字母构成的字符串v 是前 k 个小写字母中的某一个。定义MaxLen(s,v)\mathrm{MaxLen}(s,v)MaxLen(s,v) 表示 s 所有仅由字母 v 构成的连续子串的最长长度。 定义 s 的价值为所有 MaxLen(s,v)\mathrm{MaxLen}(s,v)MaxLen(s,v) 的最小值其中 v 取遍前 k 个小写字母。 现在给定一个长度为 n 的字符串 ss 中字母要么是前 k 个小写字母中的某一个要么是问号。你需要将 s 中的每一个问号替换成前 k 个小写字母中的一个并最大化 s 的价值。方便起见你只需要输出这个最大的价值即可。 保证 1≤n≤2×1051≤k≤171\leq n\leq 2\times 10^5 1\leq k\leq 171≤n≤2×1051≤k≤17。
题解
又是一个状压dp与线性dp的结合 k17求最大化的MaxLen(s,v)的最小值 不难想到是状压dp二分然后就卡住了 二分答案然后判断mid是否成立mid成立的条件是要满足所有的MaxLen(s,v)\mathrm{MaxLen}(s,v)MaxLen(s,v)大于等于mid。那我们就在原串中找是否存在一个长度为mid的全部由第i个字符构成的连续子串(i∈k),且这k个区间互不相交 然后就可以再check中利用状压dp判断mid设dp[i]表示已经解决需求的字符种类的状态为x时所选区间的最右端点的最小值。很显然当dp[i]n是合法的说明可以取到这样的区间 对于dp的转移我们需要知道指定字符在之后区间出现的位置这样才知道是否可以转移所有我们设数组pos[i][j]pos[i][j]pos[i][j]表示区间[j,n]匹配字符i的最早位置预处理出pos这样之后就可以O(1)转移 状态转移方程为 dp[x]min(1i)∈xpos[i][dp[x−(1i)]1]dp[x]min_{(1i)∈x}pos[i][dp[x-(1i)]1]dp[x]min(1i)∈xpos[i][dp[x−(1i)]1] 含义就是状态x可以由状态x-(1i)然后在区间[dp[x−(1i)]1,n][dp[x-(1i)]1,n][dp[x−(1i)]1,n]中选择字符i转移得到
代码
#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 ONLINE_JUDGE
#elsestartTime clock();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
int n, k;
const int mx (1 18) 9;
int dp[mx];
char s[maxn];
int pos[20][mx];
bool check(int mid)
{//先预处理出pos[][]for (int i 0; i k; i) {int num 0;for (int j n; j 1; j--) {if (s[j] a i || s[j] ?) //如果是第k个字符或者是?num; //符合我们要求连续elsenum 0; //否则中断if (num mid) //如果连续长度大于等于midpos[i][j] j mid - 1; //记录最左侧情况else //如果小于midpos[i][j] pos[i][j 1];}}memset(dp, INF_int, sizeof(dp));dp[0] 0;for (int i 1; i (1 k); i) { //枚举状态for (int j 0; j k; j) { //对于每个字符考虑if ((i j) 1) { //如果当前状态有这个字符if (dp[i - (1 j)] ! INF_int) { //如果去掉这个字符的状态存在if (pos[j][dp[i - (1 j)] 1]) { //如果后面的区间内有字符jdp[i] min(dp[i], pos[j][dp[i - (1 j)] 1]); //最小化所有区间右端点}}}}}return dp[(1 k) - 1] n;
}
int main()
{//rd_test();read(n, k);cin (s 1);int l 1, r n / k;int res 0;while (l r) {int mid l r 1;if (check(mid)) {res mid;l mid 1;}elser mid - 1;}cout res endl;//Time_test();
}
