12 months ago

这里就放放最近做题的时候碰到的一些原来见过的题目,再拿出来看一看。
这里的题有些比较simple但是都想法蛮好的




计数器:


  • USACOxx年xx月gold 字符串匹配

给出一个长度为N的整数串A,和一个长度为K(K<=N)的整数串B,A和B中的元素均是不大于S的正整数,我们认为两个串是相等的,当两个串的长度相当,并且两个串中,对于任意的i,第i个元素在两个串中的排名是一样的。
例如:
1 2 3 5 4
8 10 23 25 24
这两个串是相等的。
现在要求在A的所有长度=B的长度的子串中,有多少子串与B串相等。

对于100%的数据N<=100000,S<=10000

对于两个串,从前到后一个一个比较,只要满足每加入一个数,它的在之前的数中的排名相同即可。
这样是无后效性的,而且可以保证满足这个条件的串是相等的。
这样就对KMP做一下修改,每次移动模式串的时候,维护每个数出现的次数,用树状数组就可以了。
判断两个数相同的时候,就比较小于它的数的个数是否相同和等于它的数的个数是否相同。


  • [ZJOI2012] 波浪

N <= 100, K <= 30

抛开精度问题不谈,这是一道挺好的dp。
f[i][j][k]代表前i个数,放成了j块,两个边界的情况为k的方案数。
如果i不在边界上,它的贡献是这三种之一: -2i, 0, 2i, 这取决于将它放进去的时候左右有0个1个2个空。
这样就枚举四种情况:

  1. 新开一个块
  2. 合并两个块
  3. 放在某一个块的边缘
  4. 放在左边界或右边界上,此时有可能发生1、3两种情况。

使用高精度即可。


  • 实验

小C一直想变得超级无敌的扛。某天,他神奇般的得到了M+1套一模一样的铠甲。但是,他并不知道这种铠甲的防御度是多大。为了将来变得无敌的扛,他必须对这种铠甲的防御度有充分的了解。于是他决定用M套铠甲来测试防御度。
于是他找来了你,要求你用激光枪来打他。激光枪的攻击力在0~n(可调节),同样的铠甲的防御力也在0~n。铠甲有个“完好程度100%”,如果激光枪的攻击力大于铠甲的防御力,那么瞬间这套铠甲完蛋了,完好程度变为0,此铠甲废掉。如果激光枪的攻击力小于等于铠甲的防御力,那么铠甲的完好程度减少50%。
小C每次只能穿一个铠甲,小C可以随时更换铠甲。
求在最坏情况下,能够用M个铠甲测出此种铠甲防御度的最少测量次数。(激光枪的作用力也是很厉害的)。如果有可能无法测试出来,那么输出‘NO’。

n<=maxint64 – 1 , m<=100

挺有趣的一个dp题, 可以当成一个交互题来做,每次扔过去一个铠甲和一个数值去询问。返回这个铠甲的损坏程度(损坏50%/完全损坏)
f[i][j][k]代表现在有j个100%的铠甲,k个50%的铠甲, 进行i次实验后最多能区分出长度为多少的区间。
如果使用了一个50%的铠甲,那么显然不管返回值是多少,这个铠甲都坏掉了,就变成了两个完全一样的子问题,原问题的解就是子问题解的两倍。
如果使用了一个100%的铠甲,那么返回值有两种可能,一种返回左侧,一种返回右侧,返回左侧的情况下,可以得到一个50%的铠甲,返回右侧就什么也得不到,那么原问题的解就是这两种子问题的解的和。

WARNING
f[i][0][0]的值为1,因为就算没有铠甲,也可以区分出长度为1的区间


  • [SCOI2013] 密码

