B 洛谷 P3604 美好的每一天 [莫队算法]

题目背景

时间限制3s,空间限制162MB

素晴らしき日々

我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧...

由于世界会在7月20日完结，作为救世主，间宫卓司要在19日让所有人回归天空

现在已经是19日傍晚，大家集合在C栋的天台上，一共n个人

在他们面前，便是终之空，那终结的天空

题目描述

回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母'a'->'z'作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空

由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了，所以卓司的信徒很多

输入输出格式

输入格式：

第一行两个数n,m

之后一行一个长为n的字符串，代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

输出格式：

m行，每行一个数表示答案

输入输出样例

输入样例#1：

输出样例#1：

说明

对于10%的数据，n,m<=100

对于30%的数据，n,m<=2000

对于100%的数据，n,m<=60000

字符集大小有梯度

在大家回归天空之后，彩名露出了阴冷的笑容

先奉上O(n2) 30分骗分

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,l,r;

char c[N];

int a[N][N],s[N][N],cnt[],now;

void ini(){

    for(int i=;i<=n;i++){

        memset(cnt,,sizeof(cnt));now=;

        for(int j=i;j<=n;j++){

            if(cnt[c[j]]%==) now++;

            else now--;

            cnt[c[j]]++;

            if((j-i+)%==&&now==) a[i][j]=;

            if((j-i+)%==&&now==) a[i][j]=;

            s[i][j]=s[i][j-]+a[i][j];

            //printf("hi %d %d %d  %d\n",i,j,a[i][j],s[i][j]);

        }

    }

}

void solve(int l,int r){

    int ans=;

    for(int i=l;i<=r;i++) ans+=s[i][r]-s[i][i-];

    printf("%d\n",ans);

}

int main(int argc, const char * argv[]) {

    n=read();Q=read();

    scanf("%s",c+);

    ini();

    while(Q--){

        l=read();r=read();

        solve(l,r);

    }

    return ;

}

标解：

一个区间可以重排成为回文串，即区间中最多有一个字母出现奇数次，其他的都出现偶数次

发现这个和 $xor$ 类似
这样如果一个区间的 $xor$ 和为 $0$ 或者 $2^x$ ，则这个区间可以重排成为回文串，即回归天空

把每个位置的值变为前缀 $xor$ 和，那么区间 $[l,r]$ 可以回归天空当且仅当 $a[l - 1] \oplus a[r]$ 为 $0$ 或者 $2^x$

$a[i]$ 即 $1->i$ 的异或和

这样用莫队算法，可以做到 $O( 26n\sqrt{n} )$ 的复杂度

怎么用莫队呢？去请教了__stdcall

考虑[l,r]—>[l,r+1]，就是要找出这个区间里有几个前缀xor满足 a[r+1]^它 =0或(1<<x)

那么用一个桶c存起来更新答案加上c[a[r+1]^(1<<x)]和c[a[r+1]]就行了

有个细节，[l,r]对应的桶中应该是[l-1,r]的a

然后内存原因c用short

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=6e4+,M=(<<)+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,a[N],bl,pos[N];

char s[N];

struct ques{

    int l,r,id;

    bool operator <(const ques &a)const{

        return pos[l]==pos[a.l]?r<a.r:pos[l]<pos[a.l];

    }

}q[N];

unsigned short c[M];

int ans,anss[N];

inline void add(int x){//printf("add %d %d\n",x,a[x]);

    ans+=c[a[x]];

    for(int i=;i<;i++) ans+=c[a[x]^(<<i)];

    c[a[x]]++;

}

inline void del(int x){

    c[a[x]]--;

    ans-=c[a[x]];

    for(int i=;i<;i++) ans-=c[a[x]^(<<i)];

}

void solve(){

    sort(q+,q++Q);

    c[]++;

    int l=,r=;

    for(int i=;i<=Q;i++){//printf("Q %d %d %d\n",q[i].l,q[i].r,q[i].id);

        while(r<q[i].r) r++,add(r);//printf("hi %d %d %d\n",l,r,ans);

        while(r>q[i].r) del(r),r--;//printf("hi %d %d %d\n",l,r,ans);

        while(l<q[i].l) del(l-),l++;//printf("hi %d %d %d\n",l,r,ans);

        while(l>q[i].l) l--,add(l-);//printf("hi %d %d %d\n",l,r,ans);

        anss[q[i].id]=ans;

    }

    for(int i=;i<=Q;i++) printf("%d\n",anss[i]);

}

int main(int argc, const char * argv[]) {

    n=read();Q=read();

    scanf("%s",s+);

    bl=sqrt(n);

    for(int i=;i<=n;i++) a[i]=(<<(s[i]-'a'))^a[i-],pos[i]=(i-)/bl+;

    for(int i=;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;

    solve();

    return ;

}

怎么卡常也还是70分

//

//  main.cpp

//  BB

//

//  Created by Candy on 2017/2/2.

//  Copyright © 2017年 Candy. All rights reserved.

//

#pragma GCC optimize("O2")

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=6e4+,M=(<<)+;

inline int read(){

    char c=getchar();register int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,a[N],bl,pos[N],bit[];

char s[N];

struct ques{

    int l,r,id;

    bool operator <(const ques &a)const{

        return pos[l]==pos[a.l]?r<a.r:pos[l]<pos[a.l];

    }

}q[N];

unsigned short c[M];

int ans,anss[N];

inline void add(int x){//printf("add %d %d\n",x,a[x]);

    ans+=c[a[x]]++;

    for(register int i=;i<;i++) ans+=c[a[x]^bit[i]];

}

inline void del(int x){

    ans-=--c[a[x]];

    for(register int i=;i<;i++) ans-=c[a[x]^bit[i]];

}

inline void solve(){

    for(int i=;i<;i++) bit[i]=<<i;

    sort(q+,q++Q);

    c[]++;

    int l=,r=;

    for(int i=;i<=Q;i++){//printf("Q %d %d %d\n",q[i].l,q[i].r,q[i].id);

        while(r<q[i].r) add(++r);//printf("hi %d %d %d\n",l,r,ans);

        while(r>q[i].r) del(r--);//printf("hi %d %d %d\n",l,r,ans);

        while(l<q[i].l) del(l-),l++;//printf("hi %d %d %d\n",l,r,ans);

        while(l>q[i].l) add(--l-);//printf("hi %d %d %d\n",l,r,ans);

        anss[q[i].id]=ans;

    }

    for(int i=;i<=Q;i++) printf("%d\n",anss[i]);

}

int main(int argc, const char * argv[]) {

    n=read();Q=read();

    scanf("%s",s+);

    bl=sqrt(n);

    for(int i=;i<=n;i++) a[i]=(<<(s[i]-'a'))^a[i-],pos[i]=(i-)/bl+;

    for(int i=;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;

    solve();

    return ;

}

卡常后很丑

巴特西

B 洛谷 P3604 美好的每一天 [莫队算法]

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章