- 博客(757)
- 收藏
- 关注
RSS订阅
原创 模拟赛
树(tree)题目描述点此看题n≤105n\leq 10^5n≤105解法以前是暴力水过去的，结果今天考到了加强版，然后就凉了不难发现可以用线段树分别维护以 uuu 为根的最长上升子序列和最长下降子序列，然后拼起来就可以了。线段树的下标是开始位置的权值，可以快速算出 a[u]a[u]a[u] 为起始点的最长上升子序列和最长下降子序列。然后还要把子树的线段树合并上来，合并的时候可以更新一下答案（左右子树的子序列拼起来）在 dfsdfsdfs 的时候顺便算一下经过 a[u]a[u]a[u] 的子
2021-03-18 22:15:48
332
1
原创 [模板] 扩展KMP
一、题目点此看题二、解法这个算法虽然和 kmp\tt kmpkmp 或者是马拉车。我们先从题目要求的第一个数组入手，设 nxt[i]nxt[i]nxt[i] 为 bbb 和 bbb 的后缀 iii 的最长公共前缀。我们设 i+nxt[i]i+nxt[i]i+nxt[i] 覆盖最远的点是 ppp（这是我们以前就维护出来的），转移分两种情况讨论：情况 111 ：...
2020-12-12 08:30:04
313
1
原创 [WC2016] 论战捆竹竿 && [学习笔记] 同余最短路
本来想做字符串的题，结果发现了这个坑把他填上。什么是同余最短路？同余最短路是解决这样一类问题：给你若干个数 a[i]a[i]a[i] ，每个数可以选无限次加起来，问最后的和有多少种在 mmm 的范围内，这种问题 mmm 可以开到非常大，但 a[i]a[i]a[i] 不会很大。那怎么做？是个正常人都不会去跑背包，同余最短路，顾名思义肯定要和余数有关系，我们把 a[1]a[1]a[1] 单独拎出来作为模数，设 dp[i]dp[i]dp[i] 为模 a[1]a[1]a[1] 余 iii 的最小数（是剩下的
2020-12-09 17:02:09
293
原创 CF1444C Team-Building
一、题目点此看题二、解法要判断二分图可以使用带权并查集，并查集上的边设置为 111 就表示两点必须异色，设置为 000 就保证两点必须同色，所以我们在相同连通块查询合法时路径上权值异或和必须是 111补充一点，上面的问题其实是判断一棵树上加入若干条边是否形成奇环，这个问题是出过题的。只用考虑树边和一条非树边形成的环是可以证明的（这里就不证明了，分类讨论即可）我们用带权并查集首先维护颜色内部的边，首先对于自己就不行的颜色排除在外，设剩下的颜色数量为sss，那么答案可以表示成：s(s−1)2−shit
2020-12-04 11:03:26
195
原创 CF1442D Sum
一、题目点此看题二、解法一定要充分利用题目条件。第一个明显的题目条件是 aaa 数组单调不降，那么我们最后的选取一定是至多部分选取一个数组。证明可以用反证法，假设部分选取了两个数组，那么不优。然后题目变成了对数组编号为 [1,x),(x,n][1,x),(x,n][1,x),(x,n] 的做 0/10/10/1 背包，然后用 O(k)O(k)O(k) 的时间看部分选取多少。算法瓶颈在第一个部分，max\maxmax 型的背包不能做退背包，所以我们可以用分治解决。#include <cst
2020-12-03 17:53:01
180
原创 CF1437F Emotional Fishermen
一、题目点此看题二、解法嗯，这个题比较有启发性。这种 nnn 比较大的排列计数的题做法应该比较唯一吧：先思考最后的排列怎么样，然后想各种办法去计数。这道题最后的排列一定长这个样子：其中 bib_ibi 表示某一段前缀的最大值，那么我们计数可以以 bib_ibi 为关键点，设 f[i]f[i]f[i] 为最大值为 aia_iai 的方案数，初始化 f[0]=1f[0]=1f[0]=1，答案是 f[n]f[n]f[n]，我们首先需要把 aaa 数组排序。考虑转移，其实就相当于把 aaa 填到原
2020-12-03 16:13:35
356
原创 [unknown OJ] ZZH与背包
一、题目点此看题二、解法一看就是折半搜索，但是左边要排序右边要二分的，O(220×qlog)O(2^{20}\times q\log)O(220×qlog)这种题往往就是卡掉排序的复杂度，我们可以考虑用归并排序来卡。假设我们维护的是一个有序数组，那么我们加一个 vvv 的时候这个数组就变成了两个。一个是原来的数组，一个是每个元素都加上了 vvv 的数组，那么这两个数组就可以用归并，所以第一部分的复杂度变成 O(2s)O(2^s)O(2s)第二部分其实也可以用归并，一共有 q2n−sq2^{n-
2020-12-02 09:47:58
375
原创 [unknown OJ] ZZH的旅行
一、题目点此看题二、解法#include <cstdio>#include <vector>#include <iostream>#include <queue>using namespace std;const int M = 1000005;int read(){ int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while
2020-12-02 08:28:59
264
原创 [unknown OJ] 划分
一、题目点此看题二、解法首先题目的条件相当于给定了若干个前缀，让你求那些值是确定的。这种题是有套路的，把 l−1,rl-1,rl−1,r
2020-11-30 16:41:25
307
原创 [学习笔记] 点分治 and 点分树
点分治的思想我觉得点分治和 cdq\tt cdqcdq 分治极其相似，但是点分治是用于树上的问题。回忆一下 cdq\tt cdqcdq 是怎么做的，他其实是把序列从中间划开，先分别处理两边，然后算两边之间的贡献。由于划分成了相等的两端，那么复杂度就得到了保证，此算法本身是 O(nlogn)O(n\log n)O(nlogn) 的。从中间划开 是复杂度得到保证的关键，那么树上能不能也从中间划开呢？好像有点难，但是我们可以从重心划开，那么分成的子树都是小于等于原树的一半的，我们先单独递归子树，然后考虑子
2020-11-30 16:13:04
396
2
原创 [ZJOI2017] 树状数组
一、题目点此看题二、解法解决这道题需要知道树状数组的原理，iii 维护的是 (i−lowbit(i),i](i-lowbit(i),i](i−lowbit(i),i] 的求和。那么如果反过来，那么 iii 维护的是 [i,i+lowbit(i))[i,i+lowbit(i))[i,i+lowbit(i)) 的求和，所以原来求前缀和，现在求的是后缀和。那么我们把正确的条件列出来：sum[l,r]=sum[l−1,r−1]sum[l,r]=sum[l-1,r-1]sum[l,r]=sum[l−1,r−
2020-11-29 11:13:00
259
原创 [LOJ 6035] 洗衣服
一、题目点此看题二、解法其实不难看出可以分步做吧，你先求出洗完所有衣服的最小时间和每件衣服的洗衣时间，这个很容易用优先队列求，优先队列里面按洗完的最小时间排序，先选小的。然后现在等价的衣服变得不等价了，jzm yyds\tt jzm\space yydsjzm yyds 告诉我们，这时候先考虑二分怎么做再看看能不能去掉二分。类似于 迷途丛林 的方法，我们二分的时间是 midmidmid ，可以让所有的烘干机结束的时间都等于 midmidmid，这里有一种重要思想：虽然可以提前结
2020-11-27 17:36:52
373
原创 [unknown source] Random IS
一、题目给你一个数组 aaa，其中有 nnn 个元素。你现在要标记若干个元素，使得它们单调上升。你按照下面两个步骤来进行操作：step1\tt step1step1：如果一个元素称为好元素，当且仅当它被标记以后，标记过的元素仍然是单调上升的。设有 kkk 个好元素。step2\tt step2step2：从 kkk 个好元素中随机选一个进行标记，然后跳到 step1\tt step1step1，如果 k=0k=0k=0，则将所有未标记的元素删除，结束操作。问最后期望的元素个数是多少？取模 1e9+7
2020-11-25 17:31:53
223
原创 [雅礼集训 2017 Day7] 蛐蛐国的修墙方案
一、题目点此看题二、解法想不到吧，朴素的搜索都有 808080 分。我们仔细想一想， 其实给出了若干个环，对于一个环如果确定了一条边那么这个环就可以确定了。我们枚举每个环的某一条边，这样时间复杂度是 O(2n/2)O(2^{n/2})O(2n/2)注意有解必须要求偶环，所以只会有 2,4,6....2,4,6....2,4,6.... 圆环，然后 222 圆环是极其特殊的，可以把在前面的那条边定成左括号，后面的那条边定成右括号。这样只有 444 圆环及以上，时间复杂度 O(2n/4)O(2^{n/
2020-11-25 16:24:15
199
1
原创 [LOJ 6254] 最优卡组
以前是写过的，但现在旧题重做又有了新的体会！一、题目点此看题二、解法先讲一种我自己 yy\tt yyyy 的做法，虽然是错的，但是有启发意义。爆搜是不可能爆搜的，∏ci\prod c_i∏ci 是不可能爆搜的，这种题一般需要用优先队列爆搜。但这种方式很苛刻，必须要同时满足两个条件：不会算重，权值总和从大到小，下文主要解决这两个问题。我们定义三元组表示 (x,y,s,z)(x,y,s,z)(x,y,s,z) 搜到第几个卡组的第几张牌，sss 表示卡牌权值总和，zzz 表示是否能计入答案（因为我的
2020-11-25 11:09:05
240
原创 [HAOI2015] 树上染色
这么水的省选题，我直接一眼切？一、题目点此看题二、解法树形背包是很显然的呀，但是距离似乎不那么好算。点对距离不好算我们就算边的贡献嘛，这不是常考套路么？那么一条边的贡献是：上面的黑点数×\times×下面的黑点数+++上面的白点数×\times×下面的白点数。还是树形 dpdpdp，设 dp[i][j]dp[i][j]dp[i][j] 为子树 iii 中选了 jjj 个黑点的最大贡献，转移就是裸的背好，回溯是记得计算一下他连向父亲的那条边的贡献即可。类似的复杂度证明 O(n2)O(n^2)O(n
2020-11-25 09:43:35
171
原创 [unknown OJ] 选举
VOTE \tt VOTE\spaceVOTE FOR\tt FORFOR TRUMP\space \tt TRUMP TRUMP一、题目点此看题二、解法先讲一讲考试时候写的暴力吧，我们先从前往后做一遍，前缀和如果小于 000 的话就删除这个 TTT，然后从后往前做一遍，后缀和如果小于 000 的话就删除这个 TTT，由于都是不行才删的策略所以是正确的。正解竟然是推柿子，我们尝试把上述过程形式化地写出来：对于询问[l,r][l,r][l,r]，记 CCC
2020-11-25 09:10:31
195
原创 [unknown OJ] 手套
一、题目点此看题二、解法一开始的理解虽然无限接近正解却有失偏颇，还是用图灵蒋的方法写这篇博客吧。首先一定要搞清楚这个问题其实是博弈，我们所做的只有确定 xxx 和 yyy，而选出什么完全是上帝决定了。秉承这个思想，由于 nnn 很小，而上帝拥有 2n2^n2n 种组合拳，也就是让你把一种手套全部选择左，一种手套全部选择右，这样的情况最坏，上帝会根据你选的 x,yx,yx,y 决定用哪种组合拳。设每种组合拳所消耗的手套数分别是 x0x_0x0 和 y0y_0y0，那么对于我们选出的 xxx ，如
2020-11-25 08:39:46
204
原创 [unknown OJ] 记忆碎片
一、题目点此看题二、解法如果你什么都想不到的话可以搞一个暴力 dpdpdp，设 dp[i][s]dp[i][s]dp[i][s] 为考虑权值前iii小的边，用最小表示法弄出来的状态是 sss 的方案数。什么是最小表示法呢？就是把一个点所属于的并查集标上号用状态表示出来。这种方法可以过 n≤15n\leq 15n≤15 的数据。想出正解首先要知道一个东西，一个数的整数分拆方案数很小（也就是拆成若干个整数之和，不考虑顺序），n=40n=40n=40 的时候方案数是 373383733837338，那么我
2020-11-23 17:54:38
315
原创 [unknown OJ] 小A的树
一、题目点此看题二、解法明显的定义是 dp[u][x][y]dp[u][x][y]dp[u][x][y] 表示点 uuu 子树内选了 xxx 个点，yyy 个是黑点的联通子图能不能达到，但是状态就爆了，显然不行。需要猜结论：如果 xxx 个点的最小黑点数是 lll，最大黑点数是 rrr，那么黑点 [l,r][l,r][l,r] 的联通子图都存在。证明：我们增加黑点的方式是增加一个点在删一个点，此时黑点变化数最多为111，所以黑点函数可以视为在整点处连续变化，所以 [l,r][l,r][l,r] 个数
2020-11-23 16:08:03
144
原创 [unknown OJ] 游戏
一、题目点此看题二、解法当 x+y+zx+y+zx+y+z 不是333的倍数的时候无解。一看就是 dpdpdp 的题了，先把暴力一下的写出来，设 dp[i][j]dp[i][j]dp[i][j] 为这个状态到分配完成的期望轮数（i=z−x,j=z−yi=z-x,j=z-yi=z−x,j=z−y，zzz最大），也就是我们用一个差分的形式来表示状态，转移：dp[a][b]=12dp[a−2][b−1]+12dp[a−2][b−1]+1dp[a][b]=\frac{1}{2}dp[a-2][b-1]+\
2020-11-22 22:16:55
138
原创 [unknown OJ] T形覆盖
一、题目点此看题二、解法根据部分分的提示，我们可以想到如果 max(xi−xj,yi−yj)≥2\max(x_i-x_j,y_i-y_j)\geq2max(xi−xj,yi−yj)≥2，那么这两个点是毫无瓜葛的，我们可以继续用这种方法来分类讨论所有情况。情况111：如果 max(xi−xj,yi−yj)=1\max(x_i-x_j,y_i-y_j)=1max(xi−xj,yi−yj)=1，这两个点是在九宫格内的，看图：不难发现就算有两种选择他们覆盖的点都是一样的，而且十字架重
2020-11-22 18:58:19
179
原创 [CSP2020] 贪吃蛇
一、题目点此看题二、解法0x01 考场的想法由于吃的方法很唯一，真正有问题的是蛇的选择问题。但我们观察到：如果场上剩下iii条蛇，那么此时的局面是固定的（也就是哪些蛇多少血都是确定的）那么"局面"是可以求出来的，我们可以知道每条蛇的死亡时间 deadidead_ideadi，从后往前推，设 i+1i+1i+1 条蛇所选择的局面是 ttt，如果 iii 条蛇（这里指的是第iii次吃时轮到的蛇）在局面 ttt 死了，那么他为了保命就不会吃，而选择之间结束游戏。否则 iii 条蛇会吃，此时的局面还是
2020-11-20 12:19:47
608
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人