洛谷 P1486 BZOJ 1503 NOI 2004 郁闷的出纳员 fhq treap
思路：1. 此处的fhq treap的分裂是按照权值分裂然后插入的。将小于k的分为一棵子树，大于等于k的分为另一棵子树。2. 删除的时候只要将大于等于min的分裂到以root为根的树中，另一部分不用管，扔掉。3. 维护一个加标记，注意不要忘记某个地方的pushdown和pushup其他就是fhq t...
CODEVS 1074 食物链 2001年NOI全国竞赛(洛谷 P2024)
题目描述 Description动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。 现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是“1 X ...
[NOI 2017]蔬菜
Description题库链接小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。在蔬菜仓库中，共存放有 \(n\) 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。在计算销售蔬菜的收益时，每销售一个单位第 \(i\) 种蔬菜，就可以获得 \(a_i...
【NOI2018模拟】Yja
【NOI2018模拟】YjaDescription在平面上找\(n\)个点，要求这 \(n\)个点离原点的距离分别为 \(r1,r2,...,rn\) 。最大化这\(n\) 个点构成的凸包面积，凸包上的点的顺序任意。注意：不要求点全部在凸包上。Input第一行一个整数 \(n\)。接下来一行$ n$...
2877: [Noi2012]魔幻棋盘 - BZOJ
DescriptionInput第一行为两个正整数N,M，表示棋盘的大小。 第二行为两个正整数X,Y，表示棋盘守护者的位置。 第三行仅有一个正整数T，表示棋盘守护者将进行次操作。 接下来N行，每行有M个正整数，用来描述初始时棋盘上每个位置的数。 接下来T行，按操作的时间顺序给出T次操作。每行描述一次...
【BZOJ 2879】[Noi2012]美食节 费用流
思路同修车，就是多了一个骚气的操作：动态加边，我们通过spfa流的过程可以知道，我们一次只会跑一流量，最后一层边跑过就不会再悔改，所以说我们只会用到一大片里面的很少的点，所以我们如果可以动态加边的话我们的边的数量就会从n*m*p级别减少到p*n级别，点数的话有些点虽然存在但是由于我们没连上所以就不会...
[BZOJ2879] [Noi2012] 美食节 (费用流 & 动态加边)
DescriptionCZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法...
BZOJ 2879 [Noi2012]美食节 | 费用流 动态开点
这道题就是“修车”的数据加强版……但是数据范围扩大了好多，应对方法是“动态开点”。首先先把“所有厨师做的倒数第一道菜”和所有菜连边，然后跑一下spfa，找出哪一个厨师在增广路上，把“这个厨师做的倒数第二道菜”和所有菜连边，然后继续spfa，如此循环往复直到spfa找不出最短路。#include &l...
[NOI2012]美食节(费用流)
题目描述CZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于...
[NOI2012]美食节——费用流（带权二分图匹配）+动态加边
题目描述小M发现，美食节共有n种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有m个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: ...
BZOJ 2879: [Noi2012]美食节( 费用流 + 动态加边 )
倒着做菜..然后考虑为当前的人做菜对后面的人的影响就可以了..要动态加边----------------------------------------------------------------------------------#include<deque>#include<...
【BZOJ】【2434】【NOI2011】阿狸的打字机
AC自动机+DFS序+BIT好题啊……orz PoPoQQQ 大爷一道相似的题目：【BZOJ】【3172】【TJOI2013】单词那道题也是在fail树上数有多少个点，只不过这题是在x的fail树上数有多少个y的点。感觉好难搞啊……那么我们不妨反过来……离线做？既然是fail树！那么就看可以有dfs...
openjudge-NOI 2.5基本算法之搜索 专题题解目录
1、1700 八皇后问题2、1756 八皇后3、1789 算24
[NOI2014] 魔法森林 - Link Cut Tree
[NOI2014] 魔法森林Description给定一张图，每条边 \(i\) 的权为 \((a_i,b_i)\)， 求一条 \(1 \sim n\) 路径，最小化 \(\max_{i\in P}{a_i} + \max_{i\in P}{b_i}\)Solution如果我们限定最大的 \(b_i...
NOI题库刷题日志 （贪心篇题解）
这段时间在NOI题库上刷了刷题，来写点心得和题解一、寻找平面上的极大点2704:寻找平面上的极大点总时间限制: 1000ms 内存限制: 65536kB描述在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x>=a,y>=b;用图形来看就是(a,b...
[NOI2017]泳池
题目描述有一个长为\(n\)，高为1001的网格，每个格子有\(p\)的概率为1，\((1-p)\)的概率0，定义一个网格的价值为极大的全一矩形，且这个矩形的底要贴着网格的底，求这个网格的价值为\(K\)的概率。题解我们可以考虑设一个\(dp\)。我们定义每一列的高度为这一列最高的位置满足这个位置及...
P4774 [NOI2018]屠龙勇士
P4774 [NOI2018]屠龙勇士先平衡树跑出打每条龙的atk t[]然后每条龙有\(xt \equiv a[i](\text{mod }p[i])\)就是\(xt+kp[i]=a[i]\)求出一个满足条件的\(x_0\)，通解是\(x=x_0+k*\text{gcd}(t,p[i])\)就是\...
bzoj 3669: [Noi2014]魔法森林
bzoj 3669: [Noi2014]魔法森林Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，...
BZOJ 3669: [Noi2014]魔法森林( LCT )
排序搞掉一维, 然后就用LCT维护加边MST. O(NlogN)--------------------------------------------------------------------------------------#include<cstdio>#include&l...
bzoj 3669: [Noi2014] 魔法森林 LCT版
Description为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当...