一边做一边更新中
Accepts: 1519
Submissions: 10854
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
度熊手上有一本字典存储了大量的单词,有一次,他把所有单词组成了一个很长很长的字符串。现在麻烦来了,他忘记了原来的字符串都是什么,神奇的是他竟然记得原来那些字符串的哈希值。一个字符串的哈希值,由以下公式计算得到:
H(s)=\prod_{i=1}^{i\leq len(s)}(S_{i}-28)\ (mod\ 9973)H(s)=∏i=1i≤len(s)(Si−28) (mod 9973)
S_{i}Si代表 S[i] 字符的 ASCII 码。
请帮助度熊计算大字符串中任意一段的哈希值是多少。
Input
多组测试数据,每组测试数据第一行是一个正整数NN,代表询问的次数,第二行一个字符串,代表题目中的大字符串,接下来NN行,每行包含两个正整数aa和bb,代表询问的起始位置以及终止位置。
1\leq N\leq 1,0001≤N≤1,000
1\leq len(string)\leq 100,0001≤len(string)≤100,000
1\leq a,b\leq len(string)1≤a,b≤len(string)
Output
对于每一个询问,输出一个整数值,代表大字符串从 aa 位到 bb 位的子串的哈希值。
Sample Input
Python
2 ACMlove2015 1 11 8 10 1 testMessage 1 1
1234567 | 2ACMlove20151 118 101testMessage1 1 |
---|
Sample Output
Python
6891 9240 88
123 | 6891924088 |
---|
方法不少,线段树,逆元.本代码是学习了逆元模板的.
C++
#include "stdio.h" #include "string.h" #include "algorithm" using namespace std; const long long mod=9973; long long sum[100005],arr[100005],re[100005]; char str[100005]; int main(int argc, char const *argv[]) { arr[1]=1; for (int i = 2; i < 100005; i++) { arr[i] = arr[mod%i] * (mod - mod/i)% mod; } int N; while (scanf("%d", &N) != EOF) { scanf("%s", str+1); sum[0] = 1; re[0] = 1; for(int i = 1; str[i] != 0 ;i++){ sum[i]=(sum[i-1]*(str[i]-28))%mod; re[i]=arr[sum[i]]; } for (int i = 0; i < N; i++) { long long x,y; scanf("%I64d %I64d", &x,&y); long long temp = re[x-1]; printf("%I64d\n", (sum[y]*temp)%mod); } } return 0; }
123456789101112131415161718192021222324252627282930 | #include "stdio.h"#include "string.h"#include "algorithm"using namespace std;const long long mod=9973;long long sum[100005],arr[100005],re[100005];char str[100005];int main(int argc, char const *argv[]) { arr[1]=1; for (int i = 2; i < 100005; i++) { arr[i] = arr[mod%i] * (mod - mod/i)% mod; } int N; while (scanf("%d", &N) != EOF) { scanf("%s", str+1); sum[0] = 1; re[0] = 1; for(int i = 1; str[i] != 0 ;i++){ sum[i]=(sum[i-1]*(str[i]-28))%mod; re[i]=arr[sum[i]]; } for (int i = 0; i < N; i++) { long long x,y; scanf("%I64d %I64d", &x,&y); long long temp = re[x-1]; printf("%I64d\n", (sum[y]*temp)%mod); } } return 0;} |
---|
Accepts: 1992
Submissions: 7434
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
度熊面前有一个全是由1构成的字符串,被称为全1序列。你可以合并任意相邻的两个1,从而形成一个新的序列。对于给定的一个全1序列,请计算根据以上方法,可以构成多少种不同的序列。
Input
这里包括多组测试数据,每组测试数据包含一个正整数NN,代表全1序列的长度。
1\leq N \leq 2001≤N≤200
Output
对于每组测试数据,输出一个整数,代表由题目中所给定的全1序列所能形成的新序列的数量。
Sample Input
Python
1 3 5
123 | 135 |
---|
Sample Output
Python
1 3 8
123 | 138 |
---|
Hint
如果序列是:(111)。可以构造出如下三个新序列:(111), (21), (12)。
简单题,类似费波那奇数列,但是得大树解.
C++
#include<stdio.h> #include<string> #include<string.h> #include<iostream> using namespace std; //大数模板 //compare比较函数:相等返回0,大于返回1,小于返回-1 int compare(string str1,string str2) { if(str1.length()>str2.length()) return 1; else if(str1.length()<str2.length()) return -1; else return str1.compare(str2); } //高精度加法 //只能是两个正数相加 string add(string str1,string str2)//高精度加法 { string str; int len1=str1.length(); int len2=str2.length(); //前面补0,弄成长度相同 if(len1<len2) { for(int i=1;i<=len2-len1;i++) str1="0"+str1; } else { for(int i=1;i<=len1-len2;i++) str2="0"+str2; } len1=str1.length(); int cf=0; int temp; for(int i=len1-1;i>=0;i--) { temp=str1[i]-'0'+str2[i]-'0'+cf; cf=temp/10; temp%=10; str=char(temp+'0')+str; } if(cf!=0) str=char(cf+'0')+str; return str; } int main() { int N; string C[210]; C[0] = "0"; C[1] = "1"; for(int i = 2;i < 210;i ++) C[i] = add(C[i - 1], C[i - 2]); while(~scanf("%d", &N)){ cout << C[N + 1] << endl; } return 0; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657 | #include<stdio.h>#include<string>#include<string.h>#include<iostream>using namespace std;//大数模板//compare比较函数:相等返回0,大于返回1,小于返回-1int compare(string str1,string str2){ if(str1.length()>str2.length()) return 1; else if(str1.length()<str2.length()) return -1; else return str1.compare(str2);}//高精度加法//只能是两个正数相加string add(string str1,string str2)//高精度加法{ string str; int len1=str1.length(); int len2=str2.length(); //前面补0,弄成长度相同 if(len1<len2) { for(int i=1;i<=len2-len1;i++) str1="0"+str1; } else { for(int i=1;i<=len1-len2;i++) str2="0"+str2; } len1=str1.length(); int cf=0; int temp; for(int i=len1-1;i>=0;i--) { temp=str1[i]-'0'+str2[i]-'0'+cf; cf=temp/10; temp%=10; str=char(temp+'0')+str; } if(cf!=0) str=char(cf+'0')+str; return str;}int main() { int N; string C[210]; C[0] = "0"; C[1] = "1"; for(int i = 2;i < 210;i ++) C[i] = add(C[i - 1], C[i - 2]); while(~scanf("%d", &N)){ cout << C[N + 1] << endl; } return 0;} |
---|
Accepts: 2277
Submissions: 6633
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Problem Description
度熊所居住的 D 国,是一个完全尊重人权的国度。以至于这个国家的所有人命名自己的名字都非常奇怪。一个人的名字由若干个字符组成,同样的,这些字符的全排列的结果中的每一个字符串,也都是这个人的名字。例如,如果一个人名字是 ACM,那么 AMC, CAM, MAC, MCA, 等也都是这个人的名字。在这个国家中,没有两个名字相同的人。
度熊想统计这个国家的人口数量,请帮助度熊设计一个程序,用来统计每一个人在之前被统计过多少次。
Input
这里包括一组测试数据,第一行包含一个正整数NN,接下来的NN 行代表了 NN 个名字。NN 不会超过100,000100,000,他们的名字不会超过40位.
Output
对于每输入的一个人名,输出一个整数,代表这个人之前被统计了多少次。
Sample Input
Python
5 ACM MAC BBA ACM BAB
123456 | 5ACMMACBBAACMBAB |
---|
Sample Output
Python
0 1 0 2 1
12345 | 01021 |
---|
这题很好水过去用map
C++
#include "algorithm" #include "iostream" #include "string" #include "string.h" #include "stdio.h" #include "map" using namespace std; int main(int argc, char const *argv[]) { int N; map<string, int> map1; cin >> N; while (N--) { char temp[51]; scanf("%s", temp); sort(temp, temp + strlen(temp)); if(!map1[string(temp)]) map1[string(temp)] = 0; cout << map1[string(temp)] << endl; map1[string(temp)]++; } return 0; }
12345678910111213141516171819202122 | #include "algorithm"#include "iostream"#include "string"#include "string.h"#include "stdio.h"#include "map"using namespace std;int main(int argc, char const *argv[]) { int N; map<string, int> map1; cin >> N; while (N--) { char temp[51]; scanf("%s", temp); sort(temp, temp + strlen(temp)); if(!map1[string(temp)]) map1[string(temp)] = 0; cout << map1[string(temp)] << endl; map1[string(temp)]++; } return 0;} |
---|