caoyang1123-CSDN博客

原创支配树学习笔记

定理4用来求sdom，先搞一个dfs树，然后将点按dfs序从大到小加入，对每个点维护到当前根（即已加入点）路径上sdom最小是哪个（sdom的比较是对dfs序比）记为home，可以用带权并查集完成。加入一个点，就先枚举所有能直接到达本身的相邻点，用他们的home更新我，然后加入我到dfs树父亲的边。然后用推论1求idom，写一个倍增求(sdom[x], x]路径上sdom最小的点即可。模板题 HDU4694 （建立根在n的支配树）

2023-07-28 10:48:26 185 1

原创 arc062 F - Painting Graphs with AtCoDeer

F - Painting Graphs with AtCoDeer不在环上的边是平凡的。一个单独的环方案统计显然是直接用burnside引理统计即可，问题在于多个环嵌套。此时会发现，多个环嵌套时，这些环包含的边颜色可以任意排列，可以构造性地不严谨证明一下，两个环A，B相交，设一个相交边为e，则B需要的边可以通过e先都放到A里，然后不断旋转A，把B所需的下一个边转到e，然后B拿走这条边，只到B构建完成（不包括e本身所需），然后再考虑类似地构建A。判环是否无嵌套，可以DCC缩点，然后看点双中的点

2022-03-04 22:04:42 197

原创 arc062 E - Building Cubes with AtCoDeer

E - Building Cubes with AtCoDeer计数题，首先当前砖块的情况可以压缩成1个long long表示，考虑处理出每个砖块旋转同构的所有情况中，压缩后数字最小的那个作为该砖块权值。然后枚举顶面与下底面i,j （i < j）,然后枚举下底面相对顶面的旋转情况，再考察插入四周四个面，注意四周面可能是四色相同或者对角相同，需要额外统计。这样显然一种可行方案被统计3次，最后答案除以3即可。#include<bits/stdc++.h>#define pi

2022-03-04 21:49:56 268

原创 arc061 F - Card Game for Three

