- 博客(612)
- 收藏
- 关注
RSS订阅
原创 介绍自我&友链们
如果有大爷想diss了欢迎联系qq:2783556916先挂友链因为两个哥哥太神仙了 必须放在一起pb大师 永远滴神 + 徐老大 永远滴神hhnyzhowbzzzhzhhlzory----------学长们----------OZYFYCTYBTKJ----------单向膜拜大爷----------Ra1nbowL_0_Forever_LF由于某天下午b站挂了于是闲得无聊写个自我介绍GD zsyz 高二AFO预定选手这是一个初一没进联赛初二联赛打铜gg
2018-03-24 16:08:31
1420
1
原创 NOI2020退役记
真·退役记Day -1在机房里打APIO，终于在退役之前真切体验了一波IOI赛制的爽快T1T2都很sd，但是得分在大概2h之后就再也没有变化了。因为T3一直在杠删直径的方法，这种方法要把树直接还原出来，可惜4n4n4n次操作怎么看都是不够用的。出场大概就已经猜到最后NOI的结局了。打完后就一直在机房里摸，摸着摸着就跑路回家了Day 0和徐老大一起坐火车来长沙 反正就是一路摸报道的队伍好长好长，幸好排在了前面。领了两件衣服和一个包，文化课的书包有着落了。发现宿舍环境极好，啥东西都有，比我校宿舍
2020-08-21 00:27:42
2252
2
原创 正确的求解代数余子式的方法
前言在联合省选day2t3中，存在一种使用行列式求导来计算生成树边权和的方法。需要计算出每个位置的代数余子式常见的做法均是套用A×A∗=∣A∣×IA\times A^*=|A|\times IA×A∗=∣A∣×I的等式求解，这种做法在模意义下矩阵rank(A)=n−1rank(A)=n-1rank(A)=n−1时不能正确得出伴随矩阵以下给出正确的求解伴随矩阵的方法代数余子式给nnn阶方阵A=(ai,j)A=(a_{i,j})A=(ai,j)，定义ai,ja_{i,j}ai,j的余子式Mi,jM
2020-06-29 11:40:46
9538
3
原创 GDOI2020退役记
感谢各位大哥 退役失败.jpg前言去年gdoi挂掉的情景还历历在目 其实一整年都在害怕 在最后的这个时刻 会不会重演去年的悲剧考前定的计划 大概就是求稳。于是大概就打了一个十分丢脸的联考分数吧Day0考前一周都十分紧张 虽然模拟赛打得看起来还行 但是总是被省选ptsd给折磨的彻夜难眠 谢谢有你陪我啊最后一天放弃治疗了 上午把剩下来的一些板子给补了一下 看了看之前做过的几道题 然后就开始看蝙蝠侠 看完感觉心态良好晚上到了酒店 在车上和xld交流了一下省选的计划 于是就是十分坚定地求稳xld因为
2020-06-21 16:54:18
908
2
原创 JOI 2020 Final 题解
前言好久没更。来更一篇竟然直接ak了…loj#3252. 「JOI 2020 Final」只不过是长的领带考虑去除后的匹配方式，将两个序列排序注意到如果存在i<ji<ji<j满足匹配的位置ci>cjc_i>c_jci>cj，由于此时满足bi<bj,aci>acjb_i<b_j,a_{c_i}>a_{c_j}bi<bj...
2020-02-12 17:44:40
1784
原创 thuwc2020咕咕记+题解
前言upd:更新了口胡题解upd2: 全部fixed了…不知道起啥名字。那就咕咕咕吧这次看起来能写长一点…看我心情Day -?隔壁的初审出了thu的初审也出了发现thu今年的分数线怎么比pku低这么多人多警告于是和艹哥还有远哥过了thu的初审Day 0坐飞机似乎看了个很爽的电影。下飞机穿着广东穿的单薄卫衣差点没把我吹死这温差也太大了吧，风怎么也这么大啊。脸都要被吹没...
2019-12-24 15:42:46
994
4
原创 CSP-S2019退役记
前言技不如人安心退役upd:1LL<<(n-1)准备退役day1挂50没什么别的了upd1:100+100+35+100+64+90=489海星。比去年高了4分qaq退役了Day0不想写了。50元团餐实在不行吃了跟没吃一样还没得面基晚上买了个鸡排顺便带了两瓶红牛肝了两部电影空调温度十分奇怪，房内一度上升到37度Day1诶我考场怎么只认识马神仙果...
2019-11-17 20:45:13
1220
4
原创 百度之星2019决赛摸鱼记
前言绝对不鸽没有的事我云岛主已经在路上了Day0一个人来到了北京真的很冷。举目无亲，然后认识了dcx大爷，大爷非常平易近人体验极佳然后就在酒店快乐聊天睡觉，一觉睡到了欢迎晚宴。嗯。北京的电视还是一如既往的智障…欢迎晚宴非常nb，七个人上了十几个菜…果然还是百度nb然后就一路堵到了科技园，一开始不小心坐到了lyx大爷的位置上…，椅子非常高端就是想让你掉下去的，电脑就是一片白还好能...
2019-10-17 20:19:43
728
4
原创 LCT板子。
就是个板子。又短又爽我爱了。namespace LCT{ int ch[2][MAXM],fa[MAXM],rev[MAXM]; int sta[MAXM],tp; bool son(int x){return x==ch[1][fa[x]];} bool isroot(int x){return ch[0][fa[x]]!=x&&ch[1][fa[x]]!=x;}...
2019-08-19 22:44:23
635
1
原创 多项式全家桶
多项式求逆给你f(x)f(x)f(x)，要求计算g(x)g(x)g(x)满足f(x)g(x)≡1(mod  xn)f(x)g(x)\equiv 1(\mod x^n)f(x)g(x)≡1(modxn)考虑倍增的过程，常数项就直接求逆，否则已经计算完n2\frac{n}{2}2n的贡献若已知f(x)h(x)≡1(mod&Thin...
2019-08-10 22:42:14
1221
4
原创 字符串算法选讲
符号与约定s[1...x]=s[1]s[2]s[3]...s[x]s[1...x]=s[1]s[2]s[3]...s[x]s[1...x]=s[1]s[2]s[3]...s[x]组成的字符串pre[s,x]=s[1...x],suf[s,x]=s[∣S∣−x+1...∣S∣]pre[s,x]=s[1...x],suf[s,x]=s[|S|-x+1...|S|]pre[s,x]=s[1...x]...
2019-08-07 15:58:20
737
原创 thusc2019翻不了盘记
题都在下面Day -???省选完挂听说sc可以鸽掉期末考？？差点以为就没过thu的初审了Day 0和隔壁的两位爷来到了北京京城真漂亮啊我校来T的就我一个…还好我爸跟我一起来了qwq不然一人住西郊这么刺激吗Day1上午来了thu报道，试机十分无聊…小学生都能阿克的试机开营式听吹水听的睡着了都要隔壁是个河南的大爷果断先膜一手开题想起来是5h3题赛制那当然果断先全看一遍...
2019-05-27 13:30:07
701
1
原创 GDSOI2019自爆记
前言来之前啥结果都想过了就这个滚粗效果没想过…可能这样滚粗也是必然的吧Sorry for the trouble caused想了很久还是写下这个失败的东西吧…Day0不想说什么…直接从Day1开始吧Day1有点疲惫不过还好8.10开考，密码不记得了按照惯例先把四个题先看了一遍T1一眼不会这绝对不是签到难度想了想能搞到高维前缀和的20分，然后其他似乎可以容斥来拿分到...
2019-05-04 12:34:04
742
1
原创 [bzoj3579][乱搞]破冰派对
Description由于计算机系的同学们都很宅，很多同学虽然身在一个系，但是入学很久还是相互不认识。学生会主席小Y希望举办一次破冰派对，要让同学们多从寝室里走出来参加娱乐活动，也要让尽量多不认识的同学们通过活动相互认识。自然的，如果参加活动的同学互相都不认识，那便是极好的。
2019-04-28 09:17:46
884
原创 [Codeforces1155F][DP]Delivery Oligopoly
翻译给你一张双联通图，问你最少留下多少条边使得他还是双联通这里的双联通指两点能够通过至少两条边不相交路径互达题解貌似是一个经典问题fuck考场掉分一点都不想写这场题解来着…我们考虑成为答案的双联通图是可以怎么构造的我们可以每次拿出一条链，然后使得答案的双连通图变成一个更小的双联通图然后一个思路就出来了预处理一个g[S][x][y]g[S][x][y]g[S][x][y]表示...
2019-04-24 19:14:10
574
原创 20190424NOI.AC省选模拟
A怎么是个FFT裸题啊…直接通配符匹配的套路玩起来就好了吧…*B上午做题怎么都这么迷糊…首先式子可以变成这个∑dd∑i∑j[i∗j∗d2≤n][gcd(i,j)=1]\sum_d d\sum_i \sum_j[i*j*d^2\leq n][gcd(i,j)=1]d∑di∑j∑[i∗j∗d2≤n][gcd(i,j)=1]反演一手∑dd∑kμ(k)∑i⌊nd2k2i⌋\sum...
2019-04-24 15:42:26
504
原创 20190423模拟
前言CF又掉分困得又不行拿什么拯救自己T1有一个显然的思路是枚举中位数如果长度是奇数的话可以直接枚举否则，一个性质就是中位数一定是数值大小相邻的两个数的平均数然后似乎是满足三分性的，窝认为他不满足就写了个log2log^2log2成功自闭T2从AAA序列的aaa连向BBB序列的b+nb+nb+n，目标是给边定向使得一个点只有一个入度我怎么愚蠢的还认为是基环树图一定是个二分图...
2019-04-23 20:37:08
249
原创 [Codeforces1139D][DP][莫比乌斯反演]Steps to One
翻译给你一个数nnn每次随机在[1,n][1,n][1,n]中选一个数加入aaa数组如果aaa数组中gcd=1gcd=1gcd=1时就结束问aaa数组的期望长度题解把图建出来，发现如果去掉自环就是一个DAG发现自己居然不会求这个期望…先记住一点东西f[x]=∑(f[y]+1)∗tf[x]=\sum (f[y]+1)*tf[x]=∑(f[y]+1)∗t然后如果已经求出了除了...
2019-04-21 16:35:07
447
原创 动态DP随想
前言我是被逼的不打还真不会打模版题干啥的树上最大独立集？动态改点权？NOIP2018D2T3?…玩法以模版题为例先写出dpdpdp方程，常用的fi,0/1f_{i,0/1}fi,0/1表示当前点选了/没选的最大方案转移有fi,0=∑max(fson,0,fson,1)f_{i,0}=\sum max(f_{son,0},f_{son,1})fi,0=∑max(fson...
2019-04-20 10:28:15
209
原创 Atcoder训练实录
前言上一篇似乎咕咕咕了233333来Atcoder玩耍**ARC096-F - Sweet Alchemynnn不大也不小的题就有点恶心了…注意到儿子的选择次数一定大于等于父亲，那么可以转化题意每次选一棵子树+1+1+1，只有以111为根的子树可以无限选其他都仅能选DDD次值域小一点似乎可以直接背包？但是值域有点大…这时候要想到一个套路就是在大范围贪心，小范围大力dpdpdp考...
2019-04-18 20:08:58
471
原创 [ARC100-F][DP]Colorful Sequences
翻译给你KKK和mmm，给出一个长度为mmm的由[1,K][1,K][1,K]组成的序列问用[1,K][1,K][1,K]组成的长度为nnn的好序列中有多少个如上给出的序列定义一个序列为好序列当且仅当其有一个长度为KKK的子串，满足[1,K][1,K][1,K]在其中各出现了一次题解gank英文题解现场begay的题解太难懂了…正难则反考虑用在所有序列中的数量减去在非法序列中...
2019-04-17 16:13:46
501
原创 [AGC028-E][树状数组]High Elements
翻译题解菜逼选手又来报到啦！对于字典序最小的问题，我们显然是用按位确定的思想定义几个变量方便使用cnt0cnt0cnt0表示AAA序列当前有多少个前缀最大值，cnt1cnt1cnt1表示BBB序列当前有多少个前缀最大值mx0mx0mx0表示AAA序列当前的最大值，mx1mx1mx1表示BBB序列当前的最大值对于第iii位的确定工作，先分析能对序列大小做出贡献的序列的性质假设...
2019-04-16 19:49:15
228
原创 [Codeforces1153F][数论]Serval and Bonus Problem
翻译你有一个长度为LLL的数列，在上面随机选择2∗n2*n2∗n条线段求至少被覆盖了KKK次的区间的长度和的期望题解数学菜逼来啦先考虑一个子问题，在一个[0,1][0,1][0,1]的数轴上随机撒iii个点，求某个间隔长度的期望抛出结论的话就是期望是1i+1\frac{1}{i+1}i+11感性认知的话我们可以想象一下每个区间的期望其实是相同的…理性认知的话我们考虑这iii...
2019-04-14 16:52:13
641
原创 [Codeforces713E][DP]Sonya Partymaker
翻译题解注意一个人确定了一个方向就不会改变…容易想到二分+dpdpdp判断然后考场上就想了个假飞的做法23333333我们考虑怎么check首先能够发现是答案的上界是最长的一段，不妨把这一段转到111和nnn之间，为什么稍后会介绍把这个问题扔到序列上做的话，我们可以这样dpdpdp设f[i]f[i]f[i]表示覆盖完了[1,i][1,i][1,i]，往后最远还能覆盖到多少...
2019-04-13 10:49:04
393
原创 Codeforces贪心训练
贪心跟个sb一样…来cf刷几个题玩玩717B. R3D3’s Summer Adventure目标就是让你建出一个字典树，满足有nnn个叶子节点且叶子节点权最小这里的贪心我们需要考虑的是每次拓展一个点，即从上一个最优情况来到下一个最优情况听说这种拓展还有个名字叫VarnCodeTreeVarn Code TreeVarnCodeTree…考虑每次找到一个最小权的叶子节点iii，设他的权...
2019-04-10 10:21:15
555
原创 [loj#572][杜教筛][min-25筛]Misaka Network 与求和
Description传送门题解强行拼题来着啊2333推一发柿子可以得到一个线性的做法就是ans=∑i=1nf(i)∗(∑j=1niϕ(j)∗2−1)ans=\sum_{i=1}^{n}f(i)*(\sum_{j=1}^{\frac{n}{i}}\phi(j)*2-1)ans=i=1∑nf(i)∗(j=1∑inϕ(j)∗2−1)然后就不会了啊qwq如果设sum(x)=∑i...
2019-04-09 20:34:00
407
原创 杜教筛学习笔记
前言头都给队友们打烂了啊这玩意还是简单易懂的啊qwq似乎博客已经变成了笔记博客？？用途求一类积性函数的前缀和经典问题有求μ\muμ与ϕ\phiϕ的前缀和，本文将以这两个函数的前缀和为例前置狄利克雷卷积两个函数fff和ggg的狄利克雷卷积f∗gf*gf∗g即为(f∗g)(i)=∑d∣if(i)g(id)(f*g)(i)=\sum_{d|i}f(i)g(\frac{i}{d})(f...
2019-04-08 21:04:20
342
原创 [loj#3043][线段树]线段树
Description传送门题解果然这又是一个把标签告诉你的题2333简单思考一下就可以知道，其实就是要问你对于前iii个操作，有12\frac{1}{2}21的概率做或者不做，每个点有标记的概率和是多少需要维护的是一个点有值的概率$ h[x]$一个点祖先有值的概率g[x]g[x]g[x]转移分情况讨论先讨论h[x]h[x]h[x]的转移如果点是被线段树更新了的点且不是...
2019-04-04 15:48:33
248
原创 [codeforces1060F][DP]Shrinking Tree
翻译你有一棵nnn个点的树，做n−1n-1n−1次如下操作随机选择一条当前存在的边并把他的两个端点缩起来，新端点的编号在两个端点间等概率随机问最后每个点成为最后一个点的概率n≤50n\leq 50n≤50题解吼啊先放一下参考了这位爷爷的自己很辣鸡的一点就是遇见这种nnn不小不大的就不会玩了…首先当然可以想到，枚举需要计算的顶点然后把他拉到根节点，开始考虑怎么计算然后就被...
2019-04-03 19:40:18
320
原创 [codeforces1019B][二分法求函数零点]The hat
翻译有一个大小为nnn的圈，满足相邻的数绝对值差为111且nnn为偶数你每次可以询问一个位置上的数的数值现在问是否存在一个位置xxx满足xxx与x+n2x+\frac{n}{2}x+2n上的数是相等的询问次数不超过60次题解第一场vp直接给我掉飞分了肯定没有课内玩家日常gg首先可以知道n%4n\%4n%4不为000时是一定无解的我们先定义d[i]d[i]d[i]为iii位...
2019-04-02 16:36:44
228
原创 有上下界的网络流学习笔记
前言补坑补坑还债还债参考了liu_runda的前置上下界：即一条边存在必须流过的流量与至多流过的流量，分别称为上界和下界流量守恒：即满足一个点的流入流量=流出流量可行流：问一张图是否存在每个点满足流量守恒且满足上下界限制的流将以上条件称为基本条件称一条边(u,v,down,up)(u,v,down,up)(u,v,down,up)为从uuu到vvv，流量下界为downdowndo...
2019-03-30 15:54:48
227
原创 [bzoj4699][Dijkstra][线段树][并查集]树上的最短路
Description下水道的主干路由n个节点和n-l条边组成，每条边有一个通过它所需的时间Ti。换言之，这是一棵n个节点的带权树。现在，要用最快的速度赶往目标节点k。下水道有一些塌陷，这导致主干路的某一段路径可以通过该塌陷到另一条路径。对于一个塌陷，我们用(L1，ri，L2，R2，c)来描述，即对于主干路上L1到R1路径上的任意节点x，L2到r2路径上的任意节点y，都可以在c的时间内从...
2019-03-29 21:21:10
467
原创 [bzoj3946][线段树][哈希]无聊的游戏
Description小K因为学习OI认识了两位神犇，他们分别叫做小H和小Y。两位神犇平时是这么对待小K的： “这不是道傻逼题么” “这都不会做你智商堪忧啊”“。。。。。。”小K因此对生活失去了信心。最近两位神犇没什么题刷，于是他们开始用自己做题剩下的史诗级智商来享受生活的快乐——研究游戏开发了。由于两位神犇太神，不久他们就创造了新的游戏。游戏一开始会给由你N个非空串构成的序列，然后你要...
2019-03-29 10:39:55
318
原创 [bzoj4670][2-sat]佛罗里达
Description没有得到激光武器的苏联十分生气，他们决定派遣一支特种部队强行 登陆美国并造成一定的袭击。 Reddington 得到的情报是他们将在佛罗里达海岸登陆，他决定派遣他的手下去阻击他们。可惜的是， Reddington 由于 不听从总统的意见，手中的部队只剩下了 N个人。人与人之间会有一定的 矛盾值，第 i 个人与第 j 个人的矛盾值为 Ti,j，并且有 Ti,i = 0，...
2019-03-28 20:51:25
451
原创 模拟退火学习笔记
前言博主这个暴力骗分选手get到了人生的本质前置有一类函数，我们要求其的最低点/最高点二分？三分？四五六七八九分？？哦凉凉了…先介绍一个爬山我们随机撒点，然后让这些点去做类似现实的爬山即右边优就去右边，左边优就去左边直到没有比他更优秀的了！也就是相当于到山峰了吧那么这个贪心的算法显然非常容易卡在一个局部最优解出不来了哦怎么办呢…按正常人的思维想，走到了一个最高处，就应该...
2019-03-28 19:43:56
247
原创 [bzoj3157][bzoj3516][数论]国王奇遇记/国王奇遇记加强版
Description求∑i=1nimmi\sum_{i=1}^{n}i^mm^ii=1∑nimmiInput共一行包括两个正整数N和M。Output共一行为所求表达式的值对10^9+7取模的值。Sample Input5 3Sample Output36363HINT1<=N<=10^9,1<=M<=1000题解好高...
2019-03-28 15:24:27
423
原创 [bzoj5332][bzoj5276][bzoj3994][莫比乌斯反演][三元环计数]旧试题/skyfall/约数个数和
Description旧试题skyfall约数个数和约数个数和题解由于这三个题长得比较像就放一起吧设D(u)D(u)D(u)表示uuu的约数和，那么有如下结论D(x∗y)=∑u∣x∑v∣y[gcd(u,v)==1]D(x*y)=\sum_{u|x}\sum_{v|y} [gcd(u,v)==1]D(x∗y)=u∣x∑v∣y∑[gcd(u,v)==1]证明如下，设kik_i...
2019-03-27 17:19:10
274
原创 [bzoj5052][Codeforces765F][主席树]繁忙的财政官/Souvenirs
Description伟大的王朝即将在下个月迎来奥西利斯节，这是整个埃及最盛大的节日。胡夫非常重视这次盛会，所以他经常向财政官询问国家的财政事项。但是同时，有成堆的文件等待着财政官检视，为此他忙得不可开交。现在他正处于崩溃的边缘（辞职申请都写好了）。他听说你这个异乡人拥有神奇的能力，于是带着丰厚的礼品来带了你的居所，看样子你是没法拒绝他了…….财政官的工作很简单，但是国王的视察很繁琐（官...
2019-03-26 19:22:22
330
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人