【EOJ Monthly 2019.02 - B】解题(思维,抽屉原理,暴力,模运算,优化,tricks)

题干:

单测试点时限: 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 1224. 简单迷宫问题