洛谷3258：[USACO2012 MAR]Flowerpot 花盆——题解
https://www.luogu.org/problemnew/show/P2698#sub 老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。 每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着...
【题解】洛谷P1070 道路游戏（线性DP）
次元传送门：洛谷P1070思路一开始以为要用什么玄学优化 没想到O3就可以过了我们只需要设f[i]为到时间i时的最多金币需要倒着推回去 即当前值可以从某个点来那么状态转移方程为：f[i]=max(f[i],f[i-k]+val-cost[now]);now表示从now这个工厂来cost表示在now买...
洛谷 P3695 CYaRon!语 题解 【模拟】【字符串】
大模拟好啊！万一远古计算机让我写个解释器还真是得爆零了呢。题目背景「千歌です」（我是千歌）、「曜です」（我是曜）、「ルビィです」（我是露比）、「3人合わせて、We are CYaRon！ よろしくね！」（三人在一起，我们是CYaRon！多多指教哦！）CYaRon!的三人在学习了编程之后，决定发明一种...
洛谷 P1451 求细胞数量 题解
此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。 题目链接：https://www.luogu.org/problem/show?pid=1451 题目描述一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞,求给定矩形阵列的细...
BZOJ4299 & CC FRBSUM：ForbiddenSum & BZOJ4408 & 洛谷4587 & LOJ2174：[FJOI2016]神秘数——题解
https://www.lydsy.com/JudgeOnline/problem.php?id=4299https://www.lydsy.com/JudgeOnline/problem.php?id=4408https://www.luogu.org/problemnew/show/P4587h...
洛谷 P2872 [USACO07DEC]道路建设Building Roads 题解
P2872 [USACO07DEC]道路建设Building Roads题目描述Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can trave...
洛谷 P2482 loj #2885 [SDOI2010]猪国杀 题解【模拟】【贪心】【搜索】
好玩的模拟题。以后要经常写模拟题鸭题目描述游戏背景《猪国杀》是一种多猪牌类回合制游戏，一共有\(3\)种角色：主猪，忠猪，反猪。每局游戏主猪有且只有\(1\)只，忠猪和反猪可以有多只，每只猪扮演\(1\)种角色。游戏目的主猪 / MP：自己存活的情况下消灭所有的反猪。忠猪 / ZP：不惜一切保护主猪...
【题解】洛谷 P1525 关押罪犯
题目https://www.luogu.org/problemnew/show/P1525思路把所有边sort一遍从大到小排列运用并查集思想敌人的敌人就是朋友从最大边开始查找连着的两个罪犯如果他们在一个监狱就输出并结束程序如果不在就把他们互为敌人存下来如果他们已经有一个敌人了那就把他们敌人和自己合并...
洛谷 P1087 【FBI树】题解
Link 有句话说的好啊，树的题不一定要把树建出来 这题就是这样 这题直接在读入后， 写个递归函数用于二分查找， 然后，， 就没了。。 （貌似太口胡了吧） $ \rm code $ # include <bits/stdc++.h>using namespace std;const in...
洛谷P5463 小鱼比可爱（加强版） 题解
写博客不易，来玩会？这道题我和dalao们的做法略有不同，我用的是归并排序做法qwq归并排序求逆序对大家应该很清楚了，我这里就来讲讲如何用归并排序求出这道题的答案让我们先观察一下规律举个栗子，若存在一组逆序对a[3],a[4]，n = 5，则这组逆序对存在于以下区间内：[ 1 , 4 ] , [ 1...
差分约束详解&&洛谷SCOI2011糖果题解
差分约束系统：如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。——度娘。然而并没有看懂。。...
洛谷P1233 木棍加工题解 LIS
突然发现自己把原来学的LIS都忘完了，正好碰见这一道题。|-_-|\(LIS\)，也就是最长上升子序列，也就是序列中元素严格单调递增，这个东西有\(n^{2}\)和\(nlog_{2}n\)两种算法，其原理我就不多说了。注意，本题的一个要点，就是不下降连续子序列的个数等于最长上升子序列的长度。证明？...
洛谷P2891 Dining P1402 酒店之王【类二分图匹配】题解+代码
洛谷P2891 Dining P1402 酒店之王【类二分图匹配】题解+代码酒店之王题目描述XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。有一天来了n个客人...
洛谷 P1087 【FBI树】题解
Link 有句话说的好啊，树的题不一定要把树建出来 这题就是这样 这题直接在读入后， 写个递归函数用于二分查找， 然后，， 就没了。。 （貌似太口胡了吧） $ \rm code $ # include <bits/stdc++.h>using namespace std;const in...
洛谷 1373 dp 小a和uim之大逃离 良心题解
# 洛谷 1373 dp这题还不算太难，，当初看的时候不是很理解题意，以为他们会选择两条不同的路径，导致整体思路混乱传送门其实理解题意和思路之后还是敲了不短的时间，一部分身体原因再加上中午休息不太好，整个人思路较乱，靠本能打了一遍代码毫无头绪。恢复了一下状态重新开打，才算是A掉题解设dp[i][j]...
【题解】洛谷 P1014 【Cantor表】
1. 我们先引入三角形数的概念： >定数目的点或圆在等距离的排列下可以形成一个等边三角形，这样的数被称为三角形数。>古希腊著名科学家毕达哥拉斯把数1，3，6，10，15，21……这些数量的（石子），都可以排成三角形，像这样的数称为三角形数。>【百度百科】三角形数2. 我们来看看这个...
洛谷P3957 跳房子 题解 二分答案/DP/RMQ
题目链接：https://www.luogu.org/problem/P3957这道题目我用到了如下算法：线段树求区间最大值；二分答案；DP求每一次枚举答案g时是否能够找到 \(\ge k\) 的解法。我们一开始用 \(x[i]\) 和 \(s[i]\) 来表示到起点的距离以及第 \(i\) 个点的...
洛谷P1029 最大公约数和最小公倍数问题 题解
题目链接：https://www.luogu.com.cn/problem/P1029题目描述输入 \(2\) 个正整数 \(x_0,y_0(2 \le x_0 \lt 100000,2 \le y_0 \le 1000000)\) ，求满足下列条件的 \(P,Q\) 的个数。条件：\(P,Q\) ...
洛谷P1108 低价购买题解
看到“你必须用低于你上次购买它的价格购买它”，有没有想到什么？没错，又是LIS，倒过来的LIS，所以我们只要把读入的序列倒过来就可以求LIS了，第一问解决。首先要厘清的是，对于这一题第二问貌似用\(nlog_{2}n\)的算法不是很好，因为我们需要序列中每一个位置可以接成LIS的长度。再看看数据范围...
洛谷10月月赛II题解
咻咻咻令人窒息的洛谷月赛，即将参加NOIp的我竟然只会一道题（也可以说一道也不会），最终145的我只能惨惨的迎接剩下的16天（吧）下面是题解的代码（填坑），神奇的是这四道题都需要DP。参加SXOI的大佬真是tql，此处手动@ljt12138@__stdcallT1找性质，popcnt为1的加上pop...