noip2017专题

[NOIP2017 提高组] 列队

个人难度：Medium+/Hard- 题目描述给你一个矩阵，每次操作删除一个数 a x , y a_{x,y} ax,y，然后第 x x x 行 y y y 右边所有数左移一位填补空位，然后第 m m m 列 x x x 上边所有数下移一位填补空位，最后把 a x , y a_{x,y} ax,y 放到 n n n 行 m m m 列填补空位。每次操作时求 a x ,

【NOIP2017提高A组模拟9.5】NYG的背包

Description Input Output Sample Input 输入1： 3 5 3 1 4 8 8 3 输入2： 3 7 9269 21366 1233 7178 23155 16679 23729 15062 28427 939 6782 24224 9306 22778 13606 5 22367 17444 5442 164

【NOIP2017模拟9.3A组】摘果子

Description Input Output Sample Input 7 9 39 6 13 2 22 6 7 4 -19 5 28 6 -17 1 2 1 3 2 4 1 5 4 6 2 7 3 Sample Output 52 Solution 就是树上背包问题，有一个很经典的做法按照dfs序反着来dp，那么f[i][j]表示的就

【NOIP2017提高A组模拟8.10】文本编辑器

Description Input 第一行是初始内容之后按照题目要求 Output 对于每个命令，按照要求输出 Sample Input goodykc 11 I R u I R l L L L L R D R < R D R S Sample Output T T T T T T T F T T goodluck Sol

洛谷 P3956 [NOIP2017 普及组] 棋盘

思路：优先队列其实本来想用双端队列进行解答的，但是呢，题目中有一个比较特殊的地方，那就是可以施展魔法让没有颜色的格子变成有颜色的格子，这样的话你如果普通的按照双端队列那样存储，会得不偿失，因为你将面临两个问题：何时才能涂颜色？涂颜色应该涂什么颜色最好呢？所以pass。这里看了题解才知道要用优先队列进行优化。先从最折磨人的施展魔法这里讲起吧...... 这个魔法问题，我们其实可以转化连续跳

NOIP2017 - 宝藏

LibreOJ链接 Description 给出一个\(n(n\leq12)\)个点\(m(m\leq1000)\)条边的带权无向图，求该图的一棵生成树，使得其边权×该边距根的深度之和最小。 Solution 既然\(n\leq12\)，可以猜测是状压DP。定义\(f[dpt][s][s_1]\)表示一棵深度为\(dpt\)，点集为\(s\)，最深的（深度为\(dpt\)）的点的集合为\(s_

【NOIP2017模拟】猫种花

题面-猫信息组最近猫成灾了!隔壁物理组也拿猫没办法.信息组组长只好去请神刀手来帮他们消灭猫.信息组现在共有n 只猫(n 为正整数),编号为1 到n,站成了一个环,第i 只猫的左边是第i-1 只猫,右边是第i+1 只猫.特别的,第1 只猫的左边是第n 只猫,第n 只猫的右边是第1 只猫.每只猫拥有价值,表示消灭它能给信息组组长带来的声誉.注意,有的猫价值为负数,这意味着消灭它会损害组长的声

NOIP2017模拟赛 senior 6.29 T3 Gift（gift）

NOIP2017模拟赛 senior 6.29 T3 Gift（gift） Description Input Output 这道题的难度相对来说并没有第二题恼火，但还是很难搞的。那么这道题读完题目还是比较好看出这是一道背包的变形题。因为每一份礼物都是取或者不取两个状态，所以，01背包好理解吧。然后题目中说选到不能选为止，所以我们先将读入的礼物的价值排个序，然后从大到小我们去选

【NOIP2017】【洛谷P3957】跳房子【单调队列优化dp】

题目大意：题目链接：https://www.luogu.org/problemnew/show/P3957 跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。跳房子的游戏规则如下：在地面上确定一个起点，然后在起点右侧画 n n n个格子，这些格子都在同一条直线上。每个格子内有一个数字（整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳，跳到起点右侧

[NOIP2017]第一题-成绩

题目描述牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：总成绩=作业成绩×20%+小测成绩×30%+期末考试成绩×50% 牛牛想知道，这门课程自己最终能得到多少分。输入格式：输入文件只有1行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是100分。输出格式：输出文件只有1行，包含一个整数

Noip2017蒟蒻水分记

前记：这是填一个久远的坑，非常不走心~ 初赛前夕初赛那星期刚好要第一次月考，（初赛在周末，月考是星期一，星期二）然后，班主任lkh担心我们复习文化课花费太多精力，初赛考挂，于是，停了我们月考，在电脑室“复习”了两天计算机基础知识。初赛忐忑不安的考完，感觉自己要gg。然而，居然考了那么高分，又超过了ymw大佬（%ymw）复赛前夕在同学们羡慕的眼神中，又停课了，外加逃掉了期中

BFS，二分，并查集综合应用，P2658 汽车拉力比赛；P3958 [NOIP2017 提高组] 奶酪

题目描述博艾市将要举行一场汽车拉力比赛。赛场凹凸不平，所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500)，每个单元格的海拔范围在0到10^9之间。其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D，这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南

NOIP2017 提高组奶酪（DFS、BFS、并查集）一题三解

