(4)  接上一篇 水题..(1) 中的第2题,其实我一早就怀疑念珠这道题是有O(n)的解法的,可惜因为题目的数据规模比较小,我直接暴力过了..今天好无聊,于是重新看了遍题目,很神奇的看出了动态规划的转移方程.想法是这样子的: 分别用数组left_r,left_b,right_r,right_b表示在项链i处向左,右能够收集到的篮色`红色珠子数..因为念珠是环形的,为了使其为线形的,将两串念珠放在同一字符串str中即可,此时str长度为2*len.
下面以求left_r,left_b为例:

left_r[0]=left_b[0]=0
For i from 1 to 2*len-1

If     str[i]=’r’,

left_r[i]=left_r[i-1]+1

left_b[i]=0

If     str[i]=’b’,

left_b[i]=left_b[i-1]+1

left_r[i]=0

If     str[i]=’w’,

left_b[i]=left_b[i-1]+1

left_r[i]=left_r[i-1]+1

同理可以求出right_r,right_b.最终输出的结果就是:

Broken_Necklace

代码如下:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
 
int right_r[801],right_b[801],left_r[801],left_b[801];
string str;
int len;
 
int max(int a,int b)
{
    return a>b?a:b;
}
 
int main()
{
    ifstream in("beads.in");
    ofstream out("beads.out");
    in>>len>>str;
 
    for(int i=0;i<len;i++)
        str.push_back(str[i]);
 
    left_r[0]=0;
    left_b[0]=0;
    for(int i=1;i<=2*len;i++)
    {
        if(str[i-1]=='r')
        {
            left_r[i]=left_r[i-1]+1;
            left_b[i]=0;
        }
        if(str[i-1]=='b')
        {
            left_b[i]=left_b[i-1]+1;
            left_r[i]=0;
        }
        if(str[i-1]=='w')
        {
            left_r[i]=left_r[i-1]+1;
            left_b[i]=left_b[i-1]+1;
        }
    }
 
    right_r[2*len]=0;
    right_b[2*len]=0;
    for(int i=2*len-1;i>=0;i--)
    {
        if(str[i]=='r')
        {
            right_r[i]=right_r[i+1]+1;
            right_b[i]=0;
        }
        if(str[i]=='b')
        {
            right_b[i]=right_b[i+1]+1;
            right_r[i]=0;
        }
        if(str[i]=='w')
        {
            right_r[i]=right_r[i+1]+1;
            right_b[i]=right_b[i+1]+1;
        }
    }
 
    int m=0;
    for(int i=0;i<2*len;i++)
    {
        m=max(m,max(right_r[i],right_b[i])+max(left_r[i],left_b[i]));
    }
 
    if(m<len)
        out<<m<<endl;
    else
        out<<len<<endl;
    return 0;
}

其实这道题还有更加简洁的方法,继续留给明天.

(5)  三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300时刻(从5点开始计时,秒为单位)给他的牛挤奶,一直到1000时刻.第二个农民在700时刻开始,在 1200时刻结束.第三个农民在1500时刻开始2100时刻结束.期间最长的至少有一个农民在挤奶的连续时间为900秒(从300时刻到1200时刻),而最长的无人挤奶的连续时间(从挤奶开始一直到挤奶结束)为300时刻(从1200时刻到1500时刻).
你的任务是编一个程序,读入一个有N个农民(1 <= N <= 5000)挤N头牛的工作时间列表,计算以下两点(均以秒为单位):

  1. 最长至少有一人在挤奶的时间段.
  2. 最长的无人挤奶的时间段(从有人挤奶之后开始算起).

[解] 这题不像前面那道,真的是水题了.如果你会线段树的话,直接就能搞定它了.凑巧我不大会,而且我正好已经做过sicily 1484 校门外的树 这题了,因此直接拿了1484的代码修改了一下,过了.

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
 
struct tree
{
    int x;
    int y;
}over;
 
vector<struct tree> v,temp;
 
int cmp(const struct tree &t1,const struct tree &t2 )
{
    if(t1.x<t2.x)
        return 1;
    if(t1.x==t2.x)
        return t1.y<t2.y;
    return 0;
}
 
int main()
{
    int L,M;
    ifstream in("milk2.in");
    ofstream out("milk2.out");
    in>>M;
    for(int i=0;i<M;i++)
    {
        in>>over.x>>over.y;
        v.push_back(over);
    }
    sort(v.begin(),v.end(),cmp);
 
    over=v[0];
    temp.push_back(over);
 
    for(int i=1;i<M;i++)
    {
        over=v[i];
        if(over.x>temp[temp.size()-1].y)
            temp.push_back(over);
        else
        {
            if(over.x<=temp[temp.size()-1].y&&over.x>=temp[temp.size()-1].x)
            {
                over.x=temp[temp.size()-1].x;
                over.y=(over.y>temp[temp.size()-1].y)?over.y:temp[temp.size()-1].y;
                temp.pop_back();
                temp.push_back(over);
            }
            else
            {
                if(over.x<temp[temp.size()-1].x)
                {
                    if(over.y>=temp[temp.size()-1].x)
                    {
                        temp.pop_back();
                        temp.push_back(over);
                    }
                    else
                    {
                        temp.push_back(over);
                    }
                }
            }
        }
    }
 
    if(temp.size()==1)
        out<<temp[0].y-temp[0].x<<" "<<0<<endl;
    else
    {
        int max=0;
        int max2=temp[1].x-temp[0].y;
        for(int i=0;i<temp.size();i++)
        {
            if((temp[i].y-temp[i].x) > max)
                max = temp[i].y-temp[i].x;
        }
 
        for(int i=2;i<temp.size();i++)
        {
            if((temp[i].x-temp[i-1].y) > max2)
                max2 = temp[i].x-temp[i-1].y;
        }
        out<<max<<" "<<max2<<endl;
    }
}

PS: 豆瓣最近出了个豆瓣电台,好喜欢啊.对于我这种想要听歌又不清楚有什么歌可以听的人来说,豆瓣电台做得很不错.因为功能比较简单,选歌的余地很少,所以我也省去不少挑歌的时间,而且豆瓣强推的歌貌似都很合我胃口..
PS2: 老丘最近又在泡妞了..god,我的MM在哪里啊.