【弱校胡策】 2016 noip模拟赛题目
|
387
|
noip&&noi,spfa,分层图,图论,差分约束,快速幂,数据结构,模拟,算法,线段树,贪心
|
Dewct

3641 字
|
16 分钟

真 · Noip模拟赛

Day1

  1. 题目概况
试题名称 M又饿了 seq interval
英文题目与子目录名 hungry seq interval
可执行文件名 hungry seq interval
输入文件名 hungry.in seq.in interval.in
输出文件名 hungry.out seq.out interval.out
每个测试点时限 1 秒 1 秒 1 秒
测试点数目 10 10 20
每个测试点分值 10 10 5
附加样例文件 有 有 有
结果比较方式 全文比较（过滤行末空格及文末回车）
题目类型 传统 传统 传统
  1. 提交源程序文件名
对于 pascal 语言 hungry.pas seq.pas interval.pas
对于 C 语言 hungry.c seq.c interval.c
对于 C++语言 hungry.cpp seq.cpp interval.cpp

三．运行内存限制

内存限制 128MB 128MB 128MB

注意事项：

1.文件名（程序名和输入输出文件名）必须使用英文小写。

2.PASCAL 参赛选手可以使用数学库和 ansistring。

3.C/C++中函数 main()的返回值类型必须为 int，程序正常结束时的返回值必须为 0。

4.统一评测时采用的机器配置为：CPU Pentium 3.0GHz，内存 4G，上述时限以此配置为准。

Problem 1 M又饿了(hungry.cpp/c/pas)
题目描述 M又饿了，于是他找来了一些1*2的矩形煎饼，准备填满他的肚子。众所周知，M的肚子是一个2*n的矩形，他现在要将煎饼不重叠的填满肚子，于是他想知道有多少种方法可以填满肚子。
输入描述 输入一个n，表示肚子的长度。
输出描述 输出可以用1*2的煎饼填满的方案数。
样例输入 2
样例输出 2
数据范围及提示 1<=n<=50;
Problem 2 seq (seq.cpp/c/pas)
题目描述 众所周知，DQS喜欢过儿童节
这天，LOI幼儿园举行了别开生面的儿童节联欢会，园长（MC）决定举行一场比赛，来考验可爱的小DQS们，获胜者将会获得一件阳炎的手办！（DQS是阳炎厨！）
所以，可爱的DQS拼命想要赢得这场比赛，比赛要求：给你一个整数数列，和一些关于它的区间和大小的限制条件，问是否存在这样的数列。笨笨的想要奖品的DQS找来了你来帮他解决这个问题。
输入描述 第一行二个整数 N，M 分别表示区间长度和限制的个数。
接下来M行，每行四个整数 li,ni,vi,ki 表示这个数列里区间[li,li+ni]的区间和>或<ki。其中当 vi=0 为 <,vi=1 为>。
输出描述 如果存在这样的数列输出 YES，否则输出 NO.
样例输入 样例1：
4 2
1 2 1 0
2 2 0 2
样例2：
1 2
1 0 1 0
1 0 0 0
样例输出 样例1：
YES
样例2：
NO
数据范围及提示 对于 30%的数据，n<=10。
对于全部数据,n<=100,m<=100
本题将手动检查代码，直接输出 YES 或 NO 的代码将被判为 compile error.
Problem 3 interval(interval.cpp/c/pas)
题目描述 受校门外的树这道经典问题的启发，DQS根据基本的离散数学的知识，抽象出5种运算维护整数集合S(S初始为空)并最终输出S。现在，请你完成这道校门外的树之难度增强版——校门外的区间。
5种运算如下：

U T S∪T
I T S∩T
D T S－T
C T T－S
S T S⊕T

 
基本集合运算如下：

