洛谷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 <...
bzoj千题计划129：bzoj2007: [Noi2010]海拔
http://www.lydsy.com/JudgeOnline/problem.php?id=20071、所有点的高度一定在0~1之间，如果有一个点的高度超过了1，那么必定会有人先上坡，再下坡，一定不如一直上坡优2、所有点高度一定可以转化为非0即1比如：0->0.3->0.5->...
BZOJ1565: [NOI2009]植物大战僵尸
DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。Sample Input3 210 020 0-10 0-5 1 0 0100 1 2 1100 0Sample Output25HINT在样例中, 植物P1,...
Beta Round ＃9 (酱油杯noi考后欢乐赛)PLQ和他的小伙伴们
题目：http://www.contesthunter.org/contest/Beta%20Round%20%EF%BC%839%20%28%E9%85%B1%E6%B2%B9%E6%9D%AFnoi%E8%80%83%E5%90%8E%E6%AC%A2%E4%B9%90%E8%B5%9B%29/...
loj#2305. 「NOI2017」游戏 2-sat
链接https://loj.ac/problem/2305https://www.luogu.org/problemnew/show/P3825思路3-sat神马的就不要想了，NP问题除去x每个点只有两种可能，2-satx只有8个，\(3^n\)暴力枚举哪个不选2-sat是对称性的当起点x的战车不存...
【BZOJ2434-[Noi2011]】阿狸的打字机（AC自动机（fail树）+离线+树状数组）
Description阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。经阿狸研究发现，这个打字机是这样工作的：l 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。l 按一下印有'B'的按...
BZOJ.1492.[NOI2007]货币兑换(DP 斜率优化 CDQ分治/Splay)
BZOJ洛谷如果某天能够赚钱，那么一定会在这天把手上的金券全卖掉。同样如果某天要买，一定会把所有钱花光。那么令\(f_i\)表示到第\(i\)天所拥有的最多钱数（此时手上没有任何金券），可以选择什么都不干，\(f_i=f_{i-1}\)；也可以从之前的某一天\(j\)花\(f_j\)的钱买金券，在第...
【数论】【莫比乌斯反演】【线性筛】bzoj2005 [Noi2010]能量采集
http://blog.csdn.net/Clove_unique/article/details/51089272Key：1、连接平面上某个整点（a,b）到原点的线段上有gcd（a,b）个整点。2、欧拉函数的性质之一：若(N%a==0 && (N/a)%a==0) 则有:phi(N...
[BZOJ]4199 品酒大会(Noi2015)
讲道理是后缀数组裸题吧，虽然知道后缀数组的原理但是小C不会写是什么鬼。。小C趁着做这题的当儿，学习了一下后缀数组。网络上的后缀数组模板完全看不懂怎么破，全程照着黄学长的代码抄，感觉黄学长写得还是很优雅的。求LCP的部分已经崩坏了，小C自己脑补的做法是。。倍增？？看到正确的写法之后小C内心是绝望的，大...
【BZOJ】【2005】【NOI2010】能量采集
欧拉函数玛雅，我应该先看看JZP的论文的……贾志鹏《线性筛法与积性函数》例题一这题的做法……仔细想下可以得到：$ans=2*\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)-n*m$那么重点就在于算$\sum_{a=1}^n\sum_{b=1}^m gcd(a,b)$这个东西cop...
BZOJ5418 NOI2018屠龙勇士（excrt）
显然multiset求出每次用哪把剑。注意到除了p=1的情况，其他数据都保证了ai<pi，于是先特判一下p=1。比较坑的是还可能存在ai=pi，稍微考虑一下。剩下的部分即解bix≡ai(mod pi)方程组。没有保证模数互质，于是excrt一发。excrt实际上就是不停exgcd合并两个方程。...
[BZOJ4200][Noi2015]小园丁与老司机
4200: [Noi2015]小园丁与老司机Time Limit: 20 Sec Memory Limit: 512 MBSec Special JudgeSubmit: 106 Solved: 58[Submit][Status][Discuss]Description小园丁 Mr. S 负...
BZOJ1565 [NOI2009]植物大战僵尸（拓扑排序 + 最大权闭合子图）
题目Sourcehttp://www.lydsy.com/JudgeOnline/problem.php?id=1565DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。Sample Input3 210 02...
【NOI2018】
总之国赛已经过了1个月了。感谢北大当初给我的一本约救我狗命，不然国赛就要没学上了。铜牌倒数十多名，我觉得我也是混到了一种境界。虽然对于集训队已经失去梦想，但是，Day1全场堪称最低的21分，也是有点过分了吧？多组数据，万万没想到啊……我简直石乐志，雅礼考了10天的捆绑，让我以为全世界都是捆绑？还是我...
NOI2005维修数列 splay
好题，错了不知道多少遍。这题其他几个操作都是比较经典的，多了一个最大子序列的。这时候对于当前的区间，最大子序列，可能使左区间的最值，可能是右区间的最值，也可能是整个区间的。所以维护lx[],rx[],mx[]。lx[rt] = max(lx[l],sum[l]+key[rt]+max(0,lx[r]...
解题：NOI 2010 航空管制
题面常见的套路与不常见的套路第一问是常见的套路，建反边用优先队列跑拓扑排序第二问是不常见的套路，如何判断一个点最早什么时候起飞？先不加它来拓扑排序，直到拓扑排序不能进行下去了，这个时刻就是它必须加入的时刻。因为我们是反着做的，所以这样求出来的就是最早时刻。 // luogu-judger-enabl...