rqnoj题目 高考作文题目出炉

最近做的题目都来自rqnoj。

Problem 506:

题目:折型最大

问题编号:506

对于一个n*m的矩阵(1<n,m<=600),一个折型区域必须满足:
1、它的形状为“┘”(不能是“└”,“┌”,或“┐”)
2、它的宽度为1
3、它的横向长度和纵向长度都没有限制,但是不能为1(即不能退化为一条线或一个点)
现给出这个矩阵,求其中数字和最大的折型区域。

解法:这题可以分成两个部分,一个是求竖的最大值,一个是求横的最大值,把两个加起来再减去这个位置的值就可以了。求竖的或者横的就用一个简单的一维DP就可以了。

Problem 507:

题目:光的反射

问题编号:507

有一个平面正方形ABCD,边长为1,每一边的内部都是理想镜面。现从A射入一条光线,射向BC边,反射点为E。光线会在正方形中反射,只要不射到顶点上就不会停止。给出BE的长,问光线能反射多少次?

解法:这题可以把一道光线看做在穿过网格,如图:



所以当这条光线到达一个格点的时候就说明它已经不能反射了,经过的格子数就是反射的次数。所以就要把读入的数据化为最简分数然后求出答案。题目涉及到一个无限循环小数,这个化为分数的方法是:

把0.323232……(即0.3(·)2(·))化成分数.

分析:设x=3(·)2(·)=0.32+0.0032+0.000032+……①

上面的方程两边都乘以100得

100x=32+0.32+0.0032+0.000032+……②

②-①得

100x-x=32

99x=32

x=

所以0323232……=

如果不是循环小数就在方程两边同时乘一个10^X(X是不循环小数的小数位数),然后再化简就可以了。

Problem 619:

题目:最大值

问题编号:619

lqp在回忆自己初学OI的经历,他想起了自己学习如何找数组最大值的时候......
找到一个数组的最大值的一种方法是从数组开头对数组进行扫描,令max=a[0](数组下表从0..N-1),如果a_i>max,就更新max,这样就可以在O(N)的时间里找到一个数组的最大值。
这个问题是相当简单的,但是lqp想到了另一个问题,如果一个包含N个元素的数组a里面的元素的值是在1...K之间的整数,存在多少个不同的数组a,进行了如上扫描之后,max恰好进行了p次更新?
这个问题把lqp难住了,于是他想请你帮他算算。
下面是lqp手算的一组数据: N = 4,K = 3,P = 2
1) {1,1,2,3}
2) {1,2,1,3}
3) {1,2,2,3}
4) {1,2,3,1}
5) {1,2,3,2}
6) {1,2,3,3}
共有6种情况
由于答案可能很大,lqp讨厌很大的数,所以你仅仅需要把答案mod 10^9+7输出。
100%数据
1 <= T <= 100
1 <= n <= 100
1 <= K <= 300
0 <= P < n
解法:动态规划。

由于不能每次都算∑F[i-1,j-1,P](因为会超时),然后发现F[i,j,k]和F[i,j,k-1]的这个部分的差距只在于F[i,j,k]多了一个F[i-1,j-1,k-1],所以这个值可以从上一个值推来,所以这题也就解决了。

Problem 570:

题目:疯狂的方格取数

问题编号:57

题目描述:
在一个宽M,长N的矩阵中,请你编一个程序,n次从矩阵的左上角走到矩阵的右下角,每到一处,就取走该处的数字,请你选择一
种走法使取得的数字的和最大,并输出其最大值。其中:3<=M<=20M<=N<=1001<=n<=10
如输入数据:
rqnoj题目 高考作文题目出炉
3 10 13
0 1 2 3 4 9 7 1 3 1
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 5
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 5
9 1 2 2 3 6 7 8 1 2
1 2 3 4 5 9 8 7 6 1
9 7 1 3 1 9 1 2 2 3
6 7 8 1 2 1 2 3 4 0
其中n=3
M=10
N=13
即当n=3时,就相当于是3取方格数。
对于以上的数据:
将输出:297

解法:这题的正规解法是最大费用最大流,把每个点分成两个点(一个点连进边、一个点连出边),两个点中间连两条边(反向边的费用为正边的相反数),如图:


