看题：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=690
| Solved | Pro.ID | Title | Author | Source | (AC/Submit)Ratio |
 |
5685 | Problem A | 2016″百度之星” – 资格赛（Astar Round1） | (215/533)40.34% | |
|
5686 | Problem B | 2016″百度之星” – 资格赛（Astar Round1） | (150/424)35.38% | |
|
5687 | Problem C | 2016″百度之星” – 资格赛（Astar Round1） | (187/532)35.15% | |
|
5688 | Problem D | 2016″百度之星” – 资格赛（Astar Round1） | (226/315)71.75% | |
|
5689 | Problem E | 2016″百度之星” – 资格赛（Astar Round1） | (36/72)50.00% |
A.题意：定义小写字母组成的字符串的哈希值，为(单个字母的ASCII码减去28)的乘积。给出长度最多为100000的字符串和最多1000次询问，每次询问[L,R]之间的字符串的哈希值。
题解：
有多种做法。
1.逆元 2.线段树 3.分块数组
1.逆元做法：因为每次求区间[L,R]乘积，可以用[1,R]乘（[1,L-1]的逆元），就用预处理前缀积、前缀积逆元来搞，O(1)查询。好像代码写起来最简单。
2.线段树、块状数组做法：就做啊。线段树O(log(n))查询
我的是块状数组的，分sqrt大块，预处理大块，O(sqrt(n))查询，不是很推荐。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-;
const int MAXN=;
const int MOD=;
int n;
int a[MAXN],b[MAXN];
char s[];
int l; int q[];
int ql; void init() {
int i,j;
ql=sqrt(l);
int qll = l/ql;
REP(i,qll) {
q[i]=;
int ed = (i+)*ql - ;
FOR(j,i*ql,ed) {
q[i]*=s[j];
q[i]%=MOD;
}
}
} int gank(int a,int b) {
if(a==b)return s[a];
int sti=ceil(1.0*a/ql), edi=b/ql;
int st = sti*ql;
int ed = edi*ql;
int i;
int re=;
if(ed<st) {
FOR(i,a,b) {
re*=s[i];
re%=MOD;
}
} else {
FOR(i,a,st-) {
re*=s[i];
re%=MOD;
}
FOR(i,sti,edi-) {
re*=q[i];
re%=MOD;
}
FOR(i,ed,b) {
re*=s[i];
re%=MOD;
}
}
return re;
} int farm() {
int i;
l=strlen(s);
REP(i,l)s[i]-=;
init();
REP(i,n) {
WN(gank(a[i], b[i]));
}
} int main() {
int i;
while(RD(n)!=EOF) {
scanf(" %s",s);
REP(i,n) {
RD2(a[i],b[i]);
a[i]--;
b[i]--;
}
farm();
}
return ;
}
B.定义全1序列，其中任意2个1可以组成1个2。给出1的数量（N<=200），求可以组成多少不同的序列。
题解：
找规律，或者推出规律。
设n个1组成的不同序列数量为a[n]，可以得知规律：
a[n] = a[n-1] + a[n-2]
相当于n-2的序列后面跟个2，n-1的序列后面跟个1。
注意，从公式可以看出，最后答案大上天，比2^200大，用java的BigInteger搞。
代码：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.math.BigInteger; public class Main { private static final int MAXN = ; private static final StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
private static final PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); private static int RD(StreamTokenizer in) throws IOException {
in.nextToken();
return (int) in.nval;
} public static BigInteger gank(int x){
BigInteger[] a = new BigInteger[x+];
a[]=BigInteger.ONE;
a[]=BigInteger.ONE.add(BigInteger.ONE);
for(int i=; i<=x; i++){
a[i]=a[i-].add(a[i-]);
}
return a[x];
} public static void main(String[] args) throws IOException {
while (in.nextToken() != StreamTokenizer.TT_EOF) {
int n = (int) in.nval;
out.println(gank(n));
// for (int i = 0; i < n; i++) {
// int x = RD(in);
//// ma = Math.max(ma, x);
// out.println(gank(x));
// } // out.printf("%s\n", ans);
out.flush();
}
} }
C.题面：
度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：
1、insert : 往神奇字典中插入一个单词
2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词
3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串10W个操作，字符串长度不超过30。
题解：
可以看出这是Trie树题，不过有一般Trie树题没有的删除操作。注意删除时找到那个节点，得到通过节点的字符串数x, 然后子树也要处理，到根的路径也要处理。
子树可以删掉，也可以字符串数清零。到根的路径每个点减去x。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-;
const int MAXN=;
const int MAXM=; class Trie{
public:
Trie* a[];
int n;
Trie(){
int i;
REP(i,)a[i]=NULL;
n=;
}
}; Trie root; inline void ins(char s[MAXM]) {
int l=strlen(s);
int i,j;
Trie *pre = &root;
REP(i,l) {
int c = s[i] - 'a';
Trie *x = pre->a[c];
if(x==NULL) {
pre->a[c] = new Trie();
x = pre->a[c];
}
pre->n++;
pre=x;
}
pre->n++;
} inline Trie* sch(char s[MAXM]) {
int l=strlen(s);
int i;
Trie *x = &root;
REP(i,l) {
int c = s[i]-'a';
x = x->a[c];
if(x==NULL || x->n<=)return NULL;
}
return x;
} inline void delSon(Trie *x){
int i;
if(x->n<=)return;
REP(i,)if(x->a[i]!=NULL){
delSon(x->a[i]);
}
// delete(x);
x->n=;
} inline int del(const int &now, const int &l ,Trie *x, char s[MAXM]) {
char c = s[now]-'a';
Trie *w = x->a[c];
if(w==NULL || w->n<=)return ;
if(now==l-){
int n = w->n;
// x->a[c]=NULL;
delSon(w);
return n;
}
w->n -= del(now+, l, w, s);
} int main() {
int i,n;
char c[MAXM],s[MAXM];
RD(n);
root = Trie();
REP(i,n) {
scanf(" %s %s",c,s);
if(c[]=='i')ins(s);
else if(c[]=='d')del(,strlen(s),&root,s);
else {
if(sch(s)!=NULL) puts("Yes");
else puts("No");
}
}
return ;
}
D.定义某国人名：人名中的任意字母换位置，还是指同一个人。输入10W个人名，对每次输入输出这个人之前出现过多少次。
题解：
对每个人名排序一下再加入map里，随便统计。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-;
const int MAXN=; int n;
map<string,int> q; int main(){
int i;
char s[];
RD(n);
REP(i,n){
scanf(" %s",s);
int l = strlen(s);
sort(s,s+l);
string st = s;
WN(q[st]);
q[st]++;
}
return ;
}
E.题面说得超不清楚，根本不可能看懂，所以第一天只有一点点人过这题。我写一下根据Clarify中的参赛者讨论得到的题面：
样例输入：a <
c >
b > , b == , c <
a < , a >=
样例输出：
uniqueunique
其中第一个数N为下面的行数，最多1000。各种变量名最长30。
对于每行输入，输出上面有哪些行与它给出的范围有交集。
例如第二行的c>99，因为第一行没有规定c的范围，相当于c是[-无限，+无限]，第二行没有规定a的范围，所以（第一行）交（第二行）不为空。
第三行的b有冲突，是个空集，所以它和谁都不交。
第四行的确和第一行、第二行交。
还有个没说的地方是这个只看整数，a>99, a<100是空集。
题解：
可以看出每行对于每个变量只有一个区间，就暴力模拟就行了。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define FORD(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("1.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
typedef long long LL;
typedef unsigned long long ULL; const double PI=acos(-1.0);
const double EPS=1e-;
const int MAXN=;
const int MAXM=; char w[MAXN][MAXM];
int wn;
int q[MAXN];
int qn; int n;
int L[MAXN][MAXM];
int R[MAXN][MAXM];
bool isPig[MAXN]; map<string, int>mp;
int xn;
void add(int k, char xx[MAXM], char oo[MAXM], int yy) {
string name = xx;
if(mp.find(name)==mp.end())mp[name] = xn++;
int x = mp[name]; if(oo[]=='<') {
if(oo[]=='=') R[k][x] = min(R[k][x], yy);
else R[k][x] = min(R[k][x], yy - );
} else if(oo[]=='>') {
if(oo[]=='=') L[k][x] = max(L[k][x], yy);
else L[k][x] = max(L[k][x], yy + );
} else {
L[k][x] = max(L[k][x], yy);
R[k][x] = min(R[k][x], yy);
}
if(L[k][x]>R[k][x])isPig[k]=;
} void saveTheEquals() {
int i,j,k;
mp.clear();
xn=;
MZ(isPig);
REP(i,n) REP(j,) {
L[i][j]=-;
R[i][j]=;
}
i=;
j=;
k=;
while(i<wn) {
if(!isPig[k])add(k,w[i],w[i+],q[j]);
j++;
if(w[i+][]!=',') {
k++;
i+=;
} else i+=;
}
} inline bool banana(const int &x,const int &y,const int &k) {
int &L1 = L[x][k];
int &R1 = R[x][k];
int &L2 = L[y][k];
int &R2 = R[y][k];
if(L1<=L2 && L2<=R1)return true;
if(L2<=L1 && L1<=R2)return true;
return false;
} void farm() {
int i,j,k;
REP(i,n) {
vector<int>v;
v.clear();
if(!isPig[i]) {
REP(j,i) {
bool ok=true;
if(isPig[j])continue;
REP(k,xn) {
if(!banana(i,j,k)) {
ok=false;
break;
}
}
if(ok) {
v.push_back(j+);
}
}
}
if(v.size()==) {
puts("unique");
} else {
printf("%d",v[]);
for(j=; j<v.size(); j++)
printf(" %d",v[j]);
puts("");
}
}
} int main() {
// RE;
int i,j;
char s[MAXM];
char line[MAXN];
RD(n);
wn=;
qn=;
while(scanf(" %s",s)!=EOF) {
strcpy(w[wn],s);
wn++;
if(s[]!=',') {
scanf(" %s %d",w[wn], &q[qn]);
wn++;
qn++;
}
}
saveTheEquals();
farm();
return ;
}
