2016 百度之星资格赛题解(hdu 5685,5686,5687,5688,5689)

本文主要是介绍2016 百度之星资格赛题解(hdu 5685,5686,5687,5688,5689)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

此次的百度之星资格赛，题目都比较好理解，就不再给出了。以下是AC的代码，可能存在bug，欢迎大家debug

Problem A
[http://acm.hdu.edu.cn/showproblem.php?pid=5685]
化简过后的题意就是求一段序列中的区间乘，由于询问次数比较多，直接求乘可能会超时，所以想到前缀乘的想法。preMulit[i]表示前i个序列的前缀乘。若要求[l,r]区间内的的数字全乘起来，那么用preMulit[r]/preMulit[l-1]即可，考虑到取模的问题，用到逆元。

#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <cstdio>
#define MaxSize 100000+100
const int mod = 9973;
using namespace std;
char str[MaxSize];
long long PreMulti[MaxSize];long long pow_m(long long x,long long n)
{long long res = 1;while(n>0){if(n&1) res = res*x%mod;x = x*x %mod;n>>=1;}return res;
}
long long inv(long long a)
{return pow_m(a,mod-2);
}
int main()
{int n;while(~scanf("%d",&n)){scanf(" %s",str);int len = strlen(str);PreMulti[0] = 1;for(int i=0;i<len;i++){PreMulti[i+1] = (PreMulti[i]*((int)str[i]-28))%mod;}int a,b;while(n--){scanf("%d%d",&a,&b);if(a>b){int tmp = a; a=b; b=tmp;}printf("%I64d\n",(PreMulti[b]*inv(PreMulti[a-1]))%mod);}}return 0;
}

Problem B
http://acm.hdu.edu.cn/showproblem.php?pid=5686
当前个数与其上一个和上上个的个数相关，所以考虑斐波那契数列，用到大数，不想敲C++模板，所以用了java

import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {int n;BigInteger [] fun = new BigInteger[201];fun[1]=fun[0] = new BigInteger("1");for(int i=2;i<=200;i++){fun[i] = fun[i-1].add(fun[i-2]);}Scanner cin = new Scanner(System.in);while(cin.hasNext()){n = cin.nextInt();System.out.println(fun[n]);}}
}

Problem C
http://acm.hdu.edu.cn/showproblem.php?pid=5687
字典树，很明显。不过要考虑一个问题（当时我没考虑到），比如先插入abc,abd,再删除以abc及为开始的串,再查ab的时候，应该输出No, ab这个单词本来并不存在。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;struct node{node *child[26];bool isExist;node(){for(int i=0;i<26;i++){child[i] = NULL;}isExist = false;}
}*root;
void Insert(char cmp[],node* root)
{node *now = root;int len = strlen(cmp);for(int i=0;i<len;i++){now->isExist = true;if(now->child[cmp[i]-'a']==NULL)now->child[cmp[i]-'a']=new node;now=now->child[cmp[i]-'a'];}now->isExist = true;
}
void Delete(char cmp[],node* root)
{node *now = root;int len = strlen(cmp);for(int i=0;i<len;i++){int cnt =0;for(int j=0;j<26;j++){if(now->child[j]!=NULL){cnt++;}}if(cnt <=1){now->isExist = false;for(int j=0;j<26;j++){if(now->child[j]!=NULL)now->child[j]=NULL;}return ;}now=now->child[cmp[i]-'a'];}now -> isExist = false;for(int i=0;i<26;i++){if(now->child[i]!=NULL)now->child[i]=NULL;}
}
bool Search(char cmp[],node* root)
{node *now = root;bool flag = true;int len = strlen(cmp);for(int i=0;i<len;i++){if(now->child[cmp[i]-'a']==NULL||now->child[cmp[i]-'a']->isExist == false){flag = false;break;}now=now->child[cmp[i]-'a'];}return flag;
}
void TireClear(node* now){for(int i=0;i<26;i++){if(now->child[i]!=NULL) TireClear(now->child[i]);}delete now;
}
char ope[10],str[35];
int main()
{int N;scanf("%d",&N);root = new node;while(N--){scanf(" %s%s",ope,str);if('i'==ope[0]){Insert(str,root);}else if('d'==ope[0]){if(Search(str,root))Delete(str,root);}else if('s'==ope[0]){if(Search(str,root))printf("Yes\n");elseprintf("No\n");}}TireClear(root);return 0;
}

