写一下这几天多校赛做的题目
#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); }
Join the discussion