盒子
盒子
文章目录
  1. 题目
    1. Problem A Triangle (水题)
    2. 思路
    3. Problem B Alice, Bob and Chocolate (水题)
    4. 思路
    5. Problem C President’s Office (水题)
    6. 思路
    7. Problem D Longest Regular Bracket Sequence (贪心)
    8. Problem E Exposition (二分, RMQ, set)
  2. 更新日志

CF练习赛3

题目

  • Problem A [CodeForces 6A] Triangle (水题)
  • Problem B [CodeForces 6C] Alice, Bob and Chocolate (水题)
  • Problem C [CodeForces 6B] President’s Office (水题)
  • Problem D [CodeForces 5C] Longest Regular Bracket Sequence (贪心)
  • Problem E [CodeForces 6E] Exposition (二分, RMQ)

Problem A Triangle (水题)

给出四个数字,从中任意选取三个,问能否构成三角形。如果不能,能否构成退化的三角形(即两边之和等于第三遍)

思路

每次选出三个数字,试试看能否构成三角形。试的时候可以先将数字排序一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int a, b, c, d;
int get(int x, int y, int z) {
if (x > y) swap(x, y);
if (x > z) swap(x, z);
if (y > z) swap(y, z);
if (x + y > z) return 1;
if (x + y == z) return 0;
return -1;
}
int main () {
cin>>a>>b>>c>>d;
int q = get(a, b, c);
int w = get(a, b, d);
int x = get(a, c, d);
int y = get(b, c, d);
if (q == 1 || w == 1 || x == 1 || y == 1) puts("TRIANGLE");
else if (q == 0 || w == 0 || x == 0 || y == 0) puts("SEGMENT");
else puts("IMPOSSIBLE");
return 0;
}

Problem B Alice, Bob and Chocolate (水题)

有一排巧克力,Alice和Bob分别从两头开始吃巧克力,Alice从左边,Bob右边。每个巧克力要消耗不同的时间,两个人不能同时吃一块巧克力。当两人要同时开始吃一块时,Bob会让Alice吃,问Alice和Bob各可以吃几块巧克力。

思路

模拟一下就行。或者直接从中间时间找一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N = 1e5 + 10;
int n;
int a[N];
int main () {
cin>>n;
a[0] = 0;
int x;
for (int i = 1; i <= n; i++) {
scanf("%d", &x);
a[i] = a[i - 1] + x;
}
if (n == 1) {
cout<<1<<" "<<0<<endl;
return 0;
}
int id = lower_bound(a + 1, a + n + 1, a[n] / 2) - a;
for (int j = max(id - 3, 1); j <= min(id + 3, n); j++) {
if (a[j - 1] > a[n] - a[j]) {
cout<<j - 1<<" "<<n - j + 1<<endl;
break;
}
}
return 0;
}

Problem C President’s Office (水题)

给定一个地图,’R’表示boss的地盘,’.’表示空地,其他字符表示小怪的地盘。问与’R’相邻的小怪有多少种。

思路

对于每个’R’,上下左右搜一下,统计一下小怪数。

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
int n, m;
char mp[111][111];
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
char p;
int pos[10010][2], cnt;
map<char, int> has;
int main () {
cin>>n>>m>>p;
cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin>>mp[i][j];
if (mp[i][j] == p) {
pos[cnt][0] = i, pos[cnt++][1] = j;
}
}
}
int sum = 0;
has.clear();
has[p] = 1;
for (int t = 0; t < cnt; t++) {
int x = pos[t][0], y = pos[t][1];
for (int i = 0; i < 4; i++) {
int tx = x + dx[i], ty = y + dy[i];
if (POSIN(tx, ty) && mp[tx][ty] != '.') {
int d = ++has[mp[tx][ty]];
if (d == 1) sum++;
}
}
}
cout<<sum<<endl;
return 0;
}

Problem D Longest Regular Bracket Sequence (贪心)

给定一串括号,长度为$n$, 求最长的能够匹配的(符合规则)的子序列,输出最长的长度,以及该长度的个数。如果没有匹配的,输出0 1
数据范围:$1{\leq}n{\leq}10^6$
http://siofive.github.io/2014/11/09/拉练3_D/

Problem E Exposition (二分, RMQ, set)

给定$n$个数,每个数为$h_i$,以及一个$k$。求最长的区间,使得该区间内所有数字的差值不超过$k$。第一行输出区间长度以及区间的个数,第二行输出每个区间$[l_i, r_i]$
数据范围:$1{\leq}n{\leq}10^5, 0{\leq}k, h_i{\leq}10^6$
http://siofive.github.io/2014/11/09/拉练3_E/

更新日志

  • 2014-11-9 AK