原文链接：NOIP真题第三讲：奶酪题目来源：2017 年 NOIP 提高组第一题本题考察点：【DFS、BFS、并查集】一、题目及链接题目链接： https://www.luogu.com.cn/problem/P3958 题意：老鼠是否可以从下表面的空洞一直沿着空洞走到上表面，如果可以，输出Yes，否则输出No；二、问题分析该题可以通过搜索来实现，找出所有的入口（

「NOIP2017」奶酪 - 并查集

题目大意在一个三维空间内有一块长方体奶酪，下表面z=0，高度为h，长宽无限，其中有一些可以通过的空洞，如果两个洞相交或相切，就可以从一个空洞跑到另一个空洞。给定h和每个空洞的球心坐标和半径，问能否从下表面跑到上表面。分析首先要明白对于两个球体A,B如果AB的球心距离小于等于两半径和，两球相切或相交。然后，维护一个并查集，建立一个超级起点z=0和超级终点z=h，如果两个球连通，就将它们并

[NOIP2017 普及组] 棋盘——深搜详解

题目背景 NOIP2017 普及组 T3 题目描述有一个 m×m 的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的），你只能向上、下、左、右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。另外，

NOIP2017提高组day2 - T2：宝藏

题目链接 [NOIP2017 提高组] 宝藏题目描述参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n n n 个深埋在地下的宝藏屋，也给出了这 n n n 个宝藏屋之间可供开发的 m m m 条道路和它们的长度。小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很

JZOJ.5257【NOIP2017模拟8.11】小X的佛光

Description Input Output Sample Input 3 3 11 22 31 2 31 1 33 1 3 Sample Output 113 Data Constraint 题目就是要求两点到一个点的路径中重叠的点的个数。特殊性质一是一条链，我们可以通过讨论两个起点和一个终点的相对位置直

JZOJ.5257【NOIP2017模拟8.11】小X的佛光

Description Input Output Sample Input 3 3 11 22 31 2 31 1 33 1 3 Sample Output 113 Data Constraint 题目就是要求两点到一个点的路径中重叠的点的个数。特殊性质一是一条链，我们可以通过讨论两个起点和一个终点的相对位置直

【NOIP2017提高组正式赛】Day1T3逛公园

Description 策策同学特别喜欢逛公园。公园可以看成一张o个点n条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，o号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从1号点进去，从o号点出来。策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多

【NOIP2017提高A组集训10.25】天才绅士少女助手克里斯蒂娜

Description Input 第一行两个整数n;m 表示电子个数和询问个数. 接下来n 行, 每行两个整数x; y 表示vi. 接下来m 行, 每行形如1 p x y 或2 l r, 分别表示两种操作. Output 对于每个操作2, 输出一行一个整数表示飘升系数对20170927 取模的值. Sample Input 9 5 13052925 5757314 996

【NOIP2017提高A组集训10.25】天才绅士少女助手克里斯蒂娜（树状数组）

Description Input 第一行两个整数n;m 表示电子个数和询问个数. 接下来n 行, 每行两个整数x; y 表示vi. 接下来m 行, 每行形如1 p x y 或2 l r, 分别表示两种操作. Output 对于每个操作2, 输出一行一个整数表示飘升系数对20170927 取模的值. Sample Input 9 5 13052925 5757314 996

【NOIP2017提高A组模拟9.5】心灵治愈

【NOIP2017提高A组模拟9.5】心灵治愈 Description Input Output Sample Input 输入1： 2 3 输入2： 8 8 Sample Output 输出1： 8 输出2： 16711680 Data Constraint Hint 题解 code #include<cstdio>#include<cstd

【NOIP2017】队列

题目描述 Sylvia 是一个热爱学习的女♂孩子。前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。 Sylvia 所在的方阵中有n×m名学生，方阵的行数为 n，列数为 m。为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n×m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列的学生的编号是(i−1)×m+

NOIP2017提高组DAY2T1 - 奶酪

题意输入每个输入文件包含多组数据。输入文件的第一行，包含一个正整数 T，代表该输入文件中所含的数据组数。接下来是 T 组数据，每组数据的格式如下：第一行包含三个正整数 n， h 和 r，两个数之间以一个空格分开，分别代表奶酪中空洞的数量，奶酪的高度和空洞的半径。接下来的 n 行，每行包含三个整数 x、 y、 z，两个数之间以一个空格分开，表示空洞球心坐标为(x, y, z

JZOJ 5344【NOIP2017模拟9.3A组】摘果子

罕见的树形背包啊好东西要做做 (不过总感觉不会考) 先放题目 Description Input 上面由字改成有强迫症=-= Output Sample Input 7 939 613 222 67 4-19 528 6-17 12 13 24 15 46 27 3 Sample Output 52 Data Constraint

暑假篇——NOIP2017模拟赛题解

目录一.优雅的序列 1.题目 2.题解 3.Code 二.甲虫入侵 1.题目 2.题解 3.Code 三.大逃亡 1.题目 2.题解 3.Code 谢谢！虽然三道题上了200，但还是有点菜一.优雅的序列 1.题目点击打开链接 2.题解这道题难就难在重复的数字上，如果没有重复的数字，直接n-1。不难发现，越小的数越要往前面放