盒子
盒子
文章目录
  1. 题目
  2. Problem A Before an Exam
  3. 思路
  4. Problem B The least round way
  5. 思路
  6. Problem C Tic-tac-toe
  7. 思路
  8. Problem D Ancient Berland Circus
  9. Problem E Least Cost Bracket Sequence
  10. 更新日志

CF练习赛1

题目

源地址:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=61581#overview

  • Problem A Before an Exam (水题)
  • Problem B The least round way (DP)
  • Problem C Tic-tac-toe (模拟)
  • Problem D Ancient Berland Circus (几何)
  • Problem E Least Cost Bracket Sequence (贪心)

这场比赛做的很挫,水过A之后,看到学弟出了D,就去看D,发现可敲(不知道怎么发现的。。)敲一半不知道怎么处理圆心角了(赛后发现n才100!NM呀,这么重要的范围我竟然自动跳过了。n这么小枚举即可)。之后去做B,发现是个水DP(我这个不搞DP的都会,一定是水DP),但是在记录路径的时候写错坐标了。。一直没发现错。。然后听说C是模拟,便去看C。脑洞大开,以为接下来不管双方怎么走都赢不了才算平局,没什么太好的办法,只能二进制枚举一下。。然后死活不对。。最后时刻被告之是理解错题了。。sad。E比赛时候没时间看了。

Problem A Before an Exam

给定$d$天,每天可以学习$[min_i,max_i]$个小时,问如果一共学习了$sum$个小时,能否合理安排每天的学习,使得满足要求。

思路

求一下最小值和,最大值和,如果sum在之间,一定满足。

Problem B The least round way

给定一个$n × n$的矩阵,每个格子上有一个数字。现在从左上角走到右下角,规定每次只能向右、向下走,每走到一格,得到该格子上的数字。问怎么走,能够使得这些数字的乘积末尾0最少。给出最少的0和路径。

思路

对于每一个数字,进行处理,我们只需要知道这个数字分别是2、5的多少次方。
先每次走的时候,先保证取2最小,(2一样的时候,5要最小),且在走的过程中记录路径。
然后反着来一遍,先保证取5最小,(5一样的时候,2要最小),且在走的过程中记录路径。
最后的答案就是上面两个的最小值。
这道题有个trick:有可能数字为0。如果起点或终点为0,乘积一定为0,否则上述得到的最小值大于1,那么便不取,而是选择走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
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
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int N = 1000 + 10;
int a[N][N][2];
int dp[N][N];
int ss[N][N];
int pre[N][N][2];
int pre1[N][N][2];
string str;
void out(int o, int x, int y) {
//cout<<x<<" "<<y<<endl;
if (x == -1 && y == -1) {
reverse(str.begin(), str.end());
cout<<str<<endl;
return ;
} else {
if (o == 2) {
int tx = pre[x][y][0], ty = pre[x][y][1];
if (tx == -1 || ty == -1) ;
else {
if (tx == x - 1) str += 'D';
else str += 'R';
}
out(2, tx, ty);
} else {
int tx = pre1[x][y][0], ty = pre1[x][y][1];
if (tx == -1 || ty == -1) ;
else {
if (tx == x - 1) str += 'D';
else str += 'R';
}
out(1, tx, ty);
}
}
}
int main () {
int n;
cin >> n;
int sx = -1, sy = -1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int x, s = 0, b = 0;
scanf("%d", &x);
while(x % 2 == 0 && x) {
s++;
x /= 2;
}
while(x % 5 == 0 && x) {
b++;
x /= 5;
}
if (x == 0) {
sx = i, sy = j;
a[i][j][0] = INF, a[i][j][1] = INF;
}a[i][j][0] = s, a[i][j][1] = b;
}
}
if (a[0][0][0] == INF || a[n - 1][n - 1][0] == INF) {
cout<<1<<endl;
for (int i = 0; i < n - 1; i++) cout<<"D";
for (int i = 0; i < n - 1; i++) cout<<"R";
return 0;
}
dp[0][0] = a[0][0][0], ss[0][0] = a[0][0][1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!i && !j) continue;
dp[i][j] = INF, ss[i][j] = INF;
if (i) {
if ((dp[i][j] > dp[i - 1][j] + a[i][j][0]) || ((dp[i][j] == dp[i - 1][j] + a[i][j][0]) && ss[i][j] > ss[i - 1][j] + a[i][j][1])){
dp[i][j] = dp[i - 1][j] + a[i][j][0];
ss[i][j] = ss[i - 1][j] + a[i][j][1];
pre[i][j][0] = i - 1, pre[i][j][1] = j;
}
}
if (j) {
if ((dp[i][j] > dp[i][j - 1] + a[i][j][0]) || ((dp[i][j] == dp[i][j - 1] + a[i][j][0]) && ss[i][j] > ss[i][j - 1] + a[i][j][1])){
dp[i][j] = dp[i][j - 1] + a[i][j][0];
ss[i][j] = ss[i][j - 1] + a[i][j][1];
pre[i][j][0] = i, pre[i][j][1] = j - 1;
}
}
}
}
int mx1 = min(dp[n - 1][n - 1], ss[n - 1][n - 1]);
dp[0][0] = a[0][0][1], ss[0][0] = a[0][0][0];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!i && !j) continue;
dp[i][j] = INF, ss[i][j] = INF;
if (i) {
if ((dp[i][j] > dp[i - 1][j] + a[i][j][1]) || ((dp[i][j] == dp[i - 1][j] + a[i][j][1]) && ss[i][j] > ss[i - 1][j] + a[i][j][0])){
dp[i][j] = dp[i - 1][j] + a[i][j][1];
ss[i][j] = ss[i - 1][j] + a[i][j][0];
pre1[i][j][0] = i - 1, pre1[i][j][1] = j;
}
}
if (j) {
if ((dp[i][j] > dp[i][j - 1] + a[i][j][1]) || ((dp[i][j] == dp[i][j - 1] + a[i][j][1]) && ss[i][j] > ss[i][j - 1] + a[i][j][0])){
dp[i][j] = dp[i][j - 1] + a[i][j][1];
ss[i][j] = ss[i][j - 1] + a[i][j][0];
pre1[i][j][0] = i, pre1[i][j][1] = j - 1;
}
}
}
}
int mx2 = min(dp[n - 1][n - 1], ss[n - 1][n - 1]);
int mx = min(mx1, mx2);
if (sx != -1 && mx > 0) {
cout<<1<<endl;
for (int i = 0; i < sx; i++) cout<<"D";
for (int i = 0; i < n - 1; i++) cout<<"R";
for (int i = sx; i < n - 1; i++) cout<<"D";
} else {
pre[0][0][0] = pre[0][0][1] = -1;
pre1[0][0][0] = pre1[0][0][1] = -1;
cout<<mx<<endl;
if (mx1 == mx) out(2, n - 1, n - 1);
else out(1, n - 1, n - 1);
}
return 0;
}

