dilute.xyz | powered by Hexo themed "Azurus"


QQ

|

Codeforces

|

Luogu

|

Github

ACM Journal

August 1, 2022

HZEZ OIer Dilute 的故事虽然已经结束……

但是接下来是属于 HIT ACMer Dilute 的时间!

2023 CCPC 深圳站游记 with ZhangCW & skytyf

November 16, 2023

省流:真的有钱,而且卸下压力之后的比赛竟然超常发挥了这么多,从各方面来讲都是充满了无数惊喜的一场比赛。

2023 ICPC 南京站游记 with ZhangCW & skytyf

November 7, 2023

省流:过程很刺激,最后还是拿到队伍第一块 Au了

「火锅旅梦」 with. dyxg & Sooke

August 16, 2023

Day -n

在暑假的初期,突发奇想,准备和自己的好兄弟们来一场去年没能完成的旅行。

题解 CF1793E Velepin and Marketing

February 24, 2023

时隔3年 我终于又发了一篇正经题解

要不是lqr我可能这博客就卡在这里了

题解 CF1314D Tourism

February 24, 2020

开场 10 分钟就有人过的 1D ,你值得拥有!

swap(B, D)\texttt{swap(B, D)} 警告。

题解 CF1286C Madhouse

January 12, 2020

这个 0.7770.777 让我想起了某位 EDG 的退役打野选手

—— Sooke

4396(无 端 迫 害)

题解 CF498D Traffic Jams in the Land

September 1, 2019

线段树

首先观察数据范围,发现ai6a_i \le6,这个是一个非常有用的性质。

发现lcm(1,2,3,4,5,6)=60\mathrm{lcm}(1, 2, 3, 4, 5, 6)=60,这个数有一个非常优美的性质:把ttmod60\mod 60意义下进行不会影响结果的正确性。

题解 CF1178G The Awesomest Vertex

July 21, 2019

分块 + 斜率优化

G真的比F2清真

首先,看到树上 + 子树操作,第一反应使用dfs序拍平。

那么这个问题就变成了支持:

题解 CF1183H Subsequences (hard version)

June 27, 2019

瞎搞DP

CF出了H没出G 菜的真实

发现kkE\texttt{E}题的100100变成了O(1012)O(10^{12}),考虑与kk复杂度无关的做法。

我们考虑fi,jf_{i, j}表示以sis_i开始,本质不同的长度为jj的子序列数量。

题解 CF240F TorCoder

June 3, 2019

线段树乱搞

考虑如果要重排一段区间使得它是回文的是可行的

首先对这段区间的长度分类讨论

题解 CF1051E Vasya and Big Integers

May 28, 2019

哈希 + 二分 + DP

首先看到题面,很容易想到一个DPDP,令f[i]f[i]为划分到ii为止的方案数。

然后朴素的暴力转移是O(n2)O(n^2)的,非常显然一个状态ii能够转移到的jj是一段连续的,进而想到使用前缀和优化。

题解 CF15D Map

May 8, 2019

setset 瞎搞

首先非常显然,一个矩形(x1,y1,x2,y2)(x1, y1, x2, y2)的代价就是i=x1x2j=y1y2h[i][j]minx1ix2,y1jy2h[i][j]\displaystyle\sum_{i = x1}^{x2}\sum_{j = y1}^{y2} h[i][j] - \min_{x1 \le i \le x2, y1 \le j \le y2} h[i][j],我们用f[i][j]f[i][j]表示以(i,j)(i, j)为左上角的矩形的代价。即矩形(i,j,i+a1,j+b1)(i, j, i + a - 1, j + b - 1)的代价。

我们首先考虑如何求出f[i][j]f[i][j]

ZJOI2019 游记

April 27, 2019

Round 1

咕咕咕。

回头再补。

题解 CF609F Frogs and mosquitoes

April 22, 2019

set​瞎搞

预处理

我们考虑一下,一只青蛙能够影响的区间是什么

我们发现,如果将每只青蛙能够吃到的文字区间[l,r][l, r]按照左端点ll排序,然后把后面的区间和前面的区间的重复部分去掉,那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间

OI Journal

April 18, 2019

看到学长txc爷的blog里写了个“最近写的题目”

然后心血来潮准备自己也弄个这个东西

题解 CF1153E Serval and Snake

April 14, 2019

有趣的交互题

我们考虑一件事情

如果我们询问的矩形中有一个端点

那么答案 mod2=1\mod 2 = 1

否则答案 mod2=0\mod 2 = 0

换句话说,就是如果询问到的答案mod2=0\mod 2 = 0,那么这个矩形内要么没有端点,要么有两个端点

题解 CF343D Water Tree

March 29, 2019

