rprp

分类

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 668人学习

全部文章（共55篇）

「JOISC 2016 Day 2」三明治

「JOISC 2016 Day 2」三明治这题真正让我感受了记搜的强大。我真的没想过搜索可以过\(400\)的啊喂对，\(\text{NOI}\)还可以过\(1e5\)呢解法一个并不显然的\(n^4\)的做法是枚举每一个点，然后上下左右记忆化搜索。考试的时候觉得难打，但是看完别人的代码...

搜索

2020-05-18

0 609

JOISC 2016 Day3 电报

JOISC 2016 Day3 电报前置知识（伪）基环树基环外向树基环内向树此题就是一棵基环外向树。其实这些都没什么用，跟这题没啥关系思路考试的时候不会做，考完才发现自己就差那么一点点... 首先考虑这样一张图：我们的目的是让整个图成为一个环，但是这显...

妙啊基环树

2020-05-18

0 395

CF1093G Multidimensional Queries

这题妙啊。学会了一个新\(trick\)。题解 \[|x_1 - x_2|+|y_1 - y_2| = \\ max (x_1-x_2+y_1-y_2,x_1-x_2-y_1+y_2,-x_1+x_2+y_1-y2,-x_1+x_2-y_1+y_2) = \\max((x_1+y_1)...

线段树位运算妙啊

2020-05-16

0 424

CF1045G AI robots

\(CDQ\)分治的妙题。考虑按视野从大到小排序，那右边的可以看见左边的话左边一定看得见右边的，直接\(CDQ\)就行了。对于这种\([x-K,x+K]\)的区间维护可以在统计的时候差分也可以直接在更新的时候差分。本代码使用后者。 #include <cstdio> #include...

cdq分治

2020-05-15

0 389

CF149D Coloring Brackets

DP神题。。。设\(dp[i][j][0/1/2][0/1/2]\)表示\([i,j]\)这个区间内端点取不染色/染红色/染蓝色三个状态然后转移。一个新\(trick\)就是这里的转移只要考虑这个区间内的串是合法的就可以了 #include <cstdio> #include <...

区间DP

2020-05-15

0 420

CF1175E Minimal Segment Cover

一个很妙的操作，求出每个点通过一条边可以向右边覆盖的最远距离，然后倍增。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R reg...

妙啊倍增

2020-05-15

0 419

UVA10328 Coin Toss

考虑把答案拆成至多有\(n\)张朝上减去至少有\(k-1\)张朝上。显然第一部分的答案就是\(2^n\)，考虑\(DP\)第二部分。设\(dp[i][0/1]\)表示第\(i\)张是反面/正面的情况数。然后有： \[dp[i][0]=dp[i-1][0]+dp[i-1][1] \] ...

动态规划妙啊

2020-05-15

0 422

AT1983 [AGC001E] BBQ Hard

前言学到了一个\(trick\)。对于一个组合数 \(C_{x+y}^x\)可以看成是从\((0,0)\)到\((x,y)\)的路径条数。解法对于这题而言，\(C_{a_i+b_i+a_j+b_j}^{a_i+a_j}\)就表示从点\((0,0)\)到点\((a_i+a_j,b_i+b...

妙啊数学动态规划

2020-05-14

0 520

Luogu P3703 [SDOI2017]树点涂色

Luogu P3703 [SDOI2017]树点涂色用LCT中每一个Splay维护颜色相同的点集，则从一个点到根节点的轻边的条数就是这个点的到根的权值。至于路径查询的搞个差分就好，用树剖实现。至于为什么可以直接这样查，是因为LCT里面涉及子树的权值变化只有access函数。在splay中的子树的...

树链剖分 Link-Cut-Tree

2020-05-13

0 395

NTT板子

#include <cstdio> #include <algorithm> using namespace std; #define R register #define LL long long const int inf=0x3f3f3f3f; const int ...

2020-05-11

0 485