水题记录(五)

8

[BZOJ3032] 七夕祭

同BZOJ1045,如果要求满足行和列就行算一遍,列算一遍,然后加起来。

[BZOJ3033] 太鼓大人

题解貌似是求欧拉回路,不太清楚。打的暴力能过,具体做法是搜前$k$ 个和后$k$个,中间搜的时候减枝,貌似跑得很快,貌似直接$2^{2^k}$也可以过….

[BZOJ3031] 理科男

数学题…我数学好差啊..

首先50分的暴力就是记录一下余数出现的位置,如果下次出现了这个余数就可以找到循环节,最开始是A,每算一次是$a \cdot k^{times}~mod~b$。

正解:

考虑$(b,k)$是否等于$1$,也就是$b,k$是否互质。

如果互质,可以发现一定是一个纯循环小数。证明:设$p$为第一次循环的位置,$a[p]$为第$p$次得到的余数,而$a[q]$是第$q$ 次,如果有$a[p]=a[q]$且$p!=1$,那么$a[p-1]=a[p]cdot k^{-1}=a[q-1] cdot k^{-1}=a[q-1]$,与$p$为第一次循环的位置矛盾。所以目的是求出循环的长度$len$。设$a[1]=a[q]$,那么$a[q]=a[1] times k ^{len}=a[1]$,要最小化$len$.

问题变成了求$k$模$b$的阶。如果不是$1$的话,可以$BSGS$解决,这个情况可以用到特殊性质。

根据偶拉定理$k^{phi(b)} =1 ~ mod~ b$,而最小答案$ans|{phi(b)}$,可以暴力枚举$phi(b)$的因数,如果$(ans/p[i])^{phi(b)}=1$,那么可以把$ans/p[i]$。最后算出来的一定是答案。

如果不互质,把$b$不断除$gcd(b,k)$,知道$gcd(b,k)=1$,除了多少次,混循环就是几(这样的话会使$[1,t]$的答案与后面无关(这里我不知道为什么啊)

如果$b=1$,答案就是$0$,否则转化为上面互质的情况。

吐槽:我这个不会做这题的juruo还是去普及组好了(来自出题人的建议

[BZOJ4260] Codechef REBXOR

求一个区间最大异或和的方法是对于前缀和建立Trie树,然后每次查询的时候贪心(如果这一位上有相反的数就走)。

[BZOJ3059] 归途与征程

按照星号分开每段预处理,Hash 。复杂度$O(nmlogn)$,存一下省一个lower_bound就可以$O(nm)$

[BZOJ3687] 简单题

因为总和不超过$2e6$,而对于每个数,出现奇数次才会有贡献。开一个bitset,bit[i]维护第i位出现是奇数还是偶数次。对于每一个数x,f = f xor f << x。

[BZOJ2125 and BZOJ3047] 最短路 and Freda的传呼机

求仙人掌最短路,方法是把一个环里面的点都向环顶(环中深度最小的的点)连边。然后倍增,找到$x$和$y$的LCA下面的两个点。

如果这两个点相等或者是环顶按树的情况处理,否则计算出环上的两点最短路(环长-距离),加上x到倍增的点的距离和y到倍增的点的距离。

[BZOJ 3054] Rinbow的信号
对于每一位考虑,对于$i$位置,计算前面有多少个点到自己的区间可以使得这一位的答案是1。And和Or很好做,而异或的话,如果这一位是0,答案是f[i-1],否则是i-f[i-1]。

《水题记录(五)》上有3条评论

  1. 大佬,您wordpress主页显示博文摘要是怎么做到的?

    1. 我知道了,谢谢,需要插件readmore。

      1. 我没有用插件,在文章中加入即可

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*