传送带(三分查找)

题目描述:

在一个二维平面上有两条传送带,每一条传送带可以看成是一条线段。两条
传送带分别为线段 AB 和线段 CD。小 y 在 AB 上的移动速度为 P,在 CD 上的
移动速度为 Q,在平面上的移动速度 R。现在,小 y 想从 A 点走到 D 点,请问
他最少需要走多长时间。

输入格式:

第一行是4个整数,表示A和B的坐标,分别为Ax,Ay,Bx,By。
第二行是4个整数,表示C和D的坐标,分别为Cx,Cy,Dx,Dy。
第三行是3个整数,分别是P,Q,R。

输出格式:

输出一行一个数,表示小 y 从 A 点走到 D 点的最短时间,保留到小数点后
2位。

样例输入:

0 0 0 100
100 0 100 100
2 2 1

样例输出:

136.60

数据范围:

对于30%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=10
1<=P,Q,R<=5
对于100%的数据满足:
1<=Ax,Ay,Bx,By,Cx,Cy,Dx,Dy<=1000
1<=P,Q,R<=10

继续阅读传送带(三分查找)

7月21日备战Noip2017暑假集训6(A) 数对【二进制保存状态】

数对

【问题描述】

有n个数,定义友好数对为两个数至少有一个相同的数字(不要求在相同位置),那么这两个数就是友好数对。求有多少对友好数对。

【输入格式】

第一行一个正整数n。

接下来n行,每行一个正整数,范围在1—10^18。

n个数中任意两个数都是不同的。

【输出格式】

只有一行一个整数,表示友好数对的个数。

【输入样例】

4

32

51

123

282

【输出样例】

4

【样例解释】

(32,123),(32,282),(51,123),(123,282)。

数据范围与约定

对于50%的数据:n<=10000。

对于100%的数据:n <= 1000000。

继续阅读7月21日备战Noip2017暑假集训6(A) 数对【二进制保存状态】

7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

接力

【问题描述】

接力共有n名队员(编号1-n)参加,在同一时刻赛道上允许有任意多名选手同时赛跑。比赛开始前,所有交警在起跑线等待起跑。

在t=0时刻,编号为1的选手开始赛跑,L1秒后跑完一圈回到起点。当选手i跑完一圈他会示意Mi名选手开始接力。(选手可能被多次示意,只算最早的示意)每个选手只跑一圈。

接力的总时间为最后一个选手结束赛跑的时间。求接力的总时间。

【输入格式】

第一行一个单独的整数n,表示有n名选手。

接下来n行,每行开始有2个整数Li,Mi,接下来有Mi个整数,表示示意选手的编号。

【输出格式】

一行一个整数,表示接力的总时间。

【输入样例】

5

4 2 2 4

3 3 1 3 4

7 1 5

4 2 3 5

1 0

【输出样例】

14

数据范围与约定

对于30%的数据:n <= 10。

对于60%的数据:n <= 300。

对于100%的数据:n <= 1000。

继续阅读7月21日备战Noip2017暑假集训6(A) 接力【最短路,优先队列(存疑)】

7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】

单词

【问题描述】

在一种未知语言中,很多单词被发现了,但是他们的字母的字典序我们是不知道的。我们知道的是,这些单词是按照字典序从小到大排列的。

或者找出这种语言唯一的字母的字典序,或者得出这种方案是不存在的,或者得出有很多种这样的方案。

【输入格式】

第一行包括一个正整数n(1 <= n <= 100),表明单词的数量。

接下来n行,每行一个单词,每个单词最多包含10个小写的英文字母。保证单词以未知语言的字典序给出。

【输出格式】

有且仅有一行,输出包含所有字母的字典序。如果没有这种字典序,则输出“!”,如果有多种方案则输出“?”。

【输入样例1

5

ula

uka

klua

kula

al

【输出样例1

luka

【输入样例2

4

jaja

baba

baja

beba

【输出样例2

【输入样例3

3

marko

darko

zarko

【输出样例3

数据范围与约定

对于30%的数据:n <= 20。

对于100%的数据:n <= 100。

