在本文中，我们将为您详细介绍Codeforces1132A——RegularBracketSequence的相关知识，并且为您解答关于水题的疑问，此外，我们还会提供一些关于@codeforces-11
在本文中，我们将为您详细介绍Codeforces1132A——Regular Bracket Sequence的相关知识，并且为您解答关于水题的疑问，此外，我们还会提供一些关于@codeforces - 1106F@ Lunar New Year and a Recursive Sequence、BZOJ 5381 or & Codeforces 623E Transforming Sequence DP+NTT、CodeForces - 524F And Yet Another Bracket Sequence、CodeForces - 750E New Year and Old Subsequence的有用信息。
本文目录一览：- Codeforces1132A——Regular Bracket Sequence（水题）
- @codeforces - 1106F@ Lunar New Year and a Recursive Sequence
- BZOJ 5381 or & Codeforces 623E Transforming Sequence DP+NTT
- CodeForces - 524F And Yet Another Bracket Sequence
- CodeForces - 750E New Year and Old Subsequence
Codeforces1132A——Regular Bracket Sequence（水题）
Regular Bracket Sequence
time limit per test:1 second
memory limit per test:256 megabytes
input:standard input
output:standard output
A string is called bracket sequence if it does not contain any characters other than “(” and “)”. A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters “+” and “1” into this sequence. For example, “”, “(())” and “()()” are regular bracket sequences; “))” and “)((” are bracket sequences (but not regular ones), and “(a)” and “(1)+(1)” are not bracket sequences at all.
You have a number of strings; each string is a bracket sequence of length 222. So, overall you have cnt1cnt1cnt1 strings “((”, cnt2cnt2cnt2 strings “()”, cnt3cnt3cnt3 strings “)(” and cnt4cnt4cnt4 strings “))”. You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length 2(cnt1+cnt2+cnt3+cnt4)2(cnt1+cnt2+cnt3+cnt4)2(cnt1+cnt2+cnt3+cnt4). You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either.
Input
The input consists of four lines, iii-th of them contains one integer cnticnt_icnti (0≤cnti≤109)(0≤cnt_i≤10^9)(0≤cnti≤109).
Output
Print one integer: 111 if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, 000 otherwise.
Examples
input
3
1
4
3
output
1
input
0
0
0
0
output
1
input
1
2
3
4
output
0
Note
In the first example it is possible to construct a string “(())()(()((()()()())))”, which is a regular bracket sequence.
In the second example it is possible to construct a string “”, which is a regular bracket sequence.
Solve
你有四种括号，"(("，"()"，")("，"))"， 给出四种括号的数量， 问能否将这些括号以某种顺序连接起来， 使得每个左括号都有与之匹配的右括号。
观察可以发现：如果要完全匹配，() 是不会对结果产生影响的，然后可以推出一个关系式：cnt1=2×cnt3+cnt4,cnt4=2×cnt3+cnt1cnt1=2\times cnt3+cnt4,cnt4=2\times cnt3+cnt1cnt1=2×cnt3+cnt4,cnt4=2×cnt3+cnt1
即：当 cnt3≠0,cnt1=cnt4≠0cnt3\neq0,cnt1=cnt4\neq0cnt3̸=0,cnt1=cnt4̸=0 或 cnt3=0,cnt1=cnt2cnt3=0,cnt1=cnt2cnt3=0,cnt1=cnt2 时，才会完全匹配
Code
/*************************************************************************
> Author: WZY
> School: HPU
> Created Time: 2019-03-15 10:34:53
************************************************************************/
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstring>
#include <limits.h>
#include <iostream>
#include <algorithm>
#include <random>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <random>
#define ll long long
#define ull unsigned long long
#define lson o<<1
#define rson o<<1|1
#define ms(a,b) memset(a,b,sizeof(a))
#define SE(N) setprecision(N)
#define PSE(N) fixed<<setprecision(N)
#define bug cerr<<"-------------"<<endl
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"
#define LEN(A) strlen(A)
const double E=exp(1);
const double eps=1e-9;
const double pi=acos(-1.0);
const int mod=1e9+7;
const int maxn=1e6+10;
const int maxm=1e3+10;
const int moha=19260817;
const int inf=1<<30;
const ll INF=1LL<<60;
using namespace std;
inline void Debug(){cerr<<''\n'';}
inline void MIN(int &x,int y) {if(y<x) x=y;}
inline void MAX(int &x,int y) {if(y>x) x=y;}
inline void MIN(ll &x,ll y) {if(y<x) x=y;}
inline void MAX(ll &x,ll y) {if(y>x) x=y;}
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
cerr<<arg<<"";Debug(rest...);}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);cin.tie(0);
cout.precision(20);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
srand((unsigned int)time(NULL));
#endif
int cnt1,cnt2,cnt3,cnt4;
while(cin>>cnt1>>cnt2>>cnt3>>cnt4)
{
if(cnt1+cnt4==0)
{
if(cnt3)
cout<<0<<endl;
else
cout<<1<<endl;
continue;
}
if(cnt1==cnt4)
cout<<1<<endl;
else
cout<<0<<endl;
}
#ifndef ONLINE_JUDGE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s.\n";
#endif
return 0;
}
@codeforces - 1106F@ Lunar New Year and a Recursive Sequence
[toc]
@description@
定义递推数列 f：
（1）f[1] = f[2] = ... f[k-1] = 1，f[k] 是一个未知量。 （2）f[i] = (f[i-1]^b[1]) * (f[i-2]^b[2]) * ... *(f[i-k]^b[k]) mod 998244353。
其中 k 和 b[1...k] 是给定的常量。现在已知数列的第 n 项 f[n] = m，求 f[k]。
input 第一行一个整数 k (1 <= k <= 100)。 接下来一行 k 个整数 b1, b2, ..., bk (1 <= bi < 998244353)。 接下来一行两个整数 n, m (k < n <= 10^9, 1 <= m < 998244353)。
output 输出 fk 的值。若不存在，输出 -1。若多解，输出任意一个。
sample input 3 2 3 5 4 16 sample output 4
@solution@
首先，我们想要在 fk 与 fn 之间建立关系。
不难猜想到 fn = fk^x，同时这也暗示我们可以将 1 看成 fk^0。
这样的话原本是非线性递推式，就可以变成指数的线性递推式。可以用矩阵快速幂解出 x 的值。
现在，我们已知 fk^x = fn = m mod 998244353，想要解出 fk 的值。
这是一个经典的数论问题：高次剩余。它有一些复杂的方法，但是对于这个特殊的模数，我们还有一种较为简洁的方法：利用原根。
根据原根的性质，我们可以将任意一个数写成原根的幂的形式。这样上面的式子就会变为 g^(px) = g^q mod 998244353。
通过 BSGS 可以快速解出 q 的值。这样我们只需要根据指数相等列出同余方程用 exgcd 解出 p 的值就可以解决此题了。
@accepted code@
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int MAXK = 100 + 5;
const int MOD = 998244353;
const int MODPW = MOD - 1;
const int HASHSIZE = 1000037;
struct node{
int ind, key;
node(int _i=0, int _k=0):ind(_i), key(_k){}
};
vector<node>h[HASHSIZE];
void hash_insert(int n, int x) {
h[x%HASHSIZE].push_back(node(n, x));
}
int hash_search(int x) {
int y = x%HASHSIZE;
for(int i=0;i<h[y].size();i++)
if( h[y][i].key == x ) return h[y][i].ind;;
return -1;
}
void hash_clear() {
for(int i=0;i<HASHSIZE;i++)
h[i].clear();
}
struct matrix{
int m[MAXK][MAXK];
int r, c;
}A, B;
matrix operator * (matrix A, matrix B) {
matrix C; C.r = A.r, C.c = B.c;
for(int i=0;i<C.r;i++)
for(int j=0;j<C.c;j++) {
C.m[i][j] = 0;
for(int k=0;k<A.c;k++)
C.m[i][j] = (C.m[i][j] + 1LL*A.m[i][k]*B.m[k][j]%MODPW)%MODPW;
}
return C;
}
matrix mpow(matrix A, int p) {
matrix ret; ret.r = ret.c = A.r;
for(int i=0;i<ret.r;i++)
for(int j=0;j<ret.c;j++)
ret.m[i][j] = (i == j);
while( p ) {
if( p & 1 ) ret = ret*A;
A = A*A;
p >>= 1;
}
return ret;
}
int solve1() {
int k, n; scanf("%d", &k);
for(int i=0;i<k;i++) scanf("%d", &A.m[k-1][k-i-1]);
A.r = A.c = B.r = k; B.c = 1;
for(int i=0;i<k;i++) B.m[i][0] = 0;
B.m[k-1][0] = 1;
for(int i=0;i<k-1;i++)
for(int j=0;j<k;j++)
A.m[i][j] = 0;
for(int i=0;i<k-1;i++) A.m[i][i+1] = 1;
scanf("%d", &n); B = mpow(A, n-k)*B;
return B.m[k-1][0];
}
int pow_mod(int b, int p, int mod) {
int ret = 1;
while( p ) {
if( p & 1 ) ret = 1LL*ret*b%mod;
b = 1LL*b*b%mod;
p >>= 1;
}
return ret;
}
int BSGS(int a, int b) {
hash_clear();
int m = int(ceil(sqrt(MOD))), tmp = 1, tmp2;
for(int i=0;i<=m;i++) {
if( i == m ) tmp2 = tmp;
hash_insert(i, 1LL*tmp*b%MOD);
tmp = 1LL*tmp*a%MOD;
}
tmp = tmp2;
for(int i=1;i<=m;i++) {
if( hash_search(tmp) != -1 ) {
return i*m - hash_search(tmp);
}
tmp = 1LL*tmp*tmp2%MOD;
}
}
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if( b == 0 ) {
x = 1, y = 0;
return a;
}
else {
ll x1, y1;
ll d = exgcd(b, a%b, x1, y1);
x = y1;
y = x1 - a/b*y1;
return d;
}
}
int solve2(int a, int p) {
int b = BSGS(3, a);
ll x, y, d = exgcd(p, MODPW, x, y);
if( b % d ) return -1;
else {
x = (1LL*x*b/d%MODPW + MODPW)%MODPW;
return pow_mod(3, x, MOD);
}
}
int main() {
int m, p = solve1(); scanf("%d", &m);
printf("%d\n", solve2(m, p));
}
@details@
WC2019 讲了“简单”数论，所以就记住了这一算法，然后没想到这一次就用到了。
然而我并没有写过 BSGS，比赛的时候现学的（又是这样嘛……上一次 manacher 也是比赛的时候现学的……） 所以打 CF 还是有用的 2333。
靠着 CF 官方评测系统出锅，续了 40 min，终于把这道题写出来了。 人生第一次 AK。感谢 CF 的评测系统。 只不过 unrated 有点儿可惜 www。
本次比赛好像就这道题有点儿意思（因为是没有写过的新知识）。 A：大模拟 B：英语阅读理解 + 大模拟 C：常见贪心结论 D：一个关于图论的简单贪心 E：英语阅读理解 + 简单 dp
BZOJ 5381 or & Codeforces 623E Transforming Sequence DP+NTT
两道题题意都是一样的 不过$CF$的模数是$10^9+7$
很简单的分析发现$A_i$项一定要有一个之前没有出现过的二进制位才能满足条件 考虑$DP$来做
设$f_{i,j}$表示$i$个数用了二进制位上的$j$个位置后满足要求的方案数
转移式为:$f_{a+b,j}=\binom{j}{k} f_{a,k} \times (2^k)^{b}f_{b,j-k}$
即前$a$个数用去$k$位 后$b$个数用去$j-k$位 并且对于之前用过的$k$位也可以随意取
上式可化为：$\frac{ f_{a+b , j } } { j ! } = \frac { f_{ a , k } (2^ k ) ^ b} { k ! } \times \frac{ f_{ b, j - k } } { ( j - k ) ! }$
这个式子很显然可以$NTT$来搞
实现的时候写成类似快速幂的形式就可以过了 对于$CF$的模数 可以写写一个任意模数$FFT$ 算$7$次就可以了(我的精度简直醉了)
$BZOJ5381$
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 998244353
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=1e5+5;
int M,l,n,m,A[N],B[N],r[N];
int k,b,f[N],g[N],c[N],fac[N],inv[N],ans;
int poww(int x,int y){
int ans=1;
while(y){
if(y&1) ans=(ll)ans*x%mod;
y>>=1,x=(ll)x*x%mod;
}
return ans;
}
void NTT(int*A,int f){
for(int i=0;i<=M;i++) if(r[i]>i) swap(A[i],A[r[i]]);
for(int i=1;i<M;i<<=1){
int wn=poww(3,(mod-1)/i/2);
if(f==-1) wn=poww(wn,mod-2);
for(int j=0;j<M;j+=(i<<1)){
int w=1;
for(int k=0;k<i;k++,w=(ll)w*wn%mod){
int x=A[j+k],y=(ll)w*A[i+j+k]%mod;
A[j+k]=(x+y)%mod,A[i+j+k]=(x+mod-y)%mod;
}
}
}
if(f==-1){
// reverse(A+1,A+M);
int inv=poww(M,mod-2);
for(int i=0;i<=M;i++) A[i]=(ll)A[i]*inv%mod;
}
}
void init(){
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<N;i++) fac[i]=(ll)fac[i-1]*i%mod;
for(int i=2;i<N;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<N;i++) inv[i]=(ll)inv[i]*inv[i-1]%mod;
}
void NTT_MOD(int*a,int*b,int n){
cl(A),cl(B);
for(int i=0;i<=n;i++) A[i]=a[i],B[i]=b[i];
NTT(A,1),NTT(B,1);
for(int i=0;i<M;i++) A[i]=(ll)A[i]*B[i]%mod;
NTT(A,-1);
for(int i=0;i<=n;i++) a[i]=A[i];
}
void work(int*a,int*b,int n,int p){
int t=1;
cl(c);
for(int i=0;i<=n;i++) c[i]=(ll)a[i]*t%mod,t=(ll)t*p%mod;
NTT_MOD(c,b,n);
memcpy(a,c,sizeof c);
}
int Calc(int n,int m){
return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
#ifdef Devil_Gary
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif
cin>>n>>k;
for(M=1;M<=k+k;M<<=1,l++);
for(int i=0;i<M;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
init(),g[0]=1,b=2;
for(int i=1;i<=k;i++) f[i]=inv[i];
while(n){
if(n&1) work(g,f,k,b);
n>>=1,work(f,f,k,b),b=(ll)b*b%mod;
}
for(int i=n;i<=k;i++) (ans+=(ll)g[i]*fac[i]%mod*Calc(k,i)%mod)%=mod;
printf("%d\n",ans);
}
$CF623E$
#include<bits/stdc++.h>
using namespace std;
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pa pair<int,int>
#define mod 1000000007
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define cl(x) memset(x,0,sizeof x)
#ifdef Devil_Gary
#define bug(x) cout<<(#x)<<" "<<(x)<<endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define bug(x)
#define debug(...)
#endif
const int INF = 0x7fffffff;
const int N=1e5+5;
struct Cp{
double x,y;
Cp (double _x=0,double _y=0) { x=_x,y=_y;}
Cp operator + (const Cp &ch){ return Cp(x+ch.x,y+ch.y); }
Cp operator - (const Cp &ch){ return Cp(x-ch.x,y-ch.y); }
Cp operator * (const Cp &ch){ return Cp(x*ch.x-y*ch.y,x*ch.y+y*ch.x); }
}A[N],B[N],C[N],D[N],w,w0,tmp,wi[16][65536];;
int M,l,r[N];
#define pi acos(-1.0)
void FFT(Cp *A,int f){
for(int i=0;i<M;i++) if(r[i]>i) swap(A[r[i]],A[i]);
int gg=0;
for(int i=1;i<M;i<<=1){
w.x=cos(pi/i),w.y=sin(pi/i)*f;
for(int j=0;j<M;j+=(i<<1)){
for(int k=0;k<i;k++){
w0=wi[gg][k],w0.y*=f;
Cp x=A[j+k],y=w0*A[i+j+k];
A[j+k]=x+y,A[i+j+k]=x-y;
}
}
gg++;
}
if(f==-1) for(int i=0;i<M;i++) A[i].x/=M;
}
ll n;
int k,b,f[N],g[N],fac[N],inv[N],ans;
void init(){
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<N;i++) fac[i]=(ll)fac[i-1]*i%mod;
for(int i=2;i<N;i++) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<N;i++) inv[i]=(ll)inv[i]*inv[i-1]%mod;
int k=0;
for(int i=2;i<=N;i<<=1){
for(int j=0;j<i;j++)wi[k][j]=Cp(cos(j*pi/(i/2)),sin(j*pi/(i/2)));
k++;
}
}
void FFT_MOD(int*a,int*b,int n){
cl(A),cl(B),cl(C),cl(D);
for(int i=0;i<M;i++){
A[i].x=a[i]>>15;
B[i].x=a[i]&32767;
C[i].x=b[i]>>15;
D[i].x=b[i]&32767;
}
FFT(A,1),FFT(B,1),FFT(C,1),FFT(D,1);
for(int i=0;i<M;i++){
tmp=A[i]*D[i]+B[i]*C[i];
A[i]=A[i]*C[i];
C[i]=B[i]*D[i];
B[i]=tmp;
}
FFT(A,-1),FFT(B,-1),FFT(C,-1),cl(a);
for(int i=0;i<=n;i++)a[i]=((llround(A[i].x)%mod<<30)+(llround(B[i].x)%mod<<15)+llround(C[i].x)%mod)%mod;
}
int c[N];
void work(int*a,int*b,int n,int p){
int t=1;
cl(c);
for(int i=0;i<=n;i++) c[i]=(ll)a[i]*t%mod,t=(ll)t*p%mod;
FFT_MOD(c,b,n);
memcpy(a,c,sizeof c);
}
int Calc(int n,int m){
return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
#ifdef Devil_Gary
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
cin>>n>>k;
if(n>k) return puts("0"),0;
for(M=1;M<=k+k;M<<=1,l++);
for(int i=0;i<M;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
init(),g[0]=1,b=2;
for(int i=1;i<=k;i++) f[i]=inv[i];
while(n){
if(n&1) work(g,f,k,b);
n>>=1,work(f,f,k,b),b=(ll)b*b%mod;
}
for(int i=n;i<=k;i++) (ans+=(ll)g[i]*fac[i]%mod*Calc(k,i)%mod)%=mod;
printf("%d\n",ans);
}
CodeForces - 524F And Yet Another Bracket Sequence
题面在这里!
(会考完之后休闲休闲2333)
可以发现，如果把一个串中"()"自动删除，最后剩的一定是形如"))))....))(((..((("这样的串，然后我们多加进去的括号的个数就是剩的这个串的长度。。
然鹅这个题首先要求的是最后总长度最小，并且我们可以观察发现把最后一个循环位移到最前面是会使一对")("相抵消的。
所以我们最后的最优答案一定是排除已经匹配的括号之后只剩一种括号的串，我们枚举一下循环位移了多少(循环位移之后一定是一个原串的后缀+前缀的形式)，然后再判断一下这种循环位移是否会只剩一种串(可以把原串中 ''(''个数 - '')''个数 分类讨论一下，然后退出一个形如 一个区间里的前缀/后缀 都要 大于等于 某个前缀/后缀 的式子，可以 O(N) 单调队列扫一遍 )，然后用hash直接更新答案即可，显然最后多的括号都堆在前面或者后面是最优的，然后就做完了2333
(最近常数是真的小啊2333)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2000005,ha=1e9+9;
inline int Get(char x){ return x==''(''?1:-1;}
inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
int n,q[maxn],hd,tl,a[maxn],tot,p,N;
int c[maxn],h[maxn];
char s[maxn];
inline int gethash(int x,int len){ return add(h[x+len-1],ha-h[x-1]*(ll)c[len]%ha);}
inline bool cmp(int x,int y){
int l=0,r=n,mid,an=0;
while(l<=r){
mid=l+r>>1;
if(gethash(x,mid)==gethash(y,mid)) an=mid,l=mid+1;
else r=mid-1;
}
return an==n?1:s[x+an]==''('';
}
inline void update(int x){ if(!p||cmp(x,p)) p=x;}
inline void solve1(){
c[0]=1;
for(int i=1;i<=N;i++){
a[i]=a[i-1]+Get(s[i]);
c[i]=add(c[i-1],add(c[i-1],c[i-1]));
h[i]=add(add(h[i-1],add(h[i-1],h[i-1])),(s[i]==''(''?1:2));
}
hd=1,tl=0;
for(int i=1;i<N;i++){
while(hd<=tl&&a[i]<=a[q[tl]]) tl--;
q[++tl]=i;
while(hd<=tl&&q[hd]+n<=i) hd++;
if(i>=n&&a[q[hd]]>=a[i-n]) update(i-n+1);
}
for(int i=0;i<n;i++) putchar(s[p+i]);
for(int i=1;i<=tot;i++) putchar('')'');
}
inline void solve2(){
c[0]=1;
for(int i=1;i<=N;i++){
c[i]=add(c[i-1],add(c[i-1],c[i-1]));
h[i]=add(add(h[i-1],add(h[i-1],h[i-1])),(s[i]==''(''?1:2));
}
for(int i=N;i;i--) a[i]=a[i+1]-Get(s[i]);
hd=1,tl=0;
for(int i=N-1;i;i--){
while(hd<=tl&&a[i]<=a[q[tl]]) tl--;
q[++tl]=i;
while(hd<=tl&&q[hd]-n>=i) hd++;
if(i<=n&&a[q[hd]]>=a[i+n]) update(i);
}
for(int i=tot;i<0;i++) putchar(''('');
for(int i=0;i<n;i++) putchar(s[p+i]);
}
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%s",s+1),n=strlen(s+1),N=n<<1;
for(int i=1;i<=n;i++) s[i+n]=s[i],tot+=Get(s[i]);
if(tot>=0) solve1();
else solve2();
return 0;
}
CodeForces - 750E New Year and Old Subsequence
Discription
A string t is called nice if a string "2017" occurs in t as a subsequence but a string "2016" doesn''t occur in t as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren''t nice.
The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it''s impossible to make a string nice by removing characters, its ugliness is - 1.
Limak has a string s of length n, with characters indexed 1 through n. He asks you qqueries. In the i-th query you should compute and print the ugliness of a substring(continuous subsequence) of s starting at the index ai and ending at the index bi(inclusive).
Input
The first line of the input contains two integers n and q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the length of the string s and the number of queries respectively.
The second line contains a string s of length n. Every character is one of digits ''0''–''9''.
The i-th of next q lines contains two integers ai and bi (1 ≤ ai ≤ bi ≤ n), describing a substring in the i-th query.
Output
For each query print the ugliness of the given substring.
Examples
8 3
20166766
1 8
1 7
2 84
3
-115 5
012016662091670
3 4
1 14
4 15
1 13
10 15-1
2
1
-1
-14 2
1234
2 4
1 2-1
-1Note
In the first sample:
- In the first query, ugliness("20166766") = 4 because all four sixes must be removed.
- In the second query, ugliness("2016676") = 3 because all three sixes must be removed.
- In the third query, ugliness("0166766") = - 1 because it''s impossible to remove some digits to get a nice string.
In the second sample:
- In the second query, ugliness("01201666209167") = 2. It''s optimal to remove the first digit ''2'' and the last digit ''6'', what gives a string "010166620917", which is nice.
- In the third query, ugliness("016662091670") = 1. It''s optimal to remove the last digit ''6'', what gives a nice string "01666209170".
建一个节点和字符集很少的有限状态自动机，然后对于线段树每个区间用一个矩阵记录 从一个状态 到 另一个状态的 最小代价。
因为这个矩阵是满足结合律的，所以直接做就行了。
#include<bits/stdc++.h>
#define ll long long
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mid (l+r>>1)
using namespace std;
const int maxn=200005;
struct node{
int a[5][5];
inline void init(){ memset(a,0x3f,sizeof(a));}
node operator *(const node &u)const{
node r; r.init();
for(int k=0;k<5;k++)
for(int i=0;i<5;i++)
for(int j=0;j<5;j++) r.a[i][j]=min(r.a[i][j],a[i][k]+u.a[k][j]);
return r;
}
}S[maxn*4+5],ANS;
int n,m,le,ri;
char s[maxn];
inline void Set(node &x,int y){
x.init(); for(int i=0;i<5;i++) x.a[i][i]=0;
if(y==2) x.a[0][0]=1,x.a[0][1]=0;
else if(!y) x.a[1][1]=1,x.a[1][2]=0;
else if(y==1) x.a[2][2]=1,x.a[2][3]=0;
else if(y==7) x.a[3][3]=1,x.a[3][4]=0;
else if(y==6) x.a[3][3]=1,x.a[4][4]=1;
}
void build(int o,int l,int r){
if(l==r){ Set(S[o],s[l]-''0''); return;}
build(lc,l,mid),build(rc,mid+1,r);
S[o]=S[lc]*S[rc];
}
void query(int o,int l,int r){
if(l>=le&&r<=ri){ ANS=ANS*S[o]; return;}
if(le<=mid) query(lc,l,mid);
if(ri>mid) query(rc,mid+1,r);
}
inline void solve(){
build(1,1,n);
while(m--){
ANS.init(); for(int i=0;i<5;i++) ANS.a[i][i]=0;
scanf("%d%d",&le,&ri),query(1,1,n);
printf("%d\n",ANS.a[0][4]<=n?ANS.a[0][4]:-1);
}
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+1);
solve();
return 0;
}
关于Codeforces1132A——Regular Bracket Sequence和水题的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于@codeforces - 1106F@ Lunar New Year and a Recursive Sequence、BZOJ 5381 or & Codeforces 623E Transforming Sequence DP+NTT、CodeForces - 524F And Yet Another Bracket Sequence、CodeForces - 750E New Year and Old Subsequence等相关内容，可以在本站寻找。
本文标签：
