- 博客(72)
- 收藏
- 关注
RSS订阅原创 dp Regular QBXT Test Ⅸ T1
题意：给出一个只包含左括号和右括号的字符串，插入若干左右括号（可以插在任意位置）之后使得字符串长度为2n2n2n且是一个合法的括号序列。求最后能组成多少种不同的合法括号序列。【合法的括号序列：该序列任意一个前缀的左括号数大于等于右括号数,最终左括号数等于右括号数】。n<=100n<=100n<=100三维dp，dp的前两维分别为插入的括号数量和使用的原来的序列中...
2018-10-30 13:25:55
197
原创 组合数学 Count QBXT Test Ⅷ T2
题意：求nnn个带编号的点能组成多少种无向连通图。考场上直接在想通项，把自己绕进去了，结果就weila。正解是一个递推，我们设状态dp[i]dp[i]dp[i]表示iii个点的无向连通图的种数。我们用总方案数减去不合法的方案数来求最终的方案数。首先对于一个i个点的图，一共有2i(i−1)22^\frac{i(i-1)}{2}22i(i−1)种不同的图。我们固定111号节点，枚举和111号点...
2018-10-28 20:05:19
151
原创 dp+bfs CF1031D&QBXT Test Ⅵ T2
题意：一个 n∗nn*nn∗n 的矩阵， 矩阵的每个元素有一个小写字母， 可以对矩阵的至多 kkk 个字母做修改， 即把一个字母改成任意一个小写字母。路径是指从左上角出发到右下角经过的2∗n−12*n-12∗n−1个字母的序列，且每次只能向下或向右走。求至多进行 kkk 次修改之后所有路径的值的字典序最小值。首先我们发现肯定是在路径前边加aaa，所以设dp[i][j]dp[i][j]dp[i][...
2018-10-27 12:47:40
203
原创 单调队列+dp POI 2015&QBXT Test Ⅴ T2 WIL-Wilcze doły
题意：给定一个长度为nnn的序列，你有一次机会选中一段连续的长度不超过ddd的区间，将里面所有数字全部修改为000。请找到最长的一段连续区间，使得该区间内所有数字之和不超过ppp。n≤1e6n≤1e6n≤1e6首先选长度为ddd的区间一定优于选长度小于ddd的区间，而这种固定区间的大概需要O(n)O(n)O(n)复杂度的dpdpdp问题，很容易想到用单调队列优化。首先先是朴素的dpdpdp，我...
2018-10-26 21:44:35
172
原创 贪心 Fish QBXT Test Ⅳ T1
题意：第 iii 只猫吃一条鱼需要花费a[i]a[i]a[i]的时间。且一只猫在同一时间最多只会吃一条鱼。在第 000 时刻，每只猫会开始吃一条鱼。每当有一只猫吃完鱼时，如果此时还有鱼，它会立刻吃下一条鱼。如果有 kkk 只猫在同一时刻一起吃完了鱼，且此时剩下的鱼的个数 不足 kkk，a[i]a[i]a[i]较小的猫会优先吃鱼。 求 xxx 个时间后，有多少条鱼还没被吃过，以及有多少鱼已经被吃了一...
2018-10-26 12:53:57
142
转载 dp Code QBXT Test Ⅲ T2
题意：有多少个 N∗MN *MN∗M 的矩阵满足：其所有数字都是 KKK 位 222 进制数，且每一行每一列的或都是 2K−12^K-12K−1。首先对于二进制的题很大一部分是逐位处理，因为各二进制位之间互不影响，首先我们注意到 KKK 是没有意义的， 我们只要求出 N∗MN * MN∗M的 0−10-10−1 矩阵有多少种方案使得每行每列的或都是111即可，记这个答案为ans′ans&...
2018-10-26 11:30:35
114
原创 树形dp Civilization QBXT Test Ⅱ T3
题意：一棵树，qqq次询问，每次给出一个点xxx，求到该点距离为奇数的节点的距离和与到该点距离为偶数的节点的距离和。比较明显的树形dp，但是我不会QAQ。首先先考虑求树上所有点到一个点距离之和，我们使用两遍dfsdfsdfs完成，我们设f[x]f[x]f[x]表示xxx的子树中所有点到该点的距离之和，siz[x]siz[x]siz[x]表示以xxx为根的子树大小，在第一遍dfsdfsdfs中，...
2018-10-25 16:51:19
122
原创 哈希 Monitor QBXT Test Ⅱ T1
题意：有nnn个长度为mmm的串，求在长度为 LLL 的串中这nnn个串中任意一个串出现的最早位置，如果nnn个串都没有，输出nonono。(m≤20,n≤1e4,L≤1e5)(m≤20,n≤1e4,L≤1e5)(m≤20,n≤1e4,L≤1e5)做法，因为每一个串长度都是一样的，考虑在最后的串内枚举每一段长度为mmm的串，看它是否为nnn个串中的一个。这里使用双哈希，首先先将nnn串的哈希值算...
2018-10-24 21:02:24
163
原创 图论 CF547D&QBXT Test Ⅰ T2 Mike and Fish
题意：给出平面上 nnn 个点，你要把每个点染成黑色或白色。要求染完之后，任意一条与坐标轴平行的直线上，黑白点数量差的绝对值小于等于 111。这题QBXT曾经讲过，考试遇到原题依旧挂了QAQ。全网都是二分图欧拉路的做法，在这里介绍一种新的算法，思路来自于无敌的cze，首先是建图，大家都是一个点横纵坐标之间连边，这里考虑一种新的连边方式，我们让同一行之间的两点配对，同一列之间两点配对，如果遇到...
2018-10-24 20:45:44
217
原创 数论 Count QBXT Test Ⅰ T1
题意：问有几个无序二元组 (x,y)(x, y)(x,y) 满足 xy≡1xy ≡ 1xy≡1 (mod  P)(mod \ \ P )(mod  P)， 0≤x<P;0≤y&a
2018-10-24 13:07:32
148
原创 单调队列+dp 琪露诺+NOIP 2017 跳房子
一、琪露诺：题意：一开始在000号格子上，每个格子有一个权值，在格子iii时，下一次可以移动到区间[i+l,i+r][i+l,i+r][i+l,i+r]中的任意一格，只要下一步的位置编号大于nnn就算到达对岸，求最大权值。(n<=2e5)(n<=2e5)(n<=2e5)首先如果不看数据范围，这是一个普通的dp，设f[i]f[i]f[i]表示到达iii这个点的最...
2018-10-20 18:24:30
222
原创 状压dp USACO 关灯问题Ⅱ
题意：nnn盏灯，mmm个按钮，一开始所有灯都是亮的。按下iii按钮对于第jjj盏灯，是下面333中效果之一：如果a[i][j]a[i][j]a[i][j]为111，若此灯是亮的，把它关上，否则不管；如果为−1-1−1的话，若此灯是暗的，那么把它打开，否则也不管；如果是000，无论这灯是否开，都不管。求关掉所有灯的最小操作次数。(n&lt;=10)(n&lt;=10)(n<=...
2018-10-19 14:05:40
189
原创 树的直径 NOIP 2007 树网的核
题意：求一条直径上的链，要求链长&amp;lt;=s&amp;lt;=s&lt;=s，使所有点到这条链上的距离中的最大值最小。首先我们先求出直径，年轻的时候n3n^3n3求直径也是没谁了qwq首先若直径&amp;lt;=s&amp;lt;=s&lt;=s，我们枚举所有一个在直径上，一个在直径外的点对，他们距离的最小值就是答案。若直径&amp;gt;s&amp;gt;s&
2018-10-19 11:01:33
132
原创 数论 Scarlet的字符串不可能这么可爱
题意：求字符集为kkk，长度为LLL的字符串，满足没有任何一个长度超过111的回文连续子串的数量，其中可能指定了字符串的第sss位为www。字符集：一个字符串中不同字符的数量。例如，字符集是333的话，你可以认为字符串仅由“A,B,C”“A,B,C”“A,B,C”三个字母组成。(k,L&lt;=1018)(k,L&lt;=10^{18})(k,L<=1018)这题一眼看上去...
2018-10-19 10:17:52
168
原创 tarjan+分层图最短路 USACO 草鉴定
题意：一个有向带权图，问从一号点出发最后回到一号点最多经过多少个不同的点，过程中可以逆行一次。首先，如果没有逆行的话显然答案是一号点所在的强联通分量的大小。所以我们考虑tarjan缩点，将每个强联通分量缩成一个点后建一个新图，缩点时记录每一个强联通分量的大小，缩完点后我们考虑重新建图，因为可以逆行一条边，我们考虑将图分为两层，同一层内正常建图，每次在第一层到第二层之间建一条逆向有向边，边权为00...
2018-10-19 09:40:07
139
原创 状压dp NOIP 2016 愤怒的小鸟
题意：有nnn只猪，第iii只坐标为(xi,yi)(x_i,y_i)(xi,yi)，问最少要用多少形如y=ax2+bxy=ax^2+bxy=ax2+bx的抛物线才能将所有猪打下来，要求这些抛物线都过(0,0)(0,0)(0,0)点，且a&amp;amp;lt;0a&amp;amp;lt;0a&amp;lt;0。(n&amp;amp;lt;=18)(n&amp;amp;lt;=18)(n&amp;lt;=18)
2018-10-19 09:13:53
159
原创 STL Map kls与flag
题意：地上有一排nnn根竹竿，竹竿的间距均为一个单位长度，高度在1∼m1\sim m1∼m之间。每根竹竿可以往左倒或者往右倒。如果两根竹竿在选择方向放倒之后，它们的顶端可以重合，那么称它们是优秀的。求有多少对竹竿是优秀的。n&amp;lt;=2e5，m&amp;lt;=1e9n&amp;lt;=2e5，m&amp;lt;=1e9n&lt;=2e5，m&lt;=1e9做法比较简单，sum[i]su...
2018-10-18 14:46:41
138
原创 STL Set 送花
一、送花：题意：三种操作1.添加一朵美丽值为W，价格为C的花。2.删除最便宜的一朵花。3.删除最贵的一朵花。若删除操作时没有花，则跳过删除操作。如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。所有操作结束后，求美丽值之和和价格之和。这题正解是平衡树？总之用Set就过了，以下是Set的一些基本操作1.定义一个Set：set&amp;lt;int&amp;gt; s;2...
2018-10-18 14:21:14
109
原创 数论+秦九韶算法 NOIP 2014 解方程
题意：已知多项式方程：a0+a1x+a2x2+...+anxn=0a_0+a_1x+a_2x^2+...+a_nx^n=0a0+a1x+a2x2+...+anxn=0求这个方程在 [1,m][1,m][1,m] 内的整数解n&amp;amp;lt;=100,m&amp;amp;lt;=1e6n&amp;amp;lt;=100,m&amp;amp;lt;=1e6n&amp;lt;=100,m&amp
2018-10-18 11:48:46
300
原创 状压dp NOI 2001 炮兵阵地
题意：给你一个n∗mn∗mn∗m的网格，每个各自最多放一个炮兵，每一个格子有地形，平原可以放，山地不能放，并且一个炮兵的上下左右两个内不能放炮兵，问最多放多少炮兵。n≤100；m≤10n≤100；m≤10n≤100；m≤10。可以发现m非常小，考虑状压dp，这道题与常规状压dp的不同点是这道题的每一行状态在转移时要看之前两行的状态。首先我们先将每一行哪些格子可以放用二进制表示出来，g[i]g...
2018-10-18 08:43:05
139
转载 最短路+拓扑排序+dp NOIP 2017 逛公园
题意：给你一个nnn个点mmm条边的有向带权图，设111号点到nnn号点的最短路是disdisdis，给你一个k(k&amp;amp;lt;=50)k(k&amp;amp;lt;=50)k(k&amp;lt;=50)，求所有111到nnn的路径中长度不超过dis+kdis+kdis+k的数量。题解：显然我们要先处理出最短路，如果k=0k=0k=0，就是最短路计数了。要做计数，我们不难想到要在图上dpdpdp。我们发...
2018-10-18 08:13:50
131
原创 哈希 POI KOR-Beads
题意： 给出nnn个数，可将它们分为连续的若干个串，每个串有kkk个数（长度不足kkk则丢弃），如串 (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)(1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)(1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)，当k=2k=2k=2时，我们得到666...
2018-10-17 21:29:23
119
转载 WQS二分 Tree I
让我们一起来%forever_shi神犇题意：给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题解：看的别人的题解。做法是二分一个权值，可正可负，让所有白色边加上这个权值，然后再做最小生成树，显然这个全权值是可以二分的。然后最后每次二分得到的结果再加上那些减去的权值就是这种最小生成树的权值和了。另外权值相同的时候据说需要先选白色边。神奇...
2018-10-17 19:13:31
255
转载 状压+分层图最短路 孤岛营救问题
让我们一起来%forever_shi神犇题意：有一个迷宫，一开始在左上角，要走到右下角，相邻的两个格子有些不可通过的墙，还有一些门需要有了对于的那一类钥匙才能通过。求111到nnn的最短路。n∗m&amp;lt;=100n*m&amp;lt;=100n∗m&lt;=100,门和墙总数不超过150150150，迷宫中的钥匙不超过141414，同类的钥匙可能有多个。题解：建分层图，建图的方式是...
2018-10-17 19:06:38
123
转载 数论？ USACO 考试
让我们一起来%forever_shi神犇题意：你有n个判断题，每题只可能是对或者错的一种，你事先知道了最终答案是对的题目数一定是下列若干种可能的某一个，求如何安排每一道题的选项能在最坏的情况下得到最多的分？题解：NOIP模拟赛的题目，被各位大神随便切，我却当场没想出来。我们把正确答案是对号的题设为1，正确答案是错误的题设为0，这题首先是会发现，直接贪心地全选1或全选0并不一定是最优的，反例...
2018-10-17 18:58:13
191
原创 贪心+位运算 NOI2014 起床困难综合征
题意：你可以任意选择一个0−m0-m0−m的数，有nnn次操作，有n次操作，对于每次操作有三种情况：分别为&amp;一个数，|一个数，和^一个数，求n次操作后最大能得到多少。题解：直接做并不好做，暴力枚举选哪个数的话很难进一步优化了。这道题我们像很多位运算有关题目一样按位考虑，因为每一个二进制位之间互不影响。我们把数拆成二进制数，从高位到低位考虑，我们枚举答案的每一位，因为越靠前的位为11...
2018-10-17 18:16:08
135
转载 trie树 dp 前缀单词
让我们一起来%forever_shi神犇题意： 给你n个字符串，每次选出若干个字符串形成一个集合，问有多少个集合满足集合中的任何一个字符串都不是另外一个字符串的前缀。空集也一定是满足条件的。保证不会出现两个相同的字符串。首先对所有字符串建出一棵trietrietrie树，然后我们可以发现其实trietrietrie树上有用的点只有那些作为某个串的末尾被打上标记的点，于是我们根据trietrie...
2018-09-27 15:10:15
323
转载 欧拉函数 线段树 状压 奇数国
求区间积的ϕ\phiϕ值。题解：number∗x+product∗y=1number∗x+product∗y=1number∗x+product∗y=1可以转化为gcd(number,product)=1gcd(number,product)=1gcd(number,product)=1，即求ϕ(product)\phi(product)ϕ(product)。题目保证所有的数都可以表示成前6...
2018-09-27 15:01:50
194
原创 线段树+状压 色板游戏
题意：一个色板，一开始全为111号颜色，有两种操作：第一种是将区间A−BA-BA−B全部变为CCC号颜色，第二种是询问区间A−BA-BA−B一共有多少种颜色。颜色数量&lt;=30&lt;=30<=30。考虑将每一种颜色进行状压，tr[ ].sumtr[\ ].sumtr[ ].sum即表示这个区间的颜色状压后的值，每次更新使用∣|∣更新sumsumsu...
2018-09-21 10:40:12
117
原创 状压dp 星空
题意：给出一串灯的开关情况，有k盏灯是暗的，有m种操作，每种可以将长度为x的区间内的灯的开关情况取反，问最少多少次可以将所有灯泡点亮。首先我们发现对于连续的一段灯泡去操作很慢，因此我们需要一种O(1)O(1)O(1)复杂度的方法进行开关的操作。这里使用了差分，对灯开闭情况的01序列进行差分，我们设暗的灯为1，亮的灯为0。差分的方法是在原序列的前后补一个000，然后用a[i−1]a[i-1]a[...
2018-09-20 11:51:22
100
原创 yts1999 T2 容斥原理
题意：给定 l1,r1,l2,r2,l3,r3,l4,r4l1, r1, l2, r2, l3, r3, l4, r4l1,r1,l2,r2,l3,r3,l4,r4，试求满足 li≤xi≤ril_i ≤ x_i ≤ r_ili≤xi≤ri 且 x1≠x2,x2≠x3,x3≠x4,x4≠x1x1 \ne x2, x2 \ne x3, x3 \ne x4, x4 \ne x1x1̸=x2,x2...
2018-09-19 20:19:11
206
原创 状压dp USACO 奶牛混合起来
有NNN头奶牛，第i头奶牛的编号是SiS_iSi，编号是唯一的。要求相邻奶牛的编号之差均超过KKK，求有多少种队形是混乱的。dp[i][j]dp[i][j]dp[i][j]表示状态为iii的情况下最后一个牛的编号为jjj的方案数。转移方程为dp[i+(1&amp;lt;&amp;lt;(k−1))][k]+=dp[i][j];dp[i+(1&amp;lt;&amp;lt;(k-1))][k]+...
2018-09-19 16:27:39
169
原创 状压dp SCOI 2005 互不侵犯
题意：nnn个矿石，每个矿石都有自己的重量 wiwiw_i ，以及价值viviv_i 。接下来会进行以下四个操作： 1.给定mmm个区间[li,ri][li,ri][l_i,r_i]； 2.选出一个参数WWW； 3.对于一个区间[li,ri][li,ri][l_i,r_i]，计算矿石在这个区间上的检验值Yi=∑j1∗∑jvj，&amp;amp;amp;amp;nbsp;&amp;amp;amp;amp;nbsp;j∈[li,ri]&amp;amp;
2018-09-19 11:18:10
133
原创 最短路+并查集 USACO 安全出行
题意：给你一些点， 他们与节点1的最短路的最后一条边当且仅当对于这个点的最短路不可走， 求每一个点到1的最短距离。
2018-09-19 10:22:46
210
原创 随机化乱搞 NOIP 2017 宝藏
题意：一个图，可以选择任意一个点作为起点，向外拓展成一棵树，每次拓展时的花费为边权*起点到该点(均包含)经过的·所有的点的数量，求拓展成一棵树的最小花费。这题可以状压dp，可以搜索，可以模拟退火，但是以上所有的我都不会QAQ这里采用随机化乱搞——randomrandomrandom_shuffle(a+1,a+n+1)，shuffle(a+1,a+n+1)，shuffle(a+1,a+n+...
2018-09-12 20:33:11
381
原创 最大矩阵和 玉蟾宫
题意：一个n∗mn∗mn*m的矩阵，由字母FFF和字母RRR组成，求全为FFF的矩阵的最大值，要求复杂度O(n2)O(n2)O(n^2)悬线法，O(n2)O(n2)O(n^2)解决最大矩阵和问题，对于矩阵中的每一个点： 1.从它向上引一条悬线，遇到边界或障碍点停止，f[i][j]f[i][j]f[i][j] 表示从点(i,j)(i,j) (i,j) 向上的最靠上的纵坐标。 2.从该点向左延...
2018-09-03 20:26:32
113
原创 带权并查集 NOI 2002 银河英雄传说
题意：有nnn艘战舰，一开始排成一行，第iii号战舰在第iii列，两种操作： 1.MijMijM_{ij} 表示将第iii号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。 2.CijCijC_{ij} 表示询问第iii号战舰与第jjj号战舰当前是否在同一列中，如果在同一列中，那么它们之间有多少战舰。这题一看就是并查集，但怎么维护两艘战舰之间有多少战...
2018-09-01 18:58:35
142
原创 拓扑排序+贪心 NOI 2010 航空管制
题意：nnn个航班，定义一个航班的起飞序号为该航班在起飞序列中的位置。起飞序列还存在两类限制条件：1.编号为iii的航班起飞序号不得超过kikik_i。2.存在一些相对起飞顺序限制(a,b)(a,b)(a, b)，即航班aaa的起飞序号必须小于航班bbb的起飞序号。求一个可行的起飞序列&每个航班在所有可行的起飞序列中的最小起飞序号。 &nb...
2018-08-31 23:54:44
213
原创 拓扑排序+dp 旅行计划
题意：给出一张图，对于给出每一组边的关系(x,y)(x,y)(x,y)，x在yx在yx在y的西边。可以从图上的任意一个点出发，但每次只能往东走，求以1−n1−n1-n为终点的话最多可以走多少个点。首先，我们发现这是一张横向有向图，前面的结果会影响后面的结果，所以考虑拓扑排序。这里设f[i]f[i]f[i]表示以iii为终点的话最多可以走多少个点。f[i]f[i]f[i]的初值均为111，在进行...
2018-08-31 22:37:17
342
原创 最短路 玛丽卡
题意：一张图，有一条边无法通过，求1−n1−n1-n最短路的最大值。即求出边权和ansansans，保证无论哪条边无法通过，都能满足有一条从1−n1−n1-n路径边权和小于等于ansansans的最短路。很显然只有无法通过的边在一开始（没有无法通过的边）的图上的最短路上才会对答案产生影响，所以我们先跑一边最短路，然后枚举最短路上的每一条边，将它断掉后再跑最短路，结果就是maxmaxmax{di...
2018-08-31 14:57:57
96
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人