A∪B {x|x∈A or x∈B}
A∩B {x|x∈A and x∈B}
A－B {x|x∈A and x∉B}
A⊕B (A－B)∪(B－A)
输入描述 输入共M行。
每行的格式为X T，用一个空格隔开，X表示运算的种类，T为一个区间(区间用(a,b), (a,b], [a,b), [a,b]表示)。
输出描述 共一行，即集合S，以闭区间形式输出，每个区间后面带一个空格。若S为空则输出”empty!!!”。
样例输入 U [1,5]
D [3,3]
S [2,4]
C (1,5)
I (2,3]
样例输出 empty!!!
数据范围及提示 关于数据范围请参见选手目录下的data.cpp

Day2

  1. 题目概况
试题名称 daze dp 大图书馆的日常
英文题目与子目录名 daze dp marisa
可执行文件名 daze dp marisa
输入文件名 daze.in dp.in marisa.in
输出文件名 daze.out dp.out marisa.out
每个测试点时限 1 秒 1 秒 5 秒
测试点数目 10 10 10
每个测试点分值 10 10 10
附加样例文件 有 有 有
结果比较方式 全文比较（过滤行末空格及文末回车）
题目类型 传统 传统 传统
  1. 提交源程序文件名
对于 pascal 语言 daze.pas dp.pas marisa.pas
对于 C 语言 daze.c dp.c marisa.c
对于 C++语言 .cpp dp.cpp marisa.cpp

三．运行内存限制

内存限制 128MB 128MB 128MB

注意事项：

1.文件名（程序名和输入输出文件名）必须使用英文小写。

2.PASCAL 参赛选手可以使用数学库和 ansistring。

3.C/C++中函数 main()的返回值类型必须为 int，程序正常结束时的返回值必须为 0。

4.统一评测时采用的机器配置为：CPU Pentium 3.0GHz，内存 4G，上述时限以此配置为准。