(括号左边是容量,右边是费用)
把开始点和(1,1)相连,(n,n)和结束点相连,每两个相邻的点连一条可以走的边就可以了,流量为k是为了限制只能走k次,然后求的是走k次以后的最大的费用即为答案。最大费用最大流用一个SPFA求得S到T的最大值,进行增广后不断重复这个操作,最后把每次增广的费用都加起来,就是题目所求的了。

Problem 251:

题目:魔法塔防

问题编号:251

塔防游戏(TowerDefence)是dd_engi非常喜爱的一类休闲游戏。在这类游戏中,玩家需要在地图上摆放各种防御单位,打击并阻止试图跨越地图的敌对单位。一般而言,敌对单位不会攻击防御单位,但若敌对单位未被防御单位消灭且成功跨越地图,玩家的生命数会减少。
dd_engi设计出了一种一维的塔防游戏,并将其命名为“魔法塔防”,规则如下:
游戏的地图是一行N个连续的魔法塔,其中行的一端是入口,另一端是出口,怪兽会从地图的一端向另一端移动。初始时,怪兽通过每个魔法塔的时间是T秒。玩家可以在这N个魔法塔中放置魔法师以对经过的怪兽造成伤害,每个魔法塔中最多放置一个魔法师,且放置好的魔法师不能改变位置。
共有三种不同属性的魔法师,分别是红色魔法师、蓝色魔法师和绿色魔法师,作用分别是攻击、减速以及下毒。当怪兽经过一个红色魔法师所在的魔法塔时,每秒钟生命值会减少R点;当怪兽从一个蓝色魔法师所在的魔法塔走出之后,通过每个魔法塔的时间延长B秒;当怪兽从一个绿色魔法师所在的魔法塔走出之后,每秒钟会因中毒失去G点生命值。蓝色魔法师的减速效果和绿色魔法师的下毒效果是可以累加的。也就是说,怪兽通过n个蓝色魔法师所在的魔法塔之后,它通过每个魔法塔的时间会变成T+B*n秒;怪兽通过n个绿色魔法师所在的魔法塔之后,它每秒钟会因中毒失去G*n点生命值。
现在,你的任务是,在这N个魔法塔里放置各种类型的魔法师,使通过的怪兽失去的生命值最大。输出这个最大值。
100%的数据满足1<=N<=1024; 0<= R, G, B <= 65536; 0<= T <= 3。

解法:首先这题可以贪心地认为红塔是应该放在后面的,因为绿塔和红塔当然是红塔在后面好,因为绿塔可以不断伤怪物血,如果是蓝塔和红塔也是红塔在后面好,因为前面减了速后面红塔才能伤害更大(你蓝塔放在后面又没有红塔放在那里干嘛)。所以这样就使题目简单了很多了。再用Dp解决蓝塔和绿塔的问题。如图:



最后的max就是答案了。

  

爱华网本文地址 » http://www.413yy.cn/a/25101014/228024.html

更多阅读

2011全国各地高考作文题集锦 2016全国高考作文题

2011-06-10 10:32:23|分类: 作文库 |标签: |字号大中小订阅2011高考作文题2011年全国高考,全国共有933万名考生走进考场。随着首门语文科目考试的结束,各省市高考作文题目陆续公布。【1】全国卷I高考作文:期待成长全国II卷作文题:材料作文

2012年高考作文需关注的话题 知乎如何关注话题

2012年高考作文需关注的话题  现在是同学们备战各种考试作文的紧要阶段,各式各样的学习方法、作文技巧铺天盖地而来,也许你疯狂地修炼秘籍、熟记技巧,但是你有没有想过这些做法为的是一个根本目的——夺取高分作文!为了这个目的而踏

2015甘肃高考状元出炉:理科676分文科660分

2015甘肃高考状元出炉:理科676分文科660分曹斌锋甘肃省2015年高考文理状元出炉,来自民乐一中的王复英以总分676分摘取理科第一名桂冠。文科状元惠雅婕来自西北师大附中,总分660分。恭喜他们!西北师范大学附中连续四年夺得甘肃高考状

2013年山东高考作文展望 2013山东高考作文题目

2013年高考作文展望山东卷高考作文在命题上一直是以稳为主,稳中求变。从08年的“春来草自青”,到09年的“见证”10年的“光与影”,再到11年的“这世界需要你”12年的“孙中山箴言”充分体现这一变化轨迹。从这种变化趋势来看,命题作文,材

声明:《rqnoj题目 高考作文题目出炉》为网友交际花分享!如侵犯到您的合法权益请联系我们删除