- 博客(33)
- 资源 (1)
- 收藏
- 关注
RSS订阅
原创 CSP-S 考后反思
CSP-S 考后反思背景被初二的同学吊打导致自己心态崩溃！！！考试情况Day1：进考场的时候，非常自信无比，听到temp一句"今天的题并不难，比您们平时打的模拟还要简单！"试机然后进了考场，一看键盘，傻眼了，从左往右，从上往下：ABCDE…于是立马找了老师换了键盘，试了一下，不习惯。接着几乎用一指禅打完了模板，给个解压密码:RenZhenSiKaoT1打开题目，一看T1好简...
2020-04-02 17:50:53
1011
4
原创 CF362D Fools and Foolproof Road Solutions
这是一道用并查集维护，优先队列进行合并的题题目链接(luogu)CodeForces题意给定 nnn 个点 mmm 条边的无向图，问是否能在图里添加 ppp 条边使得加边后存在恰好 qqq 个连通分量，同时请求出边权总和最小的方案。新增边的两点若在同一个连通块则边权为1000，否则为 min(109,S+1)min(10^9, S+1)min(109,S+1) ， 其中 SSS 为这条边连接的两个联通块的边权之和。若存在方案，输出"YES"及任意一个边权和最小的方案；否则输出"NO"。可以重边
2020-08-17 10:36:24
233
原创 CF455C Civilization Solution
这是一道并查集的简单维护题题目链接(luogu)CodeForces题意给出一棵森林，有两种操作1。1 ^。1。 给出点 xxx，输出点 xxx 所在的树的直径2。2 ^。2。 给出点 x,yx,yx,y，（如果 x,yx,yx,y 在同一棵树中则忽略此操作）选择任意两点 u∈xu \in xu∈x所在子树， v∈yv \in yv∈y所在子树 ，将 u,vu,vu,v 之间连一条边，使得连边后的到的新树的直径最小。思路首先考虑查询操作：我们用两遍 dfsdfsdfs 求出每一颗子树树的直
2020-08-17 09:23:01
159
原创 CF319C Kalila and Dimna in the Logging Industry Solution
这是一道单调队列的板题题目链接(Luogu)Codeforces题意伐木工人用电锯伐木，一共需要砍nnn棵树，每棵树的高度为aia_iai，每次砍伐只能砍111单位高度，之后需要对电锯进行充电，费用为当前砍掉的树中最大ididid的bidb_{id}bid值题目保证a[1]=1,b[n]=0，a[i]<a[i+1]，b[i]>b[i+1] (i<j)题目保证a[1] = 1 , b[n] = 0，a[i]<a[i+1]，b[i]>b[i+1]\ (i &
2020-08-12 10:46:04
826
2
原创 CF54C First Digit Law Solution
今天整一道概率dp的题来做题目链接(luogu)codeforces题目大意给一个数nnn，然后给出nnn行，每行lil_ili，rir_iri，代表第iii个数在区间[li,ri][l_i,r_i][li,ri]中，求一个概率使得这nnn个数中有kkk%的数是111开头的。题目思路啊哈，一看到这个概率，就想到了那段黑暗的时光咳咳咳，回到正题首先对于这个区间[l,r][l, r][l,r]之间的数我们可以用差分的方式将它们开头是111的概率求出来令dp[i]dp[i]dp[i]表示
2020-08-11 09:56:45
169
原创 CF1312E Array Shrinking（区间dp模板）
题目链接(洛谷)CodeForces这是一道区间dp的板题题意给定一个数组，每一次对于两个相邻的数，如果他们相等，则可以将它们合并为一个数，其值为原数+1+1+1，求原数组合并完后的最小长度。思路首先看到这种描述，我们就可以想到区间dp区间dp的模板：dp[i][j]=min(dp[i][k]+dp[k+1][j]+w[i])（w[i]随题目改变）区间dp的模板：dp[i][j] = \min(dp[i][k] + dp[k + 1][j] + w[i])（w[i]随题目改变）区间dp的模板
2020-07-28 11:48:16
960
原创 CF620D Professor GukiZ and Two Arrays Solution
这是一道有一点费脑子的简单题题目链接(洛谷)CodeForces题意给出两个长度为nnn的数列aaa,bbb，求任意交换两个数列中相同位置的数后(至多两次)，∣Suma−Sumb∣|{Sum_a-Sum_b}|∣Suma−Sumb∣的最小值思路因为这个交换次数很少，只有222，以及这个nnn的值同样很小，只有200020002000，所以我们将这个问题拆开来看：1。1^。1。考虑不交换，直接输入的时候累加一个sumasumasuma和sumbsumbsumb，然后做一个减法，fabsfa
2020-07-26 11:06:45
220
原创 CF248D Sweets for Everyone! Solution
题目链接（洛谷）CodeForces这是一道二分加贪心题题意在一条路上有若干个店和房子，每个房子要放一个糖果，每经过一个商店可以得到一个一个糖果。现在我们开始可以携带kkk个糖果，要求在ttt时间内完成，求这个kkk的最小值。思路在这个题中，我们可以二分这个kkk值，然后考虑怎么验证可行性。首先一定是有糖肯定会给，然后再看如果当没有糖果时，是采取拿到满足之前的糖果数后就返回送糖果，还是最后一口气拿到足够的再返回。如图：画图技巧有限，望海涵那么在check()check()check(
2020-07-24 16:26:12
192
原创 CF1132D Stressful Training Solution
题目链接（洛谷）CodeForces这是一道裸的二分题题意有n个电脑，每个电脑有aia_iai的电，每个电脑一分钟用bib_ibi的电，每次可以给一个电脑充xxx的电，电脑最后一次的电可以是负数，但必须满足前一次每台电脑的电都是正数，一共要坚持kkk分钟.n,ai,bi,kn,a_i,b_i,kn,ai,bi,k均给出，求xxx的最小值.思路这种题，看到就会想到要二分这个xxx的值，那么接下来就考虑如何check()check()check()这个这个x值.考虑使用一个优先队列，按照
2020-07-24 15:50:35
305
原创 CF949D Curfew solution
题目链接今天给大家整点二分加贪心的题题意这个题是说在一个走廊上有n个房间，2个宿管从两端向中间查询，当宿管发现房间里的人数不足b个时，就记录下并锁门，两个宿管各自记录一边的，特别的，当n为奇数时，左边的宿管多查一个房间，求两个宿管记录数最大值的最小值。（P&S：当人数多于b个时，学生可以藏在床底下以躲过宿管的查房）思路像这种题，一看就是个二分题，那么我们该怎么验证可行性呢？很容易想到如果一个房间不能满足，那么我们的最优策略就是留下一个空房间，将人往中间集中所以可以得到中间一定满足的是一
2020-07-24 15:29:33
380
原创 新Nim游戏
题目题意给定nnn堆石子，两个人可以各取走任意堆石子，但不能取完，可以不取。接下来和NimNimNim游戏规则一样，询问是否有先手必胜策略。思路关于一般NimNimNim博弈游戏有这样一个结论：a1⊕a2⊕...⊕an!=0a_1\oplus a_2\oplus ... \oplus a_n!=0a1⊕a2⊕...⊕an!=0，那么先手必胜，反之如果等于0，先手必败我们从先手的角度看：如果我是先手，我一定不会给后手把剩余集合异或值改成000的机会（因为后手拿掉一些元素后可能把剩余集合的异或
2020-05-13 15:28:06
756
原创 HDU5226 Tom and matrix题解
题目链接题目意思求∑i=x1x2∑j=y1y2Cij\sum^{x2}_{i = x1} \sum^{y2}_{j = y1} C^j_i∑i=x1x2∑j=y1y2Cij推导过程∑i=abCki=Ck+1b+1−Ck+1a\sum^{b}_{i = a}C^i_k = C^{b+1}_{k + 1}-C^{a}_{k + 1}∑i=abCki=Ck+1b+1−Ck+1a证...
2020-04-22 15:38:19
324
原创 Luogu P3803 多项式乘法(ntt版)
题目链接思路相信大家都已经学会了FFTFFTFFT，若不会，请看这篇博客一个同学写的，自认为不错在我们的FFTFFTFFT中，我们使用了复数来进行计算但是我们可以发现复数的乘法时间复杂度是O(4)O(4)O(4)而doubledoubledouble的计算则更加增添了时间复杂度同时因为浮点数计算 \sqrt{\ \ \ } &n...
2019-12-18 20:59:51
1214
2
原创 【代码】洛谷P3380 二逼平衡树
题目链接代码#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>#include <cctype>#include <map>#include <set>#include <vector>#...
2019-12-04 15:48:27
777
原创 洛谷AT2444 JOIOI 王国题解
题目链接亲测可以通过\color{orange}{亲测可以通过}亲测可以通过题意JOIOIJOIOIJOIOI王国是一个HHH行WWW列的长方形网格，每个1×11\times11×1的子网格都是一个正方形的小区块。为了提高管理效率，我们决定把整个国家划分成两个省JOIJOIJOI和IOIIOIIOI。我们定义，两个同省的区块互相连接，意为从一个区块出发，不用穿过任何一个不同省的区块，就...
2019-11-30 17:16:22
982
1
原创 HDU6546 Function题解
文章目录题目链接题意数据范围思路代码Thanks!题目链接实测可以通过！\color{orange}{实测可以通过！}实测可以通过！题意wlswlswls有nnn个二次函数fi(x)=aix2+bix+ci (1≤i≤n)f_i(x)=a_ix^2+b_ix+c_i\ (1\le i\le n)fi(x)=aix2+bix+ci (1≤i≤n)现在他想在∑i...
2019-11-30 16:03:06
850
1
原创 THUPC_2017玩游戏Game题解
文章目录题目链接题意思路注意事项代码Thanks!题目链接题意ljccljccljcc和他的学妹在玩游戏，这个游戏共有nnn轮，在第iii轮获胜会获得iii分，没有平局。现在给出ljccljccljcc和学妹的得分，求是否有一种方案符合当前得分。思路首先我们可以知道，学妹和jzmjzmjzm的分数之和一定是一个可以表示为n(n+1)2的数\frac{n(n+1)}{2}的数2n(n+1...
2019-11-30 15:22:59
1072
3
原创 洛谷P3835 可持续化平衡树题解(非旋Treap)
题目链接题意您需要写一种数据结构(可参考题目标题),来维护一个可重整数集合,其中需要提供以下操作,(对于各个以往的历史版本):case 1: 插入xxx数case 2: 删除xxx数(若有多个相同的数，因只删除一个)case 3: 查询xxx数的排名(排名定义为比当前数小的数的个数+1+1+1)case 4: 查询排名为xxx的数case 5: 求xxx的前驱(前驱定义为小于xxx,...
2019-11-29 16:13:32
931
4
原创 洛谷P3369 普通平衡树题解(非旋Treap)题解
P3369普通平衡树题解(非旋Treap)题意您需要写一种数据结构，来维护一些数，其中需要提供以下操作：case 1: 插入xxx数case 2: 删除xxx数(若有多个相同的数，因只删除一个)case 3: 查询xxx数的排名(排名定义为比当前数小的数的个数+1+1+1)case 4: 查询排名为xxx的数case 5: 求xxx的前驱(前驱定义为小于xxx,且最大的数)case...
2019-11-28 20:56:55
1052
原创 Black Box题解
Black Box题解题目题意有以下两种操作:add(x)add(x)add(x): 把xxx存入get:i++get: i++get:i++，然后输出第iii小的数现在给你一个长为MMM的addaddadd操作序列AAA，NNN个时间点序列BBB，要求在每个BiB_iBi时执行一次getgetget操作，求输出结果序列思路直接按照要求在第iii个时刻插入一个aia_iai然...
2019-11-27 15:02:54
974
2
原创 营业额统计 题解
营业额统计 题解题面思路每插入一个数从前后找最小的数即可最后一个求和搞定。#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>#include <cctype>#include <map>#include <...
2019-11-26 19:44:29
1241
原创 Tyvj 1728 普通平衡树题解
Tyvj 1728 普通平衡树链接暂时不懂，直接贴板子，作为回顾的记录吧！#include <cstdio>#include <cstring>#include <algorithm>#include <cstdlib>#include <cctype>#include <map>#include <s...
2019-11-25 16:42:40
795
2
原创 sum 题解
sum 题解题目题目大意这道题就是x1+x2+x3+···+xn=N,求有几种组合方法。思路利用数学方法中的“隔板法”，不难知道结果就是Cn−10+Cn−11+Cn−12+⋅⋅⋅+Cn−1r+⋅⋅⋅+Cn−1n−1C_{n-1}^0+C_{n-1}^1+C_{n-1}^2+···+C_{n-1}^r+···+C_{n-1}^{n-1}Cn−10+Cn−11+Cn−12+⋅⋅⋅+C...
2019-11-24 10:38:34
819
原创 super a ^ b mod c问题
super ab mod csuper\ a^b\ mod\ csuper ab mod c题目大意：给定一个整型a, 数组b, 模数c, 求ab mod ca^b\ mod\ cab mod c考察对欧拉定理的降幂应用，直接将每一位都进行取模即可代码如下:#include <cst...
2019-11-24 10:09:28
769
原创 欧拉函数及定理浅谈
欧拉函数及定理浅谈什么是φ\varphiφ(欧拉函数)φ(x)\varphi(x)φ(x)是指在1→x−11 \rightarrow x-11→x−1中与x互质的数。我们先不说它有什么用处，先来讲一讲求法。少量或数据较大的求法 ⟶\longrightarrow⟶ 时间复杂度O(n)O(\sqrt{n})O(n)代码如下：int phi(int x){ int res = x...
2019-11-24 10:07:30
807
原创 洛谷P2824 [HEOI2016/TJOI2016]排序 题解
洛谷P2824 [HEOI2016/TJOI2016]排序 题解题目在此题目描述在 2016 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。这个难题是这样子的：给出一个 1 到 nnn 的排列，现在对这个排列序列进行 mmm 次局部排序，排序分为两种：0 lll rrr 表示将区间 [lll,rrr] 的数字升序排序1 ...
2019-11-12 21:31:36
730
2
原创 洛谷P1061 Jam的计数法题解
洛谷P1061 Jam的计数法题解题目在此题目描述Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，...
2019-11-12 21:20:14
834
2
原创 消防局的设立题解
[HNOI2003]消防局的设立 题解题目描述2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只...
2019-10-22 20:32:59
821
原创 矩阵加速浅谈
【矩阵加速】矩阵是什么呢，就是一个由n * m的方阵的二维数组，那么，我们的矩阵到底有什么用呢？且听分解：相信大家都听说过矩阵加速的吧，矩阵加速就是通过快速幂的方法，将O(n)的时间复杂度降到O(logn)，在一些题目中可以起到意想不到的作用！矩阵乘法首先要想使用矩阵快速幂，我们就需要知道什么是矩阵乘法。看这里，百度解释若是无法忍受百度的说法的话，我精简了一下，矩阵乘法就是：设A为 ...
2019-07-27 19:38:48
1666
原创 Luogu P1879玉米田题解
题目在这里喔题目描述农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。John想知道，如果不考...
2019-07-20 09:39:56
977
2
原创 COCI Tuna题解
题目描述渔夫sime昨晚抓住了N条金枪鱼。在一个特殊的app的帮助下，他将它们卖给一家专门收购优质鱼的日本著名公司。app是以何种方式估算金枪鱼的价值的呢？根据金枪鱼的照片，app返回两个估计价值，P1和P2。如果两个估值之间的差异小于或等于X，则采用更高的那个估值。如果差值大于X，则app返回第三个估计价值P3，然后将该估值作为金枪鱼的最终价值。编写一个程序，根据app给这每条金枪鱼的估值（有...
2019-07-18 21:30:03
850
原创 [HZOI] 弹药科技
题目描述经过精灵族全力抵挡，精灵终于坚持到了联络系统的重建，于是精灵向人类求助，大魔法师伊扎洛决定弓}用博士的最新科技来抗敌。伊扎洛:“博士，还没好吗?”博士:“只差一步了!只需要在正确的位置装上弹药就可以了!”博士的最新科技是全新的炸弹，但是现在还需要一步装弹药的操作。博士的炸弹有N!个位置可以装弹药(>.<)，但是只有在正确的位置装上弹药才能启动，博士将装弹药的位置编...
2019-04-10 14:00:10
874
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人