noip2012专题

NOIP2012 开车旅行 (倍增)

题意：一行N个城市，有各自不同的海拔，定义两个城市之间的距离为海拔之差的绝对值，小a和小b轮流开车，开车方向从左往右，小a总是开到第二近的城市，小b开到最近的城市（如有两个城市和当前城市海拔之差相等，海拔低的更近）。当其中任一人无法按照自己的方案前进或前进后总路程超过一个上限，旅行结束。一，给定一个路程上限x0，求从哪个城市出发A和B路程比值最小，这里规定任意数比零等于无穷大，比值相等输出海拔最高

【NOIP2012模拟10.25】旅行

Description 给定一个n行m列的字符矩阵，’.’代表空地，’X’代表障碍。移动的规则是：每秒钟以上下左右四个方向之一移动一格，不能进入障碍。计算：在空地中随机选择起点和终点（可以重合，此时最短耗时为0），从起点移动到终点最短耗时的平均值。每一行每一列至多有1个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的： .X X. Input 第一行两个整数n, m。接下

借教室[NOIP2012]解题报告

思路一：O(mlogn) 裸的线段树，维护最小值和区间修改；由于是第一次写线段树，所以不太会写。代码： #include<iostream> using namespace std; #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> char * ptr=ne

[二分+差分]AcWing 503 / NOIP2012提高组《借教室》

1.题目说明在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来 n 天的借教室信息，其中第 i 天学校有 ri 个教室可供租借。共有 m 份订单，每份订单用三个正整数描述，分别为 dj,sj,tj

NOIP2012 普及组 T4 文化之旅

文化之旅（NOIP2012 普及组 T4 ）题目描述有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。现给定各个国家间的地理关系，各个

P1083 [NOIP2012 提高组] 借教室

P1083 [NOIP2012 提高组] 借教室题目描述在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来 n n n 天的借教室信息，其中第 i i i 天学校有 r i r_i ri 个教室可供

jzoj3100. 【NOIP2012提高组】国王游戏（B组——Day2）

jzoj3100. 【NOIP2012提高组】国王游戏（B组——Day2）题目 Description 恰逢H国国庆，国王邀请n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这n位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的

jzoj3099. 【NOIP2012提高组】Vigenère密码（B组——Day2）

jzoj3099. 【NOIP2012提高组】Vigenère密码（B组——Day2）题目 Description 【问题描述】 16世纪法国外交家Blaise de Vigenère设计了一种多表密码加密算法——Vigenère密码。Vigenère密码的加密解密算法简单易用，且破译难度比较高，曾在美国南北战争中为南军所广泛使用。在密码学中，我们称需要加密的信息为明文，用M

jzoj3034. 【NOIP2012模拟10.17】独立集

jzoj3034. 【NOIP2012模拟10.17】独立集题目DescriptionInputOutputSample InputSample Output 分析CODE 题目 Description 对于一棵树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集，图3有5536个不同的独立

jzoj3046. 【NOIP2012模拟10.23】游戏

jzoj3046. 【NOIP2012模拟10.23】游戏题目DescriptionInputOutputSample InputSample OutputHint 分析CODE 题目 Description 游戏规则如下：给定两个正整数数列，一个游戏者通过若干次操作完成游戏。每一次操作，选择两个正整数k1和k2。将第一个数列的最后连续k1个数删除，它们的和记为S1；将第二个

jzoj3013. 【NOIP2012模拟10.6】填充棋盘

jzoj3013. 【NOIP2012模拟10.6】填充棋盘题目DescriptionInputOutputSample InputSample OutputHint 分析CODE 题目 Description 横一划竖一划，横一划竖一划…………小R画出了一个n*m的棋盘。由于NOIP快要到了，小R有了一个奇妙的想法。在棋盘的每一个小方格中填入N，O，I，P这4个字母

jzoj3012. 【NOIP2012模拟10.6】购买

jzoj3012. 【NOIP2012模拟10.6】购买题目DescriptionInputOutputSample InputSample OutputHint 分析CODE 题目 Description 小N 最近迷上了购物每天都让小A 和小T 陪她逛街拿东西。最近商店出了这样的一个活动:买东西送积分，就是买一件物品，送当前物品的积分ci*当前的倍率，初始倍率是1；

NOIP2012提高组day1-T3：开车旅行

题目链接 [NOIP2012 提高组] 开车旅行题目描述小 A \text{A} A 和小 B \text{B} B 决定利用假期外出旅行，他们将想去的城市从 1 1 1 到 n n n 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 i i i 的海拔高度为 h i h_i hi，城市 i i i 和城市 j j j 之间的距离

「NOIP2012」文化之旅 - 最短路

题目描述有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使

【NOIP2012】洛谷1082 同余方程

题目描述求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。输入输出格式输入格式：输入只有一行，包含两个正整数 a, b，用一个空格隔开。输出格式：输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。裸的扩展欧几里得算法。 #include<cstdio>#include<cstring>#define L long longvo

开车旅行（NOIP2012提高组）

题目链接这道题最基本的思路是用倍增，但是其实它的难点在预处理部分。倍增的部分此次就不细说了，和之前的最近公共祖先的思想类似。我们主要来探讨一下预处理的部分。我们需要预处理出每个城市小A和小B的选择目标和对应的距离，接下来就可以处理出进行2k轮开车的目的地和距离了。所以前者才是重中之重，而前者如果要用暴力的方法会tle的。有人可能会疑惑，我们找当前点的后面两三个不就可以了？为什么会tle呢

NOIP2012普及组初赛题目及答案分析

一、单项选择题（共20题，每题1.5分，共计30分；每题且仅有一个正确选项） 1．计算机如果缺少（A ），将无法正常启动。 A．内存 B．鼠标 C． U盘 D．摄像头【分析】电脑缺少内存将无法启动，开机会黑屏。 2．（ B）是一种先进先出的线性表。 A．栈 B．队列 C．哈希表（散列表）

【NOIP2012模拟8.9】逐个击破

题目大意给定一棵树，其中k个点被标记。现在的任务是破坏掉树上的某些边，使得k个点都属于不同的连通块。题解直接的一个想法，就是找到两两的lca，然后取路径上的最小值。但是这样是 O(n2) O(n^2)的。是否可以像对trie中的字符串进行排序那样来排序这棵树上的k个点？即每一个点维护一个 L[i] L[i]和 R[i] R[i]，表示i的子树包含了排名为 [l,r] [l,