http://bestcoder.hdu.edu.cn/
Problem A
题目链接：
http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=690&pid=1001
http://acm.hdu.edu.cn/showproblem.php?pid=5685
题目分析：
因为是中文题目，便不再赘述
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e5 + 5;
int H[MAXN];
char Hstr[MAXN];
int N, l, r;
const int mods = 9973;
typedef long long LL;
LL mod_pow(LL x, LL n, LL mod) {
LL res = 1;
while(n > 0) {
if(n & 1) res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
int main(){
while(~scanf("%d", &N)){
scanf("%s", Hstr);
int len = strlen(Hstr);
H[0] = 1;
for(int i = 1;i <= len;i ++){
H[i] = H[i - 1] * (Hstr[i - 1] - 28) % mods;
}
while(N --){
scanf("%d%d", &l, &r);
if(l > r) swap(l, r);
printf("%I64d
", (LL)H[r] * mod_pow(H[l - 1], mods - 2, mods) % mods);
}
}
return 0;
}
Problem B
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5686
题目分析：
1 1 1
2 11 2 2
3 111 21 12 3
4 1111 211 112 121 22 5
5 8
所以，很容易推出 F[i] = F[i-1] + F[i-2]
需要注意的地方是这里必须使用大数加法，不然会报错
代码：
#include <iostream>
#include<string.h>
#include <stdio.h>
using namespace std;
int a[205][205];
int main()
{
memset(a,0,sizeof(a));
a[1][200]=1;a[2][200]=2;
int i,j;
for(i=3;i<=200;i++)
{
for(j=200;j>0;j--)
{
a[i][j]=a[i][j]+a[i-1][j]+a[i-2][j];
if(a[i][j]>9)
{
a[i][j-1]=a[i][j]/10;
a[i][j]=a[i][j]%10;
}
}
}
int n;
while(cin>>n)
{
j=0;
while(a[n][j]==0)j++;
for(;j<=200;j++)
{
cout<<a[n][j];
}
cout<<endl;
}
return 0;
}
Problem C
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5687
题目分析：
使用字典树
代码：
#include<cstdio>
#include<cstring>
#include<stdlib.h>
const int N=26;
struct node{
int flag; // 记录该单词出现的次数;
node *next[N];
node(){
flag=0;
memset(next,0,sizeof(next));
}
};
node *p,*pre,*head=new node();
void Insert(char s[])
{
p=head;
int i=0;
while(s[i]){
int id=s[i++]-'a';
if(p->next[id]==NULL) p->next[id]=new node();
p=p->next[id];
p->flag++; // 标记该分支字母出现的个数;
}
//p->flag++; // 标记改单词出现过,并且记录出现的次数;
}
// 返回该单词出现的次数;
int Query(char s[])
{
p=head;
int i=0;
while(s[i]){
int id=s[i++]-'a';
if(p->next[id]==NULL) return 0;
p=p->next[id];
}
return p->flag;
}
// 不能删除，删除会导致TLE,不删除容易出现内存泄漏MLE
int deal(node *T)
{
for(int i=0;i<N;i++){
if(T->next[i]!=NULL)
deal(T->next[i]);
}
free(T);
return 0;
}
// 该单词的计数-cnt;
void Deal(char s[],int cnt)
{
p=head;
int i=0;
while(s[i]){
int id=s[i++]-'a';
p=p->next[id];
p->flag-=cnt;
}
for(int i=0;i<N;i++){
p->next[i]=NULL;
}
//deal(p);
return ;
}
int main()
{
int n;
char s1[35],s2[35];
while(~scanf("%d",&n)){
head=new node();
for(int i=0;i<n;i++){
scanf("%s %s",s1,s2);
if(strcmp(s1,"insert")==0) Insert(s2);
if(strcmp(s1,"search")==0){
if(Query(s2)) printf("Yes
");
else printf("No
");
}
if(strcmp(s1,"delete")==0){
int t=Query(s2); // 前缀为s2的单词出现的次数;
if(t)Deal(s2,t);
}
}
//deal(head);
}
return 0;
}
Problem D
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5688
题目分析：
使用map容器做
代码：
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
map<string,int>m;
char s[100];
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",s);
sort(s,s+strlen(s));
m[s]++;
printf("%d
",m[s]-1);
}
return 0;
}
anytime you feel the pain.hey,refrain.don't carry the world upon your shoulders
分类: ACM