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

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



更多相关文章:
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组day1第二题的解题报告因为太简单所以写出来(误作者:蒟蒻zrw ...
NOIP2015提高组复赛试题Day1
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组day1 (请选手务必仔细阅读本页内容)一.题目概况 中文题目...
NOIP2015提高组解题报告
NOIP2015 提高组解题报告 T1 神奇的幻方【题目大意】 告诉你幻方的构造方法,给...NOIP2015提高组day1第二... 8页 免费 NOIP2015提高组参考答案 1页 免费 ©...
NOIP2014提高组复赛试题day1+day2
(NOIP2014)复赛 提高组 day1 1.生活大爆炸版石头...保证存在一组最优解使得同一单位时间 最多点击屏幕...起点 1 与终点 3 不连通,所以满足题 目描述的...
NOIP2015提高组题解zkp蒟蒻的题解
NOIP2015提高组题解zkp蒟蒻的题解_计算机软件及应用_IT/计算机_专业资料。NOIP...[j-1][k-1]+...f[i-1][j-1][k-1]都在 f[i][j][k]之 前求...
2008noip提高组复赛题解
2008noip提高组复赛题解_学科竞赛_高中教育_教育专区...已经过掉所有标准数据,以及 5 7 2 4 1 6 3 ...文档贡献者 崔云从 贡献于2015-11-25 专题推荐 ...
NOIP2015提高组复赛试题Day1+Day2纯Word版
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 (请选手务必仔细阅读本页内容)一.题目概况 中文...
noip2015提高组复赛试题答案
全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 CCF 全国信息学奥林匹克联赛(NOIP2015)复赛 提高组 day1 (请选手务必仔细阅读本页内容) 一.题目概况 中文...
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、文件名(程序名和输入输出文件名)必须使用英文小写。...
更多相关标签:
noip2016提高组day1    noip2015提高组day1    noip2014提高组day1    noip2012提高组day1    noip2013提高组day1    noip2011提高组day1    noip2016 day1    noip2013day1    

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

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