【bzoj 十连测】[noip2016十连测第二场]Problem C. Dash Speed（树链剖分+并查集）
【题解】【树链剖分+并查集+二分】 【线段树维护边的信息，类似next数组的存储。并查集维护父子信息和每个区间的起点终点。考虑每次限定一个速度范围，速度在这个范围内的边都可以操作。分治，每次做完一个区间再把当前不符合的递归到下一区间处理，由于存在回溯和分治两侧，所以这里并查集不能进行路径压缩。...
洛谷 P1563 [NOIP2016 D1T1] 玩具谜题
题目描述 小南有一套可爱的玩具小人, 它们各有不同的职业。 有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图: 这时singer告诉小南一个谜題: “眼镜藏在我左数第3个玩具小人的右数第1个玩具小人的左数第2个玩具小人那里。 ” ...
NOIP2016纪录[那些我所追求的]
人生第一场正式OI[序] 2016-12-04见底部[Day -1] 2016-11-17期中考试无心插柳柳成荫，考了全市第2班里第1(还不是因为只复习了不到两天考试)，马上请了一个周的假准备NOIP（数学生物还是回去上课的）灰哥跟我一块，tlq考吃了没请假正好下个周老班出去学习了不害怕星期4所有人...
【NOIP2016提高A组模拟9.24】天使的分裂
Description 简化后的题意： 已知斐波那契数列 f0=f1=1 fi=f[i−1]+f[i−2] 和一个函数 Fn=∑i=0nf[i]∗f[n−i] 注意小f和大F的区别 求 ...
【NOIP2016提高A组8.12】奇袭
Description 由于各种原因，桐人现在被困在Under World（以下简称UW）中，而UW马上要迎来最终的压力测试——魔界入侵。 唯一一个神一般存在的Administrator被消灭了，靠原本的整合骑士的力量是远远不够的。所以爱丽丝动员了UW全体人民，与整合骑士一起抗击魔族。 在UW...
【NOIP2016提高组复赛】愤怒的小鸟
DescriptionSolution很明显是一个状态压缩DP的题目，不过也可以打成记忆化搜索。 设f[i]表示每个点选或不选的状态投射小鸟的最少方案。 首先预处理一个g[i][j]表示选i和选j，需要的小鸟可以经过小鸟的01状态。 然后直接DP就可以了： f[i|g[j][k]]=min(f...
【NOIP2016提高组复赛】天天爱跑步
Description Solution 这道题是NOIP里面最难的一道题。 暴力打的好可以拿80分，比赛的时候还是打暴力比较好。 我们思考一下从x到y的路径，这个可以拆成从x到lca的路径和从lca到y的路径，这个很明显。 如果一个点i在从x到lca 的路径可以检测到的话，那么就有de...
【NOIP2016提高组复赛】玩具谜题
Description Solution 这就是一道模拟题吗。 向右就加，然后mod一下。向左就减，然后mod一下。 Code #include<iostream>#include<cstdio>#include<cstring>#include&...
Matrix 【NOIP2016提高A组模拟8.17】
题目样例输入： 4 3 5 4 1 7 3 4 7 4 8样例输出： 59716数据范围： 剖解题目被虐，不多说了QwQ~~ 思路：这种题目，光看数据范围就知道暴力肯定不行，肯定是有规律或者公式的，努力推推看。 然而比赛上我推了好久好久，推出了个滑稽的公式，哭晕+_+|||。 解法40%：暴...
【NOIP2016提高A组模拟9.17】数格子
题目 分析 设表示每一行的状态，用一个4位的二进制来表示，当前这一行中的每一个位数对下一位有没有影响。 设 fi,s 表示，做完了的i行，其状态为s，的方案数。 两个状态之间是否可以转移就留给读者自己思考了。 答案就是 fn,0 因为最后一行对下一行不能造成影响。...
【NOIP2016提高A组模拟9.15】Math
Description 求 ∑i=1n(−1)∑mj=1d(i∗j) 其中d(i)表示i的因子个数。 n<=10^7,m<=10^14 Solution 既然是-1的次幂，那么我们就来分析一下奇偶性吧。。。 这里有一个很（不）显然的性质，d(...
【NOIP2016提高A组模拟9.15】Map
Description Input Output 所有询问的和 Sample Input 4 4 2 1 2 2 3 3 2 3 4 1 2 1 4 Sample Output 14 样例解释： upd:保证原图连通。 “不相交路径”的定义为不存在相同的边。可以存在相同的点...
[Noip2016]蚯蚓 D2 T2 队列
[NOIP2016]蚯蚓 D2 T2Description本题中，我们将用符号[c]表示对c向下取整，例如：[3.0」= [3.1」=[3.9」=3。蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有n只蚯蚓（n为正整数)。每只蚯蚓拥有长...
贤鱼的刷题日常--P2010 [NOIP2016 普及组] 回文日期
????今日学习目标：????学会回文日期题目✅创作者：贤鱼@TOC题目在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。牛牛习惯用8位数字表示一个日期，其中，前4位代表年份，接下来2位代表月 份，最后2位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示...
破译情报-NOIP2016提高组复赛模拟试题
【题目描述】 最近国安人员截获了一份 RB 国的秘密情报， 全文都是经过加密的，每个单 词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前 缀，但所取的前缀不能是其他单词的前缀。 这个任务现在就交给你来完成。 解释：“字符串s1是s2的前缀”意思是把字符串s2的后面去掉某些字符...
noip2016普及组初赛答案
我78.5分...........你们呢？在评论下写出自己的分数吧 广东中山分数线63分~ ...
Noip2016普及组初赛中山市成绩表、答案及分数线
2017.8.15更新 感觉这篇文章其实没什么卵用，过去了，虽然很多人关注，就暂时保留在这个博客吧 ----------------------------------- 广东中山初赛分数线62分~ [纪念中学好6] 2016年中山市信息学竞赛暨全国信息学联赛成绩表（普及组） 排名 ...
noip2016提高组初赛（答案+个人分析+个人总结）
由于网上还没有题目所以这里便没有题目=w= 一、单选 1、D 蒙也是能蒙对的=w= 2、A 注意，它问的是输出的第81个字符，不是按的，所以选B的童鞋好好读题=w= 依旧看做6个一组，81 div 6=13；易知奇数组是大写，偶数组是小写，所以显然是大写=w=； 然后再关注输出的是哪个字母，输出的看...
NOIP2016提高组初赛（C++语言）试题 个人的胡乱分析 Part 2.
洛谷秋令营day1模拟赛原地爆炸，心态崩了。于是打算写一下初赛题放松一下。 上次胡乱分析到了选择题，这次我想说说后面的题。 问题求解 T1.有一个1x8的方格图形，黑白两色填涂每个方格，两个黑格并不能相邻，求方案数。 我敢保证当时考场上要是没人跟我说这题是斐波那契数列打死我也想不起来。 当时我的做法...
NOIP2016提高组初赛(1)
一、选择题 6、后缀表达式，使用二叉树来求解，正常情况下的表达式a*（b+c）- d为中序遍历的二叉树。 即 若转换为后缀表达式（左右根）则为abc+*d- 14、代数字进去，多试几遍； 三、问题求解 1、同斐波那契数列 F[n]表示有n个格子可以用来染成黑色时满足条件的染色方案数，则有 F[0]=...