2011年4月TOJ新生有奖月赛解题报告

2011年4月TOJ新生有奖月赛-by 0929210011

A:Sort the Integers

    水题 输入一串数字,按从小到大排序,去掉重复的数字;输出的地方要注意下 不同数的个数也要输出,比赛的时候NC WA2次;

B: Frog' jump I

    给出一串字符串,判断青蛙是否能按照给定的方向跳完这些lotus leaves,按照题意的规则只要稍加判断就行了 N -> W , E , N.  E -> N , S ,E.  S -> W,E,S. W -> N,S,W.

C:2D Ballistik Game

好像是OpenGL中的碰撞检测,题意是给出圆和矩形判断圆和矩形是否相交;

那么如何判断相交呢?

(1) 先把一定不相交的情况排除掉 就是圆的外接矩形和给定的矩形不相交(即快速排斥试验

if(min(x1,x2)<=max(x3,x4) &&
min(x3,x4)<=max(x1,x2) &&
min(y1,y2)<=max(y3,y4) &&
min(y3,y4)<=max(y1,y2))  2
个矩形是相交的

(2) 2个矩形相交的前提下(圆在矩形右上),考虑下最极端的情况就是矩形的重点和圆心的连线正好经过矩形的一个顶点此时两心的距离是dis = r1 + r; 显而易见当dis > r1 + r的时候不相交,dis = r1 + r 的时候相交;然后考虑dis < r1 + r的情况,dis < r1 + r当且仅当在此基础上向左平移,向下平移或向左下平移此时也是相交的,同理可得其他四种情况 ;

 

D:塔神的钱包

这题刚开始看了几次,就是看不懂,发现XZC的题目屁话特多。

题意是给出N 个钱包 你可以取1个钱包 2个钱包 …… N个钱包,但是对于多个钱包有相同的面值的话 只能取一张 求能有多少种组合;(对于总价值 5 = 1 + 4 5 = 2 + 32种情况)。

一共最多有14种面值,那么可以把一个钱包想成一个14位的2进制数,组成的最大数也就是 (2^14 -1)

对于第一组数据

2

3 10000 500 20    -> 10100001000000; +1

4 10000 500 20 50 -> 10100101000000; +1

第一个钱包 和 第二个钱包 组合 就是10100001000000 | 10100101000000 = 10100101000000;同于第二个钱包,

所以total = 2

那么就是对状态进行或运算的母函数,每个钱包和每个状态或运算组合下

时间复杂度O(n*(2^14-1))

 

a[i]为第i个钱包的状态值

for(i = 0; i < n; i++)

{

       for(j = 1; j <= 1<<14-1); j++)

       {

              c2[(j|a[i])] |= c1[j];

       }

       for(j = 1; j <=1<<14-1); j++)

       {

              c1[j] |= c2[j];

              c2[j] = false;

       }

}

E:Twinkle, Twinkle All the Night

题意是给你一串代表夜空的字符, "*"代表star 然后让你统计star的个数

可用C++ 中的count(str.begin(),str.end(),"*");

F:Divide Two

题意是按照题目的规则(能被2整数就除2,否则变回n)产生一串序列,然后叫你求序列的第mth个数;

 

G:Edit the String

题意是首先给出一串少于80个字符的串,然后进行一系列的操作,如果操作时非法的就忽视掉;

对于操作

(1)c插入ith个字符的前面1 <= i && i <= str.length().

(2)把所有的c1替换成c2 (直接遍历替换c1 - > c2);

(3)删除第i个元素(1 <= i && i <= str.length().

(4)s串增加到str串尾部(注意str的长度要足够,因为操作多了,str会很长)

(5)输出字符串

H:蜘蛛纸牌

题意是给出一串蜘蛛纸牌,按照规则判断是否还有可行的操作,为了简化问题,我们只判断最上面的那张牌还可不可以移动到别的牌上直接暴力判断是否存在a = b + 1的情况。


为解题报告打分
暂时不评分

★★
★★★
★★★★
★★★★★
发表您的评论(若贴AC代码或发表禁止言论等违禁行为将被删除并扣除积分)

|返回 |   | 转到页头|
Copyright @ 2008-2024(浙ICP备2022001332号), TZOJ. All Rights Reserved.