题面:http://codeforces.com/contest/799/problems
A. Carrot Cakes
题意：给定$n, t, k,d$, 需要烤$n$个蛋糕。一个烤箱$t$分钟可以烤$k$个。也可以花$d$分钟新做一个烤箱。烤箱做完后才可以开始烤蛋糕。问需不需要新做一个烤箱。如果所花时间一样则不需要新做。
解法：一开始觉得这题不好写。因为不知道要怎么分配蛋糕，不好实现。
暴力：想了想，写了个暴力。反正数据范围小。
A了之后，还是想知道正解怎么做。
其实关键在于第二个烤箱是否有机会做蛋糕，只要做了一次，就一定能缩短总时间。
所以只需要判断，在第一个烤箱做完的时刻，判断是否还存在多于一次可以做完的蛋糕即可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
using namespace std;
int n, t, k, d;
void violence()//暴力
{
int t1 = (n / k) * t;
if(n % k) t1 += t;
int t2, cnt = 0;
for(t2 = 0; t2 <= 1000010; t2++)
{
cnt = (t2 / t) * k;
if(t2 > d)
cnt += ((t2 - d) / t) * k;
if(cnt >= n)
break;
}
if(t1 <= t2)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
void solve()//正解
{
int num = (d / t) * k;
if(n - num > k)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> t >> k >> d;
solve();
return 0;
}
B. T-shirt buying
题意：
$n$件T-shirt，$a_i,b_i$分别表示第$i$件T-shirt的前色和后色($1\leq a_i,b_i \leq 3$)
有$m$个顾客，会给定一个颜色，会买一件包含有这个颜色并且最便宜的T-shirt。如果没有符合条件的衣服，就不会买。求每个顾客花的钱（不买输出-1）
解法：
水题。将价格从低到高排序，每个颜色开一个数组按价格从低到高存入。
然后每次顾客来了，从这些数组里取即可。每件衣服排序后给定一个索引用于标记是否被买走
1 |
|
C. Fountains
题意：Arkady想买两座喷泉，他有两种货币，coin和diamond。现在有n座喷泉，每个喷泉有一个bueaty值，可以用coin或者diamond买。问能买到的最大的beauty值是多少。
解法：分类讨论
有以下三种情况
- 用coin买一座，用diamond买一座
- 两座都用coin买
- 两座都用diamond买
三种方式中取最大的beauty即为答案。
case1比较简单，只需要在不同货币中取能承担的并且最大的beauty值相加即可。
case2和case3做法相同。
暴力是$n^2$的，显然需要进行优化
将价格从低到高进行排序，如果说3块钱能买到beauty为5的喷泉，那么5块钱一定能买到beauty不低于5的喷泉。所以一定是一个非递减序列。有一点贪心的味道。
开一个数组存储当前价格能买到的最大的beauty值，那么我们选定了一个喷泉以后，只需要找价格满足要求的第一个，即为答案。
由于这是一个非递减序列，可以用二分进行优化。
最后的时间复杂度为$O(nlogn)$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
using namespace std;
struct node{
int bea, cost;
};
vector<node> co, di;
bool cmp(node& pa, node& pb)
{
if(pa.cost == pb.cost)
return pa.bea > pb.bea;
return pa.cost < pb.cost;
}
int solve(vector<node>& t, int val)
{
sort(t.begin(), t.end(), cmp);
vector<int> price;
int len = (int)t.size(), rul = 0;
for(int i = 0; i < len; i++)
{
rul = max(rul, t[i].bea);
price.push_back(rul);
}
int ans = 0;
for(int i = len - 1; i > 0; i--)
{
int l = 0, r = i;
for(int j = 0; j < 100; j++)//二分找到cost满足条件的最大的
{
int mid = (l + r) / 2;
if(t[mid].cost + t[i].cost <= val)
{
ans = max(ans, price[mid] + t[i].bea);
l = mid;
}
else
r = mid;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, c, d;
cin >> n >> c >> d;
int mc = 0, md = 0;
for(int i = 0; i < n; i++)
{
int b, m;
char ch;
cin >> b >> m >> ch;
if(ch == 'C' && m <= c)
{
co.push_back(node{b, m});
mc = max(mc, b);
}
if(ch == 'D' && m <= d)
{
di.push_back(node{b, m});
md = max(md, b);
}
}
if(mc == 0 || md == 0)
mc = md = 0;
int res = mc + md;
res = max(res, solve(co, c));
res = max(res, solve(di, d));
cout << res << endl;
return 0;
}
D. Field expansion
题意：给定$a, b, h, w, n$ 要对h和w进行扩展，每次可以扩大$a_i$倍，问最少需要进行几次扩展可以容纳下一个$a \times b$的矩阵
解法：dp || dfs + 剪枝
扩展一定是越大越好，所以首先将扩展的倍数从大到小进行排序。
最朴素的方法考虑递归dfs，或者将其分配为h，或将其分配给w。
如果h已经满足要求，就分配给w。反之则分配给h
极限情况下，假设$a_i$都是2，需要O($2^{32}$)显然会超时。
但是如果是2的情况下，分配给h或者w所带来的影响是一样的。
所以2的情况单独处理，任意分配。这样最多只需要$log_3 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
using namespace std;
const int maxn = 1e5 + 10;
ll ext[maxn];
ll a, b, h, w, n;
int solve(ll h, ll w, int time)
{
if(h >= a && w >= b){
return time;
}
if(time == n || ext[time] == 1) return INT_MAX;
if(ext[time] == 2)
{
if(h < a)
return solve(h * ext[time], w, time + 1);
else
return solve(h, w * ext[time], time + 1);
}
else
{
if(h >= a)
return solve(h, w * ext[time], time + 1);
else if(w >= b)
return solve(h * ext[time], w, time + 1);
else return min(solve(h, w * ext[time], time + 1), solve(h * ext[time], w, time + 1));
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> a >> b >> h >> w >> n;
for(int i = 0; i < n; i++)
cin >> ext[i];
sort(ext, ext + n, greater<int>());
int ans = solve(h, w, 0);
ans = min(ans, solve(w, h, 0));
if(ans == INT_MAX)
ans = -1;
cout << ans << endl;
return 0;
}
当然这道题也可以用dp来做。
令dp[i][j]表示处理完前i位h最大为j时的w值
如果当前数j前一位的j值被计算过，则可以转移。
转移方向有两个，乘到h上或者乘到w上。
每次乘完的结果还要进行处理，如果乘的结果超过a了，就记为a。
这样只需要最后统计dp[i][a]的值看是否大于等于b即可。
这题还有个坑，就是要考虑方向，长和宽不是定死，可以横过来计算。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
using namespace std;
const int maxn = 1e5 + 100;
ll ext[maxn];
int a, b, h, w, n;
ll dp[40][maxn];//dp[i][j]表示处理完前i位h最大为j时的w值
int solve(ll a, ll b)
{
memset(dp, -1, sizeof(dp));
dp[0][h] = w;
for(int i = 1; i <= min(n, 35); i++)
{
for(int j = 1; j <= a; j++)
{
if(dp[i - 1][j] != -1)
{
ll temp = min(dp[i - 1][j] * ext[i], b);
dp[i][j] = max(dp[i][j], temp);//乘到w上
temp = min(j * ext[i], a);
dp[i][temp] = max(dp[i][temp], dp[i - 1][j]);//乘到h上
}
}
}
int ans = INT_MAX;
for(int i = 0; i <= min(n, 35); i++)
{
if(dp[i][a] >= b)
{
ans = i;
break;
}
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> a >> b >> h >> w >> n;
for(int i = 1; i <= n; i++)
cin >> ext[i];
sort(ext + 1, ext + n + 1, greater<int>());
int ans = INT_MAX;
ans = min(ans, solve(a, b));
ans = min(ans, solve(b, a));
if(ans == INT_MAX)
ans = -1;
cout << ans << endl;
return 0;
}