F - Card Game for Three显然要出现n张a在m + 1张b、k + 1张c之前，使得Alice获胜，游戏结束。考虑枚举b和c一共出现i次，以及把这i次插入a中（得在最后1个a之前），之后剩余牌即可任选的方案数，为C(n + i - 1, i) * 3 ^ (m + k - i)再考虑这i次中b和c分别出现几次，此时限制为b小于等于m次，c小于等于k次。发现这个东西是可以随着i增大O（1）维护的，不妨记这个东西为t，则(i - 1) -> i，t = t * 2 - C(

2022-03-03 16:33:12 3421

原创 arc061 E - Snuke‘s Subway Trip

E - Snuke's Subway Trip考察建图的一个最短路问题，因为切换颜色会导致cost+1，因此可以考虑如下建图，对于某一种颜色边构成的一个连通块，新开一个点t，每个连通块内点向t连一条代价为1的边，然后t向连通块内点连一条代价为0的边，此时就可以发现选择走某种颜色就是能用1的代价到达该色的连通块内每个点，之后跑0/1bfs即可。#include<bits/stdc++.h>#define pii pair<int,int>#define fi first

2022-03-03 15:44:57 184

原创 arc060 F - Best Representation

猜一下就知道最后划分要么是1，要么是2，要么是n1就是开始就没有整除的周期，n就是字符全等，这两类方案均为1然后考虑2的方案，对每个前缀、后缀看看有没有整除的周期即可（一共要check的就是nlogn个，二分哈希、Z函数之类随便搞一下）这个结论证明也比较简单：考虑s这个串不全等，有一个大于1且小于等于n / 2且整除n的周期p，然后考察划分为n - 1, 1两段，则若这个划分不可行，同理得到s[1...n - 1]这个前缀有一个大于1且小于等于(n - 1) / 2且整除n - 1的周期q，而因

2022-03-03 15:16:00 245

原创 arc060 E - Tak and Hotels

E - Tak and Hotels先找到每个点一步最远跳到哪个点，然后用个倍增即可#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc second#define pb push_back#define ll long long#define trav(v,x) for(auto v:x)#define all(x) (x).begin(), (x).end()

2022-03-03 14:57:20 116

原创 arc60 D - Digit Sum

D - Digit Sum问题就是找到最小的进制b，使得n在b进制下各个数位求和等于s看到这个数据范围就基本上往根号算法上去想，显然如果进制b小于根号，暴力一下；大于根号，那么一定是只有一位数，且这个数小于根号，枚举这个数即可（代码之前好像写得有点蠢，搞了个整除分块）。注意还要判断一下b取n + 1时，可以得到最大的s = n#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#def

2022-03-03 14:51:03 100

原创 arc059 F - Unhappy Hacking

F - Unhappy Hacking显然跟串具体是什么无关，仅跟操作数n、串长m有关然后考虑定下结尾m个元素，现在问题发现此时要达到n个操作步数，就相当于在这m个元素空隙间（包括第一个元素前、最后一个元素后）插入n - m括号的方案数（左括号为插入0/1，右括号为退格操作，其中可以有无效右括号，但每个左括号必须匹配），然后再乘上2^(左括号数)。进一步我们能够发现，整体来考虑，方案数就相当于构建一个长为n的括号序（可以有一些无效的右括号，表示空的时候退格），最终没能匹配的左括号有m个的方案数乘

2022-03-03 14:39:02 154

原创 arc059 E - Children and Candies

简单预处理一个k次幂前缀和，然后n^3 dp即可，dp当前用了多少个candies方案贡献和。#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc second#define pb push_back#define ll long long#define trav(v,x) for(auto v:x)#define all(x) (x).begin(), (x).end

2022-03-03 14:15:06 104

原创 arc058 F - Iroha Loves Strings & Z函数学习笔记

F - Iroha Loves Stringsdp(i, j)表示考虑前i个串，拼成长度为j的字典序最小串。显然这样状态数n * k,每个状态是一个长度为k的string，不可行。发现一个性质，如果当前j < k,有字典序 dp(i, j) < dp(i, k)【此处的小于定义为严格存在一个位置小于，不包括dp(i, j)是dp(i, k)前缀，之后的比较也是这样】且(i + 1 ~ n)能够拼出一个长度k - j的串（这一步可从后向前做个可行性dp即可），则dp(i, k)显然不可

2022-03-03 13:41:23 272

原创 arc058 E - Iroha and Haiku

考察第一次出现可行位置，会发现相当于这个位置前有一段后缀和Z,一段后缀和Y + Z, 一段后缀和X + Y + Z,而发现X + Y+ Z非常小，可以用状压dp，状压sta的第i位为1则表示当前存在后缀和为i，每次转移到可行状态就统计答案并不再往后转移，否则继续转移下去。复杂度n * 2^(17) * 10#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc second

2022-03-02 12:17:57 133

原创 CF772 Div2F. Closest Pair题解

Problem - F - Codeforces一些给定n个点，求所有点对间某个最值信息的题目，可以考虑把数量为n^2边中剔除掉一定不可能的那些，之后可能剩下的边数就是O(n)之类可以接受的复杂度了。考虑对每个点i,查询...

2022-03-02 12:11:59 184

原创 CF768 Div1F. Flipping Range题解

Problem - D - Codeforces因为每个操作取负的长度都是小于等于整个区间长度一半，根据字符串周期的dilemma，可以知道所有操作等价于每次能长度g的区间，其中g为所有bi的gcd。发现这个操作下的一个性质，不管这个操作选在哪个开始位置，选到的区间中都恰好是1个下标mod g = 0, 1个下标mod g = 1,...,1个下标mod g = g - 1，然后考虑把取负的位置i记ci = 1否则ci = 0，能得到不管操作多少次，c[0] ^ c[g]^ c[2g] ^... .

2022-02-23 18:01:23 181

原创 CF 767Div1 D2. Game on Sum (Hard Version)

Problem - D2 - Codeforces考虑dp，dp(n, m)表示还有n步操作，Bob至少还需要进行m步add操作的最终答案。则假设当前Alice选择了一个x（x belong to [0, k]），那么Bob有两种走法：（假设当前不在边界情况）1) 用减, 则答案为dp(n - 1, m) - x2) 用加, 则答案为dp(n - 1, m - 1) + x注意到dp(n - 1, m) > dp(n - 1, m - 1)...

2022-02-23 00:14:26 534

原创 CF global round18 E. Purple Crayon

Problem - E - Codeforces显然先手标记叶子最优，那么：1）如果叶子数少于先手可操作数，先手一定是叶子全标红（因为如果不标完的话剩下的叶子一定会被后手标蓝，相当于白色数不增，而红-蓝下降，肯定不优），然后再暴力枚举一下叶子以外标几个，找个最大值。2）叶子数多于先手可操作数，则先手一定要标满所有可操作数，使得后手可操作性尽可能少。则可以每次贪心选能ban掉最多点的叶子，用线段树维护，每次暴力跳所有未ban点更新（总共最多ban全部）。然后后手枚举标蓝数，找个最小值。#in

2022-02-22 11:14:51 640

原创 CF global round18 D. X(or)-mas Tree

Problem - D - Codeforces首先树上两点(x, y)间简单路径上边权异或和，可以转化成(root, x)上路径异或和异或 (root, y)上路径异或和，因此我们可以把每个点点权定义为从根到当前点上边权异或和，同时发现两个数异或的奇偶性只跟两个数各自二进制下1个数奇偶性有关，可以用0/1态表示。此时问题转化为：给定一棵树，一些树边已确定了连接的两点是相同态还是相反态，然后再给出一些形如树上两点点权是相同态还是相反态的限制，求可行方案。显然是2-sat问题#includ

