子串查詢

Time Limit: 3500/3000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 228????Accepted Submission(s): 111

Problem Description

度度熊的字符串課堂開始了！要以像度度熊一樣的天才為目標(biāo)，努力奮斗哦！

為了檢驗(yàn)?zāi)闶欠窬邆洳宦犝n的資質(zhì)，度度熊準(zhǔn)備了一個(gè)只包含大寫英文字母的字符串?A[1,n]=a1a2?an，接下來他會(huì)向你提出?q?個(gè)問題?(l,r)，你需要回答字符串?A[l,r]=alal+1?ar?內(nèi)有多少個(gè)非空子串是?A[l,r]?的所有非空子串中字典序最小的。這里的非空子串是字符串中由至少一個(gè)位置連續(xù)的字符組成的子序列，兩個(gè)子串是不同的當(dāng)且僅當(dāng)這兩個(gè)子串內(nèi)容不完全相同或者出現(xiàn)在不同的位置。

記?|S|?為字符串?S?的長(zhǎng)度，對(duì)于兩個(gè)字符串?S?和?T?，定義?S?的字典序比?T?小，當(dāng)且僅當(dāng)存在非負(fù)整數(shù)?k(≤min(|S|,|T|))?使得?S?的前?k?個(gè)字符與?T?的前?k?個(gè)字符對(duì)應(yīng)相同，并且要么滿足?|S|=k?且?|T|>k，要么滿足?k<min(|S|,|T|)?且?S?的第?k+1?個(gè)字符比?T?的第?k+1?個(gè)字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。

Input

第一行包含一個(gè)整數(shù)?T，表示有?T?組測(cè)試數(shù)據(jù)。

接下來依次描述?T?組測(cè)試數(shù)據(jù)。對(duì)于每組測(cè)試數(shù)據(jù)：

第一行包含兩個(gè)整數(shù)?n?和?q，表示字符串的長(zhǎng)度以及詢問的次數(shù)。

第二行包含一個(gè)長(zhǎng)為?n?的只包含大寫英文字母的字符串?A[1,n]。

接下來?q?行，每行包含兩個(gè)整數(shù)?li,ri，表示第?i?次詢問的參數(shù)。

保證?1≤T≤10，1≤n,q≤105，1≤li≤ri≤n。

Output

對(duì)于每組測(cè)試數(shù)據(jù)，先輸出一行信息 "Case #x:"（不含引號(hào)），其中 x 表示這是第?x?組測(cè)試數(shù)據(jù)，接下來?q?行，每行包含一個(gè)整數(shù)，表示字符串?A[l,r]?中字典序最小的子串個(gè)數(shù)，行末不要有多余空格。

Sample Input

1

2 3

AB

1 1

1 2

2 2

Sample Output

Case #1: 1 1 1

Source

2018"百度之星"程序設(shè)計(jì)大賽 - 資格賽

?題意；給你一段長(zhǎng)度為n的字符串，大寫字母組成；m次詢問，每次詢問一個(gè)區(qū)間，求這個(gè)區(qū)間最小值出現(xiàn)的次數(shù)。

解析：有多種做法：

第一種：線段樹保存區(qū)間最小值，往上推的過程維護(hù)區(qū)間最小值的個(gè)數(shù)就可以。

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}const int maxn=100000+3; char s[maxn];int n; int q; struct node{int l,r,count;char mav; }t[maxn<<2];int cnt=0; void pushUp(int m) {if(t[m<<1].mav<t[m<<1|1].mav){t[m].mav=t[m<<1].mav;t[m].count=t[m<<1].count;}else if(t[m<<1].mav>t[m<<1|1].mav){t[m].mav=t[m<<1|1].mav;t[m].count=t[m<<1|1].count;}else{t[m].mav=t[m<<1].mav;t[m].count=t[m<<1].count+t[m<<1|1].count;} } void bulid(int l,int r,int m) {t[m].l=l;t[m].r=r;if(l==r){scanf("%c",&t[m].mav);t[m].count=1;return ;}int mid=l+r>>1;bulid(l,mid,m<<1);bulid(mid+1,r,m<<1|1);pushUp(m); }int query(int L,int R,int m) {if(L<=t[m].l&&t[m].r<=R){return t[m].mav;}int mid=t[m].l+t[m].r>>1;int ans=99999999;if(L<=mid)ans=min(ans,query(L,R,m<<1));if(R>mid)ans=min(ans,query(L,R,m<<1|1));return ans; } int query2(int L,int R,int m,int v) {if(L<=t[m].l&&t[m].r<=R){if(t[m].mav==v)return t[m].count;else return 0;}int mid=t[m].l+t[m].r>>1;int ans=0;if(L<=mid)ans+=query2(L,R,m<<1,v);if(R>mid)ans+=query2(L,R,m<<1|1,v);return ans; }int main() {int T,cas=1;scanf("%d",&T);while(T--){scanf("%d%d",&n,&q);getchar();bulid(1,n,1);printf("Case #%d:\n",cas++);int cnt=0;while(q--){cnt=0;int x,y;scanf("%d%d",&x,&y);int ans=query(x,y,1);printf("%d\n",query2(x,y,1,ans));}}return 0; }

?

第二種：前綴和。記錄每一個(gè)字母在該i處出現(xiàn)的總次數(shù)。

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}char s[100005]; int a[100005][30]; int main() {int T,cas=1;scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);scanf("%s",s);mem(a,0);a[0][s[0]-'A']++;for(int i=1; i<n; i++){a[i][s[i]-'A']++;//printf("%d**\n",a[i][s[i]-'A']);for(int j=0; j<26; j++)a[i][j]+=a[i-1][j];}printf("Case #%d:\n",cas++);while(m--){int ans=0;int l,r;scanf("%d%d",&l,&r);for(int i=0; i<26; i++){if(a[r-1][i]>a[l-1-1][i]){ans=a[r-1][i]-a[l-1-1][i];break;}}printf("%d\n",ans);}}return 0;}

?

總結(jié)

以上是生活随笔為你收集整理的2018百度之星程序设计大赛 - 资格赛 hdu6345（找区间最小值）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。