继续阅读7月21日备战Noip2017暑假集训6(A) 单词 【拓扑排序】

7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

晨练

【问题描述】

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。

在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下,小 Y 最多能跑多少米。

【输入格式】

第1行:2个用空格隔开的整数:n,m。

第2..n+1行:第i+1行为1个整数D_i。

【输出格式】

输出一行为一个整数,表示在满足所有限制条件的情况下,小y能跑的最大距离。

【输入样例】

5 2

5

3

4

2

10

【输出样例】

9

数据范围与约定

对于30%的数据:n<=50。

对于100%的数据:n<=10000。

继续阅读7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】

【问题描述】

Alice和Bob正在悄悄地给对方发信息,信息都是由英文小写字母组成的,他们约定,所有的字母都得经过一个字母表进行变换,以防泄漏。另一方面John却在监听。

John发现,Alice和Bob通信的时候,总是先发送加密后的密文,然后紧接着发送原文。

但是Alice和Bob似乎也意识到了似乎有人监听,有时候会随意中断了他们的通信。不过每次都是在发送完密文之后才停止传送的。也就是说,John截获到的信息是密文的全文以及前一部分原文。原文可能一个字符都没有,也可能原文的全文都被截获。

现在John比较头疼,他虽然已经得到了他们两个人通信的加密字母表,但是分不清楚什么地方是密文和明文的分界线。你能帮他还原回完整的传输内容吗?

如果有多种可能时,John认为那个最短的信息才是原始的。

【输入格式】

第一行是密码表格,包含26个小写字母,依次表示a-z加密后的字母。

第二行是John截获到的通信信息。

【输出格式】

包含一行,表示还原后的通信信息。

【输入输出样例一】

recover.in recover.out
abcdefghijklmnopqrstuvwxyz

abcdab

abcdabcd

 

【输入输出样例二】

recover.in recover.out
qwertyuiopasdfghjklzxcvbnm

qwertabcde

qwertabcde

【数据规模】

    对于30%的数据:L<=100。

对于100%的数据:通信长度L<=100000。

继续阅读7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】

7月18日备战Noip2017暑假集训3(A) 坦克

【问题描述】

小H有一位朋友叫WJ,他非常喜欢坦克,我们亲切的称他“坦克之王”。

后来WJ发现有很多人也很喜欢坦克,并且他们举办了一个关于坦克的比赛,具体规则如下:

地上的一块区域被N+1条横线和M+1条竖线(横线竖线编号从左往右从上往下从0开始到N+1和M+1)划分成了N*M块,每一块都是变长为4的正方形。每个正方形的中心放了一辆坦克,每辆坦克都有一个权值,现在裁判要求所有玩家选定一个位置(必须位于横线和竖线的交叉点上),然后计算得分,谁的得分小谁就胜出。得分的计算为参赛者所在位置与每辆坦克所在位置直线距离的平方和坦克权值乘积的和。具体如图(图在最后)。

WJ想在这次比赛中获胜,已捍卫他坦克之王的地位,请你帮帮他。

【输入格式】

第一行两个整数N,M。

下面N行每行M个数表示格子中坦克的权值。

【输出格式】

第一行一个数字表示最小的得分。

第二行两个数字空格隔开分别表示WJ所在位置横线的编号和竖线的编号。

【输入输出样例】

样例输入(tank.in) 样例输出(tank.out)
2 3
3 4 5
3 9 1

 

392
1 1

 

3 4
1 0 0 0
0 0 3 0
0 0 5 5

 

240
2 3

 

【样例说明】

得分3*8+3*8+4*8+9*8+5*40+1*40=392.

可以证明是最小的。

【数据范围】

对于40%的数据,1<=N,M<=100;

对于100%的数据,1<=N,M<=1000,坦克的权值不超过100000;

我想说的话程序会帮我解释


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
#include<cstdio>
#include<iostream>
 
using namespace std;
 
long long square(int x)
{
        return x*x;
}
 
long long move_x[1010][3], move_y[1010][3];
int map[1010][1010];
long long val_x[1010], val_y[1010];
long long cnt_val[1010][1010];
 
