RK_little

题解

翻译(1)

/ 注册

全部文章 / 题解（共38篇）

2022 牛客多校第一场题解(ACDGIJ)

A - Villages: Landlines 题意简述，给出一些区间，求取最多添加多长的区间使得这些区间合并。非常简单，按题意模拟即可。 #include <algorithm> #include <iostream> #include <vector> u...

并查集递归数组

2022-07-27

0 415

Promising String

Promising String 题意给出一个仅仅包含'+' '-'的字符串，我们可以将两个连续的'-',合并为'+'。求其所有子串经历变换后 '+' 的数量等于 '-' 的数量的个数。思路假若，我们有一段连续的序列了，其中有 x 个 '+' , y 个 '-'。那么我们如果想要成立的话...

前缀和树状数组

2022-04-01

0 548

ICPC 46th nanjing D Paimon Sorting

ICPC 46th nanjing D Paimon Sorting 题意如下所示的循环中 for (int i = 1 ; i<= n ; i ++ ) { for (int j = 1 ; j <= n ; j ++ ) { if(a[i] < a[j])...

构造

2022-03-31

0 1002

46th ICPC 南京 C. Klee in Solitary Confinement

C. Klee in Solitary Confinement 题意给出一个数组，我们可以选择一段区间加上 k (或者不加)。求出现次数最多的数出现了几次。思路对于一段区间加上 k 的话。我们不妨考虑最多的数为 a[i] + k 的情形。我们敲定区间 [L , R] 我们最优的方案一定是刚...

前缀和

2022-03-30

0 951

SP3267 D-query

SP3267 D-query 题意给出一段序列。求取区间范围[l,r] 中的序列出现的次数。思路足够详细的博文这个题目最好的方法是采用前缀和的方式离线查询。不过，为了学习莫队算法，这个题目主要用来讲解莫队算法该如何工作。首先，我们对于区间 [l,r] 的查询，由于我们可以通过改变区间的方...

莫队

2022-03-29

0 526

G - Range Pairing Query

G - Range Pairing Query 题意有 n 个人站成一排，每个人的身上都有一个数字 c。求问区间 [l,r] 范围内共有多少个颜色一样的对。思路这题大概是一个裸的莫队采取另外一种方法。首先，我们采取离线的方式进行写题。我们通过前缀和的方式进行更新我们的答案，并且我们的前缀...

莫队前缀和分类讨论

2022-03-29

0 434

D. K-good

D. K-good 极为简单，却未能想出。重点记录题意给定一个整数 n 求是否能够用 kkk 个模 k 不同的数组成一个该数。思路我们发现对于这 n 个数而言，可以简单的缩略成一个式子。 n=ks+k∗(k+1)22×n=k×(k+2s+1)n = ks + \frac {k*(k + ...

数学

2022-03-25

1 1096

D. For Gamers. By Gamers.

D. For Gamers. By Gamers. 记录一下今晚状态极差的比赛。思路我们首先以 t 为时间线划分。士兵如果要打败怪物，kd×t≥Hkd\times t \ge Hkd×t≥H 。同理，怪物要打败士兵则需要D×t≥hD\times t\ge hD×t≥h。我们发现都有共同的 ...

数学二分

2022-03-23

2 615

P5904 [POI2014]HOT-Hotels 加强版

P5904 [POI2014]HOT-Hotels 加强版题意求在一个树内有多少个三元组(i,j,k)(i,j,k)(i,j,k)满足 dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k)dis(i,j)=dis(i,k)=dis(j,k) 思...

长链剖分树形DP

2022-03-16

0 386

46th ICPC 上海 D Strange Fractions

Strange Fractions 题意在规定的范围内求解整数 a , b 满足 ab+ba=pq\frac a b + \frac b a = \frac p qba+ab=qp 思路这个题目让我来做的话，可能就暴毙了。首先我们来看几个对这个题目而言很重要的性质。 ppp qqq ...

数学素数筛

2022-03-16

1 747