09.11.13 Programming >> , 4 comments

好久没刷过题了,先找了两道水题练手..

(1)已知1900年1月1日是星期1,一年365天,闰年366天.年份y是闰年的条件是(y%400==0)||(y%4==0&&y%100!=0),随意给出一个日期,求是星期几..

[解]首先,我确实没有说错题目,它的的确确是道水题,几乎所有C++入门书练习题上都有这题的影子.简单的计算就可以搞定了.但是,它又不是一道水题,不然我也不会特地找它练手了..其实这道题有个复杂度为O(1)的解法的.既然是O(1),那肯定也就是有公式的,我一直以为这么繁琐的东西应该不存在什么公式的,所以亲手验证一遍公式后我是相当的震撼.直接上公式吧,传说中的蔡勒公式(很神奇的,wikipedia上蔡勒老人家主页上居然没蔡勒公式.):

Zeller

公式都是基于公历的置闰规则来考虑,估计会背下来的人很少,贴在墙头要用的时候翻下就OK了.公式中的符号含义如下:

  1. w : 星期
  2. c : 世纪(两位数)
  3. y : 年(后两位数)
  4. m : 月(m 的取值范围为 3 至 14,即在蔡勒公式中,某年的 1`2月要看作上一年的 13`14月来计算,比如2003年1月1日要看作2002年的13月1日来计算)
  5. d : 日
  6. [　] : 称作高斯符号，代表取整，即只要整数部份.
  7. mod : 同余‎(这里代表括号里的答案除以 7 后的余数)(请注意前面是负数取模的情况，取模只可以是正数)

有点要说明的是,假如计算的日期是在1582年10月4日或之前,公式则为:

Zeller2

额..估计上面这个公式会记下的人就更少了.为什么会有两个计算公式呢?这个也许你得自己问教皇修改历法时为什么把1582年10月4日的下一天改为1582年10月15日了.

(2)给你一串念珠,珠子有红r`蓝b`白w三色.你需要选一个地方剪断串起念珠的绳子,展开成一直线,然后从剪断的地方向两头取珠子,然后从一端开始收集同颜色的珠子直到遇到一个不同的颜色珠子,在另一端做同样的事.白w色既可以认为是红r色,也可以认为是蓝b色..你的任务就是确定在哪剪断念珠,使得收集到的珠子数目最多,将它输出.

example: rwrwbwrwbwrwr

输出为: 10

[解] 这也是道水题.一般的搜索解法复杂度是O(n^2),据说可以优化到O(n).我没做出来,直接brute force过了..有空回来做这题.据说写博是最好的监督自己的方法,暂且立此为证.

(3) 守望者的逃离(via: sicily 1484)

守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的.庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点.守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复.现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T.你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离.注意: 守望者跑步`闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒.距离的单位为米(m).

[解] 其实这题并不水,是确确实实的不水.不信你现在就可以试着敲一下.模拟是会累死人的,贪心的话边界好麻烦,动态规划其实转移方程不太好找..总之我是累了个半死,后来上网看到了提示,很NB的提示.首先不考虑守望者能跑步,就是说,他只能站着不动积聚魔法,或者使用闪烁法术,这样的话题目就是很简单很简答的了.然后才考虑守望者能跑步,这时题目也是很简单的.直接给代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/* source code of submission 257777, Zhongshan University Online Judge System */
 
#include <iostream>
using namespace std;
 
int dis[300001];
 
void solve(int m,int s,int t)
{
    dis[0]=0;
    for(int i=1;i<=t;i++)
    {
        if(m>9)
        {
            dis[i]=dis[i-1]+60;
            m=m-10;
        }
        else
        {
            dis[i]=dis[i-1];
            m=m+4;
        }
    }
    for(int i=1;i<=t;i++)
    {
        dis[i]=(dis[i]>dis[i-1]+17)?dis[i]:dis[i-1]+17;
    }
    if(dis[t]<s)
    {
        cout<<"No"<<endl;
        cout<<dis[t]<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
        int i=t;
        while(dis[i]>s)
            i--;
        cout<<i+1<<endl;
    }
 
}
 
int main()
{
    int m,s,t;
    cin>>m>>s>>t;
    solve(m,s,t);
    while(cin>>m>>s>>t)
    {
        cout<<endl;
        solve(m,s,t);
    }
}