Problem 1 daze(daze.cpp/c/pas)
题目描述 众所周知，DQS是阳炎厨（滑稽）
他为文乃舍身救大家的故事感动不已，于是决定进入阳炎daze的世界拯救文乃姐，可是当他进入阳炎daze的世界之后却发现想要拯救文乃并不是那么简单的事情，可怜的Azami用尽最后的能力给阳炎daze下达了一道指令，只要能够通过这个考验的勇者就可以把进入阳炎daze的人拉回现实世界。
考验如下：Azami在屋子前种下了n颗果树，每颗果树一到秋天就会结出大量果子，由于地心引力的作用，所有的果子都掉到了自己果树的下面，每颗果树下面的果子数量为a，屋子旁有m个袋子，DQS可以利用他目的能力使袋子的体积可变，使它们的体积都变为v，DQS会按照如下规则把果子装进袋子里：
(a)从第1棵果树开始装起，由1到n一直装到第n棵果树。
(b)如果这棵果树下的果子能全部装进当前这个袋子，就装进去；如果不能，就关上当前这个袋子，打开一个新的袋子开始装。
Azami希望DQS在能把所有果子都装进袋子里的前提下，v尽量小。m个袋子并不一定都要装进果子。
输入描述 输入第1行，包含两个整数n和m。
第2行，包含n个整数ai。
输出描述 输出仅1行，表示最小的v。
样例输入 样例1：
3 3
1 2 3
样例2：
5 3
1 3 6 1 7
样例3：
6 3
1 2 1 3 1 4
样例输出 样例1：
3
样例2：
7
样例3：
4
数据范围及提示 【输入输出样例解释1】
每个袋子的体积为3即可。前2棵果树的果子装在第一个袋子里，第3棵果树的果子装在第二个袋子里。第三个袋子不用装了。
【输入输出样例解释2】
每个袋子的体积为7即可。前2棵果树的果子装在第一个袋子里，此时第一个袋子已经装了4单位体积的果子，第3棵果树的果子装不下了，所以装进第二个袋子里，第4棵果树的果子刚好装进第二个袋子，第5棵果树的果子装进第三个袋子里。
【输入输出样例解释3】
每个袋子的体积为4即可。前3棵果树的果子装在第一个袋子里，第4~5棵果树的果子装在第二个袋子里，第6棵果树的果子装在第三个袋子里。
【数据范围】
对于40%的数据，0<m≤n≤1,000，0<ai≤1,000；
对于70%的数据，0<m≤n≤100,000，0<ai≤100,000；
对于100%的数据，0<m≤n≤100,000，0<ai≤1,000,000,000。
Problem 2 (dp.cpp/c/pas)
题目描述 按照ccf的尿性，每年至少有一个dp题，于是就有了这个题qwq。
给出一个长度为N的序列，给出一个数M，要求取出一些数，在被M整除的情况下数的和最大。
输入描述 第一行俩数分别是N，M。
第二行一个序列N个数。
输出描述 输出符合要求的最大值，如无论如何都不能被M整除，输出0。
样例输入 5 7
1 2 3 4 5
样例输出 14
数据范围及提示 对于30％的数据，1 <= N <= 10 , 1 <= M <= 10;
对于60％的数据，1 <= N <= 100 , 1<= M <= 100;
对于100％的数据，1 <= N <= 1000 , 1<= M <= 1000 ，序列中的数大小不超过1000000;
样例解释：
选2 ，3 ，4 ，5.
Problem 3 大图书馆的日常 ( marisa.cpp/c/pas)
题目描述 众所周知，幻想乡的魔理沙最喜欢去红魔馆的姆Q那里借（tou）书了，不爱打理家务的魔理沙把家里搞得乱七八糟的，其中很大一部分杂物就是姆Q的图书馆里的书。
今天，魔理沙又想去借（tou）书了。她刚从科学技术世界第一的河城荷取那里搞来了一把不需要魔法就可以飞行的神奇扫把，这把扫把飞的很快，所以魔理沙骑上扫把后跑的比谁都快！她想借此机会测试一下这把扫把。
无奈的是用这个扫把飞行是要烧油的！油自然是要花钱的啊！
幻想乡有n个建筑，m条双向道路，每条连接着两个建筑。每条道路对于这个扫把有两个参数：H和W。其中W是走过这条路的固定花费。若魔理沙骑着扫把从高度为h的高度飞过这条道路（在幻想乡，飞也要按照基本法！在道路上飞行不得改道！也就是说不能在道路上改变飞行高度），那花费就是(h-H)^2，经过这条道路的总花费就是(h-H)^2+W。
按照幻想乡的基本法，在每个建筑上是可以随意改变高度的。这把扫把每上升单位1的高度，就需要花费C，而下降则不需要花费。其中地面的高度是0，魔理沙的高度始终大于等于0，她必须从地面起飞、降落。
魔理沙摸了摸自己的口袋，她的内心是崩溃的。已知n个建筑的标号是0~n-1，魔理沙的家是0号建筑，红魔馆是n-1号建筑，她想知道她去偷一次书（也就是从她家到红魔馆）最少需要花费多少钱。
输入描述 第1行：三个整数，n,m,c。分别代表幻想乡的建筑数、道路数量、升高一单位所需花费。
接下来m行，每行4个整数，依次是u,v,H,W，表示这条道路连接u,v两地，两个参数分别是H,W。
输出描述 一行一个整数，表示最小花费。
样例输入 3 2 5
0 1 10 10
1 2 20 10
样例输出 114
数据范围及提示 魔理沙在0号建筑，红魔馆在2号建筑。
魔理沙在0号建筑上升10个单位高度，此时她的高度为10。花费为10*5=50，然后通过道路到达1号建筑，花费为(10-10)^2+10=10，此时总花费为60。
接下来，她在1号建筑上升了8个单位高度，此时她的高度为18。花费为8*5=40,然后通过道路到达2号建筑，也就是红魔馆，花费为(20-18)^2+10=14，此时总花费为60+40+14=114。然后她在红魔馆下降了18个单位高度，不需要花费，成功降落。所以总花费是114。
 
对于30%的数据，N,M<=5,H<=200
存在另外30%的数据，N<=100,M<=500,H<=100，其中存在10%的数据，H=0。
对于100%的数据，N<=2000, M<=10000, C<=10, 0<=H<=10^5, 0<=W<=2*10^5.保证答案不超过int范围

题目数据见题解

上一篇
下一篇