int main(void)
{
 
       
        int i, j, n, m;
        scanf("%d%d", &n, &m);
        for (i = 1; i <= n; i++)
        {
                for (j = 1; j <= m; j++)
                {
                        scanf("%d", &map[i][j]);
                        val_x[i] += map[i][j];
                        cnt_val[1][1] += (square((i-1)*4-2)+square((j-1)*4-2))*map[i][j];
                }
        }
        for (i = 1; i <= m; i++)
        {
                for (j = 1; j <= n; j++)
                {
                        val_y[i] += map[j][i];
                }
        }
       
        for (i = 1; i < n; i++)
        {
                for (j = 1; j <= n; j++)
                {
                        move_x[i][1] += val_x[j]*(square((4*(i+1))-(4*j-2))-square((4*i)-(4*j-2)));
                        //move_x[i][0] += val_y[j]*(square((4*i)-(4*j-2))-square((4*(i-1))-(4*j-2)));
                }
        }
        for (i = 1; i < m; i++)
        {
                for (j = 1; j <= m; j++)
                {
                        move_y[i][1] += val_y[j]*(square((4*(i+1))-(4*j-2))-square((4*i)-(4*j-2)));
                        //move_y[i][0] += val_y[j]*(square((4*i)-(4*j-2))-square((4*(i-1))-(4*j-2)));
                }
        }
       
       
        long long minx = 500000000000000000ll;
        int ans_x,ans_y;
        if (n == 1) n++;
        for (i = 1; i < n; i++)
        {
                for (j = 1; j < m; j++)
                {
                        if (i == 1&&j == 1) continue;
                        if (j == 1) cnt_val[i][j] = move_x[i-1][1] + cnt_val[i-1][j];
                        else cnt_val[i][j] = move_y[j-1][1] + cnt_val[i][j-1];
                        if (minx > cnt_val[i][j])
                        {
                                minx = cnt_val[i][j];
                                ans_x =i;  ans_y=j;
                        }
                }
        }
        if (ans_x == 1&&n == 2) ans_x--;
 
        printf("%lld\n%d %d", minx, ans_x, ans_y);
 
        return 0;
}

【NOIP2011】观光公交 题解

题目传送门:!点我传送!

每个人在车上的时间 等于 车到达目的站的时间 减去 这个人到达起始站的时间
由于人到达起始站的时间题目给出不会变化
所以求解一个最优的车到达目的站的时间即可

假设到达第i+1站的时间是time[i]
从前往后逐个求解到站时间
可以得出time[i] = max{time[i-1], last[i]} + d[i]
其中last[i]为从第i站上车的旅客中最后到达的一个到达的时间 可以用O(n+m)的时间预处理得出
d[i]为从i走到i+1所用的时间
很明显的 我们可以利用这个递推关系式用O(n)的时间求解time[i]

当我们令d[i]减少1时
time[1..i-1]不会变化
time[i]会减少1
考虑time[i+1]
由前面的式子得出time[i+1] = max{time[i], last[i+1]} + d[i+1]
若我们令d[i]减少之前 存在time[i] > last[i+1]则time[i+1]会减少1 否则time[i+1]就会不变
若time[i+1]减少了1 我们可以用同样的方法判断time[i+2]直到最后是否变化
若time[i+1]不变 则time[i+2]及之后的time值都不会变化
**所以 当我们令某个d[i]减少1时 从time[i]开始会有一段区间的time值均减少1

这个区间的左端为i 我们令右端为range[i]
对于j属于从i+1到range[i] 均存在time[j-1] > last[j] 且对于range[i]+1不存在time[j-1] > last[j]

说到这里 大家应该发现求解range[i]的方法了
若range[i+1] = t 则对于从i+2到t前不等式均成立且对于t+1不成立
所以我们求解range[i]只需判断对于i+1前不等式是否成立即可
若成立则 range[i] = range[i+1] 不成立则 range[i] = i

