- 博客(100)
- 收藏
- 关注
RSS订阅
原创 System.out.println("Hello World!");
1、HeRaNO是什么？ HeRaNO，一种化学物质，常温下为肉色无味固体，可溶于水，熔点沸点不详，该种物质结晶质硬且脆。有时有毒，但大多时候并没有毒性。导电性未测，导热性较差，有时可积累温度使其因与氧气反应而钝化，所以自带透明属性。常温下化学性质稳定，不与哲（内啥）学或妹纸等奇奇怪怪的物质反应，常温下与少量稀考试作用，反应平稳进行并生成可以交（内啥）流的答案气体，但与浓考试作用，可迅速被氧化生...
2016-04-26 18:33:05
2375
原创 [杂言] 祭奠与真正的告别
可能大家看到了，我的博客里面的链接都被改到 GitHub 上了，有些公式也修了，但是排版还是老样子。今年才注意到我曾经用的 coding.net 已经彻底改变了它的架构，导致各种神仙兼容问题，虽然这种升级可能是必要的，但是真的很影响用户体验，我的老代码库和图床都收到了比较严重的影响，折腾了很长时间图床才让它能用，今天也进行了一次大规模迁移，老代码库删掉了，它的使命也结束了。CSDN 也是多年不...
2020-05-04 02:43:21
408
原创 [NOIP] [LCA] [贪心] NOIP2012Day2 疫情控制(blockade)
//这题真心BT，阅读时请做好心理准备 题目描述 Description H国有n个城市，这n个城市用n-1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。 H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检
2019-12-08 16:55:02
1706
原创 [分块打表] [Luogu P1822] 魔法指纹
题目传送门 （反正老年选手写题解也没人看随便水2333333） 一向毒瘤的 dayu 模拟赛这回搞到了这道题…… 看起来很像数位 DP 不是吗？ 可是不会转移啊QAQ……想了半天决定分块打表！ 分块打表这个黑科技是从Po姐那里学来的……（其实只不过是知乎上的一个回答…… 于是借鉴这个思路，分块打表……处理出 [x×106,(x+1)×106][x\times 10^6,(x+1)\tim
2017-10-28 21:08:02
763
原创 [DP] [二进制分组] 逃亡的准备
题目传送门 如果是普通多重背包的话时间复杂度是O(V∑m)O(V\sum m)的，过不去…… 于是考虑二进制分组，即将mim_i写成∑2i+k\sum 2^i+k的形式，这样由于任意正整数可以写成一系列二进制的和，所以正确性可以保证。 这样，每一组的物品数由mim_i降至了log2mi\log_2 m_i，这样再做01背包，复杂度是O(V∑log2mi)O(V\sum \log_2m_i)，这
2017-10-19 22:55:50
646
原创 [启发式合并] [模拟] [BZOJ5040] 未来研究
题目传送门 又是水UOJ群看到的题（我怎么这么能水群……），卡了三天终于A了…… 这道题是[BZOJ4221]历史研究的加强版，回滚莫队或者分块是过不了的，会T得很惨…… 爱JOI人士表示强烈谴责 分析题目发现加入了条件： 询问保证不会存在Ai<Aj<Bi≤BjA_i<A_j<B_i\le B_j的情况，且对于任意的ii,jj不会有Bi=Aj,Ai=AjB_i=A_j,A_i=A_j。
2017-10-04 18:40:43
761
原创 [虚树] [LCA] [Treap] [CH Round #56] 异象石
题目传送门 这题是和某JMS一中联考的题……也不知道NOIP模拟赛为什么会有平衡树和虚树的知识估计是卡AK的，据说SDOI2015的寻宝游戏是一道题…… 虚树可以处理一类树上问题，每次操作为树上的点打标记，询问打上标记的一类点的性质。这种性质与未打标记的点无关或可以消除这种影响。 很自然想到把这些点单独拎出来建一棵新树，在新树处理所有询问，可是单独拎出来点破坏了原有的父子信息，所以我们把LCA
2017-09-23 01:41:30
644
原创 [三分] [BZOJ5041] LWD 的降临
题目传送门 UPD2：这道题题解已经半残，请结合这里的研究食用。 2017.9.15 水 UOJ 裙的时候 onepointo 童鞋说这道题没人水……于是看了看…… 其实就是求一个椭圆与给定圆外切的切点坐标，这个椭圆不是标准椭圆（即主轴为 xx 轴）。 如果我们暴力列方程的话有如下几个方程： 切点在圆上； 切点在椭圆上； 该点处圆的切线与椭圆的切线相同。 按理说是可求的，可是切点未
2017-09-16 16:12:06
653
原创 [DP] [组合数学] [BZOJ4807] 車
题目传送门 蛤蛤蛤蛤……高三真是狗…… （别问我开学第一周怎么度过的我不想说……） 看到题目首先想到一个DP，dp[i][j]dp[i][j]表示放在第ii行第jj列的可行方案数，于是就有如下转移辣： dp[i][j]=∑k=j+1mdp[i−1][k]i∈[2,n],j∈[1,m]\begin{equation}dp[i][j]=\sum\limits_{k=j+1}^{m}dp
2017-08-19 02:36:53
519
原创 [平衡树] 平衡树学习笔记
好久不见！ 就差这个坑就补齐了！ 估计高三也不会太更博客了，不知道是不是NOIP前的最后一篇？ 在博客园的新博客欢迎关注！ 发现自己平衡树学了跟没学一样，退役了简单学了一发…… 平衡树有很多，比如AVL树，红黑树（RBTree）什么的，AVL被魔改成SBT？RBTree是系统中的平衡树。但是不常用不介绍了。 平衡树的本质是一棵二叉搜索树（Binary Search Tree，即BST），
2017-07-27 01:01:13
1039
1
原创 [树形DP] 猴腮雷 （没有上司的舞会）
题目描述 Description 新年就要来临啦，小猴腮雷一家NN人将作为嘉宾被邀请到了春晚上。然而小猴腮雷的一家都曾经是大名鼎鼎的熊孩子，无论在什么时候都会，也只会和自己的直系亲属，也就是父母吵架，当然，即便是在春晚这个舞台上也是这样。为了到时候不会引起战争，组委会据此思考到底要邀请哪些人？更让组委会头疼是，每个猴腮雷拥有一个活泼值AiA_i，组委会既想要他们不会发生矛盾，也想尽量让来参加的猴
2017-07-08 01:01:19
522
原创 [DP] [2D2D优化] [二维树状数组] [SCOI2014] 方伯伯的玉米田
题目传送门 这是WC2015教师测试的第三题，原题稍有改动…… 先看这道题，貌似不会做…… 考虑如果选择区间[l,r][l,r]进行拔高操作，对[r+1,n][r+1,n]的操作可能是需要的且不能是不合法的。 于是考虑DP，记dpi,jdp_{i,j}为前ii株玉米进行jj次操作所留下的最多玉米数。可以写出如下转移： dpi,j=max{dpx,y}+1(x<i,y≤j,ax+y≤
2017-07-08 00:30:06
484
原创 [线段树] [Hash] [BZOJ2124] 等差子数列
题目传送门 好久之前做过WC2015教师测试（大概是今年年初），CCF也是醉了搬了三道题考老师…… 第一题是没有上司的舞会，题面被改成了猴腮雷……啊一遍树形DP就行了很休闲的就写了题解…… 这是第二题，（就是从BZ的非权限题里扒了一道吗……） 暴力三元组是n3n^3的过不去…… 考虑对每个位置加入对应数据的过程，记一个序列ana_n，初始均为00。如果我们加入ii，就把aia_i变成11（
2017-07-08 00:04:33
716
原创 [树的点分治] [HDU4812] D Tree
题目传送门 （这次英语题应该比较好懂吧……） 大意是 给定一棵有nn个点的树，每个点有权值viv_i，求是否存在一条路径使得路径上所有点的权值的乘积mod106+3\bmod 10^6+3为kk，输出路径首尾编号，若有多解输出字典序最小的解。貌似很像不虚就是要AK？ 现在求路径上点权的乘积，继续点分治，怎么合并答案？ 我们已经统计出一棵子树到重心的权值积了，因为这些乘积mm对MOD\t
2017-07-01 00:49:20
490
原创 [树的点分治] 不虚就是要AK
hzwer%%%，czy%%% 题目描述 Description czy很火。因为又有人说他虚了。为了证明他不虚，他决定要在这次比赛AK。现在他正在和别人玩一个游戏：在一棵树上随机取两个点，如果这两个点的距离是44的倍数，那么算czy赢，否则对方赢。现在czy想知道他能获胜的概率。 输入 Input 本题多组数据。对于每组数据： 第一行一个数nn，表示树上的节点个数。
2017-07-01 00:28:22
696
原创 [树的点分治] [BZOJ3648] 寝室管理
题目描述 Description T64有一个好朋友，叫T128。T128是寄宿生，并且最近被老师叫过去当宿管了。宿管可不是一件很好做的工作，碰巧T128有一个工作上的问题想请T64帮忙解决。 T128的寝室条件不是很好，所以没有很多钱来装修。礼间寝室仅由n−1n-1条双向道路连接，而且任意两间寝室之间都可以互达。最近，T128被要求对一条路径上的所有寝室进行管理，这条路径不会重复经过某个
2017-06-26 19:26:20
528
原创 [省选] [线段树] [BZOJ1858] [SCOI2010] 序列操作
题目传送门 写这道题写了两天我是不是要退役了…… 考数学竞赛前想着我是接着码题还是去学高考，考完之后想着是去学高考还是回家种地…… 在Ferric的BZ.rand()上随机了一题，就随到了这道题……居然认为这道题很无脑？
2017-06-18 19:36:22
503
原创 [树的点分治] [树形DP] [BZOJ2599] [IOI2011] Race
题目传送门 这题相对POJ2114改了个询问……询问的是等于kk的最少边数…… 考虑树形dp……dpidp_i表示权值为ii的路径所用最少边数。 点分治照常，找到重心分成若干子树，可以统计子树内的点到根的距离和权值。就可以dp了！ dpi=min{dpi−disx+depx}\begin{equation}dp_i=\min\{dp_{i-dis_x}+dep_x\}\end{equat
2017-06-10 22:36:00
424
原创 [树的点分治] [POJ1741/POJ1987] Tree/Distance Statistics
传送门：POJ1741、POJ1987 题目大意是询问树上两点间距离小于等于kk的点对个数。 很容易想到O(n2log2n)O(n^2\log_2n)暴力，即枚举所有路径，然后LCA统计长度。过不去！ 考虑一种对于树的分治，找到树的重心，可以将树分成一些子树，那么需要统计的路径就有三种情况（其实是两种）： 1、完全在一个子树中； 2、两端在不同子树中，易知这条路径一定过重心； 3、（2的
2017-06-10 21:49:36
539
原创 [XJB出题] [分块] 篮球架
题目传送门（感谢Vijos的域功能……） 维护点啥？区间加，查询这两个貌似是线段树，可是区间变换φ\varphi …… 考虑分块！维护块内元素和。 对于查询操作，查询整块和，零散部分暴力，最差为O(T1n√)O(T_1\sqrt n) 对于区间加， 设加α\alpha ， 则整块加nαn\alpha，标记，零散部分暴力， 最差为O(T2n√)O(T_2\sqrt n)； 对于变换φ\var
2017-06-03 21:43:05
399
原创 [树形DP] [FWT] [HDU5909] Tree Cutting
题目传送门 给出了一棵树，每个点有一个点权，求这棵树的所有连通子集的权值异或起来为i(i∈[0,m))i(i\in [0,m))的情况有多少种。 我们考虑一种树形DP，记dpi,j\text{dp}_{i,j}表示以ii为根的树，其子树异或和为jj的总数。 那么加入子树xx后，一个新状态dpni,j\text{dp}_{ni,j}就可以统计为： dpni,j=dpi,j+∑p⊕q=jdpi,
2017-06-03 16:41:04
585
原创 [FFT] [矩阵快速幂] [HDU4914] Linear recursive sequence
题目传送门 翻译： 题目描述 Description 一个众所周知的线性递推数列f(n)f(n)被定义如下： 对于k≤0k\le 0,f(k)=1f(k)=1 对于k≥1k\ge 1,f(k)=af(k−p)+bf(k−q)f(k)=af(k-p)+bf(k-q) 给出n,a,b,p,qn,a,b,p,q，求出f(n)f(n)对119119取模后的值。输入 Input
2017-06-03 02:16:32
587
原创 [FFT] [矩阵快速幂] [POJ3150] Cellular Automaton
题目传送门 （POJ原地址，如果上不去请看这里） 还是翻译： 题目描述 Description 细胞自动机是处在一个特定形状网格上的一组细胞，这些细胞按照一组基于相邻细胞的状态描述新状态的规则通过一系列离散的时间进化。细胞自动机的顺序是它包含的细胞数量。一个顺序为nn的细胞自动机中的细胞编号为11~nn。 细胞的顺序是它可能包含的不同价值数。通常情况下，顺序为mm的细胞的价值为00~
2017-06-03 02:06:38
770
原创 [树] [HDU5830] Rikka with Subset II
题目传送门 还是翻译： 题目描述 我们都知道，Rikka酱数学不好，勇太君担心这个情况，所以他给了六花同学一些数学题来练习，下面是其中的一道： 勇太桑有一棵有nn个节点的树，树上的所有边长度都是11，对于这些点的一个非空子集SS，SS的价值value(S)\text{value}(S)等于max(dis(u,v))\max(\text{dis}(u,v))，其中u,v∈Su,v\in
2017-05-30 17:18:10
827
原创 [BFS] [Luogu P1299] 切孔机
题目传送门 好像是矩形覆盖？woc不会啊！！！ 我们发现范围很小，于是本着暴力能AC的想法就写发暴搜试试…… 嗯搜地图都是BFS，于是奇奇怪怪的BFS就出来了…… 将整个图片像素化，变为黑色，把线画上的像素标记。然后从一个不在这些线围成的区域内部的点开始BFS，把外围的像素表记为白色。那么我们就需要统计的是黑色的块数，再一波BFS找并标记连通块即可。 但是这样会WA得很惨，原因是一些奇奇怪
2017-05-29 23:54:43
505
原创 [DP] [1D1D优化] [FFT] [CDQ分治] [HDU5730] Shell Necklace
题目传送门 接着翻译：（这次翻译可能不太好……） 题目描述 Description 也许大海对贝壳的定义是珍珠。然而在我看来，一串带有nn个美丽的贝壳的贝壳项链包含着我对我最爱的Arrietty最真挚的感情。 假设这串贝壳项链是一个贝壳序列（不是一个环？）。考虑项链中连续ii个贝壳，我知道存在不同的方案去装饰这ii个贝壳作为一个爱的宣言（什么鬼？？？）。 我想用几个爱的宣言装饰所
2017-05-29 23:36:02
687
原创 [NTT] [HDU5829] Rikka with Subset
题目传送门 接着翻译： 题目描述 Description 我们都知道，六花同学数学不好，勇太君担心这个状况，所以他给了六花酱一些数学问题作为练习，这里有其中的一道题： 勇太君有nn个数字A[1]A[1]~A[n]A[n]，还有一个数字KK。对于任意一个AA的非空子集SS，SS的价值等于SS集合中最大的min(|S|,K)\min(|S|,K)个数之和（译者注：|S||S|表示集合S的大
2017-05-29 23:15:46
831
原创 [FFT] [HDU4609] 3-idiots
题目传送门 下面还是我的翻译 题目描述 Description OMeGa国王抓住了三个在街上裸奔的人。虽然他们被看做是智障，这三个人坚持说只是一种行为艺术，然后乞求国王放了他们。出于对真正智障的仇恨，国王想测试一下他们是不是说谎了。这三个人被送到了国王的森林中，并且每个人都被要求依次捡一根树枝。如果他们带来的三根树枝能构成一个三角形，他们的数学能力就会解救他们。否则，他们就会蹲监狱……
2017-05-29 22:41:24
662
原创 [FFT] [HDU5307] He is Flying
题目传送门。 假如大家烦E文，下面是我的翻译版…… （假如翻译也不想看请直接跳到题解部分……又XJB翻译） 题目描述 Description 劼劼劼想沿着一条漫长的路飙车，这条路有nn段，第ii段有一非负整数的长度sis_i。劼劼劼将选择一些连续部分在上面飙车（以一个不可思议的速度），所以共有n×(n−1)2\frac{n\times (n-1)}{2}种不同方法飙。如果劼劼劼从第ii段飙
2017-05-29 02:57:32
847
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人