2 Aaplloo

尚未进行身份认证

我要认证

樱岛麻衣 wlp!

等级
TA的排名 12w+

[CF 372C] Watching Fireworks is Fun

题目洛谷思路要求 max⁡∑bi=i−∣ai−x∣\max\sum b_i=_i−∣a_i−x∣max∑bi​=i​−∣ai​−x∣可以拆成 ∑bi−min⁡∣ai−x∣\sum b_i-\min∣a_i−x∣∑bi​−min∣ai​−x∣定义 dp[i][j]dp[i][j]dp[i][j] 为第 iii 时刻在 jjj 位置的最小代价。发现有些时间是空的,所以稍微改一下:dp[i][j]dp[i][j]dp[i][j] 为第 iii 个烟花绽放时刻在 jjj 位置的最小代价。易得到:dp[

2020-08-13 08:09:46

[CF 319C] Kalila and Dimna in the Logging Industry

题目洛谷思路考虑 dp[i]dp[i]dp[i] 为砍掉第 iii 棵树的最小代价,因为 b[n]=0b[n]=0b[n]=0,所以目的是求 dp[n]dp[n]dp[n]考虑计算 dp[k]dp[k]dp[k]。因为 bib_ibi​ 单调递减,所以砍掉编号 >k>k>k 的树之后,就不会再回来管 kkk,而是向 nnn 奋起直追。这一点似乎很多题解里并没有考虑。所以 dp[k]dp[k]dp[k] 只会由 <k<k<k 的 dpdpdp 来转移,所以我们考虑

2020-08-12 16:30:04

[CF 1107G] Vasya and Maximum Profit

好久没做过单调栈单调队列的题了,看到式子都不知道怎么运用了。

2020-08-12 10:47:02

[CF 855E] Salazar Slytherin‘s Locket

搞半天才发现是道板?

2020-08-11 18:34:55

[CF 628D] Magic Numbers

还是得想清楚

2020-08-11 17:24:26

[CF 431D] Random Task

做题好慢啊……

2020-08-11 17:23:34

[CF 821E] Okabe and El Psy Kongroo

湘妹好强啊,天天虐我

2020-08-10 16:30:14

[CF 837D] Round Subset

题目洛谷题解似乎并不难,不知道为啥标了道紫题。首先可以判断出,末尾 000 的个数与选的数中 222、555 的最小值有关。那么定义 dp[i][j][k]:dp[i][j][k]:dp[i][j][k]: 前 iii 个数中选 jjj 个,得到 kkk 个 555,能得到 222 的最大个数然而,发现这不是道 01\tt 0101背包吗,怎么多搞了一维——……好吧,太久没做背包了,都忘记了。所以直接定义 dp[i][j]:dp[i][j]:dp[i][j]: 选 iii 个数,得到 jjj

2020-08-10 15:02:04

浅浅浅谈矩阵乘法

JZM 又AK 了!

2020-08-10 11:32:52

[CF1073E] Segment Sum

似乎就是一道数位dp\tt dpdp的板,只是维数有点多,用状压来开?CodeLL k, a[MAXN], Jw[MAXN];struct node{ LL tot, Sum; node(){} node(LL TOT,LL SUM) { tot = TOT; Sum = SUM; } void Clear() { tot = Sum = 0; } bool Check() { return ~ tot && ~ Sum; }} dp[2][2][MAXN][

2020-08-09 17:48:59

[CF 903F] Clear The Matrix

题目洛谷思路这道题一开始还是挺有思路的。首先,我们一列一列地考虑,因为长度最大为 444,所以每次只考虑一个 4∗44*44∗4的矩形就够了。如果固定了某列,现在的矩形就是一个4∗44*44∗4 的,有 161616 格,用状压 2162^{16}216 存下状态是绰绰有余的。而对于确定下一个左上角填入矩形,对于这个 4∗44*44∗4 矩形的影响也是能够计算出来的。于是定义 dp[i][j]dp[i][j]dp[i][j] 为:前 i−1i-1i−1 列都为 ′.′'.'′.′,以第 iii

2020-08-09 17:39:28

[CF 757D] Felicity‘s Big Secret Revealed

题目洛谷思路定义 dp[i][j]dp[i][j]dp[i][j] 为: 划分到 iii 位,集合元素状态为 jjj 方案数。转移似乎很简单了,向后枚举断点,记录段值。假设断点为 kkk,段值为 ValValVal,即:dp[k][j∣(1<<(Val−1)]+=dp[i][j]dp[k][j |(1<<(Val-1)]+=dp[i][j]dp[k][j∣(1<<(Val−1)]+=dp[i][j]边界为 dp[i][0]=1dp[i][0]=1dp[i][0

2020-08-09 17:11:42

[CF 743E] Vladik and cards

题目戳这洛谷思路似乎想到一个状态,感觉不甚靠谱。正解:似乎和我的思考有一些相似之处,然而我是把出现次数放进 dpdpdp 数组的状态里,这样是不好搞的,这就是我放弃自己思路的原因。而题解里选择的方法是:直接二分这个最少的出现次数——似乎很可行?定义 dp[i][j]dp[i][j]dp[i][j] :考虑前 iii 位,状态(即为数组出现的不可重集)为 jjj 可得到的最长序列长度。满足二分出来的最小长度 xxx。转移似乎很简单了,考虑 xxx 个和 x+1x + 1x+1 个就好了。Cod

2020-08-08 22:18:43

[CF 377C] Captains Mode

洛谷题解首先,只会用到 banbanban 和 pickpickpick,因为 m<=min(n,20)m<=min(n,20)m<=min(n,20)Code#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define MAXM 25#define MAXN (1 <<

2020-08-08 02:12:49

[CF 71E] Nuclear Fusion

洛谷似乎就是一道暴搜题,只是用状态记忆化?时间复杂度似乎不会证。Code:LL n, m;string Names[] = {" ","H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar","K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu","Zn" ,"Ga", "Ge", "As" ,"Se" ,"Br" ,"Kr"

2020-08-06 00:09:31

[CF111C Petya] and Spiders

题目洛谷思路首先,min(n,m)<=6min(n,m)<=6min(n,m)<=6 是很容易判断出来的。于是我想着:这么小的数据范围,能够直接分类讨论吗?但由于是状压dp板块的题,也没有从这方面细想,题解中似乎有分类讨论的做法。想状压dp的做法。由于之前状压dp做得太少,实在是没什么想法。看了题解梳理一下。由于蜘蛛可以往上下左右四个方向走,以及原地待着,我们将题目转化为:在棋盘上选一些点,点可以覆盖上下左右即自身,求最少多少点可以将棋盘完全覆盖。定义 dp[i][k1][k

2020-08-05 15:33:40

[CF 629E] Famil Door and Roads

我选择先写题解再做题。思考阶段我们似乎可以考虑计算:总边数 以及 总长度如果 aaa 与 bbb 有祖先关系?总边数: 似乎是 aaa 的子树内方案数乘 bbb 的子树外方案数? (方案数就是子树大小?)总长度: 这个有点不好算了,难道是: (aaa 的子树内所有路径总长乘 bbb 的子树外方案数)+(bbb 的子树外所有路径总长乘 aaa 的子树内方案数)+(a−ba-ba−b之间链长乘总边数)?如果 aaa 与 bbb 无祖先关系?总边数: 似乎是 aaa 的子树内方案数乘

2020-07-31 16:52:45

[CF 960E] Alternating Tree

每个人也许都有自己不同的做题节奏和方法,做好自己就行

2020-07-31 09:40:06

[CF 1249F] Maximum Weight Subset

题目洛谷题意给定一棵含 nnn 个节点的树,每个节点含一个点权 a[i]a[i]a[i]。现在请你选出一些节点,使得这些节点的权值和最大并且这些节点中任意两个节点的距离都 >k>k>k。并输出这个最大的权值。思路一道似乎有很多时间复杂度做法的题?因为数据规模开的实在是太小了,只有 200200200,所以 n3,n2,nn^3,n^2,nn3,n2,n 都可以过,n4n^4n4 的卡卡也能过?对于很多算法,还没来得及研究,这里讲一种较为常规的 n2n^2n2 的树形 dp\tt

2020-07-30 12:35:16

[CF 734E] Anton and Tree

题目洛谷题意有一棵树,每个点初始有黑白色,每次操作将一个同色连通块颜色翻转——至少多少次翻转能让整张图颜色相同。思路首先,可以想到:一开始可以将同色的连通块缩成一个点——这点很显然,就不说明了。缩点后,得到一张黑白分层图。现在是在这张黑白分层图上得到答案。怎么做呢?给出一个结论——答案为缩点后图的直径加一除以二。即记直径为 ddd,Ans=(d+1)/2Ans=(d+1)/2Ans=(d+1)/2证明现在考虑如何证明这个结论:懒得搞图,就不放图了。——刚刚本来还准备证一番,PPL\tt PP

2020-07-30 10:13:59

查看更多

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