題干：

單測試點時限: 2.0 秒

內存限制: 1024 MB

“我把房門上鎖，并非為了不讓她進去，而是為了防止自己逃到她身邊”。

她又被數學難住了。QQ 小方當然是不會對女生說”不”的。

她的數學題是這樣的，她得到了一個十進制大整數，這個大整數只包含 1 - 9 這 9 個數字。

現在，要求選出其中連續的一段數字，把其他未被選中的數字全部變成 0 ，并且使得變換以后的大整數恰好是 m 的倍數。

QQ 小方為了表現自己的能力，所以一口答應給她寫出在所有可能的數里面最小的一個。

但是她的問題太多了，她對于這一個大整數，需要對于 q 個不盡相同的 m 分別給出答案。

但是 QQ 小方自己不會。只能來求助你了，你能幫他解答嗎？

輸入

第一行包含一個大整數，這個整數的位數為 n (1≤n≤106 )。

第二行一個整數 q (1≤q≤500 ) 代表詢問次數。

對于每一個詢問，包含一行一個整數，表示第 i 次詢問的 mi (1≤mi≤5×107 )。

保證 ∑qi=1mi≤5×107 。

輸出

對于每一個詢問輸出兩個整數 l,r 表示保留第 l 到第 r 位。保證一定有解。

樣例

Input

1249 4 7 3 2 83

Output

3 4 4 4 3 3 2 4

提示

對于樣例：
1249 這個數中，可選出的最小的7 的倍數是49 ，最小的3 的倍數是9 ，2 的倍數是40 ，83 的倍數是249 。

解題報告：

? ?注意到連續區間，考慮兩部分作差（兩后綴相減）

設 ai 是從第 i 位到末位代表的整數，我們發現答案一定可以表達成 ai?aj (i<j )的形式。

例如，對于 1249 ，1000=1249?249 ，1200=1249?49 ，240 =249?9 。因此，問題可以轉化為找到一個最小的 ai?aj ，使得 ai?ajmodm=0 。

要使 ai?ajmodm 為 0 ，只需要 aimodm=ajmodm 。要使 ai?aj 最小，首先需要 ai 最小，其次讓 aj 最大。但是容易發現，在 ai 最小的情況下不可能有兩個數 aj,ak 同時滿足條件，否則 aj,ak 可以組成一個更小的解。因此，我們只要找到兩個最小的 ai,aj ，使其對 m 同余即可。注意，aj 是可以等于 0 的。

同時，因為抽屜原理，我們最多只要處理 m+1 個 ai 就能找到答案。

注意別每次都memset，會超時的。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; const int MAXMAX = 5e7 + 5; char s[MAX]; int n,q,m; int main() {scanf("%s",s+1);n=strlen(s+1);cin>>q;while(q--) {scanf("%d",&m);vector<int>vis(m,-1);//memset(vis,-1,sizeof vis);ll now=0,pw=1;vis[0]=n+1;for(int i=n; i; --i) {now=(now+pw*(s[i]-'0'))%m;pw=pw*10%m;if(vis[now]!=-1) {printf("%d %d\n",i,vis[now]-1);break;}vis[now]=i;}} }

優化2：

#include<cstdio> #include<bitset> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int maxn=1e6+10,N=5e7+10; char s[maxn]; int a[maxn]; void up(int i,int j,int& l,int& r) {if(!l)l=i,r=j; } bitset<N>mp; int main() {int q,m,n;scanf("%s",s+1);n=strlen(s+1);scanf("%d",&q);while(q--) {scanf("%d",&m);int y=1,l=0,r=n+1;mp.reset();for(int j,i=n; i; i--) {a[i]=(a[i+1]+y*(s[i]-'0'))%m;y=y*10%m;if(mp[a[i]]) {for(j=i+1; j<=n; j++)if(a[j]==a[i])break;up(i,j-1,l,r);} else if(a[i]%m==0)up(i,n,l,r);mp[a[i]]=1;if(l)break;}printf("%d %d\n",l,r);} }

優化3：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e6 + 5; const int MAXMAX = 5e7 + 5; char s[MAX]; int vis[MAXMAX]; int q,m; int main() {scanf("%s",s+1);int len =strlen(s+1);cin>>q;while(q--) {scanf("%d",&m);for(int i = 0; i<=m; i++) vis[i] = -1;ll cur = 0,pw = 1;vis[0] = len+1;for(int i = len; i>=1; i--) {cur = (cur + (s[i]-'0') * pw)%m;pw = (pw*10)%m;if(vis[cur] != -1) {printf("%d %d\n",i,vis[cur]-1);break;}else vis[cur] = i;}} }

?

總結

以上是生活随笔為你收集整理的【EOJ Monthly 2019.02 - B】解题（思维，抽屉原理，暴力，模运算，优化，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。