2 DD(XYX)

尚未进行身份认证

我要认证

\(~ _ ~)/

等级
TA的排名 12w+

CF453C Little Pony and Summer Sun Celebration

CF453C Little Pony and Summer Sun Celebration题解这道题要求输出任意解,并且路径长度不超过4n就行,所以给了我们乱搞构造的机会。我这里给出一种构造思路:首先一个连通块如果没有要求奇数次的点,那么就可以不管他,如果超过一个连通块内有要求奇数次的点,那么无解。然后在那个唯一需要走的连通块里,我们随便抠一个生成树出来,从根遍历①首先把每次向下走以及回溯的路径记录到序列的新一位(并不需要一开始就把根节点加入,反正最后会回溯到根,于是最后一个

2020-07-26 20:50:16

CF914G Sum the Fibonacci (快速沃尔什变换FWT + 子集卷积)

题面题解这是一道FWT和子集卷积的应用题。我们先设 cnt[x] 表示 Si= x的 i的数量,那么这里的Nab[x]指满足条件的 Sa|Sb=x、Sa&Sb=0的(a,b)二元组数量,这个可以通过子集卷积快速求出,复杂度为然后又设那么就把答案简化为了我们可以再次简化,设...

2020-06-11 21:16:29

CF662C Binary Table (快速沃尔什变换FWT)

题面题解我们会发现,如果单独的一列或一行,它的答案是O1确定的,如果确定了每一行是否变换,那么最后的答案也就简单了许多,如果确定了行的变换状压下来是x(即x的i位表示第i行是否变换,理解就行),那么每列的状态就要异或x,这没问题吧接着,其实它的行列是可以交换顺序的,对答案没有影响,状态一定的列的最终贡献都一样,所以就把状态为 i 的列的数量记为 c[i],方便计算,然后,提前预处理出列的状态为 i 时单独考虑的答案 f[i](即反转或不反转的最小1数量),方便计算若枚举行的变

2020-06-10 21:12:35

FWT快速沃尔什变换——基于朴素数学原理的卷积算法

这是我的第一篇学习笔记,如有差错,请海涵...目录引子卷积形式算法流程OR卷积AND卷积XOR卷积模板引子首先,考虑现在有一只兔子数一数,会发现你有一只兔子,现在,我再给你一只兔子再数一数,会发现什么?没错,你有两只兔子,也就是说,1+1=2!这就是算数的基本原理了,聪明的你懂了吗?好,我们可以学FWT了..卷积形式我们回忆一下多项式乘法的式子:这个可以用FFT或NTT优化到O(nlogn)求出每一个Ci,但不是本章的重点,只是

2020-06-10 20:34:59

Jamie and Tree (dfs序 + 最近公共祖先LCA)

题面题解我们求它子树的权值和,一般用dfs序把树拍到线段树上做。当它换根时,我们就直接把root赋值就行了,树的结构不去动它。对于第二个操作,我们得到的链和根的相对位置有三种情况:设两点为A、B,LCA 为 C,一个点x的dfs序为ld[x],从它的子树里出来时的dfs序为rd[x]第一种情况,根是C的祖先,他的实际操作区间就是原本的子树区间[ld[C],rd[C]]第二种情况,根在A、B路径上,那么它的实际LCA就应该是root,操作区间为[1,n]第三种情

2020-06-06 08:12:21

Centroids (换根DP)

题面题解删一条边、加一条边,相当于把一个子树折下来,然后嫁接在一个点上,那么最优的情况肯定是接在根上,对吧,很好理解吧那么这个拆下来的子树大小就不能超过n/2。我们用son[]来表示每个点为根的子树大小,如果一个点x可以改造后变成重心,那么要么它本来就是重心,要么它最多只有一个儿子y的son[y]大于n/2,并且y的子树大小可以通过改造变得<=n/2。要改造一个儿子的子树,最优的方法就是减去里面最大的小于等于n/2的子子树,我们用dp1[]来表示一个点的子树里这样一个子

2020-06-05 12:13:42

[JOI 2017 Final] 足球 (建图,最短路)

题面题解我们可以总结出球的两种状态,要么自己飞,要么在球员脚下被带飞。自己飞的情况下,他只能单向直线运动,每一步代价为A,被带飞可以乱走,每一步代价为C。从自己飞到被带飞需要一个距离自己最近的球员过来,代价为 ,对于每个格点,这个代价都是确定的,因为球不可能两次到同一个球员脚下,所以球员就相当于一次性的工具人,输入后bfs处理 就可以了。从被带飞到自己飞需要踢一脚,给它自由,代价为B。那么我们可以把每个格点拆成5个点,然后建个图。自己飞要四个点,分别表示四个方向,每个点朝那

2020-05-30 16:38:55

HDU 6222 Heron and His Triangle (pell 方程)

题面(本人翻译)A triangle is a Heron’s triangle if it satisfies that the side lengths of it are consecutive integers t - 1, t, t + 1 and thatits area is an integer. Now, for given n you need to find a Heron’s triangle associated with the smallest t biggerthan

2020-05-23 15:27:09

LOJ2312 LUOGU-P3733「HAOI2017」八纵八横 (异或线性基、生成树、线段树分治)

八纵八横题目描述Anihc国有n个城市,这n个城市从1~n编号,1号城市为首都。城市间初始时有m条高速公路,每条高速公路都有一个非负整数的经济影响因子,每条高速公路的两端都是城市(可能两端是同一个城市),保证任意两个城市都可以通过高速公路互达。国正在筹划“八纵八横”的高铁建设计划,计划要修建一些高速铁路,每条高速铁路两端也都是城市(可能两端是同一个城市),也都有一个非负整数的经济影响因子。国家还计划在“八纵八横”计划建成之后,将“一带一路”扩展为“一带_路一环”,增加“内陆城市经济环”即选择一条

2020-05-18 22:16:56

[HDU1812] Count the Tetris - polya定理

题面Problem Description话说就是因为这个游戏,Lele已经变成一个名人,每当他一出现在公共场合,就有无数人找他签名,挑战。为了防止引起社会的骚动,Lele决定还是乖乖呆在家里。在家很无聊,Lele可不想像其他人一样每天没事在家数钱玩,于是他就开始数棋盘。他想知道,一个有N×N个格子的正方形棋盘,每个格子可以用C种不同颜色来染色,一共可以得到多少种不同的棋盘。如果一个棋...

2020-04-20 15:45:06

CF915G Coprime Arrays (莫比乌斯反演)

CF915G Coprime Arrays题解(看了好半天终于看懂了)我们先对于每一个i想,那么我们设我们用莫比乌斯反演有了这个式子,可比可以求出△ans呢?我们注意到,由于那个(i/d)是下取整了的,所以i++后(下文的 i 是+1后的 i),只有当(d+1)|i 时答案有变化,于是我们可以预处理a^n,以及用埃氏筛预处理△ans[i...

2020-03-31 08:59:02

[Noi2010]能量采集 (莫比乌斯反演)

[Noi2010]能量采集Description栋栋有一块长方形的地,他在地上种了一种能量植物,这种植物可以采集太阳光的能量。在这些植物采集能量后,栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。 栋栋的植物种得非常整齐,一共有n列,每列有m棵,植物的横竖间距都一样,因此对于每一棵植物,栋栋可以用一个坐标(x, y)来表示,其中x的范围是1至n,表示是在第x列,y的...

2020-03-30 09:45:21

Crash的数字表格 (莫比乌斯反演)

Crash的数字表格Description今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple)。对于两个正整数a和b,LCM(a, b)表示能同时被a和b整除的最小正整数。例如,LCM(6, 8) = 24。回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张N*M的表格。每个格子里写了一个数字,其中第i行第j列的那个格子里写着...

2020-03-29 09:58:59

CF1019B The hat (二分)

题面题解如果位置为i的人与对面的差是x,i+1位置由于只能+1或-1,所以i+1位置与对面的差就是x、x+2或x-2,可以发现,奇偶性不变。所以只要判断出是奇差,就可以直接输出“! -1”,如果是偶差,就一定有解。下面是个圆环,从1~n/2+1开始,顺时针转,记L=1,R=n/2+1。把两个点转半圈的函数记录下来:(谁是L谁是R已经不重要了)会发现两者一定...

2020-02-04 15:27:59

奇妙的数列(单调栈)

即:题解我们分析一下条件,bj <= bi <= bn 什么意思? 说明bj和bi都不超过bn,那么首先可以确定范围bi可以在bj~bn的范围内任意波动,设bm是bn左边第一个严格比它大的数,那么j只能在m+1~n内取值。然后可以用反证法证明bj就是m+1到n中的最小值。那么可以用一个单调递减单调栈来算每一个m,然后设第i个元素的“m”为Ai,不难发...

2020-01-19 20:03:15

[HNOI2010]弹飞绵羊 (平衡树,LCT动态树)

题面题解因为每个点都只能向后跳到一个唯一的点,但可能不止一个点能跳到后面的某个相同的点,所以我们把它抽象成一个森林。(思考:为什么是森林而不是树?)子节点可以跳到父节点,根节点再跳就跳飞了。由于我们发现有一些父子关系要变,所以不能用树链剖分等静态的数据结构,可以用LCT(Link-Cut-Tree联-切-树,即动态树,支持动态修改父子关系)。但是当我们询问答案的时候...

2020-01-10 17:24:27

[HDU3976]Electric resistance(电阻)(信竞&物竞)(高斯消元)

题面Problem DescriptionNow give you a circuit who has n nodes (marked from 1 to n) , please tell abcdxyzk the equivalent resistance of the circuit between node 1 and node n. You may assume that the ...

2020-01-02 20:02:08

HDU 5362 Just A String 指数型母函数

题面Description用m种字母构造一个长度为n的字符串,如果一个字符串的字母重组后可以形成一个回文串则该串合法,问随机构成的长为n的字符串的合法子串数目期望值.Input第一行一整数T表示用例组数,每组用例输入两个整数n,m(1≤n,m≤2000).Output问构成的字符串的合法子串数目期望值,结果乘m^n后模10^9+7.题解这是一道很好的练指数型母函数的...

2019-12-27 20:31:25

HDU2065 “红色病毒”问题 (指数型母函数经典板题)

题面医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。现在有一长度为N的字符串,满足一下条件:(1) 字符串仅由A,B,C,D四个字母组成;(2) A出现偶数次(也可以不出现);(3) C出现偶数次(也可以不出现);计算满足条件的字符串个数.当N=2时,所有...

2019-12-26 19:50:05

[BZOJ3625][CF438E]小朋友和二叉树 (多项式开根,求逆)

题面题解设多项式的第a项为权值和为a的二叉树个数,多项式的第a项表示是否为真,即则,所以F是三个多项式的卷积,其中包括自己:,1是F的常数项,即。我们发现这是一个一元二次方程,可以求出,因为g的常数项为零,所以1-4g的常数项为1,的常数项也为1,的常数项就为零,就跑不了逆元,所以舍掉。最终,跑一个多项式开根和一个多项式求逆就行。CODE大常数TLE...

2019-12-25 20:28:30

查看更多

勋章 我的勋章
  • 签到达人
    签到达人
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。