似乎莫得人是不用树剖的w

但是为什么的一只log\log乱搞被树剖的两只log\log爆踩啊

是因为我实现的太丑了吗

不管了直接讲做法好了

题解 CF1117D Magic Gems

March 2, 2019

有趣的矩阵乘法

(为方便,下文中“大号宝石”代指连续的mm个分裂出来的宝石,“小号宝石”代指未分裂的单个宝石)

首先,我们观察这题,考虑DPDP​,设状态fif_i​表示已经取了ii​个单元的方案数的不难推出一个朴素的O(n2)DPO(n^2) DP​方程fi=ijmfj+1f_i = \displaystyle\sum_{i - j \geq m} f_j +1​(可以理解成上一个大号宝石放的位置,最后一个11​即为全部用小号宝石填满的方案)

我们再仔细看看这个式子,加个前缀和,不难优化到O(n)O(n),然而数据范围n1018n \leq 10^{18},这让我们考虑O(logn)O(\log n)级别的算法,我们接下来考虑矩阵乘法优化这个式子。

题解 CF452F Permutation

February 26, 2019

又双叒叕是题外话

今天模拟考是原题大战。

T1T1​是这题。
T2T2是某次CF Div1 ECF\ Div1\ E题。
T3T3​反正是某道神仙题。

像我这样的菜鸡只能来做做相对可做的T1

虽然只是相对可做但是还是被全场切穿了啊喂

内心OS:这个不订正的理由真的nice

题解P2892 追捕盗贼

February 21, 2019

本篇题解讲述的为非完美做法,但是可以骗到96分

说实话我在网上找了好久结果都是这个O(n2)O(n^2)的非正解树型DPDP

听说有个O(N)O(N)​的正解在某篇论文里?

算了反正我也看不懂

所以我接下来就介绍一下这个O(n2)O(n^2)的树型DPDP吧QwQ

顺手丢一下我学习的这篇blog​

题解 CF1111C Creative Snap

February 12, 2019

简单递归

首先我们如果要消灭一段区间[l,r][l, r],我们可以有三种选择:

题解 洛谷P5174 圆点

January 28, 2019

题外话

我本来自己想到的的做法是跟别的大多数题解一样的

但是LJC00118LJC00118大仙跟我讲了他的做法,据说常数更小一些,于是我就过来发(水)题(社)解(区)了(分)。

PKUWC2019游记

January 20, 2019

Day 0Day\ 0

早上八点的飞机从杭州飞到广东中山纪念。

飞机上跟旁边的sjnsjn神犇聊了一会之后开始颓废,后来敲了fhq Treapfhq\ Treap、最大流、费用流三个板子。

到了广东之后做了3个小时的公交车

到了中山纪念之后觉得宿舍略破,不过至少有电QwQ

试了个机,T1水题,T2据说是去年PKUSC的D1T2,想出了DP的状态定义不会转移,结果后来Sooke教我了一下,感觉不是特别想敲=-=

试完机之后还有蛮长的一段时间吃饭,于是我们就打了一盘狼人杀(法官真好玩)

饭菜一般般,坐我旁边的Sooke想找人面基,但是最后也就来的路上遇到了bztQwQ

晚上吃完饭,又来了一盘狼人杀(我还是法官)(双预言家真好玩)

现在是晚上7点,我躺在床上跟LJC00118一起写游记

真是充(颓)实(废)的一天

fhq Treap与区间操作

January 16, 2019

​ 前段时间在机房里几个大爷的墙裂安利下学了发fhq treapfhq\ treap 于是就顺带着把fhq treapfhq\ treap的区间操作给学了(比SplaySplay的好理解多了)

似乎这么一点字太少了?那我放张图=-=

题解 洛谷4142 洞穴遇险

January 10, 2019

题外话

我们模拟赛考了这题。

模拟赛大概还剩一个半小时的时候,我想出了这题,并且说

“要是我这没A掉,我就不交卷了”

于是我就没有A掉。

其实赛后半个小时左右就调出来了(我才不会告诉你我比赛的时候那个建模是有锅的呢)

浅谈珂朵莉树

January 10, 2019

Ⅰ 什么是珂朵莉?

珂朵莉是世界上最幸福的女孩,没有之一,不接受任何反驳。

题解 CF1096G Lucky Tickets

December 29, 2018

其实我很想吐槽这题

我比赛的时候疯狂WA on test 16​\text{WA on test 16}​

然后死活找不出来哪儿错了

我觉得我数组开小了

于是我开到MLEMLE都没有过掉

最后一看

被一个n = 2的点卡掉了……

才出4题,罚时爆炸,上黄失败,掉分哭唧唧

题解 CF1095D Circular Dance

