首页 > 代码库 > B 洛谷 P3604 美好的每一天 [莫队算法]
B 洛谷 P3604 美好的每一天 [莫队算法]
题目背景
时间限制3s,空间限制162MB
素晴らしき日々
我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧...
由于世界会在7月20日完结，作为救世主，间宫卓司要在19日让所有人回归天空
现在已经是19日傍晚，大家集合在C栋的天台上，一共n个人
在他们面前，便是终之空，那终结的天空
题目描述
回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母‘a‘->‘z‘作为编号
一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空
由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空
因为世界末日要来了，所以卓司的信徒很多
输入输出格式
输入格式：
第一行两个数n,m
之后一行一个长为n的字符串，代表每个人的编号
之后m行每行两个数l,r代表每次卓司妄想的区间
输出格式：
m行，每行一个数表示答案
输入输出样例
输入样例#1：
6 6zzqzzq1 62 43 42 34 51 1
输出样例#1：
1642231
说明
对于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=2005;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,l,r;char c[N];int a[N][N],s[N][N],cnt[300],now;void ini(){ for(int i=1;i<=n;i++){ memset(cnt,0,sizeof(cnt));now=0; for(int j=i;j<=n;j++){ if(cnt[c[j]]%2==0) now++; else now--; cnt[c[j]]++; if((j-i+1)%2==0&&now==0) a[i][j]=1; if((j-i+1)%2==1&&now==1) a[i][j]=1; s[i][j]=s[i][j-1]+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=0; for(int i=l;i<=r;i++) ans+=s[i][r]-s[i][i-1]; printf("%d\n",ans);}int main(int argc, const char * argv[]) { n=read();Q=read(); scanf("%s",c+1); ini(); while(Q--){ l=read();r=read(); solve(l,r); } return 0;}
标解：
一个区间可以重排成为回文串，即区间中最多有一个字母出现奇数次，其他的都出现偶数次
发现这个和
类似
这样如果一个区间的
或者
，则这个区间可以重排成为回文串，即回归天空
把每个位置的值变为前缀
可以回归天空当且仅当
为
即
的异或和
这样用莫队算法，可以做到
的复杂度
怎么用莫队呢？去请教了__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+5,M=(1<<26)+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; 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=0;i<26;i++) ans+=c[a[x]^(1<<i)]; c[a[x]]++;}inline void del(int x){ c[a[x]]--; ans-=c[a[x]]; for(int i=0;i<26;i++) ans-=c[a[x]^(1<<i)];}void solve(){ sort(q+1,q+1+Q); c[0]++; int l=1,r=0; for(int i=1;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-1),l++;//printf("hi %d %d %d\n",l,r,ans); while(l>q[i].l) l--,add(l-1);//printf("hi %d %d %d\n",l,r,ans); anss[q[i].id]=ans; } for(int i=1;i<=Q;i++) printf("%d\n",anss[i]);}int main(int argc, const char * argv[]) { n=read();Q=read(); scanf("%s",s+1); bl=sqrt(n); for(int i=1;i<=n;i++) a[i]=(1<<(s[i]-‘a‘))^a[i-1],pos[i]=(i-1)/bl+1; for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; solve(); return 0;}
怎么卡常也还是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+5,M=(1<<26)+5;inline int read(){ char c=getchar();register int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,Q,a[N],bl,pos[N],bit[27];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=0;i<26;i++) ans+=c[a[x]^bit[i]];}inline void del(int x){ ans-=--c[a[x]]; for(register int i=0;i<26;i++) ans-=c[a[x]^bit[i]];}inline void solve(){ for(int i=0;i<26;i++) bit[i]=1<<i; sort(q+1,q+1+Q); c[0]++; int l=1,r=0; for(int i=1;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-1),l++;//printf("hi %d %d %d\n",l,r,ans); while(l>q[i].l) add(--l-1);//printf("hi %d %d %d\n",l,r,ans); anss[q[i].id]=ans; } for(int i=1;i<=Q;i++) printf("%d\n",anss[i]);}int main(int argc, const char * argv[]) { n=read();Q=read(); scanf("%s",s+1); bl=sqrt(n); for(int i=1;i<=n;i++) a[i]=(1<<(s[i]-‘a‘))^a[i-1],pos[i]=(i-1)/bl+1; for(int i=1;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i; solve(); return 0;}
B 洛谷 P3604 美好的每一天 [莫队算法]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。