[2017 HDU多校赛] 解题报告

写一下这几天多校赛做的题目

#Round 1

今天只做出一道题…

Hints of sd0061

题目大意: 给你生成一个数列的种子, 生成一个长度达到[latex]10^7[/latex]的数列, 接下来你需要回答100个第k大数的询问。

解题报告

这道题…首先写了一个大力桶排, 桶两次, 发现过不了??
@WC2017, 于是桶4次, 依然过不了??
然后想到分块…首先按找二进制高16位分块, 每个块开一个vector保存块内数字, 询问直接在块上二分, 然后进入块内大力std::sort查询, 依然时间超限…
最后结合了一下两个做法…由于发现当长度很大时, 生成的数列数值分布比较均匀, 于是当长度较小时直接大力桶排, 长度达到一个阀值就把询问直接离线一发, 然后数列按照二进制高12位分块, 直接用查询的rank算出这个数很可能被分到哪里去, 然后暴力std::sort查询即可。
就过了?
然后后半场我啥也没做出来…

#Round 2

今天又只做出一道题…

hash

题目大意: 给你一个可以O(1)生成[latex]10^6 \times 10^6[/latex]大小01矩阵指定坐标上的值得哈希函数和它的一个[latex]10^3\times 10^3[/latex]大小的01子矩阵, 问这个子矩阵的出现位置。

解题报告

又一道傻逼题…

鉴于在原01矩阵中随机选择一个01位, 出现在子矩阵中的可能性为[latex]\frac{1}{10^6}[/latex], 那么按照期望我平均只要随机[latex]10^6[/latex]次就可以随机到。

那么我们把子矩阵按照64位unsigned long long进行压位, 然后塞到一个哈希表里, 然后开始随机大矩阵中的一个坐标, 用哈希函数算出连续64位的哈希值, 然后查表, 如果查到了就直接输出答案, 否然继续随机。

很明显总哈希值数量为[latex]10^{12}[/latex], 远远小于unsigned long long的[latex]2^{64}[/latex], 冲突概率是极小的。

差点全场第一个AC这题…可惜rand函数范围太小QwQ…

然后后半场各种弃疗, 一道题也没A。

#Round 3

今天一道题都没做…

主要是因为hdu炸了!不知道为什么CQ今天就是不能访问, UOJ裙内dalao都说没有问题但是我们就是访问不起!

然后在星巴克浪了一下午…更了一篇小说和这个博客。

#Round 6

别问我前几场去哪里了…

String

题目大意: 给你N个全小写字母单词, 然后再给M个询问, 每次询问给出一个前缀和后缀, 问所有单词中有多少满足这个前后缀并且前后缀不重叠。
[latex]单词和询问总长度≤10^6[/latex]

解题报告

字符串处理题…考试的时候傻逼了杠了好久不重叠没想出来…本来很正解了…
首先把单词离线, 字典序排序, 然后每个询问前缀就转化成了在一段区间内的单词进行询问。
然后写一个可持久化Trie把所有单词翻转后挨个按照字典序插♂入其中, 就转化成在可持久化Trie上进行询问了
接下来就是去重的问题了..
大力方法:首先把所有单词哈希一波塞到哈希表里, 然后大力用哈希计算每个询问的前后缀可以怎么重叠, 然后到哈希表里进行查询去重即可.
考试时就是没有想到啊QAQ泪崩
这个算法是全线性的, 但是由于Hineven比较懒直接strcmp排序(用字典树应该更快), 并且没有手写哈希表, 就不是线性的啦…
跑了300ms+, 还算很快的, 应该还可以更快但是我懒嘛…
顺便一提:哈希如果使用这种姿势: hash[i] = hash[i-1]*SEED+str[i]-'a' 会被这么爆卡: a->0, aa->0, aaa->0
以后注意, 放个代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <set>
#include <map>
using namespace std;
typedef unsigned long long ULL;
const int MAXN = 100010;
const int MAXL = 5000050;
const int MAXM = 100010;

char mempool[MAXL*2];
char *words[MAXN];
char *qry[MAXM][2];
int wlen[MAXN], qlen[MAXM][2];
bool diccmp (char * s1, char * s2) {
	return strcmp(s1, s2) < 0;
}

