BZOJ 1497 [NOI2006]最大获利 ——网络流
【题目分析】最大权闭合子图。S到集合1容量为获利的大小，集合2到T为所需要付出的相反数。然后求出最大流，然后用总的获利相减即可。【代码】#include <cstdio>#include <cstring>#include <cmath>#include <...
BZOJ 1415: [Noi2005]聪聪和可可 [DP 概率]
传送门题意：小兔子乖乖~~~题意·真：无向图吗，聪抓可，每个时间聪先走可后走，聪一次可以走两步，朝着里可最近且点编号最小的方向；可一次只一步，等概率走向相邻的点或不走求聪抓住可的期望时间和游走很像，只不过这道题限制了一个人走的方向，两人间的距离具有了阶段性!可以直接$DP$求期望一般倒推$f[i][...
1064: [Noi2008]假面舞会 - BZOJ
Description一年一度的假面舞会又开始了，栋栋也兴致勃勃的参加了今年的舞会。今年的面具都是主办方特别定制的。每个参加舞会的人都可以在入场时选择一 个自己喜欢的面具。每个面具都有一个编号，主办方会把此编号告诉拿该面具的人。为了使舞会更有神秘感，主办方把面具分为k (k≥3)类，并使用特殊的技术...
BZOJ3670 [Noi2014]动物园
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！Description近日，园长发现动物园中好吃懒做的动物越来...
【BZOJ 1492】【NOI 2007】货币兑换Cash
这是道CDQ分治的例题：$O(n^2)$的DP：f [1]←S* Rate[1] / (A[1] * Rate[1] + B[1]) Ans←SFor i ← 2 to nFor j ←1 to i-1x ← f [j] * A[i] + f [j] / Rate[j] * B[i]If x>...
【刷题】BZOJ 4945 [Noi2017]游戏
Descriptionhttp://www.lydsy.com/JudgeOnline/upload/Noi2017D2.pdfSolution字符串里的'x'看起来很烦，于是考虑枚举这些'x'的情况。这里只要枚举'a'和'b'就行了，因为如果存在解的话，肯定包含了解那么在枚举之后，每场比赛两个点，...
uoj #5. 【NOI2014】动物园 kmp
#5. 【NOI2014】动物园Time Limit: 20 SecMemory Limit: 256 MB题目连接http://uoj.ac/problem/5Description近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭...
BZOJ 4945 NOI2017 游戏 搜索+2-SAT
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4945分析：首先考虑没有x的情况，发现有一个明显的推理模型，容易看出来可以用2-SAT做。然后考虑有x的情况，发现最多只有8个x，不难想到可以搜索每个x为a,b,c中的哪个然后跑2-SAT。...
●BZOJ 3672 [Noi2014]购票
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3672题解：斜率优化DP，点分治（树上CDQ分治...）这里有一个没有距离限制的简单版：BZOJ 1767 [Ceoi2009]harbingers定义$DP[i]$为从i出发到1号点的最小花费，...
洛谷1196【NOI2002】题解
题目描述公元五八○一年，地球居民迁至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威利擅...
BZOJ_4197_[Noi2015]寿司晚宴_状态压缩动态规划
BZOJ_4197_[Noi2015]寿司晚宴_状态压缩动态规划Description为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。在晚宴上,主办方为大家提供了 n−1 种不同的寿司，编号 1,2,3,…,n−1，其...
NOI2018准备Day5
3个半小时，连看题解带超过了一道二分题。
NOI2001 方程的解数（双向搜索）
solution一道非常经典的双向搜索题目，先将前3个未知数枚举一遍得到方程的前半部分所有可能的值，取负存入第一个队列中再将后3个未知数枚举一遍，存入第二个队列中。这样我们只要匹配两个队列中相同的元素即可使方程为零。方法：将两个队列排序，用尺取法+乘法原理扫一遍即可。=>code：#inclu...
线性规划||网络流(费用流)：COGS 288. [NOI2008] 志愿者招募
[NOI2008] 志愿者招募输入文件：employee.in 输出文件：employee.out 简单对比时间限制：2 s 内存限制：512 MB【问题描述】申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批...
bzoj2876 [NOI2012]骑行川藏（拉格朗日乘数法）
题目描述蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限，因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。由于蛋蛋装备了一辆非常好的自行车，因此在...
洛谷P4770 [NOI2018]你的名字 [后缀自动机，线段树合并]
传送门思路按照套路，直接上后缀自动机。部分分：\(l=1,r=|S|\)首先把\(S\)和\(T\)的后缀自动机都建出来。考虑枚举\(T\)中的右端点\(r\)，查询以\(r\)结尾的串最长可以往左延伸多长，使得它仍然是\(S\)的子串。记该长度为\(lim_r\)。\(lim_r\)可以在\(SA...
bzoj 2435: [Noi2011]道路修建
Description在 W 星球上有 n 个国家。为了各自国家的经济发展，他们决定在各个国家之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬，他们只愿意修建恰好 n – 1条双向道路。 每条道路的修建都要付出一定的费用， 这个费用等于道路长度乘以道路两端的国家个数之差的绝对值。例如，在...
BZOJ2007——[Noi2010]海拔
1、题意：一个裸的最小割2、分析：直接转成对偶图最短路就好了，水爆了！（雾）#include <queue>#include <cstdio>#include <cstdlib>#include <cstring>#include <algori...
2433: [Noi2011]智能车比赛 - BZOJ
Description新一届智能车大赛在JL大学开始啦！比赛赛道可以看作是由n个矩形区域拼接而成（如下图所示），每个矩形的边都平行于坐标轴，第i个矩形区域的左下角和右上角坐标分别为(xi,1,yi,1)和(xi,2,yi,2)。题目保证：xi,1<xi,2=xi+1,1，且yi,1< y...
BZOJ 2435：[Noi2011]道路修建（树型DP）
http://www.lydsy.com/JudgeOnline/problem.php?id=2435题意：中文题意。思路：很简单的树形DP，sz记录儿子有多少个和cur记录走的哪条弧，然后直接算就可以了。（时间有点紧）。 #include <cstdio> #include <...