noip2010专题

NOIP2010 引水入城(BFS+贪心)

题意：一个N*M矩形，每个格子有一个海拔。第一行靠近水源，要在矩形中恰当位置建水利设施将水引到最后一行的每个格子。有两种设施：抽水站，可以建在第一行任意位置；引水站，只要它周围存在一个格子比它地势高且那个格子建的有任意一种水利设施，就可以建造，建造后水引到这里。第一行输出1/0代表能否使得后一行全部引到水。如果是1，求最少需要多少抽水站；如果无法满足，输出(M - 最多可以满足的最后一行的城市数

NOIP2010 关押罪犯 (二分答案+二分图染色)

题意：有两个监狱，N个犯人，M对关系，每对关系描述一对犯人如果在一个监狱将会产生一个冲突值。任意安排犯人的分配，使得产生的最大冲突值最小。题解：最大值最小，先考虑二分。二分中最重要的环节就是判定猜测值可行性以及保证答案单调性。可行性判定：对于一个猜测的最大冲突值，判定时就要保证所有大于这个冲突值的两个人不能在一个监狱。只需要将需要满足不在同一监狱的两个人连上边，如果最后可以染成二分图，就存在分

洛谷 P1179 [NOIP2010 普及组] 数字统计

本文由Jzwalliser原创，发布在CSDN平台上，遵循CC 4.0 BY-SA协议。因此，若需转载/引用本文，请注明作者并附原文链接，且禁止删除/修改本段文字。违者必究，谢谢配合。个人主页：blog.csdn.net/jzwalliser 题目洛谷 P1179 [NOIP2010 普及组] 数字统计 [NOIP2010 普及组] 数字统计题目描述请统计某个给定范围

洛谷 P1541 [NOIP2010 提高组] 乌龟棋

思路：暴力DP‘“ 其实在想到暴力dp之前，作者寻思着这个题目可能和”摆花“那道题差不多，就用那种思想想了一下，结果其实不是这样的。这里并不能开二维进行推进。由于我们在二维表示的时候，代表的含义就是在走了i个格子用了j个票子所积累到的最大积分。其实DP思路上看起来是没有什么错误的，但是呢，我这里忽略掉了：这里的票子是分种类的，也就是说，这里的票子并不是自由选的，我们必须保证这个票子正好用完，

笔试强训-day01_T1 BC153 [NOIP2010]数字统计

一、题目链接 BC153 [NOIP2010]数字统计二、题目描述描述请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。输入描述：输入共1行，为两个正整数L和R，之间用一个空格隔开。输出描述：输出

NOIP2010提高组复赛解题报告（C/C++）（机械翻译）（乌龟棋）（关押罪犯）（引水入城）

2017.2.18日的练习赛（NOIP2010）作为一个OI届的晚辈，能接触到近七年前的NOIP考试无疑是一件令人兴奋的事情。这倒不是因为什么信仰，实在是因为只有一试四道题（而不是二试六道题），做起来让人没有“后顾”之忧。下面我们来看看： 1.机械翻译解题报告：不得不说，这道题作为第一题是非常“温柔”的。众所周知，“模拟”算法（如果能称作一个算法的话）是NOIP最常考的考点（没有

$洛谷P1190 [NOIP2010 普及组] 接水问题$

洛谷P1190 [NOIP2010 普及组] 接水问题

题目描述学校里有一个水房，水房里一共装有个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从到n编号，号同学的接水量为。接水开始时，到号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学完成其接水量要求后，下一名排队等候接水的同学马上接替同学的位置开始接水。这个换人的过程是瞬间完成的&

NOIP2010普及组T3 接水问题 ——S.B.S.

题目描述学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1到 n 编号，i 号同学的接水量为 wi。接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 j 完成其接水量要求 wj后，下一名排队等候接水的同学 k马上接替 j 同学的

洛谷入门——P1179 [NOIP2010 普及组] 数字统计

[NOIP2010 普及组] 数字统计题目描述请统计某个给定范围 [ L , R ] [L, R] [L,R] 的所有整数中，数字 2 2 2 出现的次数。比如给定范围 [ 2 , 22 ] [2, 22] [2,22]，数字 2 2 2 在数 2 2 2 中出现了 1 1 1 次，在数 12 12 12 中出现 1 1 1 次，在数 20 20 20 中出现 1

P1540 [NOIP2010 提高组] 机器翻译题解

题目小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内存中有M

P1179 [NOIP2010 普及组] 数字统计————C++

目录 [NOIP2010 普及组] 数字统计题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示解题思路Code1Code2运行结果 [NOIP2010 普及组] 数字统计题目描述请统计某个给定范围 [ L , R ] [L, R] [L,R] 的所有整数中，数字 2 2 2 出现的次数。比如给定范围 [

P1158 [NOIP2010 普及组] 导弹拦截

题目描述经过11年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要求是拦

NOIP2010 机器翻译|模拟

题目背景 Background 小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述 Description 这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中

【NOIP2010】洛谷1514 引水入城

题目描述在一个遥远的国度，一侧是风景秀美的湖泊，另一侧则是漫无边际的沙漠。该国的行政区划十分特殊，刚好构成一个N 行M 列的矩形，如上图所示，其中每个格子都代表一座城市，每座城市都有一个海拔高度。为了使居民们都尽可能饮用到清澈的湖水，现在要在某些城市建造水利设施。水利设施有两种，分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此，只有与湖泊毗邻的第1

【NOIP2010】洛谷1541 乌龟棋

题目背景小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。题目描述乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。乌龟棋中M张爬行卡片，分成4种不同的类型（M张卡片中不一定包含所有4种类型的卡片，见样例），每种类型的卡片上分别标有1、2、3、4四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬

【NOIP2010】洛谷1199 三国游戏

题目描述小涵很喜欢电脑游戏，这些天他正在玩一个叫做《三国》的游戏。在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有 N 位武将（N为偶数且不小于 4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的

【NOIP2010】洛谷1158 导弹拦截

题目描述经过 11 年的韬光养晦，某国研发出了一种新的导弹拦截系统，凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为 0 时，则能够拦截与它位置恰好相同的导弹。但该导弹拦截系统也存在这样的缺陷：每套系统每天只能设定一次工作半径。而当天的使用代价，就是所有系统工作半径的平方和。某天，雷达捕捉到敌国的导弹来袭。由于该系统尚处于试验阶段，所以只有两套系统投入工作。如果现在的要

[NOIP2010 普及组] 三国游戏

题目传送门引为了夯实基础解法考虑严谨证明一下最优策略首先当小涵选了一个数后，一定会产生一个最优搭配和一个次优搭配，明显最优搭配永远取不到，那么他就只能选次优搭配还有一个选择是在选一个不相干的数，产生新的最优搭配，但是无济于事所以最后一定是取最大的次优搭配 Code #include <algorithm>#include <iostream>#include <c

关押罪犯-详解-noip2010-并查集--搜索--二分图

关押罪犯网址：https://vijos.org/p/1776 描述 S城现有两座监狱，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一监狱，他们俩之间会发生摩擦，

noip2010 引水入城 bfs+贪心

如果能够实现，每个河边的城市对应的控制区域一定是一条线段。所以直接bfs每个河边的城市，贪心线段的右端点 #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int qx[500005],qy[500005],a[505][505],n,m,bo[50

P1190 [NOIP2010 普及组] 接水问题【贪心】

P1190 [NOIP2010 普及组] 接水问题【贪心】题目描述学校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1 到 n 编号，i 号同学的接水量为 wi 。接水开始时，1 到 m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学 j 完成其接