Fish 是一条生活在海里的鱼。有一天他很无聊,就到处去寻宝。他找到了位于海底深处的宫殿,但是一扇带
有密码锁的大门却阻止了他的前进。
通过翻阅古籍,Fish 得知了这个密码的相关信息:

  1. 该密码的长度为N。
  2. 密码仅含小写字母。
  3. 以每一个字符为中心的最长回文串长度。
  4. 以每两个相邻字符的间隙为中心的最长回文串长度。 很快Fish 发现可能有无数种满足条件的密码。经过分析,他觉得这些密码中字典序最小的一个最有可能是答 案,你能帮他找到这个密码么? 注意:对于两个串A 和B,如果它们的前i 个字符都相同,而A 的第i +1 个字符比B 的第i +1 个字符小, 那么认为是则称密码A 的字典序小于密码B 的字典序,例如字符串abc 字典序小于字符串acb。如果密 码A 的字典序比其他所有满足条件的密码的字典序都小,则密码A 是这些密码中字典序最小的一个。

可以通过暴力的方法来把任意两个位置之间是否一定相同或者一定不同这个限制给求出来
求回文串有manacher算法。可以用manacher算法的思想去掉冗余的限制。这样限制的数量就是O(n)了。
对于每个位置确定值的时候,只要把和他相连的,与它不同的数取mex即可。


  • 约瑟夫问题

为了铭记历史,国王准备在阅兵的间隙玩约瑟夫游戏。它召来了n(1≤n≤5000) 个士兵,逆时针围成一个圈,依次标号 1, 2, 3 ... n。

第一轮第一个人从 1 开始报数,报到 1 就停止且报到 1 的这个人出局。

第二轮从上一轮出局的人的下一个人开始从 1 报数,报到 2 就停止且报到 2 的这个人出局。

第三轮从上一轮出局的人的下一个人开始从 1 报数,报到 3 就停止且报到 3 的这个人出局。

第 n - 1轮从上一轮出局的人的下一个人开始从 1 报数,报到 n - 1 就停止且报到 n−1 的这个人出局。

最后剩余的人是幸存者,请问这个人的标号是多少?

这题非常naive..
dp[i][j]表示i个人玩游戏,从0开始报数,报j个数之后踢人,最后剩下的人的编号。
dp[i][j] = dp[i - 1][j + 1] + j


  • 做任务

现有一款游戏,你作为玩家,拥有k种物品。开始时,每种物品有1000件。

现在,在你面前有n个任务,每种任务都可能消耗一些物品,也可能得到一些物品。做第i个任务的物品得失情况用一个包含k个字母的字符串Si表示,其中每个字母都是+,-,/中的一种,第j个字母表示该任务对物品j的数量的影响。+表示做这个任务能得到一个物品j,-表示做这个任务会消耗一个物品j,/表示做这个任务对物品j的数量不产生影响。

但是,做任务是有前提条件的。游戏设计者约定了m个限制关系,每个限制关系是一个有序数对(i, j),表示做任务i前必须先做任务j。

现在,你需要选择性的做一些任务,使得获得的物品最多。

比较两种方案的获得的物品数的方法如下:先比较他们获得第物品1的个数,若相同,再比较物品2,若相同,再比较物品3,以此类推。

100%的数据,n≤1000, k≤5, m≤5000,保证限制关系不会有环。

如果是树的结构那么显然可以dp.
不是树,就考虑最大权闭合子图,跑最小割。问题就在于怎么求这个最小字典序呢..
k那么小..就直接按照2001进制把一个方案给压成一个数就可以了。


  • 自动机(automaton)

我们有一台(并没有什么实际用途的)自动机。它包含 N 个状态,指令集为前 M 个小写字母,而对于每个状态 s 和每个指令 i,自动机均有后继 T(s, i)。

亦即,自动机可以表示为一张有 N 个节点的有向图,有向图的每条边上都标有前 M 个小写字母之一,并且,对于任一节点 v 和前 M 个小写字母组成的集合中的任一元素 a,有且仅有一条标有字母 a 的有向边 (v, w),记 T(v, a) = w。自动机的状态可以用一个节点 s 表示,若此时自动机执行指令 i,自动机的状态就会变为 T(s, i)。

