标签归档:bitset

“玲珑杯”ACM比赛 Round #18做题记录

这场比赛感觉题目较为简单,但是体验较差。主要是评测机崩掉了,然后莫名延时莫名突然结束,算了,按照qwertier大爷的口头禅:“这都无所谓了,反正你那么垃圾早过一个题又能怎样?”

A — 计算几何你瞎暴力

题意:略。

因为坐标范围较小,最多也就一千多个,所以暴力枚举然后统计一个关于距离的前缀和就好了。但是因为我一开始的脑子进水了,居然调了很久。

B — 数论你还会快速幂

题意:给出\(n\),\(p\),\(k\),范围都是\(10^{18}\),并且保证\(0 \leq n-p \leq 100\)。求\(\sum_{i=1}^{n}i^{k} \mod p\)

我是打表找规律,首先大于p的幂和不会超过100项所以选择直接暴力。那么转化成我们要求这么一个东西\(\sum_{i=1}^{p}i^{k} \mod p\)。那么当k为奇数的时候这部分一定是0.但是偶数的部分我不知道,所以选择打表,发现也是0。。。。当然,当k时p-1倍数的话,这一坨是p-1,根据费马小定理。。。所以说我们直接从p算到n求个快速幂就可以了,为什么要从p呢?因为会有k=0的情况,这时候\(p^{k} \mod p=1\)。机房几位大爷比我先发现这个规律,但是貌似就是因为这个坑,没我A的早。。。但是A了以后还是把我踩爆。。。

至于正解貌似是从原根角度证明的。。。我连原根是啥都不知道,贴个链接好了:链接

C — 图论你先敲完模板

题意:略。

和开火车的一道煞笔题一样的思想,就是随着距离增大增长是指数级的,这也就意味着当两个点距离过大的时候肯定分段比不分段优秀。。。所以\(n^2\)的dp就可以优化到\(nlogn\)

D — 最后你还是AK了

题意:略。

一开始以为是求一种分配方案让最长路径上的值最大,不会做。。。最后还剩半个小时才听闻原来是求sum最大。然后写完突然又告诉我比赛结束了。。。

那么每条边被经历的次数一定是他两个端点\(u\),\(v\)的子树大小中的最小值。所以我们可以先求出来每条边被经历了多少次,再考虑如何让路径和最大。那么自然是给经历次数最多的边次多的边依次加最大的变化,次大的变化这样的。。。。

所以就是dfs完成后,排序贪心。

E — 数据结构你干瞪眼啊

题意:给出一个\(n*m\)的矩阵,\(n*m<=100000\),每个值在\([0,255]\)的范围内。有\(q\)次操作。

(1)询问某个格子的值

(2) 询问某一行一段区间有多少种不同的值。

(3)某一行区间加一个数并且模256

(4)某一行区间翻转

比赛的时候看到了\(n*m<=100000\)的条件,但是因为下意识的想的是二维数据结构,或者什么东西套个分块之类的。。。觉得自己的码力根本没法写。。。。简直傻逼透顶。。。

其实直接当成区间操作就好了,然后splay随便做,维护一个256位的bitset的标记记录一下子树都有哪些值即可。如果没有区间翻转直接线段树就可以了。

 

hdu 5745 La Vie en rose(bitset优化字符串匹配)

Problem Description
Professor Zhang would like to solve the multiple pattern matching problem, but he only has only one pattern string p=p1p2...pm. So, he wants to generate as many as possible pattern strings from p using the following method:

1. select some indices i1,i2,...,ik such that 1i1<i2<...<ik<|p| and |ijij+1|>1 for all 1j<k.
2. swap pij and pij+1 for all 1jk.

Now, for a given a string s=s1s2...sn, Professor Zhang wants to find all occurrences of all the generated patterns in s.

 

Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains two integers n and m (1n105,1mmin{5000,n}) — the length of s and p.

The second line contains the string s and the third line contains the string p. Both the strings consist of only lowercase English letters.

 

Output
For each test case, output a binary string of length n. The i-th character is “1” if and only if the substring sisi+1...si+m1 is one of the generated patterns.

 

Sample Input
3
4 1
abac
a
4 2
aaaa
aa
9 3
abcbacacb
abc
Sample Output
1010
1110
100100100
题意:给出一个长度不超过10^5的母串,以及一个不超过min(n,5000)的模式串。输出母串中可以匹配到的模式串的起始位置。在匹配的过程中,模式串的字符是可以交换的,但是这种交换是不能有交叉的,也就是说位置1和2互换,2和3是不能再换的。
有一个暴力的dp:代表了母串第i个字符和模板串第j个字符匹配(这也就意味着有j个字符是匹配的),0代表第i个字符没有发生交换,1代表第i个字符和前面i-1这个字符发生互换,2代表第i个字符和i+1个字符发生互换。
那么转移方程就是:
我们可以用bitset来压第一维,因为是模板串可以交换,所以预处理出来字符集中每个字符在母串可以匹配到的位置。然后用shift-and算法那样的思路来转移就好了,但是因为从j-1转移到j这道题目的转移形式有点多,所以用个滚动数组就好了。

 

hdu 5716 带可选字符的多字符串匹配(shift-and算法)

Problem Description
有一个文本串,它的长度为m(1m2000000),现在想找出其中所有的符合特定模式的子串位置。

符合特定模式是指,该子串的长度为n(1n500),并且第i个字符需要在给定的字符集合Si中。

因此,描述这一特定模式,共需要S1,S2,...,Snn个字符集合。每个集合的大小都在162之间,其中的字符只为数字或大小写字母。

 

Input
第一行为一个字符串,表示待匹配的文本串。注意文本串中可能含有数字和大小写字母之外的字符。

第二行为一个整数n

以下n行,分别描述n个字符集合。每行开始是一个162之间的整数,随后有一个空格,接下来有一个字符串表示对应字符集合的内容。整数表示字符集合的大小,因此它也就是字符串的长度。输入保证字符串中的字符只为数字或大小写字母且没有重复。<b>(注:本题有多组测试数据)</b>

 

Output
每当从某个位置开头的,长度为n的子串符合输入的模式,就输出一行,其中包含一个整数,为它在文本串的起始位置。位置编号从1开始。

如果文本串没有任何位置符合输入模式,则最后输出一个字符串”NULL”,占一行。

 

Sample Input
aaaabacabcabd
3
3 abc
2 bc
3 abc

Sample Output

4
6
8
9
shift-and算法的应用,预处理出来26种字符分别能匹配子串的哪些位置(也就是对应集合的位置)。当到第i个字符,dp[n]等于1的时候,也就意味着存在一种匹配是以i位置为止,向前长度为n的子串满足题意的。注意当读到不属于字符集的字符需要把整个bitset置为0重头算起。。。