首页 > 代码库 > HDU5090模拟,hash
HDU5090模拟,hash
- /*
- HDU 5090
- 算是一道简单模拟题,但其中有很深的hash思想
- 这是本人的第一道hash题
- 更是本人的第一道纸质代码不带编译不带运行提交AC的题
- 值得纪念
- 废话讲这么多之后,讲述题中思想
- 由于n很小不超过100,可以开个数组记录每个数出现多少次
- 由于只能i+n*k变大,因此只需要从1到n逐个检查
- 若当前检查的hash[i]=0则无解:因为不可能有其他数能够变化成它
- 若当前检查的hash[i]>1则必须将i变化为j=n*k+i(n>0),其中hash[j]=0代表 j 在输入的数中没有出现过由数 i 变过来的
- 若当前检查的hash[i]=1继续
- 循环一遍之后,只需判断标志符号
- */
- #include <iostream>
- #include <algorithm>
- #include <stdio.h>
- #include <math.h>
- #include <map>
- #include <set>
- #include <vector>
- #include <string>
- #include <cstring>
- #include <sstream>
- using namespace std;
- #define input freopen("input.txt","r",stdin);
- #define output freopen("output.txt","w",stdout);
- #define For1(i,a,b) for (i=a;i<b;i++)
- #define For2(i,a,b) for (i=a;i<=b;i++)
- #define Dec(i,a,b) for (i=a;i>b;i--)
- #define Dec2(i,a,b) for (i=a;i>=b;i--)
- #define Sca_d(x) scanf("%d",&x)
- #define Sca_s(x) scanf("%s",x)
- #define Sca_c(x) scanf("%c",&x)
- #define Sca_f(x) scanf("%f",&x)
- #define Sca_lf(x) scanf("%lf",&x)
- #define Fill(x,a) memset(x,a,sizeof(x))
- #define MAXN 1110
- template <typename T>
- T gcd(T a,T b)
- {
- return b==0?a:gcd(b,a%b);
- }
- template <typename T>
- T lcm(T a,T b)
- {
- return a/gcd(a,b)*b;
- }
- int main()
- {
- int hash[MAXN];
- int t,n,k,i,j,m,flag;
- cin>>t;
- while(t--)
- {
- cin>>n>>k;
- Fill(hash,0);
- For2(i,1,n)
- Sca_d(m),hash[m]++;
- flag=1;
- For2(i,1,n)
- if (!hash[i])
- {
- flag=0;
- break;
- }
- else if (hash[i]==1) continue;
- else
- {
- for(j=i+k;j<=n;j+=k)
- if (hash[i]>1&&hash[j]==0)
- {
- hash[j]=1;
- hash[i]--;
- }
- }
- if (flag) cout<<"Jerry\n";
- else cout<<"Tom\n";
- }
- return 0;
- }
HDU5090模拟,hash
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。