若我们修改每个值所减少的时间为reduce[i] 则reduce[i] = v[i] + v[i+1] + ... +v[range[i]]
v[i]表示到达第i+1个车站的人的数量
很明显的 reduce[i] = v[i] + reduce[i+1] 或 v[i]

现在 我们可以用O(n)的时间求解reduce了
然后每次选择一个令reduce[i]最大的i 令d[i]减少即可

注意每次修改d[i]之后 要重新计算新的time[i]

时间复杂度O(kn)

继续阅读【NOIP2011】观光公交 题解

【NOIP2010】引水入城 题解(Probably)

题目传送门:!点我传送!

知识点:广度优先搜索+区间最小覆盖

题目大意就是给我们一张图,我们只能从第一行的任意位置出发,走一条高度递减的路径到最后一行,要求我们达到最后一行的每一个位置。问我们最少要走几条路,若无法达到最后一行的全部位置则要求输出有几个位置我们无法到达。

首先我们先对题目进行分析,因为流水路径是连续的,所以对于在可以到达最后一行每个位置的情况下,第一行某个位置作为起点,则其能到达最后一行的位置势必是连续的,不理解的可以自己画图举反例看看。对于每个起点所到最后一行我们可以看做是一个范围是[L,R]的区间,那接着我们只要求出哪几个区间能将总区间覆盖并使使用的区间最少,这就是区间最小覆盖问题。

  • 对于找第一行所对应很明显我们只要用广度优先搜索找出其对应的区间即可。但在这要注意要进行剪枝,不然讲道理是会被卡一个点的。因为每个点所能流到位置是固定的,所以如果X点能到达Y点,那X点也能到达Y所能到达的点。所以对于第一行我们只要对凸出来的最高点进行广搜。
    
    
    1
    2
    3
    4
    5
        for (i = 1; i <= m; i++)
        {
            if (map[1][i]<map[1][i+1]||map[1][i]<map[1][i-1]) continue;//判断是否有其他点可以流到该点
            ji[++ji[0]] = i; //将凸出的点记录到数组中
        }
  • 在已知第一行的范围后,我们只要跑一遍区间最小覆盖问题即可。
  • 用一个数组f[i]记录以i为左端点的区间能覆盖的最大距离,再用一个数组Ans记录能覆盖这个点的且向右距离最大的区间的右端点。最后再根据Ans让每个取得查询尽量靠右,统计取得区间个数即为最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    Ans[1] = f[1];
    for(i = 2; i <= m; i++)
    {  
        if(Ans[i-1]>f[i])  
        {  
            Ans[i] = Ans[i-1];  
        }  
        else  
        {  
            Ans[i]=f[i];  
        }  
    }  
   
    i = 1;
    int sum = 0;
    while (i<=m)
    {
        i = Ans[i]+1;
        sum++;
    }

以下为完整代码:

继续阅读【NOIP2010】引水入城 题解(Probably)

【NOIP2011】 Mayan游戏(gtmd搜索)

传送门:!点我传送!

话不多说,先贴代码


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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int map[6][8];

int ans[4][10];

void fall()
{
    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= 7; j++)
        {
            int x=i,y=j;
            while (map[x][y]!=0&&map[x][y-1]==0&&y>1)
            {
                map[x][y-1]=map[x][y];
                map[x][y]=0; y--;
            }
        }
    }
}

void check()
{
    int k = 1;
    while (k)
    {
        int map_D[6][8];
        memset(map_D,0,sizeof(map_D));
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 7; j++)
            {
                if (map[i][j] == 0) break;
               
                if (j>=3&&map[i][j] == map[i][j-1]&&map[i][j-1] == map[i][j-2])
                    map_D[i][j]=map_D[i][j-1]=map_D[i][j-2]=1;
                   
                if (i>=3&&map[i][j] == map[i-1][j]&&map[i-1][j] == map[i-2][j])
                    map_D[i][j]=map_D[i-1][j]=map_D[i-2][j]=1;
            }
        }
       
        k=0;
        for (int i = 1; i <= 5; i++)
        {
            for (int j = 1; j <= 7; j++)
            {
                if (map_D[i][j] == 1)
                {
                    k = 1;
                    map[i][j] = 0;
                    map[i][0]--;
                }
            }
        }
        if (k) fall();
    }
}