namespace Hash {
	map<ULL, unsigned> mp;
	const ULL HASHSEED = 29;
	ULL powr[MAXL];
	void init () {
		powr[0] = 1;
		for(int i = 1; i<MAXL; i++)
			powr[i] = powr[i-1]*HASHSEED;
	}
	void clear () {
		mp.clear();
	}
	void insert (char * str) {
		ULL code = 0;
		while((*str) != '\0') {
			code = code*HASHSEED+*str;
			++ str;
		}
		mp[code] ++;
	}
	ULL hashtmp1[MAXL], hashtmp2[MAXL];
	unsigned overcovered(int p) {
		int a = qlen[p][0], b = qlen[p][1];
		hashtmp1[0] = qry[p][0][0];
		for(int i = 1; i<a; i++)
			hashtmp1[i] = hashtmp1[i-1]*HASHSEED+qry[p][0][i];
		hashtmp2[0] = qry[p][1][0];
		for(int i = 1; i<b; i++)
			hashtmp2[i] = hashtmp2[i-1]*HASHSEED+qry[p][1][i];
		ULL e = hashtmp1[a-1];
		int t = min(a, b);
		unsigned ret = 0;
		for(int i = 1; i<=t; i++) {
			ULL tmp;
			if(a-i-1 >= 0) tmp = hashtmp1[a-i-1];
			else tmp = 0;
			if(e-tmp*powr[i] == hashtmp2[i-1]) {
				ULL code = tmp*powr[b]+hashtmp2[b-1];
				//printf("qcode:%llu\n", code);
				if(mp.find(code) != mp.end())
					ret += mp[code];
			}
		}
		//printf("cut:%u\n", ret);
		return ret;
	}
}

namespace Trie {
	const int MAXD = MAXL;
	struct Node {
		int cnt;
		int ch[26];
	} d[MAXD];
	int dtot;
	int roots[MAXN], rtot;
	void clear () {
		rtot = dtot = 0;
	}
	int newNode (int base) {
		memcpy(d+(++dtot), d+base, sizeof d[0]);
		return dtot;
	}
	char temp[MAXL];
	void insertReverse (char * ss, int len) {
		for(int i = 0; i<len; i++)
			temp[len-i-1] = ss[i];
		rtot ++;
		roots[rtot] = newNode(roots[rtot-1]);
		int u = roots[rtot], lst = roots[rtot-1];
		for(int i = 0; i<len; i++) {
			d[u].cnt ++;
			u = (d[u].ch[temp[i]-'a'] = newNode(d[lst].ch[temp[i]-'a']));
			lst = d[lst].ch[temp[i]-'a'];
		}
		d[u].cnt ++;
	}
	int query(int u, char * str) {
		while((*str) != '\0') {
			u = d[u].ch[(*str)-'a'];
			str ++;
			if(!u) return 0;
		}
		return d[u].cnt;
	}
	int queryReverse (int linv, int rinv, char *ss, int len) {
		if(linv > rinv) return 0;
		for(int i = 0; i<len; i++)
			temp[len-i-1] = ss[i];
		temp[len] = '\0';
		return query(roots[rinv], temp)-query(roots[linv-1], temp);
	}
}

int main () {
	int N, M, cas;
	scanf("%d", &cas);
	Hash :: init();
	while(cas --) {
		scanf("%d%d", &N, &M);
		words[1] = mempool;
		Hash :: clear();
		for(int i = 1; i<=N; i++) {
			scanf("%s", words[i]);
			Hash :: insert(words[i]);
			words[i+1] = words[i]+(strlen(words[i])+1);
		}
		qry[1][0] = words[N+1];
		for(int i = 1; i<=M; i++) {
			scanf("%s", qry[i][0]);
			qlen[i][0] = strlen(qry[i][0]);
			qry[i][1] = qry[i][0]+qlen[i][0]+2;
			scanf("%s", qry[i][1]);
			qlen[i][1] = strlen(qry[i][1]);
			qry[i+1][0] = qry[i][1]+qlen[i][1]+1;
		}
		sort(words+1, words+N+1, diccmp);
		Trie :: clear();
		for(int i = 1; i<=N; i++)
			Trie :: insertReverse(words[i], strlen(words[i]));
		
		for(int i = 1; i<=M; i++) {
			int lpos = lower_bound(words+1, words+N+1, qry[i][0], diccmp)-words;
			qry[i][0][qlen[i][0]] = 'z'+1;
			qry[i][0][qlen[i][0]+1] = '\0';
			int rpos = (upper_bound(words+1, words+N+1, qry[i][0], diccmp)-words)-1;
			qry[i][0][qlen[i][0]] = '\0';
			printf("%d\n", Trie :: queryReverse(lpos, rpos, qry[i][1], qlen[i][1])-Hash :: overcovered(i));
		}
	}
	fclose(stdout);
}