我们称编号为 0 的状态为自动机的“初始状态”。现在你的任务是,求任一可行的且长度不超过 1 MiB (= 1048576 Bytes) 的指令序列,使得无论自动机当前处在何种状态(包括初始状态),按顺序执行序列中的所有指令后,自动机都处于初始状态。

  • 对于 100% 的数据,N ≤ 100,M ≤ 26。

这题可以用一个看似乱搞的方法来解决。
先随机一个长度为10^6的串


  • 量子通讯

有N个强相互作用力探测器在太空中航行。M对探测器之间可以通过量子纠缠进行双向通讯,这样所有的探测器都可以直接或间接地联系。

由于量子纠缠态在被干扰后就会消失,因此可以通过这种方式破坏某些双向通讯。

受技术手段限制,只能破坏两个这样的量子纠缠。有多少种破坏方法可以把所有探测器分成至少两个互相无法联系的部分?

对于100%的数据,1<=N<=2000,1<=M<=100000.

先随意dfs出一棵生成树。
对于每条非树边随机赋予一个权值。 每条树边的权值等于覆盖其的所有非树边的权值异或和。
这样如果两条边权值相等或其中有条边的权值为0.那么这张图不联通。


  • DZY Loves Sorting

DZY有一个数列a[1..n],它是1∼n这n个正整数的一个排列。

现在他想支持两种操作:

0 l r: 将a[l..r]a[l..r]原地升序排序。

1 l r: 将a[l..r]a[l..r]原地降序排序。

操作完后,他会给你指定一个位置k,请你告诉他a[k]的值。

二分答案,每次回答a[k]是否小于等于mid
把数列里的数替换成0和1,这样每次排序的时候,把0都弄在一起,1也弄在一起就好了。
用个线段树来实现。


  • 光盘(disk)

