Codeforces Round #327 div2
Codeforces Round #327 div2
熙世
发布于 2019-07-14 13:47:02
发布于 2019-07-14 13:47:02
Problem_A(591A):
题意：
有一段长度为l的路，两个人分别在两个端点，1, l。 现在已知每个人的速度为p,q. 求第一个人(初始位置在1)在他们第二次相遇的时候的位置。
当他们相遇的时候， 他们会掉头返回走， 走到端点再返回来。
思路：
首先可以确定的是， 这两个人每次相遇的地点都是一样的。
然后， 设他们相遇时时间为t, 所以有：p * t + q * t = l
即：t = l / (p + q)
第一个人位置即为：t * p = l / (p + q) * p;
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int l, p, q;
36
37 int main()
38 {
39 scanf("%d %d %d", &l, &p, &q);
40 printf("%.4lf\n", (double)(l * 1.0 / (p * 1.0 + q * 1.0)) * (p * 1.0));
41 return 0;
42 }Problem_B(591B):
题意：
给一个长度为n的字符串， 然后进行m次操作。
每次操作(ch_a, ch_b)：将当前字符串中所有的字符ch_a替换成ch_b, 所有的ch_b替换成ch_a
求操作完后的字符串。
思路：
乍一看是个模拟， 再一看数据量2* 10 ^5 有点大， 不能直接模拟。
题目中有个条件：所有字母均为小写字母！！！
小写字母只有26个， 每次对这26个字母进行操作即可。
设 f[i] = j 为初始字母为i + 'a'的字符 当前变换成j + 'a' 字符
每次找出值为ch_a, ch_b的字符， 然后对其进行赋值操作即可。
这样一来就成了O(m * 26) 妥妥的1s
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 200010
23 #define MAXM 30
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n, m;
36 int name[MAXN];
37 int f[MAXM];
38 char read_char()
39 {
40 char ch;
41 while(ch = getchar())
42 {
43 if(ch >= 'a' && ch <= 'z') return ch;
44 }
45 }
46 int find_char(int x)
47 {
48 for(int i = 0; i < MAXM; i ++)
49 if(f[i] == x) return i;
50 return -1;
51 }
52
53 int main()
54 {
55 scanf("%d %d", &n, &m);
56 for(int i = 0; i < n; i ++)
57 name[i] = (read_char() - 'a');
58 for(int i = 0; i < MAXM; i ++)
59 f[i] = i;
60 char ch_a, ch_b;
61 for(int i = 0;i < m; i ++)
62 {
63 ch_a = read_char();
64 ch_b = read_char();
65 int pos_a = find_char(ch_a - 'a');
66 int pos_b = find_char(ch_b - 'a');
67 f[pos_a] = ch_b - 'a';
68 f[pos_b] = ch_a - 'a';
69 }
70 for(int i = 0; i < n; i ++)
71 printf("%c", f[name[i]] + 'a');
72 printf("\n");
73 return 0;
74 }Problem_C(590A):
题意：
给一个长度为n的数组a[]， 它有如下变化：
1：b[0] = a[0], b[n-1] = b[n - 1]
2：b[i] = （a[i - 1] ， a[i], a[i + 1])的中位数
且a[i] = 0 || a[i] = 1
求出最少多少次变化之后， 此数组不能再变化(即变化后和变化前一样)
思路：
有一个规律不难发现：如果有两个以上连续相同的数 如11, 00 那么这两个数在接下来的变化中会保持不变！！！
很简单， 因为是中位数， 而且只有0 1 那么如果a[i]的左右两边有一个或以上相同的数 那么a[i]就不会变。
然后再来看看那些不连续的数的规律：
1 1 0 1 0 1 0 1 0 0
这个数最后会变成 1 1 1 1 1 0 0 0 0 0！ 对称了， 再来看一个
0 0 1 0 1 0 1 0 0
变化后： 0 0 0 0 0 0 0 0 0 全变成0 了！ 再改变一下两端连续的那个值找找规律 就会发现
如果不连续串的长度为奇数， 那么它的左右两端肯定是相等的， 那么它中间的这段不连续的串最后都会变成它。且次数为(len / 2 + len % 2)
如果不连续串的长度为偶数， 那么它的左右两端肯定是不等的，最后中间这段不连续的串都会对半变化！ 左边的与左端点相等， 右边的与右端点相等。次数为 len /2
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n;
36 int a[MAXN];
37 void read()
38 {
39 for(int i = 0; i < n; i ++)
40 scanf("%d", &a[i]);
41 }
42
43 void solve()
44 {
45 int cnt = 0;
46 for(int i = 0; i < n;)
47 {
48 int j = i;
49 while(j + 1 < n && a[j] != a[j + 1])
50 j ++;
51 j ++;
52 cnt = max(cnt, (j - i - 2) / 2 + (j - i - 2) % 2);
53 if((j - i) % 2 == 1)
54 {
55 for(int k = i + 1; k < j; k ++)
56 a[k] = a[i];
57 }
58 else
59 {
60 for(int k = i + 1; k < (i + j) / 2; k ++)
61 a[k] = a[i];
62 for(int k = (i + j) / 2; k < j; k ++)
63 a[k] = a[j - 1];
64 }
65 i = j;
66 }
67 printf("%d\n", cnt);
68 for(int i = 0; i < n - 1; i ++)
69 printf("%d ", a[i]);
70 printf("%d\n", a[n - 1]);
71 }
72 int get_ans(int l, int r)
73 {
74 if(l == r) return 0;
75 if(a[l] == a[r])
76 {
77 for(int i = l + 1; i < r; i ++)
78 a[i] = a[l];
79 return (r - l) / 2;
80 }
81 else
82 {
83 for(int i = l + 1; i < (l + r + 1) / 2; i ++)
84 a[i] = a[l];
85 for(int i = (l + r + 1) / 2; i < r; i ++)
86 a[i] = a[r];
87 return (r - l - 1) / 2;
88 }
89 }
90 void solve_2()
91 {
92 int l = 0, ans = 0;
93 for(int i = 0; i < n; i ++)
94 if(i == n - 1 || a[i] == a[i + 1])
95 {
96 ans = max(ans, get_ans(l, i));
97 l = i + 1;
98 }
99 printf("%d\n", ans);
100 for(int i = 0; i < n; i ++)
101 printf(i == n - 1? "%d\n" : "%d ", a[i]);
102 }
103
104 int main()
105 {
106 scanf("%d", &n);
107 read();
108 // solve();
109 solve_2();
110 return 0;
111 }Problem_D(590B):
题意：
在一个二维坐标系上， 给两个点， 一个起点(x1, y1)， 一个终点(x2, y2).
一个时间t, 一个最大速度vmax
然后给两个速度向量（vx, vy）, (wx, wy).
从起点飞到终点， 方向和速度可以在任何时刻随意变换， 速度不超过vmax即可。
在前t秒， 会受到风的阻力(vx, vy). t秒风的速度变成(wx, wy)。 求到终点的最短时间。
思路：
首先， 不考虑方向和风的影响， 以最大速度前进， 那么ts内的移动的距离就是vmax * t。 如果再加上方向呢？
是不是就成了一个圆：
圆心 O = (x1, y1)
半径 r = vmax * t
再加上风的影响呢？
是不就就是将这个圆整体位移(vx*t, vy*t) ？
此时圆为：
圆心 O = (x1 + vx * t, y1 + vy * t)
半径 r = vmax * t
如果此时， 终点在圆内， 是否代表在ts内可以到达？
如果终点在圆外， 那么设时间为w， 此时这个圆:
圆心O = (x1 + vx * t + wx * (w - t), y1 + vy * t + wy * (w - t))
半径r = vmax * w
所以， 对时间进行二分， 找到最小的满足终点在圆内的时间即可。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 double x[2], y[2];
36 double v, t;
37 double vx, vy, wx, wy;
38 double sqr(double x)
39 {
40 return x * x;
41 }
42 double dis(double x1, double y1, double x2, double y2)
43 {
44 return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
45 }
46 bool is_ok(double tmp_t)
47 {
48 double tx, ty;
49 if(tmp_t > t)
50 {
51 tx = x[0] + t * vx + wx * (tmp_t - t);
52 ty = y[0] + t * vy + wy * (tmp_t - t);
53 }
54 else
55 {
56 tx = x[0] + tmp_t * vx;
57 ty = y[0] + tmp_t * vy;
58 }
59 double ans = dis(tx, ty, x[1], y[1]);
60 if(ans < v * tmp_t) return true;
61 return false;
62 }
63
64 int main()
65 {
66 scanf("%lf %lf %lf %lf", &x[0], &y[0], &x[1], &y[1]);
67 scanf("%lf %lf", &v, &t);
68 scanf("%lf %lf %lf %lf", &vx, &vy, &wx, &wy);
69 double ans_l = 0, ans_r = 1e8, mid;
70 while((ans_r - ans_l) >= eps)
71 {
72 mid = (ans_l + ans_r) / 2.0;
73 if(is_ok(mid)) ans_r = mid;
74 else ans_l = mid;
75 }
76 printf("%.7lf\n", ans_l);
77 return 0;
78 }Porblem_E(590C):
题意：
一个n * m的网格， #代表不能走， .代表沼泽，1 2 3 分别代表一类区域
现在要将这三个区域连通， 你可以把沼泽变成路。 求变化最少的沼泽， 使得三个区域连通起来。
思路：
因为1,2,3 可以看成三个块， 也可以看成三类起点。
将所有的1, 2, 3记录下来， 以此为起点， 搜索三次。
然后枚举它们三个区域的交点， 算出到三个区域的长度(沼泽数量)，取最小值即可。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 1000100
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1010
23 #define MAXM 3
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n, m;
36 int step[MAXM][MAXN][MAXN];
37 int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
38 int grid[MAXN][MAXN];
39 int read_ch()
40 {
41 char ch;
42 while(ch = getchar())
43 {
44 if(ch >= '1' && ch <= '3') return (int)(ch - '1');
45 if(ch == '.') return -1;
46 if(ch == '#') return -2;
47 }
48 }
49 bool check(int i, int j)
50 {
51 if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == -2) return false;
52 return true;
53 }
54 void bfs(int pos)
55 {
56 queue <int> Q;
57 while(!Q.empty()) Q.pop();
58 for(int i = 0; i < n; i ++)
59 for(int j = 0; j < m; j ++)
60 if(grid[i][j] == pos)
61 {
62 Q.push(i);
63 Q.push(j);
64 step[pos][i][j] = 0;
65 }
66 while(!Q.empty())
67 {
68 int x = Q.front();
69 Q.pop();
70 int y = Q.front();
71 Q.pop();
72
73 for(int i = 0; i < 4; i ++)
74 {
75 int xx = x + dir[i][0];
76 int yy = y + dir[i][1];
77 if(!check(xx, yy)) continue;
78 if(step[pos][xx][yy] > step[pos][x][y] + (grid[x][y] == -1))
79 {
80 step[pos][xx][yy] = step[pos][x][y] + (grid[x][y] == -1);
81 Q.push(xx);
82 Q.push(yy);
83 }
84 }
85 }
86 }
87
88 void show(int pos)
89 {
90 printf("%d\n", pos);
91 for(int i = 0; i < n; i ++, printf("\n"))
92 for(int j = 0; j < m; j ++)
93 printf("%d ", step[pos][i][j]);
94 printf("\n");
95 }
96
97 int main()
98 {
99 mes(grid, 0);
100 for(int k = 0; k < MAXM; k ++)
101 for(int i = 0; i < MAXN; i ++)
102 for(int j = 0; j < MAXN; j ++)
103 step[k][i][j] = INF;
104
105 scanf("%d %d", &n, &m);
106 for(int i = 0; i < n; i ++)
107 for(int j = 0; j < m; j ++)
108 grid[i][j] = read_ch();
109
110 for(int i = 0; i < MAXM; i ++)
111 bfs(i);
112
113 int ans = INF * 3;
114 for(int i = 0; i < n; i ++)
115 for(int j = 0; j < m; j ++)
116 ans = min(ans, step[0][i][j] + step[1][i][j] + step[2][i][j] + (grid[i][j] == -1));
117 if(ans >= INF) ans = -1;
118 printf("%d\n", ans);
119 return 0;
120 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-05-25 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号