- 博客(324)
- 收藏
- 关注
RSS订阅原创 国王游戏证明
假设我们现在已经有了一个顺序，大臣左手的数字为A[1]A[1]A[1] ~ A[n]A[n]A[n]，右手的数字为B[1]B[1]B[1] ~ B[n]B[n]B[n]，国王则为A[0],B[0]A[0],B[0]A[0],B[0]现在我们交换位置为i,i+1i,i+1i,i+1两位大臣之间的位置交换前，两人的收益分别为1B[i]∏j=0i−1A[j]\frac{1}{B[i]}{\prod_{j=0}^{i-1}A[j]}B[i]1∏j=0i−1A[j]和A[i]B[i+1]∏j=0i−1A[j]
2022-03-17 23:39:31
174
原创 codeforces1158D Winding polygonal line
题面题意在平面上有n个点,现在给你一个长度为n-2的由LR构成的序列,要求你求出一个排列,使得按照排列在点之间连线后组成的路径中没有相交的线段,而且n-2个拐点的转弯方向与给出的序列相同.做法可以先在这n个点构成的凸包上任选一点作为起点,然后若第一个拐点的方向是向左,则可以在剩下n-1个点中选择一个点,使得无论第三个点选什么都满足第一个拐点是向左拐的,不难发现这个点一定存在,可以用差积求出...
2019-05-19 16:37:25
587
原创 [ZJOI2019]语言
题面题意有一棵有n个点的树,上面有m条链,两个点可以互达当且仅当存在一条两点都在上面的链.问有几对点可以互达.做法对每个点考虑它对答案的贡献,可以发现,若点x在链a1,b1;a2,b2.....a_1,b_1;a_2,b_2.....a1,b1;a2,b2.....上,则与x可以互达的点恰好都在点a1,b1,a2,b2.....a_1,b_1,a_2,b_2.....a1,b1...
2019-05-14 10:44:06
508
原创 codeforces1163 F Indecisive Taxi Fee
题面题意给出一张无向图,每次询问修改一条边的权值,并询问此时点1到点n的最短路的长度,询问之间相互独立.做法首先将修改分成以下三种情况:1.修改了非最短路上的边,则最短路变为min(\min(min(原来的最短路长度,d[1][u]+d[v][n]+len),d[1][u]+d[v][n]+len),d[1][u]+d[v][n]+len)2.修改了最短路上的边,且比原来短,则最短路...
2019-05-13 22:33:49
604
原创 codeforces1149E Election Promises
题面题意给出一张DAG,每个点上有一个数字,双方轮流进行操作:选择一个权值不为0的点,然后减少它的权值,并任意修改这个点所有后继的权值.做法这道题显然是Nim博弈,但是直接计算整张图的sg函数显然不可能,所以可以考虑将点进行分组,分别进行博弈,因此分组必须满足如下要求:1.一次操作不能同时修改一个组中中的两个数2.对同一个组中的点操作,可以修改的点所在的组构成的集合相同.因此可以按如...
2019-05-13 15:39:50
405
原创 codeforces1149D Abandoning Roads
题面题意给出一张无向图,每条边的权值只有两种:a或b(a<b),现在对每个点求,在这张图的所有最小生成树中,1号点到它的最短距离是多少.做法首先在建最小生成树时,权值为a的边比权值为b的边的优先级高,因此可以先将所有边权为a的边缩起来,这样如果权值为b的边连接的点在同一个联通块中,则这条边没有价值.然后我们可以发现,如果一条路径经过某个联通块两次,则这条路径不可能出现在最小生成树上...
2019-05-12 21:19:07
340
原创 codeforces1149C Tree Generator™
题面题意给出一棵树的括号序列,每次询问会交换括号序列中的两个字符,求交换之后树的直径.做法此题的难点在于如何将树的直径转化为括号序列上的某个值.将’)‘看作1,’('看作-1后,发现直径就是maxi−1<=j<=k<=2∗(n−1)∑x=ijnum[x]−∑x=j+1knum[x]\max_{i-1<=j<=k&am...
2019-05-12 18:37:26
398
1
原创 codeforces1161F Zigzag Game
题面题意交互题.给出一张二分图,左右两个点之间两两有边,每条边有一个权值且每条边的权值都不相同,Alice与Bob在上面玩游戏.每局游戏由Alice选择"增加"或"减少",Bob自动选择另外一项,然后Alice选择一个点并将棋子放在上面,Bob将它移动到一个与它相连的点,之后Alice与Bob轮流将棋子移动到一个之前没有移动到过的相邻点上.要求若Alice选的是"增加",则棋子移动所经过的边...
2019-05-09 19:52:46
290
原创 codeforces1161E Rainbow Coins
题面题意交互题有n个硬币,每个硬币有一个颜色,这个颜色是R或G或B,每次询问可以询问多对硬币是否相同(一个硬币不能同时属于两对),最多7次询问,将硬币按颜色分成三对.做法首先考虑硬币只有两种颜色怎么做,发现可以只用两次询问得到:第一次询问:1 2|3 4|5 6|…第二次询问:2 3|4 5|6 7|…这样就可以得到标号相邻的硬币的颜色是否相同,即可得到每个硬币的颜色.考虑三种颜...
2019-05-08 20:32:22
230
原创 codeforces1146H Satanic Panic
题面题意平面上有n个点,两两之间连线后,求一共能构成多少个五角星.做法首先可以将五角星看作是有5个点的凸包,也就是5个极角排序后递增的向量首尾相接后得到的图形.因此可以记dp[x][y][i]dp[x][y][i]dp[x][y][i]表示从点x到点y经过i个线段的方案数,对所有向量(一个线段可以看作是两个向量)进行极角排序后,依次来更新dp值,这样∑i=1ndp[i][i][5]\su...
2019-05-07 10:05:14
220
原创 codeforces1146G Zoning Restrictions
题面题意在一条路上有标号为1-n的n座房子,每座房子最高为h,若一座房子的高度为x,则这座房子的收益为x*x,有m条限制,每条限制表示如果在l-r之间的所有房子的最大高度超过hi,则罚款ci.问所有房子的最大收益是多少.做法一道经典的最小割.假设一开始所有房子的高度均为h,初始答案为n∗h∗hn*h*hn∗h∗h,可以对每座房子的每一种取值建一个点,并且这样连边S->0->1...
2019-05-07 07:31:18
324
原创 Atcoder agc033 D - Complexity
题面题意给出一个矩阵,若一个矩阵中的所有元素都相同,则这个矩阵的代价为0,反之可以将它分成两个子矩阵,代价为两个子矩阵的代价的较大值+1.做法因为答案是log级别的,所以可以考虑枚举答案,记dp[l][r][i]dp[l][r][i]dp[l][r][i]从第l行到第r行从第i列开始最多可以向右扩展到哪一列所形成的矩阵的代价为当前答案,若dp[1][n][1]=mdp[1][n][1]=m...
2019-05-05 11:55:37
457
1
原创 Atcoder agc033 E - Go around a Circle
题面题意给出一个环,上面有n个点,将他划分为n段弧,现在要求对每段弧进行红蓝染色,要求染色完成后,从每个点开始通过在环上移动,经过的弧构成的字符串都可以成为给定的字符串,问一共有几种染色方法.做法首先要确定一些结论.假设给出字符串的第一个字符为’R’('B’同理).分两种情况进行讨论:1.给定字符串中的所有字符都相同可以发现环上不存在两个连续的弧且它们的颜色都是B,因此除了所有弧同...
2019-05-05 09:32:20
989
原创 codeforces1155F Delivery Oligopoly
题面题意给出一张无向图,问至少保留几条边才能使此图是一个边双,并输出方案.做法考虑怎么构造出一个边双,发现可以通过在一个小边双上加一条链,使它变为一个新的大边双,所以可以记f[u][v][i]f[u][v][i]f[u][v][i]表示是否存在一条从u到v的链上包含了状态i的点,然后进行dp,dp[i]dp[i]dp[i]表示状态为i的点组成的边双至少要有几条边,用f数组进行转移即可.代...
2019-05-04 19:57:57
385
原创 codeforces954I Yet Another String Matching Problem
题面题意定义一种对字符串的操作为将某种字符全部替换为另一种字符,定义两个字符串之间的距离为让两个串相同的最少操作次数.现给出两个字符串S,T,求S的每个长度为∣|∣T∣|∣的子串与T之间的距离.做法首先转化一下两个字符串a,b之间的距离,若a[i]=u,b[i]=va[i]=u,b[i]=va[i]=u,b[i]=v,则可以由u向v连一条边,这样最后所有联通块的大小减一之和即为答案.现...
2019-04-18 08:42:32
291
原创 [CQOI2012]局部极小值
题面题意将1,2,3…,m*n填入一个m∗nm*nm∗n的矩阵,要求一些位置满足比周围八个数都小,且其他位置不满足,则一共有几种方案.做法首先不考虑"其他位置不满足"这个要求,因为数据范围很小,因此最多有8个位置符合条件,可以状压dp.考虑将m∗nm*nm∗n个数从小到大依次填入矩阵,用dp[i][j]dp[i][j]dp[i][j]表示当前要求位置填的数的状态为i,其他位置一共填了j个的...
2019-04-15 10:20:53
430
原创 codeforces1153F Serval and Bonus Problem
题面题意在一条线段上随机放n个线段,则被至少k条线段覆盖的区间总长度期望为多少.做法首先可以发现这n个线段的2∗n2*n2∗n个端点期望把线段等分为2∗n+12*n+12∗n+1段,那么只要计算每一段的贡献即可.这个可以用dp求出每段区间被大于等于k条线段覆盖的方案数,再除以总方案数,即可得到每段区间对答案的贡献,然后就能统计答案了.代码#include<bits/stdc++....
2019-04-15 08:37:28
394
原创 codeforces1119H Triple
题面题意给出三个数x,y,z,再给出n组数,每组数包含(x+y+z)个数,x个a,y个b,z个c,那么从每一组数中选择一个数的异或值为t的方案数是多少,对每个t输出答案,a,b,c均小于(1<<m).做法首先考虑一个简单的暴力,对每组数进行一次fwt,然后全部乘起来,时间复杂度为O(2m∗m∗n)O(2^m*m*n)O(2m∗m∗n),肯定不行.对于一组数a,b,c,可以考虑...
2019-04-14 22:18:52
381
原创 codeforces1119F Niyaz and Small Degrees
题面题意给出一棵有n个点的树,每条边有一个边权,对于[0,n−1][0,n-1][0,n−1]的每一个数x求,至少删掉权值和为多少的边后,所有点的度数都小于等于x.做法首先考虑对于一个x怎么做,记dp[i][2]dp[i][2]dp[i][2]表示第i个点与其父亲之间的边是否删去时,以i为根的子树最小要删去权值和为多少的点,转移时可以用堆处理出所有子节点t中dp[t][1]+val−dp[...
2019-04-12 19:54:13
438
原创 [ZJOI2019]麻将
题面题意共有n种麻将牌,给出一开始的13张麻将牌,问期望摸上来几张牌后,与开始的13张牌组合后存在一个大小为14的能和的子集.做法因为要求期望的摸牌次数,我们可以将这个次数转化为∑i=134∗np(i),p(i)\sum_{i=13}^{4*n}p(i),p(i)∑i=134∗np(i),p(i)表示总共有i张牌后仍然没和的概率,而p(i)=cnt(i)/A4∗n−13i−13,cnt(...
2019-04-11 07:41:10
447
1
原创 codeforces864F Cities Excursions
题面题意给出一张有向图，多次询问，每次询问给出三个数u,v,k，表示询问从u到v的路径上第k个点是什么。若u,v不连通或长度大于k或该路径无限长输出-1做法首先可以通过n次dfs求出数组ok,ok[i][j]表示从点i出发是否可到达点j，然后将询问离线。对于以点v为终点的询问，可以对于所有可以到达它的点u(u!=v)，找到点u直接连接，字典序最小且可以到达点v的点t，并让t向v连一条边...
2019-03-21 19:00:16
286
原创 codeforces193D Two Segments
题面题意给出一个有n个数的排列，现在请你选择两个不重叠的区间，使这两个区间的数的集合可以组成一个公差为1的等差数列，问有几个这样的集合。做法我们可以用f[l,r]表示[l,r]中的所有数在给出排列中最少分成几段，这样问题就转化为了求满足f[l,r]<=2,l≠rf[l,r]<=2,l =\not rf[l,r]<=2,l≠r的区间个数。可以考虑枚...
2019-03-19 20:24:58
263
原创 codeforces949D Curfew
题面题意一条直线上有n个寝室，每个寝室中有aia_iai个人，现在有两个宿管分别从左右两边向中间走，每个单位的时间查一个寝室，若人数不足b个，则会记录，最中间的寝室归左边的宿管，现在每个人每个单位的时间可以跑d个寝室，则两个宿管记录下的寝室数量的较大值的最小值是多少。做法这题有一个很棒的贪心，可以从左向右扫（直到中间），如果可以到达这个寝室的人数（在宿管来之前）大于等于b，就让这些人过来...
2019-03-19 16:00:51
1915
原创 codeforces1111E Tree
题面题意给出一棵树，多次询问，每次询问给出一个根节点和k个点，问要求将它们划分为至多m个集合，要求每个集合中不包含存在祖先关系的点，则一共有几种方法。做法考虑单次询问怎么做，可以发现一个非常重要的性质，一个点的两个不同祖先不可能在同一个集合中，因此可以先将所有点根据到根节点的距离排序，记dp[i][j]dp[i][j]dp[i][j]表示前i个集合划分为j个集合的方案数，然后可得dp转移：...
2019-03-14 10:09:09
227
原创 洛谷 P4595 [COCI2011-2012#5] POPLOCAVANJE
题面题意给出一个字符串S(长度不超过300000)和至多5000个串，用这至多5000个串去覆盖S，每个串允许用多次，且允许串重叠，则S中至少有几个字符不被覆盖。空间限制为64MB做法这题可以用后缀自动机和AC自动机都可以直接做，但是因为空间限制，都不能直接建。但是注意到这5000个字符串相互独立，所以可以进行分块，对约根号个串建出AC自动机后，计算贡献，然后每次再清空重建即可代码...
2019-03-13 21:52:57
187
原创 AtCoder Grand Contest 019F Yes or No
题面题意你要做一共(n+m)(n+m)(n+m)道判断题，其中有m道题的答案是对，n道题的答案是错，当你做一道题之后，就可以知道对错，则你期望最多能做对多少题。做法首先最优方法肯定是写当前剩余数量最多的答案，我们可以将求正确期望改为求错误期望，对此建一张图：横纵坐标分别表示此时剩下的答案数，自下而上的边表示此时答案是对的题较多但正确答案是错，自右向左的边则相反，这样将每条边的权值为设1...
2019-03-13 16:40:15
142
原创 codeforces1137F Matches Are Not a Child's Play
题面题意给出一棵树，每个点有一个优先级，初始为自己的标号，如果每次删去树上优先级最低的叶子，将得到一个序列，要求维护有三种操作：1.将一个点的优先级修改为此时所有点的优先级的最大值+12.询问某个点在序列中的位置3.询问两个点中哪一个点先被删去做法首先第三种操作只要经过两次二操作即可得到，因此不用管它。观察一下第一种操作之后对序列的影响，发现第一次操作就相当于把原来最大节点到修改节...
2019-03-12 12:05:40
483
原创 codeforces1120E The very same Munchhausen
题面题意给出一个正整数a，问是否存在一个正整数n，满足S(a∗n)=S(n)/aS(a*n)=S(n)/aS(a∗n)=S(n)/a且n&amp;lt;=10500000n&amp;lt;=10^{500000}n&lt;=10500000S(x)S(x)S(x)表示x各个数位的数字和。做法首先可以考虑把n分成多个部分，使n形如b1+b_1+b1+"0000"+b2++b_2++b2...
2019-03-06 14:57:58
731
原创 codeforces1132G Greedy Subsequences
题面题意给出n个数和一个数m，求区间[1,m],[2,m+1]......[n−m+1,n][1,m],[2,m+1]......[n-m+1,n][1,m],[2,m+1]......[n−m+1,n]的最长贪心子序列，最长贪心子序列的求法是，在每个数后面接上右边第一个比它大的数。做法这几个询问区间可以看作是在原区间的左边加数，右边删数。如果我们记dp[i]表示以该位置为结尾的子序列的...
2019-03-06 10:37:45
352
原创 2018-2019 ACM-ICPC, Asia East Continent Finals J. Philosophical … Balance
题面题意多组数据，每组数据给出一个长度为n的字符串S，求maxi∑j=1nlcp(i,j)∗kj\max_{i}{\sum_{j=1}^{n}lcp(i,j)*k_{j}}maxi∑j=1nlcp(i,j)∗kj的最小值其中kik_{i}ki由你定，但是要满足∑i=1nki=1\sum_{i=1}^{n}k_{i}=1∑i=1nki=1，且0&amp;amp;lt;=ki&amp;amp;lt...
2019-03-05 17:58:26
534
原创 codeforces403E Two Rooted Trees
题面题意给出两棵树A，B，其根节点都是1，现在删掉A树中的一条边(u,v)，然后将B树的所有满足p,q两点中有一点在u,v的公共子树中，另外一个点不在的边(p,q)删去，然后再按上述规则来删掉A树中的所有满足条件的边，输出删边顺序。做法首先可以对于一棵树上的边(p,q)，如果它要被删掉，当且仅当另外一棵树上路径pq中的任意一条边被删去，而这条路径可以通过树链剖分转化为线段树上的几段区间。...
2019-03-04 20:40:41
226
1
原创 codeforces528E Triangles 3000
题面题意在平面上有n条直线，随机选择三条，其面积的期望大小是多少。做法很显然，面积的期望要转化为所有三角形的面积和除以(n3)n\choose3(3n)，考虑计算三角形的面积和。可以把三角形ABC的面积转化为(OA×OB+OB×OC+OC×OA)/2，这样只要分别计算这几个叉积的和即可。经过观察不难发现，如果OA，OB的叉积会被计算，当且仅当A，B两点都在某条给出的直线上 ，因此我们...
2019-03-03 20:29:24
427
原创 codeforces335F Buy One, Get One Free
题面题意你要买n个东西，当你买了一个价格为x的东西时，可以让商店免费赠送你一个价格严格小于x的东西，则你买下这n个东西至少要花多少钱。做法n很大，考虑贪心。首先根据商品的代价从大到小排序，价格相同的商品一起考虑。可以把所有赠送的商品的价格都放到一个小根堆里，当我们考虑价格为x的商品时，记一共有sum个商品的价格比x大，首先将可以送的商品直接赠送(共有min(sum−2∗pq.size...
2019-03-03 16:20:22
830
原创 codeforces506E Mr. Kitayuta's Gift
题面题意给你一个长度为n的字符串，现要你加上m个字符，使其变为一个回文串，问有几种加法。做法首先题目可以转化为，求有几个长度为n+m的字符串，使给出的字符串为该字符串的子序列。这样可以考虑从两边开始确定字符，并与给出的字符串进行匹配，然后我们就可以根据此时的字符串已经匹配的位置建立自动机，这个自动机由多个节点构成，每个点都有一个权值为24,25或26（仅终点是26）的自环，然后非自环会形...
2019-03-03 13:44:01
347
原创 codeforces258D Little Elephant and Broken Sorting
题面题意给出n个数，有m次操作，每次操作给出两个数，会有50%的概率交换这两个数，问m次操作后逆序对的期望数量。做法我觉得这题的难点主要在于dp状态的设计。可以记dp[i][j]dp[i][j]dp[i][j]表示第i个位置上的数比第j个位置上的数大的概率。这样开始dp[i][j]=(num[i]&gt;num[j])dp[i][j]=(num[i]&gt;num[j]...
2019-03-01 22:10:11
197
原创 codeforces516E Drazil and His Happy Friends
题面题意有n个男孩，m个女孩，他们中有些人高兴，其他人不高兴，第iii天，第imod&ThinSpace;&ThinSpace;ni\mod nimodn个男孩会和第imod&ThinSpace;&ThinSpace;mi\mod mimodm个女孩约会，若两人中有一个人高兴，则两个人都会高兴，则至少几天后，所有人都会高兴。做法首先可以将所有人根据模gcd...
2019-03-01 17:53:38
298
原创 codeforces633H Fibonacci-ish II
题面题意给出n个数，每次询问给出l，r，询问把[l,r][l,r][l,r]这段数排序去重后，求第i个数乘上斐波那契数列的第i项的和。做法这题需要一个公式Fi−1∗Fk+Fi∗Fk+1=Fk+iF_{i-1}*F_k+F_i*F_{k+1}=F_{k+i}Fi−1∗Fk+Fi∗Fk+1=Fk+i发现利用这个公式，可以推得∑i=1nnumi∗Fi+t−1∗Fk+∑i=1nnum...
2019-02-27 15:45:44
163
原创 codeforces1023F Mobile Phone Network
题面题意有n个点，并给出k条还没有权值的边和m条有权值的边，要求你给这k条边赋上权值，使得存在一种最小生成树包含这k条边，问k条边的最大权 值和是多少。做法首先可以先求出这棵最小生成树，然后这m条边中的所有非树边都会与原树构成一个环，要满足它不是树边，它就必须是环上的最大值，相当于要对环上的所有树边都取一次最小值，这个用树链剖分，差分+启发式合并或可并堆…都可以做，但都很麻烦。可以发现，...
2019-02-26 18:51:13
153
原创 codeforces1129E Legendary Tree
题面题意交互题，要求你通过询问确定一个有n个节点的树的边，每次询问输出两个集合S，T和点v，将会告诉你从S集合的某个点到T集合的某个点并经过点v的路径数。做法首先钦定点1为根节点，然后发现，询问({x∈N∗x \isin N^*x∈N∗ | 2&lt;=x&lt;=n,x̸=i2&lt;=x&lt;=n,x\not =i2<=x<=n,x̸=i...
2019-02-25 21:47:21
302
原创 codeforces1129D Isolation
题面题意给出一个长度为n的序列，将它划分成一个或多个子串，使每个串中只出现过一次的数字个数小于等于m，求方案个数。做法记dp[i]表示前i个的答案，f(i)f(i)f(i)表示iii到nnn（nnn表示此时的右端点）的只出现一次的数字个数，则dp[n]=∑f(i)&lt;=mdp[i−1]dp[n]=\sum_{f(i)&lt;=m}dp[i-1]dp[n]=∑f(i)&...
2019-02-25 19:28:21
268
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人