4 Rose_max

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 7k+

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

thuwc2020咕咕记+题解

前言upd:更新了口胡题解upd2: 全部fixed了…不知道起啥名字。那就咕咕咕吧这次看起来能写长一点…看我心情Day -?隔壁的初审出了thu的初审也出了发现thu今年的分数线怎么比pku低这么多人多警告于是和艹哥还有远哥过了thu的初审Day 0坐飞机似乎看了个很爽的电影。下飞机穿着广东穿的单薄卫衣差点没把我吹死这温差也太大了吧,风怎么也这么大啊。脸都要被吹没...

2019-12-24 15:42:46

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 16:46:41

暂别

懒了不想往csdn上贴博客了最近做的题都存本地了当然仍然欢迎大家与博主讨论qq:2783556916

2019-10-24 14:59:33

百度之星2019决赛摸鱼记

前言绝对不鸽没有的事我云岛主已经在路上了Day0一个人来到了北京真的很冷。举目无亲,然后认识了dcx大爷,大爷非常平易近人体验极佳然后就在酒店快乐聊天睡觉,一觉睡到了欢迎晚宴。嗯。北京的电视还是一如既往的智障…欢迎晚宴非常nb,七个人上了十几个菜…果然还是百度nb然后就一路堵到了科技园,一开始不小心坐到了lyx大爷的位置上…,椅子非常高端就是想让你掉下去的,电脑就是一片白还好能...

2019-10-17 20:19:43

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

多项式全家桶

多项式求逆给你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

字符串算法选讲

符号与约定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

生成函数常用公式

搬运自@_rqy不定期更新

2019-07-20 11:40:27

thusc2019翻不了盘记

题都在下面Day -???省选完挂听说sc可以鸽掉期末考??差点以为就没过thu的初审了Day 0和隔壁的两位爷来到了北京京城真漂亮啊我校来T的就我一个…还好我爸跟我一起来了qwq不然一人住西郊这么刺激吗Day1上午来了thu报道,试机十分无聊…小学生都能阿克的试机开营式听吹水听的睡着了都要隔壁是个河南的大爷果断先膜一手开题想起来是5h3题赛制那当然果断先全看一遍...

2019-05-27 13:30:07

GDSOI2019自爆记

前言来之前啥结果都想过了就这个滚粗效果没想过…可能这样滚粗也是必然的吧Sorry for the trouble caused想了很久还是写下这个失败的东西吧…Day0不想说什么…直接从Day1开始吧Day1有点疲惫不过还好8.10开考,密码不记得了按照惯例先把四个题先看了一遍T1一眼不会这绝对不是签到难度想了想能搞到高维前缀和的20分,然后其他似乎可以容斥来拿分到...

2019-05-04 12:34:04

[bzoj3579][乱搞]破冰派对

Description由于计算机系的同学们都很宅,很多同学虽然身在一个系,但是入学很久还是相互不认识。学生会主席小Y希望举办一次破冰派对,要让同学们多从寝室里走出来参加娱乐活动,也要让尽量多不认识的同学们通过活动相互认识。自然的,如果参加活动的同学互相都不认识,那便是极好的。

2019-04-28 09:17:46

[Codeforces1155F][DP]Delivery Oligopoly

翻译给你一张双联通图,问你最少留下多少条边使得他还是双联通这里的双联通指两点能够通过至少两条边不相交路径互达题解貌似是一个经典问题fuck考场掉分一点都不想写这场题解来着…我们考虑成为答案的双联通图是可以怎么构造的我们可以每次拿出一条链,然后使得答案的双连通图变成一个更小的双联通图然后一个思路就出来了预处理一个g[S][x][y]g[S][x][y]g[S][x][y]表示...

2019-04-24 19:14:10

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

20190423模拟

前言CF又掉分困得又不行拿什么拯救自己T1有一个显然的思路是枚举中位数如果长度是奇数的话可以直接枚举否则,一个性质就是中位数一定是数值大小相邻的两个数的平均数然后似乎是满足三分性的,窝认为他不满足就写了个log2log^2log2成功自闭T2从AAA序列的aaa连向BBB序列的b+nb+nb+n,目标是给边定向使得一个点只有一个入度我怎么愚蠢的还认为是基环树图一定是个二分图...

2019-04-23 20:37:08

[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

动态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

Atcoder训练实录

前言上一篇似乎咕咕咕了233333来Atcoder玩耍**ARC096-F - Sweet Alchemynnn不大也不小的题就有点恶心了…注意到儿子的选择次数一定大于等于父亲,那么可以转化题意每次选一棵子树+1+1+1,只有以111为根的子树可以无限选其他都仅能选DDD次值域小一点似乎可以直接背包?但是值域有点大…这时候要想到一个套路就是在大范围贪心,小范围大力dpdpdp考...

2019-04-18 20:08:58

[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

[AGC028-E][树状数组]High Elements

翻译题解菜逼选手又来报到啦!对于字典序最小的问题,我们显然是用按位确定的思想定义几个变量方便使用cnt0cnt0cnt0表示AAA序列当前有多少个前缀最大值,cnt1cnt1cnt1表示BBB序列当前有多少个前缀最大值mx0mx0mx0表示AAA序列当前的最大值,mx1mx1mx1表示BBB序列当前的最大值对于第iii位的确定工作,先分析能对序列大小做出贡献的序列的性质假设...

2019-04-16 19:49:15

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。