首页 > 其他分享 >题解:[BZOJ2958] 序列染色

题解:[BZOJ2958] 序列染色

时间:2024-11-07 15:11:05浏览次数:1  
标签:题解 tt 染色 字符串 长度 include sum BZOJ2958

Problem Link

BZOJ2958 序列染色

题意

给出一个长度为 \(n\),由 \(\tt B,W,X\) 三种字符组成的字符串 \(S\),你需要把每一个 \(\tt X\) 染成 \(\tt B\) 或 \(\tt W\) 中的一个。

Solution

字符串,染色,方案数,一眼 \(dp\)。

要求前半段是 B,后半段是 W。考虑容斥。

\(f_{i, 0/1}, g_{i, 0/1}, h_{i, 0/1}\) 代表选到第 \(i\) 位的方案,\(0\) 代表填 B,\(1\) 代表填 W,\(f\) 代表没有长度为 \(k\) 的带 B 字符串,\(g\) 代表有长度为 \(k\) 的带 B 字符串但没有长度为 \(k\) 的带 W 字符串,\(h\) 代表既有长度为 \(k\) 的带 B 字符串,又有长度为 \(k\) 的带 B 字符串。

显然,只有 XB 可以填 B,只有 XW 可以填 W。所以从 \(i - 1\) 转移时只需分类讨论填 BW,即:

\[ s_i \ne B:\\ f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1},\\ g_{i, 0} = g_{i - 1, 0} + g_{i - 1, 1},\\ h_{i, 0} = h_{i - 1, 0} + h_{i - 1, 1} \\ s_i \ne W:\\ f_{i, 1} = f_{i - 1, 0} + f_{i - 1, 1},\\ g_{i, 1} = g_{i - 1, 0} + g_{i - 1, 1},\\ h_{i, 1} = h_{i - 1, 0} + h_{i - 1, 1} \]

从 \(i - k\) 转移时只需保证 $\left [ i - k, i \right ] $ 中可以全填 BW,即:

\[ sum_{i, 0} = sum_{i - k, 0}:\\ g_{i, 1} = g_{i, 1} - g_{i - k, 0},\\ h_{i, 1} = h_{i, 1} + g_{i - k, 0} \\ sum_{i, 1} = sum_{i - k, 1}:\\ f_{i, 0} = f_{i, 0} - f_{i - k, 1},\\ g_{i, 0} = g_{i, 0} + f_{i - k, 1} \]

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string.h>
#include <cstring>
using namespace std;

#define Maxn 1000005
#define Mod 1000000007
#define fo(i, l, r) for(int i = l; i <= r; ++i)

int n, k, a[Maxn], sum[Maxn][2], f[Maxn][2], g[Maxn][2], h[Maxn][2]; // f : no B, g : have B && no W, h : have B && have W
char s[Maxn];

void Input_data()
{  
    scanf("%d%d%s", &n, &k, (s + 1));
    fo(i, 1, n) sum[i][0] = sum[i - 1][0], sum[i][1] = sum[i - 1][1], (s[i] == 'B') && (++sum[i][0], a[i] = 1, 0), (s[i] == 'W') && (++sum[i][1], a[i] = 2, 0);
    // fo(i, 1, n) cerr << a[i] << " " << sum[i][0] << " " << sum[i][1] << " " << endl;
}

void Solve() 
{
    f[0][1] = 1;
    fo(i, 1, n) {
        if(a[i] != 2) f[i][0] = (f[i - 1][0] + f[i - 1][1]) % Mod, g[i][0] = (g[i - 1][0] + g[i - 1][1]) % Mod, h[i][0] = (h[i - 1][0] + h[i - 1][1]) % Mod;
        if(a[i] != 1) f[i][1] = (f[i - 1][0] + f[i - 1][1]) % Mod, g[i][1] = (g[i - 1][0] + g[i - 1][1]) % Mod, h[i][1] = (h[i - 1][0] + h[i - 1][1]) % Mod;
        // cerr << "f[" << i << "][0] : " << f[i][0] << " " << "f[" << i << "][1] : " << f[i][1] << endl;
        if(i < k) continue;
        if(sum[i][0] == sum[i - k][0]) g[i][1] = (g[i][1] - g[i - k][0] + Mod) % Mod, h[i][1] = (h[i][1] + g[i - k][0]) % Mod;
        if(sum[i][1] == sum[i - k][1]) f[i][0] = (f[i][0] - f[i - k][1] + Mod) % Mod, g[i][0] = (g[i][0] + f[i - k][1]) % Mod;
    }
}

