在线做公章网站,推广型网站制作公司,wordpress ios7教程,网站图片速度题干#xff1a;
单测试点时限: 2.0 秒
内存限制: 1024 MB
“我把房门上锁#xff0c;并非为了不让她进去#xff0c;而是为了防止自己逃到她身边”。
她又被数学难住了。QQ 小方当然是不会对女生说”不”的。
她的数学题是这样的#xff0c;她得到了一个十进制大整数…题干
单测试点时限: 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 )。
保证 ∑qi1mi≤5×107 。
输出
对于每一个询问输出两个整数 l,r 表示保留第 l 到第 r 位。保证一定有解。
样例
Input
1249
4
7
3
2
83Output
3 4
4 4
3 3
2 4提示
对于样例 1249 这个数中可选出的最小的7 的倍数是49 最小的3 的倍数是9 2 的倍数是40 83 的倍数是249 。
解题报告 注意到连续区间考虑两部分作差两后缀相减
设 ai 是从第 i 位到末位代表的整数我们发现答案一定可以表达成 ai−aj (ij )的形式。
例如对于 1249 10001249−249 12001249−49 240 249−9 。因此问题可以转化为找到一个最小的 ai−aj 使得 ai−ajmodm0 。
要使 ai−ajmodm 为 0 只需要 aimodmajmodm 。要使 ai−aj 最小首先需要 ai 最小其次让 aj 最大。但是容易发现在 ai 最小的情况下不可能有两个数 aj,ak 同时满足条件否则 aj,ak 可以组成一个更小的解。因此我们只要找到两个最小的 ai,aj 使其对 m 同余即可。注意aj 是可以等于 0 的。
同时因为抽屉原理我们最多只要处理 m1 个 ai 就能找到答案。
注意别每次都memset会超时的。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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,s1);nstrlen(s1);cinq;while(q--) {scanf(%d,m);vectorintvis(m,-1);//memset(vis,-1,sizeof vis);ll now0,pw1;vis[0]n1;for(int in; i; --i) {now(nowpw*(s[i]-0))%m;pwpw*10%m;if(vis[now]!-1) {printf(%d %d\n,i,vis[now]-1);break;}vis[now]i;}}
}
优化2
#includecstdio
#includebitset
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int maxn1e610,N5e710;
char s[maxn];
int a[maxn];
void up(int i,int j,int l,int r) {if(!l)li,rj;
}
bitsetNmp;
int main() {int q,m,n;scanf(%s,s1);nstrlen(s1);scanf(%d,q);while(q--) {scanf(%d,m);int y1,l0,rn1;mp.reset();for(int j,in; i; i--) {a[i](a[i1]y*(s[i]-0))%m;yy*10%m;if(mp[a[i]]) {for(ji1; jn; j)if(a[j]a[i])break;up(i,j-1,l,r);} else if(a[i]%m0)up(i,n,l,r);mp[a[i]]1;if(l)break;}printf(%d %d\n,l,r);}
}优化3
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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,s1);int len strlen(s1);cinq;while(q--) {scanf(%d,m);for(int i 0; im; i) vis[i] -1;ll cur 0,pw 1;vis[0] len1;for(int i len; i1; 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;}}
}