December 28, 2018

我们令fa[i]fa[i]ii直接连向的点

那么显然,fa[i]{ai,1,ai,2}fa[i] \in \{a_{i, 1}, a_{i, 2}\}​

假设ai,1a_{i, 1}fa[i]fa[i],那么a2,i{afa[i],1,afa[i],2}a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \}

否则肯定有a2,i∉{afa[i],1,afa[i],2}a_{2, i} \not\in \{ a_{fa[i], 1}, a_{fa[i], 2} \}

所以,如果有a2,i{afa[i],1,afa[i],2}a_{2, i} \in \{ a_{fa[i], 1}, a_{fa[i], 2} \},那么fa[i]=ai,1fa[i] = a_{i, 1},否则fa[i]=ai,2fa[i] = a_{i, 2}

题解 洛谷P5003 跳舞的线-乱拐弯

November 21, 2018

一道有点套路化的网格图上DPDPQwQ

我们用fmin[i][j][0]f_{min}[i][j][0]表示线头在(i,j)(i, j)这个点的时候,线的方向朝__下__,我们能取到的最小的拐弯次数、用fmin[i][j][1]f_{min}[i][j][1]表示线头在(i,j)(i, j)这个点的时候,显得方向朝__右__,能够取到的最小的拐弯次数

同理,我们用fmax[i][j][0]f_{max}[i][j][0]fmax[i][j][1]f_{max}[i][j][1]表示线头在(i,j)(i, j)位置是线朝下和朝右能够取到的最大的拐弯次数。

接下来,对于有障碍的点,我们直接不处理

显然,答案分别为max(fmax[n][m][0],fmax[n][m][1])\max(f_{max}[n][m][0], f_{max}[n][m][1])min(fmin[n][m][0],fmin[n][m][1])\min(f_{min}[n][m][0], f_{min}[n][m][1])

题解 CF1070H BerOS File Suggestion

November 19, 2018

对于这题,看到字符串匹配,第一反应想到字符串hash,同时看到$len \leq 8 $ ,考虑对于先给出的nn个字符串,O(len2)O(len^2)枚举它的子串,将其加入mapmap中,但是要注意如果一个然后对于每个字符串,我们都统计一下它最后一次出现在哪里(于是就可以顺便判一下重)

然后我们在询问的时候,就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

题解 洛谷P3022 [USACO11OPEN]奇数度Odd degrees

November 18, 2018

我感觉思路隔壁题解给的不够清楚啊……

感觉我无法直接理解隔壁dalao的“正经的图上神搜”啊……

那本蒟蒻就补充一下吧QwQ

我来了,我出锅了,我走了——NOIp2018游记

November 18, 2018

Day (不想算)

将RP耗尽在了初赛QwQ

Day 0

教练说这天Openday,随便打游戏,于是上午随手把最大流、费用流、树剖三个听说可能会考的板子给敲了一遍于是就去跟同学颓了一天的LOL

题解 CF1068B LCM

November 17, 2018

第一篇题解

我们都知道lcm(a,b)=abgcd(a,b)lcm(a, b) = \frac{a * b}{\gcd(a, b)}

lcm(a,b)a=abgcd(a,b)a=bgcd(a,b)\frac{lcm(a, b)}{a} = \frac{\frac{a * b}{\gcd(a, b)}}{a} = \frac{b}{\gcd(a, b)}

题目的意思就被我们转化成了求bgcd(a,b)\frac{b}{\gcd(a, b)}的种类数

又∵b是一个确定的数

bgcd(a,b)\frac{b}{\gcd(a, b)}的种类数就等于gcd(a,b)\gcd(a, b)的种类数

由于aa的范围在[1,1018][1, 10^{18}]范围内,所以gcd(a,b)\gcd(a, b)的种类数就等于b的因数个数。

因数个数就可以O(n)O(\sqrt n)求辣QwQ

题解 CF1077C Good Array

November 17, 2018

