rprp

分类

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

/ 注册

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

1篇文章 672人学习

全部文章（共9篇）

Luogu P4511 CTSC 2015 日程管理

正题一开始的时候显然第\(i\)天以前可以放\(i\)个任务是吧，然后考虑用一棵线段树维护这个数量，设每天的这个值为\(lev(i)\) 考虑在\(t\)这个截止时间位置放了一个任务，那\((t,n)\)这个区间的$ lev(i)$ 都要减去\(1\)。　　插入设插入的终止时间为\(t...

set 线段树妙啊

2020-04-30

0 543

Luogu P3631 【[APIO2011]方格染色】

T15 Apio2011 方格染色 20分算法：暴力枚举每个点抄题解做的还是好好写总结吧把红色视为0，蓝色视为1 假设有一个表格如下： A C E G B D F H ...

并查集位运算妙啊

2020-04-30

0 716

Luogu AT2557 【Ball Coloring】

题目大意：有n对数字，让你将这n对数字染色成红的或蓝的，求\((Rmax-Rmin)*(Bmax-Bmin)\) \(n<=2e5,0<a<=1e9\) 解题过程: 还是luogu比较香..... 在atcode上不会做今天用luogu看就会了是什么鬼... (难道我的水平...

线段树妙啊

2020-04-30

0 423

Luogu P4151 [WC2011]最大XOR和路径

原题传送门看见异或最值，估计线性基跑不了了。考虑先随便提出一条从\(1\)到\(n\)的路径，这显然不一定是最优的，但是可以让它变强。比如可以让它中间插入一个环来让它变优。比如说有一条路径: \(1->A->B->C->N\) 可以补成： \(1->A->B-...

线性基妙啊

2020-05-02

0 420

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

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 424

CF1175E Minimal Segment Cover

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

妙啊倍增

2020-05-15

0 420

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 425

JOISC 2016 Day3 电报

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

妙啊基环树

2020-05-18

0 395