Problem D
用map映射，很简单想到
http://acm.hdu.edu.cn/showproblem.php?pid=5688

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>using namespace std;
const int INF=0x3f3f3f3f;
char s[100005];
int N;
map<string,int> MP;
string now;
int main()
{while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++){cin>>now;sort(now.begin(),now.end());printf("%d\n",MP[now]);MP[now]++;}}return 0;
}

Problem E
http://acm.hdu.edu.cn/showproblem.php?pid=5689
一道模拟题，求当前式子与前面的式子是否矛盾，当输入的是复合句子的时候，对自身检查是否矛盾，如果是那么这个句子以后也就不需要检查了，否则对前面所有的句子进行检查，依次输出。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <map>
#define MaxSize 1000+10
using namespace std;
//每个简单条件
struct formula{string name,ope;int number;
};
//每个复合条件
struct node{int id;int fcnt;bool isRight; //复合式子本身是否合法formula f[500];node(){fcnt = 0;isRight = true;}
}Each[MaxSize];//判断交集
bool Judge(formula x,formula y){if(x.name != y.name)return true;bool ok = true;if(x.ope=="=="){if(y.ope=="=="&&y.number!=x.number){ok = false;}else if(y.ope==">"&&y.number>=x.number){ok = false;}else if(y.ope==">="&&y.number>x.number){ok = false;}else if(y.ope=="<"&&y.number<=x.number){ok = false;}else if(y.ope=="<="&&y.number<x.number){ok = false;}}else if(x.ope==">"){if(y.ope=="=="&&y.number<=x.number){ok = false;}//3 <x <4 is not okelse if(y.ope=="<"&&y.number<=x.number+1){ok = false;}else if(y.ope=="<="&&y.number<=x.number){ok = false;}}else if(x.ope==">="){if(y.ope=="=="&&y.number<x.number){ok = false;}//3 <x <4 is not okelse if(y.ope=="<"&&y.number<=x.number){ok = false;}else if(y.ope=="<="&&y.number<x.number){ok = false;}}else if(x.ope=="<"){if(y.ope=="=="&&y.number>=x.number){ok = false;}else if(y.ope==">"&&y.number>=x.number-1){ok = false;}else if(y.ope==">="&&y.number>=x.number){ok = false;}}else if(x.ope=="<="){if(y.ope=="=="&&y.number>x.number){ok = false;}else if(y.ope==">"&&y.number>=x.number){ok = false;}else if(y.ope==">="&&y.number>x.number){ok = false;}}return ok;}
int main()
{int N;scanf("%d",&N);int allcnt = 0;int idcnt = 0;while(N--){Each[allcnt].id = ++idcnt;string str;scanf("\n");getline(cin,str);int len = str.length();string tope="";string tname="";int number = 0;//number < 0;bool isS = false;//模拟出每行输入的简单式子for(int i=0;i<len;i++){if(isalpha(str[i])){tname += str[i];}else if(isdigit(str[i])){number = (number*10)+(str[i]-'0');}else if(str[i]=='>'||str[i]=='<'||str[i]=='='){tope += str[i];}//负数else if(str[i]=='-'){isS = true;}if(str[i]==',' || i==len-1){if(isS) number = -number;Each[allcnt].f[Each[allcnt].fcnt].name = tname;Each[allcnt].f[Each[allcnt].fcnt].ope = tope;Each[allcnt].f[Each[allcnt].fcnt++].number = number;tope="";tname="";number = 0;isS = false;}}//对复合句子本身进行判断，如果本身就是空集，就Passnode now = Each[allcnt];bool flag = true;for(int i=0;i<now.fcnt;i++){for(int j=0;j<now.fcnt;j++){if(now.f[i].name==now.f[j].name&&now.f[i].number==now.f[j].number&&now.f[i].ope==now.f[j].ope)continue;if(!Judge(now.f[i],now.f[j])){Each[allcnt].isRight = false;flag = false;break;}}}//对每个式子进行判断bool searchflag = false;for(int i=0;i<allcnt&&flag;i++){node tmp = Each[i];if(!tmp.isRight) continue;bool ok = true;for(int j=0;j<now.fcnt;j++){for(int k=0;k<tmp.fcnt;k++){if(!Judge(now.f[j],tmp.f[k])){ok = false;break;}}}if(ok){if(searchflag) printf(" ");printf("%d",i+1);searchflag = true;}}if(!flag||!searchflag){printf("unique\n");}else printf("\n");allcnt++;}return 0;
}