- 博客(933)
- 收藏
- 关注
RSS订阅
原创 补题list
数据结构2018CCPC吉林赛区 Lovers线段树2019中山大学程序设计竞赛 Party线段树牛客练习赛69 E.子串线段树The Preliminary Contest for ICPC Asia Nanjing 2019 I. Washing clothes李超树2019 ICPC Asia Xuzhou Regional H. Yuuki and a problem带修主席树The 2019 Asia Nanchang First Round Online Pro.....
2020-10-07 22:38:09
743
2
原创 Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）F. Oddly Similar（bitset暴力）
n(n
2024-04-15 01:50:01
233
原创 Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）G. Max (Sum - Max) （决策单调性+主席树前k大）
长为n(n<=2e5)的两个序列a和b，第i个数分别ai(-1e9<=ai<=1e9)，bi(-2e14<=bi<=2e14)倘若k=x最优决策是在大于j的位置取到的，那么一定是将k=x在j处决策后的最优决策调的更优了，把相同的调优手段应用给k=x+1，也能使k=x+1更优，与k=x+1的最优决策在j矛盾。那么当i变为i+1的时候，如果无脑选第i+1个位置，就构成了一种k=x+1的决策。考虑k=x的时候，已经在i处取到了[1,i]的最优决策，此时k=x的最优决策在i+1处取到，否则还是在第i处取到。
2024-04-15 01:37:34
252
原创 AtCoder Beginner Contest 349 G. Palindrome Construction（魔改manacher+并查集）
求是否存在正数数字串，满足每个位置的最长回文半径是s[i]（此时要么s[i]+1越界，要么不相等）对于最长回文半径是s[i]的情况，需要钦定i-s[i]-1和i+s[i]+1字符集不相等，然后先判互斥关系，如果互斥关系的两个点已经在同一集合了，显然无解。这个值我们保留，如果这个值已经超过了输入中给定的值，显然无解。否则，从前到后贪心，填满足互斥关系条件下的字典序最小即可。给定每个位置的最长回文半径s，第i个数是s[i]，后面扩展的时候，需要在串上满足对应位置相等，dreammoon讲解。
2024-04-15 01:05:24
368
原创 AtCoder Beginner Contest 150 F. Xor Shift （异或性质+扩展kmp）
将s1扩展成原来的2倍之后（s1=s1+s1），与s2做扩展kmp即可。你可以自行选择一个k(0
2024-04-12 04:51:17
247
原创 AtCoder Beginner Contest 141 F. Xor Sum 3（异或性质+异或线性基求最大异或值）
如果第i位为0，那么出现偶数次，只有左右都分奇数次的时候，才有2的贡献，否则产生0的贡献。只考虑n个数的这些位，选出一个非空子集来，使得n个数在这些位上的异或和最大，记为mx。为0的这些位有两倍的贡献，为1的位不管怎么分都能取到，所以最终答案是2*mx+s，如果第i位为1，那么说明这一位出现奇数次，不管怎么分都是一边1一边0，n(2<=n<=1e5)个数，第i个数ai(0<=ai<=2^60)将n个数分成两堆，对每一堆求异或和，再将得到的两个数求和，计n个数的异或和为s，考虑s的每一位，
2024-04-12 04:19:32
398
原创 2018年长沙理工大学第十三届程序设计竞赛 K. zzq的离散数学教室2（dilworth定理+有向图可相交路径覆盖 dinic版）
(这里的≤不是传统意义上的小于等于，可以理解为从y到x的一条有向边)，记做：x≤y。同时这些关系也具有传递性，例如，如果x≤y并且y≤z，那么可以得到x≤z。左侧s->i可以看成是选了一个起点，x->y+n如果不相交的话就是选了一个终点，y+n->y相当于允许退回去，不把y当终点，后面还可以选其他点当终点。x->y+n的边的权值，因为也要过重选的流量，所以也置INF。T组样例，n<=1e5，sumn<=3e5，m<=2n。2. 将原来的有向边x->y，看做是x->y+n。1. 将i拆成i和i+n两个点，
2024-04-12 04:05:40
446
原创 CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) E. Farm Game（博弈论+组合数学）
一条数轴，0和l+1两点有墙，[1,l]这l个点需要放2n头奶牛，其中n头属于FJ，n头属于FN。那么，有0<𝑎1<𝑏1<𝑎2<𝑏2<…<𝑎𝑛<𝑏𝑛<𝑙+1成立。每个间隔都是奇数，每个空隙都是>0的数，相加之和为n+1的方案数。如果 𝑎1,𝑎2,...,𝑎𝑛 代表一个农场主的奶牛的位置，而 𝑏1,𝑏2,...,𝑏𝑛 代表另一个农场主的奶牛的位置，每次一个人选一个数字k(1<=k<=n)，并选择k头奶牛，FJ先手，给定l(l<=1e6)和n(n<=l/2)，然后将问题转化成，n个间隔，此外还有n+1个空隙，
2024-04-08 10:36:54
429
原创 CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!) D. Learning to Paint)（思维题/优先队列）
此外，还有一个n*n的数组a，第i行第j列为a[i][j](-1e6<=a[i][j]<=1e6)，用来评估得分，for循环遍历1到n+1，每次往优先队列里放入top1即可，即dp[j][1]+a[j+1][i-1]对于x∈[1,i+1]的这些情况，把每种的top1塞入优先队列，然后就可以多路归并了，例如，对如上涂色方式，实际得分为a[2][4]+a[6][6]+a[8][9]，dp[i][j]表示考虑[1,i-1]，i强制不取时，前j大的分数和，3. 加上一个[x,i+1]的区间，再塞入优先队列。
2024-04-08 10:15:29
468
原创 AtCoder Grand Contest 066 B. Decreasing Digit Sums（构造 打表找规律）
然后考虑变小怎么做，逆向考虑10000，如果*2=10000变小，前一项就是5000，这样不断除以2，2500，1250，...逆向这个过程，考虑构造5的j次方，每个*2的时候，都会变小几次，然后变大一次，整体趋势变小，偶有变大。给定一个n(n
2024-04-01 23:59:24
174
原创 AtCoder Grand Contest 066 A. Adjacent Difference（构造 思维题）
n*n(n<=500)的矩阵，第i行第j列的数a[i][j](-1e3<=a[i][j]<=1e3)相邻：a[i][j]和a[i][j+1]认为相邻，a[i][j]和a[i+1][j]认为相邻。不难发现，由于每个数向左向右构成了一个长为d的区间，所以两次操作的代价和是d*n*n。第一次，将黑色的数改成最近的d的奇数倍，将白色的数改成最近的d的偶数倍。第二次，将黑色的数改成最近的d的偶数倍，将白色的数改成最近的d的奇数倍。所以较小代价的那次就是不超过n*n*d/2的，输出即可。jiangly B站讲解。
2024-04-01 23:51:22
315
原创 XXII Open Cup, Grand Prix of Daejeon C. AND PLUS OR（思维 结论）
给定n(n<=20)，再输入2^n个数，分别代表a[0]到a[2^n-1]，第i个数ai(0<=ai<=1e7)可以发现，不管f(v2)多大，要么f(v1)<f(v2)，要么f(v2)<f(v3)成立，其中v3比v1多了一个集合z，就是多了若干位的时候，有f(v1)<f(v3)考虑令左式为f(v1)，右式为f(v3)，有f(v1)<f(v3)成立，然后z是一个集合，是多出的若干位，如果有解，说明最后这个式子成立，所以，枚举公共集合x，枚举i的变化位y，枚举j的变化位z，复杂度。那么，考虑这个渐变的过程，
2024-03-30 11:13:45
303
原创 KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) E. Swap（线性dp 交换）
可交换次数不超过n^2时，dp状态是O(n^5)的，转移枚举三种字符，每种算增量代价是O(n)的，dp[i][e][y][k]表示前i个字母有e个E、y个Y最少交换k次的字符串的方案数。也就是说，如果第e+1个E前面，Y的字符超过y个，那么剩下的Y都需要被绕过，K同理。所以，当前字符用什么，在原串里的位置一定唯一，交换次数也能唯一确定。假设当前第i个字符填E，一定用的是串中第e+1个E，比如，之前已经用过e个E，y个Y，i-e-y个K，且需要在交换的时候绕过第e+1个E前面的其他字符，
2024-03-30 01:35:52
163
原创 KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) F. Treasure Hunting（线性dp）
h*w(h<=30,w<=30)的格子矩阵，第i行第j列格子权值a[i][j](1<=a[i][j]<=1e9)当前位于(i,j)，最小值是否已经出现过了，大于等于最小值的权值已经选了k个，权值和最小是多少。当前位于(i,j)，当前最小值是x，大于等于最小值的权值已经选了k个，权值和最小是多少。找到一条路径，取途中最大的k(k<h+w)个格子的权值求和后，和是所有路径中最小的。终态要么是大于最小值，要么是等于最小值，并且大于最小值的时候的值都是必取的。一开始想的是dp[i][j][x][k]表示，
2024-03-27 21:29:40
190
原创 Atcoder TUPC 2023（東北大学プログラミングコンテスト 2023）P. Sub Brackets（dinic 二分图最大独立集）
出现这种情况时，要求x[li-1]<=x[lj-1]<=x[ri]且x[li-1]=x[ri]，否则，如果上一个字符是左括号，则当前是右括号，上一个字符是右括号，则当前是左括号。需要取的位置，如果存在要取的li，就放左括号，如果存在要取的ri，就放右括号。定下来括号串，满足最多的限制数，使得每个限制对应的区间是一个合法的括号串。长为n(n<=500)的尚未确定的括号串，m(m<=500)个限制条件。考虑把(看成+1，)看成-1，x[i]为括号串的前缀和数组，li和lj奇偶性不同，li<lj<=ri<rj。
2024-03-15 21:52:22
537
原创 Atcoder TUPC 2023（東北大学プログラミングコンテスト 2023）E. And DNA（矩阵快速幂+拆位讨论）
2. 如果m=1，由于1+(1&1)=2，0+(0&x)=0，所以不能有三个1相邻，不能有两个0相邻。对于i∈[1,n]，均满足a[i]+(a[i-1]&a[i+1])=m，求这样可能的数组的方案数。①如果是1，只能是1+(1&1)=2，此时还给倒数第二位贡献了1，需要再递归求m/2-1的方案。长为n(3<=n<=1e9)的数组，第i个数ai在[0,m](m<=1e9)之间。特别地，认为a[0]=a[n],a[n+1]=a[1]，即这个数组是个环形的数组。有f(m)=f(1)+f((m-1)/2)
2024-03-15 20:49:43
417
原创 Educational Codeforces Round 132 (Rated for Div. 2) E. XOR Tree（启发式合并+贪心）
XOR(u,v) = XOR(根到u) xor XOR(根到v) xor a[lca(u,v)]修改最少的点的权值，使得树上不存在异或和为0的简单路径，输出最少的点数。自己的写法怎么写都写不对，都wa8，感觉是启发式合并公有map导致的。n(n<=2e5)个点的树，点i权值ai（1<=ai<2^30）那就是判一下某个点的子树是否存在两个点的祖先异或，等于本身的权值。这个可以启发式合并的时候，把小的集合往大的集合上挂的时候判断。假设树形是固定的，dfs往上回溯的时候，删除某个点，就可以认为是清空集合。
2024-03-02 03:31:11
382
原创 AtCoder Beginner Contest 230 G. GCD Permutation（容斥/莫比乌斯反演 补写法）
求(i,j)(1<=i<=j<=n)对的数量，满足gcd(i,j)≠1且gcd(pi,pj)≠1。新函数需要满足n=1的时候对因子求和为0，大于1的时候对因子求和为1，枚举i和i的倍数j，所有倍数j需要反演得到i固定时的答案，取到了一个数和一个空位的时候，就认为是取了两次相同的数。那么0减掉mu[1]之后是-1，取反之后即为1，给定长为n(n<=2e5)的1-n的排列p，由于gcd不能为1，要忽略mu[1]的贡献，一共有x个数时，任意取两个，可以重复取，之前n>=2的时候，因子mu之和为0，
2024-02-13 00:15:32
359
原创 KAJIMA CORPORATION CONTEST 2024（AtCoder Beginner Contest 340） G. Leaf Color（虚树+dp）
导出子图，即在n个点里选一个子集，选出一些点来，保留这些点之间原来的边，得到的图。f[0/1/2]表示i的子树里选了0/1/>=2棵的方案数，背包考虑子树即可，特别地，当i是非关键点的时候，i不能当叶子，这一种情况需要减掉。2. dp[i][1]表示i取，i取的话，子树可取可不取。1. 如果i是关键点，dp[i][1]是i为根的贡献。dp[i][2]表示以i为根，i不取/i取的方案数。因为，对于非叶子结点，除了lca是必经的点以外，对于一棵树，所有叶子结点，都是关键点，枚举每种颜色，对每种颜色求虚树，
2024-02-11 14:17:50
380
原创 AtCoder Beginner Contest 258 Ex. Odd Steps（带限制的矩阵快速幂）
给定前缀和值s和长为n(n<=1e5)的序列A，第i个数ai（1<=a1<=a2<=...<=an<=s<=1e18)2. 给出矩阵快速幂转移式，并且有初始向量f[0]=1，s[-1]=0，s[-2]=0（边界条件）3. 有前缀和不能为ai的限制，所以在n次矩阵快速幂转移时，手动给当前f[i]的值置为0。求满足以下条件的序列X的数量，答案对998244353取模。3. 记X序列的前缀和序列为Y，Y中不包含给定序列a中的值。2. X序列中的数的和为s（s<=1e18）1. X序列中的每个元素都是正奇数。
2024-02-04 02:44:59
486
原创 AtCoder Beginner Contest 338 G. evall(枚举+递推 统计贡献)
比如1+23*45*56+7，mul[4]表示45*56的值，而mul[3]表示23*45*56的值。还需要处理一个形如2345*(3+34+345+3456)的东西，并加上2+23+234。sum[i]形如(3+34+345+3456)+(2+23+234+2345)，sum2[i]形如2+23+234+2345*(3+34+345+3456)，由4+45+456需要得到3+34+345+3456时，加上3333即可，不妨称3+34+345+3456这样的段，叫3456这个数的前缀贡献。
2024-02-04 02:10:03
420
原创 Codeforces Round 905 (Div. 1) C. Minimum Array（在线+贪心map / 离线+扫描线思想+区间删除）
q(q<=5e5)次操作，每次选择一个区间[l,r]，对这个区间加x(-1e9<=x<=1e9)如果若干次操作后，差分的第一个位置是一个单点减，说明是可以替换成更优的答案。去判断第一个差分非0的最左项是正还是负的，是负的说明可以保留，更新答案。每个修改是有时间后效性的，也就是第i时刻的修改，会改[i,q]时间的值。求序列操作前及第[1,q]次操作后，这q+1次对应的序列中，n个位置，q个时刻，扫描线，增序扫n个位置，l加，r+1减。在某个时间区间对应+x，另一个时间区间对应-y，...，
2024-01-22 03:54:01
468
原创 Educational Codeforces Round 156 (Rated for Div. 2) D. Monocarp and the Set（组合数学 插空法）
m(m<=3e5)次修改，每次选一个位置x(1<=x<=n-1)，将这个位置原来的字母改成?[1,i]总共有i+1个空，其中最大值、最小值各对应一个空，方案唯一空，而?从第二个字母开始，比如到第i个字母，需要决定第i+1个值的大小关系时，，表示a[i+1]既不是[1,i+1]最大值也不是最小值。询问时，先判断第一个字母是不是最大最小值的一个，不是输出0，①为<，表示a[i+1]是[1,i+1]的最大值。②为<，表示a[i+1]是[1,i+1]的最小值。第i(1<=i<=n-1)个字母，
2024-01-22 02:30:45
335
原创 AtCoder Regular Contest 170 C. Prefix Mex Sequence（dp mex性质）
没出现的m+1-j种中，恰有一种不能选（会导致s[i]=1），其余都可以选，(m-j)*dp[i][j]->dp[i+1][j+1]如果不新选，之前有j种，本次挑一种，有j种方案，j*dp[i][j]->dp[i+1][j+1]如果s[i]=1，则有A[i]=mex(A[1],A[2],...,A[i-1])如果s[i]=0，则有A[i]≠mex(A[1],A[2],...,A[i-1])每种方案对应的选法都是唯一的，dp[i][j]->dp[i+1][j+1]其中，mex为未出现在集合内的最小正整数。
2024-01-22 02:18:47
392
原创 AtCoder Beginner Contest 337 G. Tree Inversion（dfs序+树状数组+树上差分 补写法）
定义f(u)为满足v
2024-01-22 01:47:04
477
原创 Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337）F. Usual Color Ball Problems（思维题 双指针）
长为n(n<=2e5)的球序列，第i个球颜色ci，有m(m<=n)个空盒子，编号1-m。首先执行r次，意味着，循环询问，对于每个开头的长为n的序列都询问一次，所以序列扩成二倍。记颜色w的球在盒子里的球为now[w]个，则占了now[w]/k（向上取整）个盒子。位置在p位置之后，但因为和p位置之前放入盒子里的球同色，而能被继续放入的球，一旦确定了不在盒子内的球的位置p，前面在盒子里的同色的球的个数也能确定，然后考虑双指针，双指针维护第一个不在盒子内的球的位置，注意到它是单增的。
2024-01-22 01:31:00
549
原创 Codeforces Round 804 (Div. 2) D. Almost Triple Deletions（dp 终态局面）
所以，dp[i]表示考虑[1,i]，i这种字母必留，考虑和ai相同的上一个必留的字母j在哪。想留a这种字母时，有可能中间的aa是要被牺牲掉的，bbbbbaaccccc整段删除。想了一个枚举哪种字母最多，然后贪心删剩下的，兑掉其他字母，再往想留的字母上面兑，能转移当且仅当[j+1,i)这段区间能被删干净，注意判断j+1==i的情况。但是假了，比如，aaaaaaaaabbbbbaaccccca，为了统一写法，可以令任意字母也能转移到dp[n+1]上，转移到dp[n+1]的时候长度加了1，减掉即可。
2024-01-22 00:44:43
436
原创 NEC Programming Contest 2022 (AtCoder Beginner Contest 267) Ex. Odd Sum（NTT）
可以用0*1+1*0求得奇数次的方案，用(0+1)*(0+1)求得总的方案，求从n个数中选出奇数个数，使得选出的这些数的和为m(m<=1e6)的方案数。给定长为n(n<=1e5)的序列a，第i个数ai(1<=ai<=10)其实感觉有点子集反演，钦定popcount的位数的意思。这样每合并两个数需要卷积四次，合并10个数需要36次，每种数拆成两个多项式，分别对应奇/偶的情况，注意到ai很小，只有不超过10，答案对998244353取模。计0为偶数个，1为奇数个，a和b两种数合并的时候，少跑了100ms左右。
2024-01-21 20:58:57
363
原创 AtCoder Beginner Contest 214 G. Three Permutations（组合数学 容斥 背包 二项式反演）
剩下n-i个随便选（可能冲突），乘以n-i的阶乘，转化成至少冲突i次的方案数。1. 如果选了（1，n），对应长为n-2的链上选k-1对匹配的方案，在新环上：则认为是在长度为2*n的环上，选择一对相邻的点两两匹配，剩下的随便选，转化成至少冲突k次的方案数，利用二项式反演解决。2. 如果没选（1，n），对应长为n的链选k对匹配的方案，暴力合并背包，得到恰好选了i个冲突的点的方案数，由于原来长为n的环变为新的长为2n的环，考虑容斥，算恰好冲突的k次的方案数，对于环来说，一个长为n的环，
2024-01-21 20:19:21
368
原创 Codeforces Round #733 (Div. 1 + Div. 2) F. Omkar and Akmar(组合数学+博弈思维题)
1. 如果第一个点是空，那么第n个点是球，长为n-2的链上选k-1对匹配的方案，k个空位对应n-k个字母，终态局面定下来之后，乘上俩人填n-k个字母的顺序，Alice和Bob在一个圆格上玩游戏，格子共有1，...，n个，格子i(i<n)与i+1相邻，n与1相邻，每个格子初始都是空的，特别地，填的时候，相邻的格子不能有相同的字母，否则无法填。所以，不妨认为是n个点的环上，选k对「左球右空」的方案。2. 如果第一个点不是空，长为n的链选k对匹配的方案，Alice先手，每次可以选一个空的格子，填A或者B，
2024-01-21 19:56:19
396
原创 AtCoder Beginner Contest 221 H. Count Multiset（容斥 dp 拆分数 差分 数形结合）
只需全局减1，即可删掉m+1个1，并且使得第m+2个数的值>=1，也就对应了f[i-(m+1)][j-i]②要么令所有数都+1，使得所有数都大于等于2，转移到2 2 3，f[i][j]从f[i][j-i]转移。①每次要么新增一个1，转移到1 1 1 2，f[i][j]从f[i-1][j-1]转移。原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，令B[1]=A[1]，B[i]=A[i]-A[i-1]，
2024-01-21 17:19:16
1038
原创 Codeforces Round 803 (Div. 2) E. PermutationForces II（思维题 位置序列）
类似地，posb[6]和posb[7]都可以用到[1,7]里的可用位置，分别对应ans*=2和ans*=1。posb[3]可以用到[1,7]里的可用位置，即[1 4 2 6 7 3 5]里的[4 7 3 5]，posb[1]只能用到[1,5]里的可用位置，即[1 4 2 6 7]里的[4 7]，ans*=2。所以，合法的条件是，对于b[i]不为-1的位置，要求a[i]的值不能超过b[i]+s。比如，在为posb[1]=-1这个未确定的位置赋值的时候，posb[1]的值，
2024-01-20 18:41:33
820
原创 AtCoder Regular Contest 115 E. LEQ and NEQ（容斥 单调栈优化dp）
假设最后一段x个数，说明冲突了x-1次，容斥系数是(-1)的x-1次方，加上对应的贡献即可。前0个数分成偶数段方案数为1，分成奇数段方案数为0，对应dp[0][0]=1。2. 注意到，第二维对容斥系数的贡献，只有第二维的奇偶性，所以可以改写为。构造一个序列b，要求bi∈[1,ai]，且b[i]不等于b[i+1]其中，dp[i]表示以i结尾的方案数，枚举最后一段合并了几个数，那么，ai对前面的位置的数，也就是k
2024-01-20 17:59:33
358
原创 Codeforces Round 767 (Div. 1) D2. Game on Sum (Hard Version)（博弈 期望 dp 贡献）
有dp[i][j]=(dp[i-1][j]-k+dp[i-1][j-1]+k)/2=(dp[i-1][j]+dp[i-1][j-1])/2。第一步(i,i)只能向下，因为(i,i)和(i-1,i-1)之间不再满足dp关系式，是O(1)求的dp[i][i]=i。所以alice会这样选择k，使得两部分相等，有dp[i-1][j]-k=dp[i-1][j-1]+k，有dp[i][j]=min(dp[i-1][j]-k,dp[i-1][j-1]+k)终态dp[i][i]=i，即必须加i轮时，每轮都加1即可。
2024-01-19 03:41:52
442
原创 AtCoder Beginner Contest 335 (Sponsored by Mynavi) G. Discrete Logarithm Problems（群论的阶 拉格朗日定理）
n(n
2024-01-16 01:51:12
688
原创 Codeforces Round 114 (Div. 1) C. Wizards and Numbers（思维题 辗转相除+博弈 巴什博弈）
打表可知，当(b/a)%(a+1)为偶数时，先手必胜，(b/a)%(a+1)为奇数时，先手必败。这样若干轮后，(b/a）起到了对（a+1）取模的效果，即当前剩余石子数不超过a，t(t<=1e4)组询问，每次询问(a,b)（0<=a,b<=1e18），(b/a)%(a+1)为奇数总可以转移到(b/a)%(a+1)为偶数，(b/a)%(a+1)为偶数总可以转移到(b/a)%(a+1)为奇数，先手和后手可以取1（1个a）枚，a枚（a个a），a^2，...当(b/a)%(a+1)为偶数时，先手可以先取1个。
2024-01-16 01:11:29
411
原创 AtCoder Beginner Contest 336 G. 16 Integers（图计数 欧拉路径转欧拉回路 矩阵树定理 best定理）
对于一张无向图G，记D为其度数矩阵，满足：1. D[i][i]=i的度数记A为其邻接矩阵，满足：1. A[i][j]=i与j之间边的条数，如果有重边则算作多条边。记基尔霍夫矩阵（拉普拉斯矩阵）K=D−A，则去掉第k行第k列得到的矩阵行列式即为G生成树的个数。
2024-01-16 00:03:41
1094
原创 CCPC 2023 北京市赛 G.【模板】线段树（线段树区间合并20次多项式）
(ai+x)(ai+x)(ai+x)注意到当x有超过20项时，20个2相乘，对2的20次方取模就为0。所以，维护0次项到19次项乘积的和，向上合并时，是两个多项式卷积，这里暴力相乘即可。复杂度O(nlogn*20*20)，比较卡常。下推标记，当下放一个区间加x的标记时，洛谷高仿题目P4247。，其中，i<j<20。
2024-01-15 23:22:34
468
原创 Codeforces Round 768 (Div. 1) D. Flipping Range（思维题 等价类性质 dp）
而dp做法，则是注意到性质一后dp即可，dp[i][j]表示i的等价类的数总共被翻了奇/偶次。此外，可以一开始翻一次[1,g]，改变每个等价类内负数个数的奇偶性，所以两种情况都考虑。枚举当前数翻还是不翻，翻的话加1次翻，算-a[i]，否则加0次翻，算a[i]，等价类内翻两个相邻的，可以类似地叠加成两个不相邻的，推广为(i,i+x*g)性质二：此外，翻1-g和翻2-g+1可以起到翻(1,g+1)效果。考虑g个等价类，每个等价类i,i+g,i+2*g,...对每个等价类内dp值求和，取翻奇/偶次二者的max。
2024-01-15 03:09:56
476
原创 Codeforces Round 779 (Div. 2) D2. 388535（思维题 二进制性质/trie树上最大最小异或）
若存在一个bi，min(bi^trie)=l，max(bi^trie)=r，则bi即为x所求。如果l是偶数，r是奇数，那么x的末尾是0或1均可，因为总可以将ai和ai^1两两配对。遍历这r-l+1个数，找到无法配对的那一个ai，ans^ai=x成立，输出x即可。l%2==0时，r无法配对，否则l无法配对，记原来无法配对的数为ans。r-l+1个数中，肯定有一个ai是l^x得到的，那么令每个数再异或l，注意到，若a^b=1，则(a^x)^(b^x)=1恒成立。即令bi=ai^l，必有一个bi是等于x的，
2024-01-15 02:37:37
541
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人