Problem C Tic-tac-toe

有一个游戏,给定一个3 X 3的棋盘,两个人连续在棋盘上放棋子(第一个人为X,第二个人为0),如果出现某行某列或者对角线上全为同样的棋子,那么该人获胜。
现在的问题是:给定一个棋盘,以及棋盘上的状态(空为.),问分别为以下哪种情况?

  • illegal 棋盘不可能出现这种情况
  • the first player won 第一个人赢
  • the second player won 第二个人赢
  • draw 平局
  • first 接下来轮到第一个人走
  • second 接下来轮到第二个人走 -

思路

其实理解对题意了,就是道很水的题。。
主要illegal的情况比较多:

  • 双方棋子数不符合规则
  • 双方都赢了
  • 先手赢了,后手还放棋子
  • 后手赢了,先手还放棋子
    然后是判断先手赢、后手赢或是平局(摆满了才有平局。。)最后都不符合,判断该谁走。
    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
    /*
    ID: wuqi9395@126.com
    PROG:
    LANG: C++
    */
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<fstream>
    #include<cstring>
    #include<ctype.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define INF (1 << 30)
    #define LINF (1LL << 60)
    #define PI acos(-1.0)
    #define mem(a, b) memset(a, b, sizeof(a))
    #define rep(i, a, n) for (int i = a; i < n; i++)
    #define per(i, a, n) for (int i = n - 1; i >= a; i--)
    #define eps 1e-6
    #define debug puts("===============")
    #define pb push_back
    #define mkp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
    typedef long long ll;
    typedef unsigned long long ULL;
    char mp[4][4];
    int fi, se;
    int win(char mp[4][4], int t) {
    char ch;
    if (t == 1) ch = 'X';
    else ch = '0';
    for (int i = 0; i < 3; i++) {
    int x = 0;
    for (int j = 0; j < 3; j++) {
    if (mp[i][j] == ch) x++;
    }
    if (x == 3) return 1;
    }
    for (int j = 0; j < 3; j++) {
    int x = 0;
    for (int i = 0; i < 3; i++) {
    if (mp[i][j] == ch) x++;
    }
    if (x == 3) return 1;
    }
    int x = 0;
    for (int i = 0; i < 3; i++) {
    if (mp[i][i] == ch) x++;
    }
    if (x == 3) return 1;
    x = 0;
    for (int i = 0; i < 3; i++) {
    if (mp[i][2 - i] == ch) x++;
    }
    if (x == 3) return 1;
    return 0;
    }
    int check() {
    int x = win(mp, 1);
    int y = win(mp, 2);
    //cout<<x<<" "<<y<<endl;
    if (x == 1 && y == 1) return 0;
    if (x == 1 && fi == se) return 0;
    if (y == 1 && fi == se + 1) return 0;
    if (x == 1) return 1;
    if (y == 1) return 2;
    if (fi + se == 9) return 3;
    return 4;
    }
    int main () {
    fi = se = 0;
    for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
    cin>>mp[i][j];
    if (mp[i][j] == 'X') fi++;
    else if (mp[i][j] == '0') se++;
    }
    }
    if ((fi > se + 1) || (fi < se)) {
    puts("illegal");
    return 0;
    }
    int dd = check();
    if (dd == 0) puts("illegal");
    else if (dd == 1) puts("the first player won");
    else if (dd == 2) puts("the second player won");
    else if (dd == 3) puts("draw");
    else {
    if (fi == se) puts("first");
    else puts("second");
    }
    return 0;
    }

Problem D Ancient Berland Circus

有一个正多边形(3<=n<=100),现在只知道其中的三个顶点,问这个正多边形最小可能的面积。
http://siofive.github.io/2014/11/02/拉练1_D/

Problem E Least Cost Bracket Sequence

有一串字符串,每个字符为’(‘, ‘)’ 或’?’。现在需要将其中的’?’替换为’(‘或’)’,使得最后的括号匹配。每个’?’替换成相应的括号都有一个花费。如果最后不能匹配,输出-1。否则输出最少的花费。
http://siofive.github.io/2014/11/02/拉练1_E/

更新日志

  • 2014-11-2 AK