显然,我们可以发现一个序列是“好的”当且仅当这个序列中的最大值等于这个序列中的其他数之和相加,所以我们只需要保证序列单调递减,同时维护一下这个序列里面元素之和我们就可以O(1)O(1)判断一个序列是不是“好的”序列(a1=Suma1a_1 = Sum - a_1

由于题目要求求出去掉哪些元素之后,这个序列会变为一个“好的”序列,所以我们只需要把原序列排序之后再按照刚刚说过的办法O(1)O(1)判断,只需要吧把原序列之中的SumSum减去我们需要去掉的元素即可

还有一点需要注意,我们需要特判去掉第一个的情况,这样删去后最大值就是原先的次大数,即a2a_2

上代码QwQ

题解 洛谷P2547 [AHOI2004]DNA变异

October 24, 2018

首先我作为一个蒟蒻,拿到字符串题,首先看看能不能无脑哈希

然后于是我们就发现了一个绝妙的做法:暴力枚举每个字符串能够转换成的字符串

于是我们就获得了O(N84)O(N * 8^4)的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

算法学习笔记-最小费用最大流

October 1, 2018

前言

某天我看到了memset0巨佬怒切17道网络流神仙题的时候,我顿时准备去做做看网络流24题以满足我内心的抖M之魂

于是,我这个蒟蒻看到某道费用流神题的时候,一脸懵逼地看着“费用流”的标签,决心去学一学这玩意

算法学习笔记-单调队列

September 27, 2018

前言

单调队列一种非常经典的将O(n^2)的DP优化的O(n log n)的方式,在一个点可以更新一个范围的时候可以发挥很大作用。

记得当年NOIp2017我考PJ(那年的T4考到了单调队列),当时还不会,在考后听教练讲了一遍之后仍旧处于懵逼状态,大概1个月前照着题解打了一遍,但是到了现在已经忘得差不多了QwQ,于是写了一遍优化过的多重背包来练练手。

杭十三中冠军联赛S1 Extra Round 题解

September 26, 2018

$$ \texttt{ Writer:世界最蒻Dilute}$$

$$\texttt{ #A 某脱碳甲醛的电磁炮题}$$

 出题人 Dilute\texttt{ 出题人 Dilute}​

电流公式I=URI=\frac{U}{R}大家都知道(不知道的话在题面中也给出了)

所以直接输出就可以了(ps:C++中除法自动向下取整)

题解 洛谷P4819 [中山市选]杀人游戏

August 29, 2018

首先我们考虑一件事:如果存在一个人,使任何一个人都不认识,我们称这种人为“孤独”的人,那么警察只能通过调查他来取得他的身份。

然后对于一个不“孤独”的人,我们发现他们肯定至少被一个那些“孤独”的人直接或间接的认识。

所以我们得出结论:只要统计“孤独”的人的数量即可。


你照着这么做,就可以获得100 mod 10分的好成绩。

题解 CF702E Analysis of Pathes in Functional Graph

August 21, 2018

一道非常好的练倍增的题目

思路很简单,就是倍增处理出每个点往后2i2^i个点的路径权值和与最小值,同时要注意一下kk​要用longlong存,否则会挂掉

如果不会倍增的右转百度找其他博客去吧……我这里就不赘述了

题解 洛谷P3045 [USACO12FEB]牛券Cow Coupons

August 3, 2018

欧洲退火!

没错你没有看错这么一道Heap的题我拿出了退火来做!

那么模拟退火的基本思路这里不讲了如果要看右转P1337去看。

废话不多说,上思路

题解 洛谷P4267 [USACO18FEB]Taming the Herd

July 31, 2018

竟然没有人写题解2333那本蒟蒻就来H2OH_2O一篇吧

首先,看完题面不难想到DP,之后再看数据范围考虑O(N3)O(N^3)DP,之后瞎搞一通可以想到

f[i][j]f[i][j]表示在前ii个里面经历kk次出逃可以取到最少的修改数

那么接下来我们就发现f[i][j]f[i][j]可以影响的范围为f[u][j+1]f[u][j+1](i<uni < u ≤n),然后我们就可以写出如下的程序:

题解 洛谷P1704 寻找最优美做题曲线

April 9, 2018

暴力赛高!暴力是全世界最最最(以下省略2147483647个人最)NB的算法!

AC记录

这里似乎没有朴素的算法啊(啊当然Pascal不算哈)

我开始做题的时候还专门为了求稳去学习了一下nlognnlogn的最长上升子序列呢

其实我们会发现,暴力的时间复杂度其实根本不是O(n2)O(n^2),就让我们来分析一下暴力的时间复杂度。

题解 洛谷P1396 营救

March 23, 2018

令人智熄的二分操作

AC记录

要看正常的解法请看其他题解

而且还蛮快的。。。

其实,这是非常奇葩的一个想法

总体思路就是:二分答案

你没听错,二分答案

我们从题面中可以看到,其实这道题的拥挤度也就1000010000而已,所以我们就会发现二分似乎可以???

存图存完之后直接二分,二分的Check()Check()里面打一个BFSBFS,来求能否通往终点,就好了

具体的东西就上代码来看吧

题解 洛谷P2814 家谱

March 16, 2018

STL大法好!

(看到楼下的大佬们都没有用我这个方法,我就来脱碳甲醛一下辣~~)


以上都是废话

我所说的这个方法,具体思路是这样的:


QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动,使用 Azurus 作为主题。