2 Fxkkks

尚未进行身份认证

been jinxed

等级
TA的排名 7w+

(分层图+DP)hihoCoder1147 时空阵

传送门第二次做这道题还是不记得怎么做。。考虑在分层图上跑dp。。dp[i][j][k]dp[i][j][k]dp[i][j][k]表示在前iii层有jjj个点,第iii层有kkk个转移方程:i<K:dp[i][j][k]=dp[i−1][j−k][x]×Cn−j+k−1k×(2x−1)k×2k(k−1)2i<K:dp[i][j][k]=dp[i-...

2019-08-13 07:45:41

CCPC-Wannafly 夏季欢乐赛 题解

博主又复活了(因为文化课作业太多写不完了所以继续自爆自弃A.完全k叉树签到题,考虑最底层的点的距离即可,注意细节(成功拉低了平均通过率)#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#defineMpmake_pair#defi...

2019-07-29 22:58:04

NOI膜你赛2019/7/9硬币(coin)

万年没写博客的博主又回来拉先放题面link考场上一读题目,这不是裸的生成函数吗??推式子…Gf(x)=∏k≥0,k∈Z11−xmkGf(x)=\prod_{k\geq0,k\in\Z}\frac{1}{1-x^{m^k}}Gf(x)=∏k≥0,k∈Z​1−xmk1​然后呢,就一脸懵圈了,如果按照一般的生成函数的某一项系数的求法,还不如打dp来的更优所以就开始打dp…m=2:1,2...

2019-07-09 21:11:09

[Violet]天使玩偶/SJY摆棋子——k-d tree & Scapegoat tree

BZOJ2648-SJY摆棋子题目大意一堆点,可以加点,询问离某个点曼哈顿距离最近的点的曼哈顿距离Solution离线做法:cdq分治,代码量蛮短的这里主要讲在线做法这是k-dtree的模板题,但是因为有加点操作,所以不能保证k-dtree的重量平衡,可能会使这棵BST的结构变得很难看,随便一卡就能卡掉所以我们要加上Scapegoattree来暴力维护它的相对平衡Code#...

2019-06-02 19:24:43

(wqs二分)CF739E Gosha is hunting

传送门这篇林克卡特树+简单的wqs二分/凸优化是来骗访问量的Solution这其实是个wqswqswqs二分套wqswqswqs二分O(nab)\mathcal{O(nab)}O(nab)的dpdpdp很好写我们要做的是用凸优化,把时间复杂度降到O(nlog⁡alog⁡b)\mathcal{O(n\loga\logb)}O(nlogalogb)显然这是一个凸函数,为什么呢?因为你...

2019-05-15 19:19:21

[学习笔记]dp凸优化/wqs二分&[八省联考2018]林克卡特树lct

废话很早就想学wqs二分,结果拖了好久。因为以前是看了几遍都没有懂。。(太菜了后来因为计划里凸优化的题(比如CF321ECielandGondolas,CF739EGoshaishunting…)太多了。。又不会高深的数据结构,所以只能硬着头皮学网上blog这么多,还是wqs神仙本人的论文最好懂。。网上应该会有,这边就不放资源了然后灵光一现就突然懂了先上题这道算是经典题了叭...

2019-05-14 19:10:24

上海华师大"游族杯"acm现场赛一日游

这篇算是[余姚之魂——雀魂的后续]叭(https://blog.csdn.net/jokingcoder/article/details/89502201)day3于是我们就坐大巴去了上海(一路颠簸)不知道为什么雀魂这么耗电。。所以后半程就开始看杂志。。他们居然还能玩起狼人杀。。到了华师大第一眼居然看不出这是在大学里面(我果然是孤陋寡闻后来是xjd学长和另外一个不知道叫什么的小哥哥...

2019-04-27 21:40:52

余姚之魂——雀魂(ZJOI2019Day2游记)

(这是个什么沙雕标题)day1为什么只有我的游记是从day1开始的。。。因为窝前一天还在补文化课。。。寝室铃响,6:08起床去食堂吃早饭,6:39上车,7:42准时到达余姚中学报告厅的空调吹得蒟蒻瑟瑟发抖上午的神仙zyz讲课(雾树上分治+杂题选讲难度比提高略微高一点点???虽然没有完全掉线,恐怕也是半离线了没错后来就去打雀魂了...

2019-04-25 14:45:22

[HNOI2016]树-缩点+倍增lca+主席树(码农)

传送门博主心态以崩,打到一半再打啥都不知道所以先挖坑,等心态恢复好了继续打专业挖坑不填100年#include<cstdio>usingnamespacestd;structTemplateTree{ inttot=0,lst[N],size[N],dfn[N],dep[N]; structEdge{ intto,nxt; }e[...

2019-04-22 20:55:27

CF731D.80-th Level Archeology(暴力)

为什么这么水一道题没人写呢qwq传承cy的水博客精神(雾传送门RuA!题意给你一堆字符串(其实是数组?)对每个字符(数)+x+x+x(超过ccc就从头开始)Solution要满足整体字典序非递减,那不就是前一个的字典序一定要小于等于当前的字典序咩?发现两个字符串的相对顺序不会变所以只要找到相邻两个第一个不同的位置(或者说某一个先没有了)这样我们就可以使前一个字母小于后一个字母所需要...

2019-04-21 19:38:05

c++模拟质点在万有引力下的运动轨迹

2019-04-19 16:21:46

JZOJ5813Count-质因数分解+dp

#include<cstdio>#include<algorithm>#include<cstring>#defineMOD998244353usingnamespacestd;typedeflonglongLL;LLdp[10000][220],all;intcc[110];inlineLLqui_pow(...

2019-04-18 21:22:34

ZJOI2014力-FFT快速傅里叶变换

Luogu-ZJOI2014力说在前面鸣谢hsy\mathcal{h{\color{red}sy}}hsy

2019-04-17 21:13:09

[ZJOI2012]波浪——dp+__float128卡精度

ZJOI2012波浪题意在1→N1\toN1→N的全排列PPP中L=∣P1–P2∣+∣P2–P3∣+…+∣PN−1–PN∣L=|P_1–P_2|+|P_2–P_3|+…+|P_{N-1}–P_N|L=∣P1​–P2​∣+∣P2​–P3​∣+…+∣PN−1​–PN​∣问L≥ML\geqML≥M的概率有多大,保留k位小数,k≤30k\leq30k≤30Solution(这个solut...

2019-04-12 19:19:52

[学习笔记]dsu on tree

dsuontreeBBdsuontree树上并查集?其实这东西跟并查集一点关系都没有吧(可能是我太年轻树上启发式合并和莫队一样有着看上去貌似特别高深的名字,其实就是XJB暴力正题实质上dsuontree运用了一个轻重链剖分的思想。适用于不带修改的树上询问操作离线操作比莫队优越有些树上题目我们每次暴力时间复杂度是O(n2)\mathcal{O(n^2...

2019-04-08 16:08:43

CF260E Dividing Kingdom(暴力+线段树)

原题E.DividingKingdomAcountrycalledFlatlandisaninfinitetwo-dimensionalplane.Flatlandhasnnncities,eachofthemisapointontheplane.FlatlandisruledbykingCircleIV.CircleIVhas...

2019-04-03 21:02:04

镇海三日游——ZJOI2019游记

写在前面突然想起来是时候(乱)写一篇游记了我只是一只辣么弱的蒟蒻,jls你居然还忍心骗我说不是你出题。。。Day0在学校听完一个讲座后直接去了镇海,没去镇中。。。因为蒟蒻太菜了tg都打不到515然后就去宾馆嗨皮了♂宾馆就在镇中走出100m左右,炒鸡近然后。。也没有到多晚,颓了会儿BigBangTheoryDay1~3(自闭了)大早上的,lyxlyxlyx神仙讲了《具体数学》...

2019-03-29 18:28:43

[学习笔记]拉格朗日插值法

pre很早以前就知道这玩意儿,但是一直没有学。。。然后突然看到了这东西,就顺便学了一下然后发现十分简单用途(众所周知,n阶多项式能用n+1对不同的(x,y)来表示)能将n阶多项式的点值表达式转换成系数表达式,主要就是用了构造法实现这个叫Joseph-LouisLagrange的神仙把这个多项式分成了n个部分的和使第iii个部分fi(xi)=yi,fi(xj)=0(j≠i)f_i...

2019-03-28 18:40:52

POJ1764.Dice Contest(矩阵快速幂)

原题地址蛮好的一道题目,但是一开始根本想不到这是矩阵快速幂一开始最简单的想法就是dp,因为如果两个相差比较远的块中间是不可能走回头路的,只有可能是上下移动,所以就能使用dp来维护相邻两列之间的转移我们用f[i][j][k]f[i][j][k]f[i][j][k]表示在第iii列,第jjj行,骰子状态为kkk的最小代价这里的状态存储方式需要使用得当一个有242424种状态转移方程为f[i]...

2019-03-18 20:34:05

[一道感觉做过的题]翻牌游戏

(巨弱写题解不易,转载或沿袭请标明出处)题面题目描述现在有nn种图案以及2n2n张卡牌,每张卡牌上有一种图案,每种图案对应两张卡牌一开始卡牌都是面朝下放在桌子上的,玩家每次可以翻开其中两张卡牌:如果这两张卡牌的图案相同,则这两张牌都会被移除否则这两张牌必须留在原处,并保持图案向下摆放现在某位玩家的策略是这样的:如果知道某些卡牌的图案相同,则优先翻开这些卡牌否则随机翻开两张...

2019-03-10 17:59:58

查看更多

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