可以很轻易地建出一个费用流的模型。
考虑用线段树去维护费用流。是一个贪心的过程,每次选出最优的合法方案。
可以把这个模型看做一个括号序列。每次有两种可能

  1. () 一个左括号加上一个右括号
  2. )( 一个右括号加上一个左括号

第一种情况显然合法,对于第二种情况。可以想到维护每个位置的前缀和。一个合法方案每个位置的前缀和一定都是非负的。
用线段树去维护这个前缀和即可。
需要维护的东西比较多:

代码能力捉急,总是莫名其妙的下标打错


这个式子就相当于在一个联通块里可重复地取k个点,把它们的权乘起来相加。
这样就得到了一个naive的dp式子。
然后发现这东西是可以NTT的。


  • 下棋

你现在在玩一种有趣的棋。这种棋在一个 4 × 4 的棋盘上进行,这个棋盘 上有一些位置是障碍,其他位置是空地。游戏开始时,有些空地上摆放了一些棋子。之后每个玩家可以选择两种操作:将一个棋子移动到相邻的格子中,或者是移除掉某个棋子。为了避免游戏无法结束,每次操作后不允许出现与之前相同的局面。

现在给定一系列局面,对于每个局面,你需要判断先手是否一定能够获胜。

这个题还是稍微有点意思的。
如果没有移除某个棋子这个操作的话。我们可以把所有的状态都拿出来。给能转移的状态之间连上边。
这样就相当于有一个棋子,两个人在图上交替移动,不能经过重复的节点,不能移动的人输。
这是一个经典问题。 CC上有道HAMILG就是这样的。如果一个点一定在最大匹配上,那么这个点必胜,反之必败。
对于这个题只要一层一层去做,每一层取出必败点跑一个匹配就好了。


  • yist

杜老师的爆算题.. 似乎毛爷他们有神奇的搞法。
杜老师这个算法还是蛮有启发的


  • sanrd

这题其实仔细想想还是挺简单。
从高到低考虑图R的每一位,这位选0/1就相当于把这张图分成两个部分:

  1. 两部分的图同构
  2. 两部分图的顶点之间形成一个双射。

这样只要找出这样的划分然后两部分递归下去搞就行了。
具体过程就跟璀璨光华一样确定一个点集之后不断DFS,扩大划分的点集就好了。


  • 巧克力

n <= 10^9, c <= 10^5.

这题是算生成函数的,对这套理论不是特别熟练啊..
做法是这样的,考虑一个元素出现奇数次和出现偶数次的EGF:

发现n!十分巧妙地被消掉啦


  • Prime的把妹计划

这题有个巧妙的nlogn做法。
先用单调栈把每个数向左向右能覆盖到的范围给求出来,这里只考虑第一种情况,对于第二种情况,只要把所有数都取相反数就好了。
考虑把询问离线,从左向右一个一个加入每个数。用个线段树来维护当前询问右端点为i的情况下每个位置作为左端点的答案。
对于一个左端点l来说,如果它向右不能覆盖到i,那么它肯定也不能覆盖到i右边的点,因此每次处理i之前可以先把不能覆盖到它的点给删掉。 对于剩下的点,把所有i能覆盖到的点的答案全都更新即可。这些操作可以通过线段树简单完成。


  • 神奇字符串

啊..这题其实非常简单啊,为什么不会做啊。
对这种题就轻易地放弃了思考..


  • 生成树求和

这一看就是用矩阵树定理做。
考虑分开来计算每一位的贡献,对于每一位,如果一条边的权值为k, 就把它看做x^k。
然后计算这个图的基尔霍夫矩阵的行列式,这样就得到了一个2n-2次的多项式,按照次数模3分类之后加进答案即可。
高斯消元的时候处理多项式比较困难,可以代2n-1个数进去然后插值。
复杂度O(n^4*logn)


  • 道路

看到k^2, 显然就是枚举两条边然后计算包含这两条边的连通图的个数。
考虑一个经典问题,求n个点的完全图的连通子图个数,这个可以容斥来做。

考虑枚举的两条边只有三种位置关系:

  1. 两条边共用2个端点
  2. 两条边共用1个端点
  3. 两条边不共用端点

对于每一种情况都可以把边给缩起来,然后用跟上面相似的容斥方法计算方案数。
最后的答案就是每种情况的方案数乘以这种情况发生的次数。


  • Fenwit

原题解的做法用到了这个B序列的一些性质。
我来说说我的做法吧。这个做法可以处理B为任意长度为2^m的序列。
我们直接对A序列和B序列FWT. 有一种FWT的姿势是:

这样我们就把P乘上2^M, 逆变换的时候直接除以2^M即可。

这样直接做的话复杂度是O(M*2^M + 2^M*logT), 这里T比较大, 应该是跑不过去的。

其实指数是有循环节的:

因此如果T比较小就直接做,否则把T模掉phi(p)再加上phi(p)就好了,复杂度O(M*2^M + 2^M*logP)


  • Stage

小清新几何题。
考虑每条边在凸包上的概率以及它的贡献。
一条边在凸包上的概率就是这条边右侧不存在任何一个关键点的概率乘上它们本身被选中的概率。
一条边的贡献等于这条边与原点所形成的三角形区域内固定点的个数。
这两个信息都可以通过排序+线段树/树状数组在O(n^2logn)的时间内算出来。
根据边的方向(正向/逆向)来更新答案。


  • Alphadog

这题一看就是回文树的题目嘛...
用LCT去维护,还是比较裸的。

WARNING
回文树建新节点的时候要先算出它的fail节点再将它插进去。


  • yist II

n <= 8

又是一次杜老师的题目。这题似乎能被很多乱搞弄过去...
标算是这样的,n比较小,那就先枚举在凸包上的点是哪些,以及他们的顺序。
然后考虑每一块小三角形的面积,其中Ai是两条边的长度之积,Xi是角度:
Maximize

S.T.

考虑拉格朗日乘数法:

注意到:


  • ernd

这个计数题还是挺小清新的..
设f[i][j]为从1~i的幂集中选出一些集合,其中并且形成j个联通块的方案数。
g[i]为从1~i的幂集中选出一些集合,其中包含了1~i所有元素的方案数。

这样去搞就行了。


  • sanrd

这题蛮简单的,跟实验一样做就行了


  • K小数查询

这题时限一看就很谜啊..肯定是什么大力出奇迹的做法。
再一看..这不是ORZJRY I的子问题嘛..
直接强上分块.. 复杂度..大概是


  • 不是回文串

SAM裸题


  • 线性代数与逻辑

水题


  • problem a

这题是个非常naive的主席树题目,然而我WA40了...怎么回事呢..

int ask(int u, int L, int R, int p) {
    if (p == 0) return 0;
    if (L == R) return tree[u].sum;
    int mid = (L + R) >> 1;
    if (p <= mid) return ask(tree[u].l, L, mid, p);
    else return ask(tree[u].r, mid + 1, R, p) + tree[tree[u].l].sum;
}

WARNING
这里第一句话一定不能省略 不然就WA掉了


  • problem b

这题是比较无聊的一个FFT题目。
考虑把M维的贡献分开来计算,计算每一维的Ai贡献,这样就能轻易地得到一个形如的卷积。
又可以发现N都是质数,这样就可以通过原根来进一步转化卷积,就可以FFT了。
复杂度


  • problem c

这题就是一个裸的最小二乘。
可以列出偏导方程来,解一发线性方程组就好了。
然而这样是不能过的.. 目前大家都不知道这题是怎么回事。
感觉是防AK的。


  • 宝藏

这题是个很经典的2-sat计数问题。 这个问题是NP-hard的..考虑搜索。。 可以MIM实现,根据2-sat问题将边对称连起来。然后对前一半的点枚举选或者不选。这样后一半的点就知道哪些可选可不选。这些部分可以用类似的状压dp求出来..复杂度O(2^(n/2) * n)
2-sat问题具有很强的对称性。


  • 共价大爷游长沙

这题是毛爷出的挺不错的一个LCT题目..
这题的瓶颈在于每次linkcut操作的时候..每对点之间的路径都发生了变化。
如果路径无法很方便维护的话,考虑把信息放到点上面。给每条路径一个随机的哈希值。每次询问的时候只要知道每个点子树内哈希值的异或和就行了。这样就能知道是不是所有区间都经过了这条路径。

WARNING
用LCT维护子树信息..Link的时候要把父亲节点给变成根。再接上去,这样才能保证每个点的子树信息都是正确的。


  • reimu hakurei

发现这个限制条件十分松。因此猜想肯定存在使每一个位置都合法的方案。
考虑从1到n来做。如果i之前对i的贡献等于r[i].. 那么就把i选上,反之不选。这样一定能让每位都合法。


  • nekopara

CF原题..排序一下搞个树剖就好了。


  • 一堆堆

先排序,对于每个数枚举它的倍数, 发现有贡献的是一段区间, 于是可以树状数组。


  • 圈草地

这题首先可以观察.. 发现可选的左上角一定是一条直线,可选的右下角也是..进而发现这东西是有决策单调性的。
可以通过决策单调性+主席树来求解。

这个题发现对于一般的点来说是没有决策单调性的..但是如果限定了一些条件..就有了。

WARNING
使用决策单调性的时候一定要搞清楚符号..到底是大于还是大于等于。


  • 挤奶工

这个题还是比较妙的..遇到这种问题,发现要求最大匹配是很困难的。先把左边的点补成和右边一样多,这个问题等价于是否所有完备匹配的权都是一样的。考虑调整法,如果不管怎么交换任意两个元素,权值都不变,那么就合法反之不合法。这样就相当于对于这个矩阵来说,任意一对对角线的和都相等。这等价与每一列差分之后都相同。
这样的话只要判断两两列之间差分是否相等就行了。可以用哈希来做。


  • 小 H 的卡片

这题有个无脑dp的方法。直接把目前数的gcd给压起来..发现状态数是很少的。因为合法的gcd一定是某个数的因子,所以状态数是不多的,直接压起来没问题。


  • 小 Z 的积木

把每个方块的四个角分开来,计算出其在平行光下的对坐标轴的投影,就可以扫描线+线段树维护了。
这题线段树需要支持区间取max和求区间最小值的操作。 可以通过标记永久化来实现


  • 小 W 的数字

这题和第一题一样,可以通过大力出奇迹的记忆搜来做。
首先观察到一个性质,每次肯定是减去最大一位。 这样就可以数位dp了。记录一下目前这个数以及之前位数的最大值。dp的同时记录一下把当前这个状态建成0的最小开销以及在最小开销的情况下最多等变成负几。
因为一点一点减,在后面的位减到0之前都不会影响到前面的位。


  • Digits’ path

这题就是一个最短路
需要压一下状态然后spfa.. 记录一下是否存在2357以及这个数对21的模即可。因为245的模数可以通过末两位来计算。


  • Landlords

这题是个挺妙的dp.. 令f[i][j]为目前己方有i张,对方j张的情况的最大值。目前本方决策有三种:直接猜,报一张自己没有的牌,报一张自己有的牌。考虑到不管对方策略如何,直接猜的胜率都不变,因此直接猜肯定不是混合策略的一部分。对于双方来说,直接的对抗就是,如果报出了一张牌但是对方没有,对方就会考虑我是不是在骗他,他就会决定到底是相信我还是不相信我。而对我来说,报自己的牌和不报自己的牌也存在决策。而如果猜中了对方的牌..这就是子问题了。 假设对方知道了自己做两种决策的概率,那么就能得出一个纯策略来对抗我。假设我骗人的概率是X..那么对方做出两种决策的收益是一个一次函数,而我的X就是这两个函数的交点。这就是一个纳什均衡点。


  • COOHxNH2

这题的话..判断什么时候无解对解题十分重要。发现如果图中有奇环就无解。那么我们只要解决二分图的情况即可。
对于一个联通的二分图。可以发现答案是可以取到这个二分图的直径的。首先..直径一定是答案的上界。其次,假设已经得到了一条直径,那么任意一条不在直径上的边一定有一个点在直径上,只要把它与直径上的点合并起来就可以了。


  • 异或

首先对于这种xor的题目..要先想到的一个东西就把基给消出来。接着要做的事情和最近做到的一些题目比较像。如果基的大小不超过K..就直接暴力计算。 加入基的大小大于K..说明自由元的数目比较少。可以用一个dp..把自由元给压起来。感觉还是比较巧妙的。


  • Train

对于这题来说,中位数有个非常常见的处理方法是二分它。把小于X的数都变成-1,大于X的数都变成1。这样就需要找到一条长度在[l,r]之间的权值和非负的路径。这个可以通过dp来实现。合并两个子树的时候用单调队列搞。


  • Gene

这道题如果求指标去做的话还是比较simple的..但是BSGS太慢了。
由于我们只要知道某个数指标和(p-1)的gcd就行了。因此只要枚举(p-1)的因子d然后判断一下Ai ^ ((p - 1) / d) = 1(mod p)是否成立就可以了。


  • Save

这题还是非常好的..kruskal重构树确实挺有用的。
至于后面的那个区间覆盖撤销,区间查询。因为所有


  • 求和

复习一下一些筛的技巧。


  • Philosopher

这题有两个idea..第一个是如何计算最高位。 这个只要取对数即可。这题就变成了区间排序,区间求和。
这个可以用平衡树/线段树的合并来做。
把每段有序区间放到一个权值线段树上去维护。还是可以想清楚的。

WARNING
线段树合并的时候叶子要单独考虑。因为线段树的叶子是有实际信息的。

← SRM 576 弱鸡题解 CTT2016 DAY1简单题解 →
 
comments powered by Disqus