2016″百度之星” – 资格赛(更新中)

一边做一边更新中

Problem A

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=1​i≤len(s)​​(S​i​​−28) (mod 9973)

S_{i}S​i​​代表 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

Sample Output

Python

6891 9240 88

题解:

方法不少,线段树,逆元.本代码是学习了逆元模板的.

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; }

Problem B

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

Sample Output

Python

1 3 8

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; }

Problem D

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

Sample Output

Python

0 1 0 2 1

题解:

这题很好水过去用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; }