9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

NOIP2015提高组Day1题解



NOIP2015 Day1 题解
Yang Jiaqi 2015 年 11 月 10 日

1

1

神奇的幻方

2

1 神奇的幻方
鉴于题目已经给出了当 n 为奇数时, n 阶幻方的构造方法, 因此直接模拟就可以了.

2 信息传递


题目实际上是要我们输出一个 n 个点的有向图的最小的 SCC 的大小, 并且每个点都只有 一条出边, 没有自环. 这个做法还是比较经典的. 不妨设每个点 i 有一条边连向点 succ[i], 我们可以枚举从点 s 出发, 然后一直走下去, 并且每经过一个点就标记这个点. 如果我们走到了一个已经标记了的点, 此时有两种情况 1. 这个点在我们从 s 出发走出的这条路径上, 这说明我们找到了一个环, 那么用这个环的大 小更新答案即可; 2. 否则, 我们已经处理过这个点了, 直接退出, 枚举下一个起点. 显然, 每个点只会被走一次, 因此时间复杂度是 O(n) 的.

3 斗地主
题目给出了斗地主的规则, 然后给出某个人手中的牌, 让我们求最少要多少次才能出完这些 牌, 并且题目保证数据随机. 那么首先, 牌的花色是没有用的. 然后通过观察可以发现, 题目中的出牌规则大致可以分为 三种 1. 顺子, 也就是连续五张单牌, 连续三对, 或者连续两个三张牌; 2. 带牌, 也就是三带一和四带二; 3. 其他, 那么直接把每一种牌单独打出来就可以了. 由于题目数据是随机的, 因此可以直接爆搜. 顺子最特殊, 我们可以先搜出每一种顺子一共有几个. 之后再搜四带二, 我们可以枚举每个四张牌是带了两张单牌还是两对, 然后再枚举它带了哪 些. 之后我们可以发现, 三带一的情况是可以直接贪心的. 因为如果你有三张牌, 你肯定会让它 带另外一张牌或者另外一对. 所以此时我们直接算就可以了.

3

斗地主

3

我们可以加一个非常简单的全局的最优化剪枝, 并且很显然, 一开始可以令这个最优值为我 们把所有牌分开打出去所需要的步数. 这样就可以非常快地通过极限数据.



更多相关文章:
NOIP2014提高组复赛试题day1+day2
(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头...保证存在一组最优解使得同一单位时间 最多点击屏幕...起点 1 与终点 3 不连通,所以满足题 目描述的...
NOIP2015提高组复赛试题Day1+Day2纯Word版
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文...
2008noip提高组复赛题解
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区...已经过掉所有标准数据,以及 5 7 2 4 1 6 3 ...文档贡献者 崔云从 贡献于2015-11-25 专题推荐 ...
noip2015提高组复赛试题答案
noip2015 提高组复赛试题答案一. 单项选择题 (共 20 题,每题 1.5 分,共计...1) offset := 4 2) (dayNum[i] + offset) mod 7 3) dayNum[m] 4)...
NOIP2015普及组复赛试题解题报告word版第一二题满分程序
NOIP2015普及组复赛试题解题报告word版第一二题满分程序_学科竞赛_初中教育_教育...salesman.pas 注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文小写。...
NOIP2015普及组复赛试题
(NOIP2015)复赛 普及组 (请选手务必仔细阅读本页内容)一、 题目概况 中文题目...Pascal 语言 四、注意事项: 1、文件名(程序名和输入输出文件名)必须使用英文...
NOIP2014提高组复赛试题
(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头...3.解方程 (equation.cpp/c/pas) 【问题描述】 ...文档贡献者 年华似火燃烧 贡献于2015-09-26 相关...
noip2015普及组题解最终
noip2015普及组题解最终_学科竞赛_小学教育_教育专区...*? 【样例输出】 *10 221 1*1 【数据说明】 ...
NOIP2014复赛提高组模拟试题
(NOIP2014)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一、题目概况 中文...2015国考面试通关宝典 67份文档 九妖笑话 2014年笑话大全之让你笑个够 儿童...
历年提高组复赛题目(1995-2015)
全国信息学奥林匹克联赛(NOIP2015)复赛提高组 day1...程序要求: 输入:N; 输出:如有多种解,则输出第...(NOIP2015)复赛提高组 day1 题二 侦探推理 【问题...
更多相关标签:
noip2016提高组day1    noip2015提高组day1    noip2014提高组day1    noip2016day1    noip2016 day1 t2    noip2013day1    noip2015 day1    noip2012day1    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图