盒子
盒子
文章目录
  1. 题目
    1. Problem A Die Roll
    2. Problem B Train and Peter
    3. Problem C Kalevitch and Chess
    4. Problem D Line (扩展欧几里得)
    5. 思路
    6. Problem E Exposition (bitmasks, dp)
  2. 更新日志

CF练习赛4

题目

  • Problem A [CodeForces 9A] Die Roll
  • Problem B [CodeForces 8A] Train and Peter
  • Problem C [CodeForces 7A] Kalevitch and Chess
  • Problem D [CodeForces 7C] Line (扩展欧几里得)
  • Problem E [CodeForces 8C] Looking for Order (bitmasks, dp)

Problem A Die Roll

给定三个骰子,已知前两个的数字,问有多大的概率使得第三个骰子的值不小于前两个的最大值。

1
2
3
4
5
6
7
8
9
10
int main () {
int x, y;
cin>>x>>y;
if (x > y) swap(x, y);
x = 6 - y + 1;
int g = __gcd(x, 6);
if (x == 0) puts("0/1");
else cout<<x / g<<"/"<<6 / g<<endl;
return 0;
}

Problem B Train and Peter

给定三个字符串A,B,C。问B和C是否按照顺序出现在A中(B和C分别为A的子串,且不重复)
如果只有从左到右可以,输出forward
如果只有从右到左可以,输出backward
如果都可以,输出both
否则输出fantasy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1e5 + 10;
char str[N];
char a[111], b[111];
int n, la, lb;
int get(char a[], char b[], char str[]) {
char *t = strstr(str, a);
if (!t) return -1;
if (strstr(t + la, b)) return 1;
return -1;
}
int main () {
scanf("%s%s%s", str, a, b);
n = strlen(str);
la = strlen(a); lb = strlen(b);
int x = get(a, b, str);
reverse(str, str + n);
int y = get(a, b, str);
if (x == 1 && y == 1) puts("both");
else if (x == 1 && y == -1) puts("forward");
else if (x == -1 && y == 1) puts("backward");
else puts("fantasy");
return 0;
}

Problem C Kalevitch and Chess

给定一张8X8的地图,一开始全是白色,每次可以选择一行或一列将其全部染为黑色。现给定一个最终状态的地图,问最少需要染色多少次。

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
int mp[10][10];
int b[10][10];
int main () {
int tot = 1 << 16;
int mn = 100;
char ch;
rep(i, 0, 8) {
rep(j, 0, 8) {
cin>>ch;
if (ch == 'B') mp[i][j] = 1;
else mp[i][j] = 0;
}
}
for (int i = 0; i < tot; i++) {
memset(b, 0, sizeof(b));
int t = 0;
for (int j = 0; j < 16; j++) if ((i >> j) & 1) {
t++;
if (j >= 8) for (int l = 0; l < 8; l++) b[l][j - 8] = 1;
else rep(l, 0, 8) b[j][l] = 1;
}
if (t < mn) {
bool ok = 1;
rep(l, 0, 8) rep(q, 0, 8) if (mp[l][q] != b[l][q]) {
ok = 0;
break;
}
if (ok) mn = t;
}
}
cout<<mn<<endl;
return 0;
}

Problem D Line (扩展欧几里得)

给定一条直线:$Ax+By+C=0$。请在$[-5{\cdot}10^{18},5{\cdot}10^{18}]$的范围内找到任意一个在该直线上的整点,否则输出-1
数据范围:$-2{\cdot}10^9{\leq}A,B,C{\leq}2{\cdot}10^9$

思路

扩展欧几里得,如果C % gcd(A, B) != 0,无整数点,否则有解。

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
ll x, y;
ll extend_gcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
else {
ll r = extend_gcd(b, a % b, y, x);
y -= x * (a / b);
return r;
}
}
int main () {
ll A, B, C;
cin>>A>>B>>C;
if (A == 0) {
if (C % B) puts("-1");
else {
cout<<0<<" "<<-C / B<<endl;
}
} else if (B == 0) {
if (C % A) puts("-1");
else {
cout<<-C / A<<" "<<0<<endl;
}
} else {
ll d = __gcd(A, B);
if (C % d) puts("-1");
else {
extend_gcd(A, B, x, y);
ll tx = x * (-C / d), ty = y * (-C / d);
cout<<tx<<" "<<ty<<endl;
}
}
return 0;
}

Problem E Exposition (bitmasks, dp)

给定起点,以及$n$个物品的位置。现在规定每次从起点出发,可以选择一个物品,并且将其带回起点;或者选择两个物品,先后走到两个物品处,将其带回起点。问将所有物品带回起点的最少时间,每段路程的时间为该路程值的平方。
数据范围:$1{\leq}n{\leq}24$
http://siofive.github.io/2014/11/12/拉练4_E/

更新日志

  • 2014-11-12 AK