void Print_ans()
{
    printf("%d", (h[n][0] + h[n][1]) % Mod);
}


int main()
{
    Input_data();

    Solve();

    Print_ans();

    return 0;
}

标签:题解,tt,染色,字符串,长度,include,sum,BZOJ2958
From: https://www.cnblogs.com/naughty-naught/p/18532262

相关文章

  • IOR的脚本化、版本兼容性及常见问题解答
    脚本化IOR可以使用-f选项在命令行中使用输入脚本。在-f选项之前设置的命令行选项将被视为运行脚本的默认设置。例如:mpirun./ior-W-fscript将使用隐式-W运行脚本中的所有测试。脚本本身可以覆盖这些设置,并且可以设置为在一次执行下运行许多不同的IOR测试,重要的是要注意在-......
  • 【题解】CF1944
    CF1944A简要题意给定完全图删k条边使得从一号点开始的可达点最少Solution注意到最多需要删n-1条边就可以使得任意一个其他点都到达不了又注意到只要删的边少于n-1就可以从一号点走出去,主要走出去就可以走到任何点所以这题答案只有两种如果k≤n-1答案为n否则答案为1......
  • 题解:P11248 [GESP202409 七级] 矩阵移动
    题目传送门题目大意给出一个nnn行mmm列的只包含0、1、?的矩......
  • 【记录】Cordial Sync具身智能协作源码复现及问题解决
    论文简要总结智能体需要合作将家具移动到客厅的指定位置。这个任务与现有的任务不同,它要求智能体在每个时间步都必须进行协调。模型部分1.SYNC-policies(SynchronizeYourActionsCoherently)为了解决智能体在每个时间步都需要协调的问题,研究者提出了SYNC-policies。这......
  • AtCoder Beginner Contest 284题解
    AtCoderBeginnerContest284A没有什么难点,反着输出一遍就可以了。#include<bits/stdc++.h>usingnamespacestd;stringa[2000];intmain(){ intn; cin>>n; for(inti=1;i<=n;i++)cin>>a[i]; for(inti=n;i;i--)cout<<a[i]<<'\n';......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......
  • CF 1438 题解
    CF1438题解ASpecificTastesofAndre考虑一种非常简单的构造:\(a_i=1\).不难发现满足条件.BValeriiAgainstEveryone结论:符合条件当且仅当有两个一样的元素.证明:充分性显然,下证必要性.若不存在两个一样的元素,则由于无法进位,故没有办法得到两个区间和在相......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • CF2001 题解
    A给定循环数组,每次操作时,设当前大小为m。选择$i\in[0,m)$,若满足$a_i\lea_{i+1\bmodm}$,则可删除$a_i,a_{i+1\bmodm}$中的任意一个。求最小的操作次数,使得数组中所有元素都相等。$n\le100$操作非常强,除了两个相邻位置相等的情况,可以删除任意元素。然而所有位置都......
  • 暂存的题解
    P4011孤岛营救问题感觉其实我能想出来,但是对难题产生了恐惧,直接看题解了,确实简单,很抱歉浪费了一道题。数据范围很小,搜索bfs,钥匙直接状态压缩,找到答案立即返回,否则就无解。我们要彻底的分析问题,为什么我想不到,以后我要怎么总结,首先看到题之后要先看数据范围,看到数据范围非常小......