2022-02-21 23:25:51 384

原创 CF global round18 C题解

好像在打这场前在atc上做了道特别ex的翻转问题（要建图跑差分约束系统），然后碰到这么一道水题往很难的方向想了。。。本质上偶数步操作就是每两步操作将1个1和1个0的位置互换，因此只要比两个串1个数，不同1位置即可。奇数步操作则尝试找一个答案串里有的1位置保留，没有的话就任意找一个，然后整个串取反，接着按偶数串做即可#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc s

2022-02-21 23:04:07 102

原创 CF Edu119 F. Bipartite Array题解

不难发现充要条件就是不能出现i < j < k，ai > aj > ak最暴力的dp，考虑可行性dp，dp(ps, x, y)表示考虑到ps位置，前面aj最大的ai > aj = x，ai最大的ai = y这一方案是否存在。显然这样状态数就已经爆了，发现x一定时y越小越好，因此用最值dp优化。dp(ps, x)表示考虑到ps位置，出现了ai > aj = x时，之前的y能取到的最小值。然后又发现x增大时y单调不增，因此可以用线段树区间修改优化dp更新。恶心之处

2022-02-21 22:21:09 98

原创 CF 761 Div2E. Christmas Chocolates 题解

Problem - E - Codeforces观察下或者打个表就能发现各个数从大到小走到0构成一棵树，然后问题是找树上相距最远两点。//#define LOCAL#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc second#define pb push_back#define ll long long#define trav(v,x) for(auto ..

2022-02-21 22:06:58 91

原创 CF761 Div2 D2. Too Many Impostors题解

Problem - D2 - Codeforces首先发现能找到1好人1坏人就可以用这两个人确定所有人好坏。考虑如何找，发现题目给的条件满足鸽笼原理，即我们三个人三个人划分为一组，那么一定会有一组好人多于坏人，一组坏人多于好人，不妨分别记为good组、bad组（此时花费n/3步）考虑从bad组拿出2个人固定，去查good组的3个人，分几种情况讨论一下：（花费3步）1)存在一次好人更多，则说明bad组剩下一个一定是坏人，且good组查出来了一个好人，找到一好一坏。2)不存在坏人更多，那么当

2022-02-21 21:58:46 157

原创 CF edu118F 题解

Problem - F - Codeforces题意：给一棵树染色染一个排列，要求整棵树内不存在儿子染色的值是父亲值-1，求方案数。显然可以上容斥，考虑树里面至少有k个儿子染色的值是父亲值-1，考察当前这k个儿子向父亲的边，发现这些边在树上构成一些链，而贡献的方案数有奇妙的性质：每一条链内部大小关系是确定的，即从最浅到最深依次-1，而各链、各未选中点之间的大小关系是不确定的，此时我们发现方案数就是（链数+未选中点数）的阶乘，因为我们只要固定彼此之间的大小关系就可以唯一对应原问题的一个排列。此时相

2022-02-21 21:41:53 126

原创 lyndon分解学习笔记

Problem - H - Codeforces假模板题，b站看jls用一个叫lyndon分解的神仙算法秒杀了此题，于是去学了lyndon分解，结果自己写完发现随便造了个数据就hack掉了（顺便去b站评论hack了一波jls，被回复了，XD），出题人可能自己没想到有人用这么冷门的算法......lyndon分解就是说每一个字符串，都能唯一地划分为一系列子串s1,s2,s3...sk，满足如下两条性质1）si是lyndon串，lyndon串的定义为最小后缀为自身的串,如ab、aab是，aa，ba不

2022-02-20 19:37:02 226

原创牛客挑战赛57C题解

登录—专业IT笔试面试备考平台_牛客网最近题刷了一堆，结果碰上这种裸的数据结构题（套路题）不会做了（场上想了个对询问分块，还去搞了个O(1)求k级祖先，结果被卡爆）......remake吧。直接大力树剖，每条修改的链被划分为log段，向上的修改存在孩子处，向下的存在父亲处，注意向上的时候跳轻边处理下即可。#include<bits/stdc++.h>#define pii pair<int,int>#define fi first#define sc secon

2022-02-20 19:10:22 420

原创牛客练习赛94F题解

链接：登录—专业IT笔试面试备考平台_牛客网令sec(x)表示mex为x的最小区间，假设当前插入到t，只需维护x = 1 ~ t的sec（x）的左右端点位置即可（这里端点位置定义为在当前已经存在的数中的位置）（sec（0）不产生贡献，不用管）首先考虑插入操作，假设插入操作t，修改sec(t)、sec(t + 1)是平凡的, 对于x = 1 ~ t - 1的sec(x),发现如果左端点位置大于当前t的插入位置，则sec(x)左端点要+1，而又有sec(x)左端点关于x单调不增，因此可以用线段树维护;

2022-02-20 18:22:48 457

空空如也

空空如也