首页 > 代码库 > SDUT oj 选拔赛1 迷之好奇
SDUT oj 选拔赛1 迷之好奇
迷之好奇
Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
FF得到了一个有n个数字的集合。不要问我为什么，有钱，任性。
FF很好奇的想知道，对于数字x，集合中有多少个数字可以在x前面添加任意数字得到。
如，x = 123，则在x前面添加数字可以得到4123，5123等。
输入
多组输入。
对于每组数据
首先输入n(1<= n <= 100000)。
接下来n行。每行一个数字y(1 <= y <= 100000)代表集合中的元素。
接下来一行输入m(1 <= m <= 100000),代表有m次询问。
接下来的m行。
每行一个正整数x(1 <= x <= 100000)。
输出
对于每组数据，输出一个数字代表答案。
示例输入
312345666661235634512345356
示例输出
101
算法分析：数据量太大，常规的算法必然超时，并且那样做我个人感觉描述起来相当麻烦。
换个想法：比如要问45 在集合中有那些数字的尾部是45，只需要找到那些数对100取余==45就行了。但是为了避免
超时，需要在一开始时，对集合的这个数就进行从10 100 ，，，，的取余，记住不对比本身大的数取余！
哈希数组初始化为0，然后取余出来的dd, 进行f[dd]++,说明dd这个数有f[dd]个数字的尾部是dd ！
但注意这类数据: 例如：3000005
对10取余 ==5；
对100取余==5；
对1000取余==5； 但是对于3000005这个数只能加一次
代码：
#include <iostream>#include <string>#include <stdio.h>#include <string.h>#include <algorithm>#include <ctype.h>using namespace std;int f[100001];int main(){ int n; int i, j; int m; int x; int dd, ff, gg; int flag; int w; while(scanf("%d", &n)!=EOF) { memset(f, 0, sizeof(f)); for(i=0; i<n; i++) { scanf("%d", &ff ); if(ff>10) { gg=10; dd=ff%gg; flag=dd; w=1; while( dd<ff ) { if(w==1) { f[dd]++; gg=gg*10; dd=ff%gg; w=0; } else if(w==0) { if(flag==dd) { gg=gg*10; dd=ff%gg; } else { f[dd]++; flag=dd; gg=gg*10; dd=ff%gg; } } //f[dd]++; } } } scanf("%d", &m); for(i=0; i<m; i++) { scanf("%d", &x); printf("%d\n", f[x] ); } } return 0;}
SDUT oj 选拔赛1 迷之好奇
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。