洛谷P4719 【模板】"动态 DP"&动态树分治
【模板】"动态 DP"&动态树分治 第一道动态\(DP\)的题，只会用树剖来做，全局平衡二叉树什么的就以后再学吧所谓动态\(DP\)，就是在原本的\(DP\)求解的问题上加上修改操作，从而使得问题变成动态的问题这道题的问题就是普通的树形\(DP\)上加上了修改点权的操作题意：给定一棵 \(...
洛谷 P3750 - [六省联考2017]分手是祝愿（期望 dp）
题面传送门首先我们需注意到这样一个性质：那就是对于任何一种状态，将其变为全 \(0\) 所用的最小步数的方案是唯一的——考虑编号为 \(n\) 的灯，显然如果它原本是暗着的就不用管它了，如果它是亮着的那就只能通过拉它自己使其变暗，这需要 \(1\) 步操作，并会使所有 \(i\mid n\) 的灯 ...
洛谷P3750 [六省联考2017]分手是祝愿（期望dp）
传送门嗯……概率期望这东西太神了……先考虑一下最佳方案，肯定是从大到小亮的就灭（这个仔细想一想应该就能发现）那么直接一遍枚举就能$O(nlogn)$把这个东西给搞出来然后考虑期望dp，设$f[i]$表示从$i$个正确选项中选择一个正确的变为$i-1$个的期望次数那么$$f[i]=\frac{i}{n...
洛谷 P1223排队接水【贪心】
题目描述有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。输入输出格式输入格式：输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。输出格式：输出文件有两行，...
洛谷 P2622 关灯问题II【状压DP;隐式图搜索】
题目描述现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯...
模板—点分治B(合并子树)（洛谷P4149 [IOI2011]Race）
洛谷P4149 [IOI2011]Race点分治作用（目前只知道这个）：求一棵树上满足条件的节点二元组(u,v)个数，比较典型的是求dis(u,v)（dis表示距离）满足条件的(u,v)个数。算了自己懒得写了，安利几个blog吧：https://www.cnblogs.com/LadyLex/p/8...
「P4996」「洛谷11月月赛」 咕咕咕（数论
题目描述小 F 是一个能鸽善鹉的同学，他经常把事情拖到最后一天才去做，导致他的某些日子总是非常匆忙。比如，时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单：看 iG 夺冠；补月赛题的锅。小 F 虽然经常咕咕咕，但他完成任务也是很厉害的，他一次性可以完成剩余任务的任一非空子集。...
洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows(bitset Floyd)
题意题目链接Sol显然如果题目什么都不说的话需要\(\frac{n * (n - 1)}{2}\)个相对关系然后求一下传递闭包减掉就行了#include<bits/stdc++.h>using namespace std;const int MAXN = 1001;inline int ...
洛谷2114 bzoj3668[NOI2014]起床困难综合症
题目描述21世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因： 在深邃的太平洋海底中，出现了一条名为drd的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。 ...
洛谷P1108 低价购买[DP | LIS方案数]
题目描述“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一...
洛谷P2574 XOR的艺术
题目描述\(AKN\)觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下1、 拥有一个伤害串为长度为\(n\)的\(01\)串。2、 给定一个范围\([l,r]\)，伤害为伤害串的这个范围内中\(1\)的个数3、 会被随机修改伤害串中的...
洛谷 P2574 XOR的艺术(线段树 区间异或 区间求和)
To 洛谷.2574 XOR的艺术题目描述AKN觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下1、 拥有一个伤害串为长度为n的01串。2、 给定一个范围[l,r]，伤害为伤害串的这个范围内中1的个数3、 会被随机修改伤害串中的数值，...
l洛谷 P2326 AKN’s PPAP
P2326 AKN’s PPAP题目描述“I have a pen,I have an apple.Eh,Apple-Pen!.I have a pen,I have pineapple.En,Pineapple-Pen!Apple-Pen,Pineapple-Pen.Eh,Pen-Pineappl...
[洛谷P4340][SHOI2016]随机序列
题目大意：有$n(n\leqslant10^5)$个数，每两个数之间可以加入$+-\times$三种符号，$q(q\leqslant10^5)$次询问，每次询问修改一个数后，所有表达式可能的值的和题解：发现任意一个表达式，把所有的$+-$取反，后面的值为相反数，相互抵消，而第一项的连乘，符号一定是正...
bzoj 4597||洛谷P4340 [Shoi2016]随机序列
https://www.lydsy.com/JudgeOnline/problem.php?id=4597https://www.luogu.org/problemnew/show/P4340妄图直接暴力维护一堆东西，以直接维护题目要求的值（具体见代码...）最后花了2个小时维护完了，A掉了，然而好...
[洛谷U990]传递游戏（90分）
【题目描述 Description】n个人在做传递物品的游戏,编号为1-n。游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；...
洛谷 P1903 [国家集训队]数颜色 / 维护队列
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：1、 \(Q\) \(L\) \(R\)代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。2、 \(R\) \(P\) \(Col\)把第P支画笔替换为颜色\(Col\)。为了满足墨...
洛谷P4823 拯救小矮人 [TJOI2013] 贪心+dp
正解:贪心+dp解题报告:传送门!我以前好像碰到过这题的说,,,有可能是做过类似的题qwq?首先考虑这种显然是dp?就f[i][j]:决策到了地i个人,跑了j个的最大高度,不断更新j的上限就得到答案了(显然i可以省略但为了表述更清晰一点就懒得省辣?然后这时候就考虑一个问题,就是,dp的要求是无后效性...
洛谷P2670扫雷游戏题解
题目这道题是一个简单的模拟搜索题，可以把每个雷的位置都记作1。这样就可记录出数字啦#include<iostream>#include<cstring>using namespace std;int n,m;char a;bool b[10000][11000];int i ...
洛谷P1155 双栈排序题解(图论模型转换+二分图染色+栈)
洛谷P1155 双栈排序题解(图论模型转换+二分图染色+栈)标签：题解阅读体验：https://zybuluo.com/Junlier/note/1311990原题地址：洛谷P1155 双栈排序那么讲题了很好的一道图论模型转化的题目考虑什么情况下两个元素一定要放在不同的栈内经过一番仔细思考+草稿模拟...