void exchange(int x, int y, int k)
{
    if (map[x+k][y] != 0)
    {
        int ex=map[x+k][y];
        map[x+k][y] = map[x][y];
        map[x][y] = ex;
        check();
    } else
    {
        int ex=map[x+k][y];
        map[x+k][y] = map[x][y];
        map[x][y] = ex;
        map[x][0]--; map[x+k][0]++;
        fall();
        check();
    }
}

int boom = 0,n;
void dfs(int x)
{
    int sum = 0;
   
    int col[12];
    memset(col,0,sizeof(col));
    for (int i = 1; i <= 5; i++)
    {
        sum+=map[i][0];
        for (int j = 1; j <= map[i][0]; j++)
            col[map[i][j]]++;
    }
    for(int i = 1; i <= 10; i++)  
        if(col[i] != 0&&col[i] < 3) return;
         
    if(sum==0&&x<n) return;
    if(x==n)
    {
        if (sum==0)
            boom = 1;
        return;
    }
   
    int map1[6][8];
    memcpy(map1,map,sizeof map1);

    for (int i = 1; i <= 5; i++)
    {
        for (int j = 1; j <= map[i][0]; j++)
        {
            for (int k = 1; k >= -1; k=k-2)
            {
                if (i == 5 && k == 1) continue;
                if (i == 1 && k == -1) continue;
                if (map[i][j] == map[i+k][j]) continue;
                if (k == -1 && map[i-1][j]!=0) continue;
                exchange(i, j, k);
                dfs(x+1);
                if (boom)
                {
                    ans[1][x] = i-1;
                    ans[2][x] = j-1;
                    ans[3][x] = k;
                    return;
                }
                memcpy(map,map1,sizeof map);
            }
        }
    }
   
}

int main(void)
{
    int i;
    scanf("%d", &n);
    for (i = 1; i <= 5; i++)
    {
        int x_;
        map[i][0] = 0;
        while (1)
        {
            scanf("%d", &x_);
            if (!x_) break;
            map[i][++map[i][0]] = x_;
        }
    }
    dfs(0);
    if(boom)
      for (i=0;i<n;i++)
        printf("%d %d %d\n",ans[1][i],ans[2][i],ans[3][i]);
    else printf("-1");
    return 0;
}

写得我心神憔悴,讲道理这题不难,所以难度就只有代码的构建。

对于这种脑残模拟,代码长度成了它报复社会的唯一方法。这题也就照着题目意思分成下面几个步骤

  1. 深搜:每次对每一个方块进行搜索,分别列举出其向右移和向左移的情况,找出符合题目要求情况即可。
  2. 下落:对于下落的判断只要是图中一个方块其底下有空,那其就得不断下落,直到接触方块为止,对于下落方块上方的方块也应进行下落。至于执行下落的时间就是在交换后或在去除方块后要执行下落的步骤。
  3. 去除方块:去除方块就是连续3个相同颜色要进行删除,在此要注意删除是在要搜索完整个图再进行删除,若是搜索到一个可删的三个方块就直接删除的话就无法判断类似“丁”字图形删除的了。同样这个步骤要在交换和下落后进行。
  4. 注意:去除方块后要执行下落,下落后要执行去除方块。。。直到没有方块去除为止

对于一些剪枝

在每次搜索过程中我们若发现某一颜色少于三种,那这种颜色就永远无法消去,直接return就好了。


1
2
3
4
5
6
7
8
    int col[12];
    memset(col,0,sizeof(col));
    for (int i = 1; i <= 5; i++)
    {
        sum+=map[i][0];
        for (int j = 1; j <= map[i][0]; j++)
            col[map[i][j]]++;
    }

因为题目要求答案按字典序输出,所以如果只是交换的话,和右边的方块交换是没有意义的(因为可看做右边的方块与左边的交换),同样,和相同方块交换也是没有意义的。


1
2
    if (map[i][j] == map[i+k][j]) continue;
    if (k == -1 && map[i-1][j]!=0) continue;