CH Round #58 - OrzCC杯noip模拟赛day2
A:颜色问题题目：http://ch.ezoj.tk/contest/CH%20Round%20%2358%20-%20OrzCC杯noip模拟赛day2/颜色问题题解：算一下每个仆人到它的目的地的时间取max即可代码： #include<cstdio> #include<cstd...
CH Round #55 - Streaming #6 (NOIP模拟赛day2)
A.九九归一题目：http://ch.ezoj.tk/contest/CH%20Round%20%2355%20-%20Streaming%20%236%20(NOIP模拟赛day2)/九九归一题解：题目意思就是问 a是不是n的一个原根首先如果 gcd(a,n)!=1 显然不可能 输出0然后我们有性...
NOIP2003传染病控制[按层DFS]
题目背景近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断传播途径的方法控制疾病传播。...
NOIp2010 关押罪犯
二分+2-SAT先预处理出所有的v，然后离散化一下，在那个的基础上二分，对于每次二分出的值约束边权超过所二分出的边权的两点。 //OJ 1322 //by Cydiater //2015.8.26 #include <iostream> #include <cstdio> #...
【NOIP2015】提高day2解题报告
题目：P1981跳石头描述一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终 点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为...
noip的一些模板(参考了神牛的博客)
一、图论1.单源最短路洛谷P3371(1)spfa已加SLF优化 419ms #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using nam...
Noip前的大抱佛脚----根号对数算法
根号算法分块数列分块入门九题（hzwer）入门题1,2,3,4,5,7问题：给一段区间打上标记后单点查询解法：主要是每块维护一些标记，计算答案等，此类分块较为简单注意：块大小一般为\(\sqrt n\)复杂度：\(O(n\sqrt n)\)入门题6问题：每次朝数列中间插入一个元素，查询第k个元素是什...
一本通1632【 例 2】[NOIP2012]同余方程
1632：【 例 2】[NOIP2012]同余方程时间限制: 1000 ms 内存限制: 524288 KB【题目描述】求关于 x 的同余方程 ax≡1(mod b) 的最小正整数解。【输入】输入只有一行，包含两个正整数 a,b，用一个空格隔开。【输出】输出只有一行，包含一个正整数 ...
code vs 1094 FBI树 2004年NOIP全国联赛普及组
题目描述 Description我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法...
[NOIP2013/Codevs3287]货车运输-最小[大]生成树-树上倍增
Problem 树上倍增题目大意给出一个图，给出若干个点对u,v，求u,v的一条路径，该路径上最小的边权值最大。Solution看到这个题第一反应是图论。。然而，任意路径最小的边权值最大，如果仔细思考的话就会知道，如果两个点相互连通，那么一定走的是最大生成树上的路径，而不会选择其他任何一条路径去走。...
NOIP2003 传染病控制
题四 传染病控制【问题背景】近来，一种新的传染病肆虐全球。蓬莱国也发现了零星感染者，为防止该病在蓬莱国大范围流行，该国政府决定不惜一切代价控制传染病的蔓延。不幸的是，由于人们尚未完全认识这种传染病，难以准确判别病毒携带者，更没有研制出疫苗以保护易感人群。于是，蓬莱国的疾病控制中心决定采取切断...
Noip2016のmengbier
Day0上午10点多上了火车，向三位学长问了一路去年noip他们是用什么心态去考的，明明老师和同学都说我正常发挥应该没什么问题但心里就是紧张的不行，就是害怕犯个sb错误爆上一道题TAT。去试机。。。想着敲一遍dinic敲到一半不想敲了。。。去敲dijkstra。。。敲到一半又写不下去了。。。于是最后...
NOIP2013 提高组day2 2 花匠 动规 找拐点 树状数组
花匠描述花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具体而言，栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后，剩下的花的高度依次...
2013 Noip提高组 Day2
3288积木大赛正文题目描述春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦，大厦可以看成由n块宽度为1的积木组成，第i块积木的最终高度需要是hi。在搭建开始之前，没有任何积木（可以看成n块高度为 0 的积木）。接下来每次操作，小朋友们可以选择一段连续区间[l, r]，...
2012Noip提高组Day2 T3 疫情控制
题目描述H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都...
3537. 【NOIP2013提高组day2】华容道（搜索 + 剪枝）
Problem给出一个类似华容道的图。\(q\)次询问，每次给你起始点，终止点，空格位置，让你求最少步数\(n,m\le 30, q\le 500\).Soultion一道智障搜索题。弱智想法最多80分。不用想了。我已经试过所有非O2的常数优化，还是有1.05秒。考虑一下预处理。事实上，我们发现只有...
2013 Noip提高组 Day1
3285 转圈游戏2013年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond题解题目描述 Descriptionn 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙...
2012 Noip提高组 Day2
1265. [NOIP2012] 同余方程★☆ 输入文件：mod.in 输出文件：mod.out 简单对比时间限制：1 s 内存限制：128 MB 【题目描述】求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。【输入格式】输入只有一行，包含两个正整数 a, b，用一...
2014 Noip提高组 Day2
P2038 无线网络发射器选址【题目描述】随着智能手机的日益普及，人们对无线网的需求日益增大。某城市决定对城市内的公共场所覆盖无线网。假设该城市的布局为由严格平行的129 条东西向街道和129 条南北向街道所形成的网格状，并且相邻的平行街道之间的距离都是恒定值 1 。东西向街道从北到南依次编号为0,...
NOIP2013 提高组day2 3 华容道 BFS
描述小 B 最近迷上了华容道，可是他总是要花很长的时间才能完成一次。于是，他想到用编程来完成华容道：给定一种局面，华容道是否根本就无法完成，如果能完成，最少需要多少时间。小 B 玩的华容道与经典的华容道游戏略有不同，游戏规则是这样的：在一个 n*m 棋盘上有 n*m 个格子，其中有且只有一个格子是空...