盒子
盒子
文章目录
  1. 题目
    1. Problem A Chat Server’s Outgoing Traffic (水题)
    2. 思路
    3. Problem B Center Alignment (水题)
    4. 思路
    5. Problem C Mysterious Present (dp, 最长上升子序列)
    6. Problem D Lorry (贪心)
    7. 思路
    8. Problem E Commentator problem (几何, 模拟退火)
  2. 更新日志

CF练习赛2

题目

  • Problem A [CodeForces 5A] Chat Server’s Outgoing Traffic (水题)
  • Problem B [CodeForces 5B] Center Alignment (水题)
  • Problem C [CodeForces 4D] Mysterious Present (dp, 最长上升子序列)
  • Problem D [CodeForces 3B] Lorry (贪心)
  • Problem E [CodeForces 2C] Commentator problem (几何, 模拟退火)

Problem A Chat Server’s Outgoing Traffic (水题)

有一个聊天系统,每次可以进来一个人,出去一个人,或是在系统内的一个人说一些话。而在系统内说的话,所有人(包括自己)的屏幕上都会出现。问所有人的屏幕上总共出现了多少字符。

思路

统计一下人数就好。总数就是每段话的字符串乘以人数的乘积和。

Problem B Center Alignment (水题)

有一段文字,现在要把这段文字放在一个方框里,并且居中。如果不能绝对居中的,按照先靠左,再靠右的格式居中。

思路

用一个变量来区分靠左还是靠右。

Problem C Mysterious Present (dp, 最长上升子序列)

有一个明信片,宽度为$w$,高度为$h$。以及$n$个信封,每个的宽度为$w_i$,高度为$h_i$,信封$A$的宽度和高度均大于$B$时,$B$可以装进$A$。现在要把明信片装进信封里(规则与信封嵌套一样),且要求信封嵌套的层数最多。问最多能有多少层,并输出嵌套方案。
数据范围:$1{\leq}n{\leq}5000, 1{\leq}w_i, h_i{\leq}10^6$
http://siofive.github.io/2014/11/07/拉练2_C/

Problem D Lorry (贪心)

有两种船,$A$船的体积为$1$,$B$船的体积为$2$。而每条船的价值不同。现在有$n$条船,给出每条船的体积$t_i$和价值$p_i$。问一个体积为$v$的仓库,怎样存放可以使得价值最大。求最大的价值,并输出存放的船。
数据范围:$1{\leq}n{\leq}10^5, 1{\leq}v{\leq}10^9, 1{\leq}t_i{\leq}2, 1{\leq}p_i{\leq}10^4$

思路

将$A$类型和$B$类型分开,然后按照价值排序。
如果按照正常的思路:如果两个$A$船的价值和大于$B$船,那么选择两个$A$船,否则选$B$。然后依次处理。
但上述方法需要处理很多细节,很容易出现问题。其实可以换个思路考虑,枚举选取的$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
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
/*
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;
int n, v;
int ca, cb;
const int N = 100000 + 10;
struct ka {
int c, id;
}a[N];
struct sb {
int c, id;
}b[N];
bool cmp1(ka s, ka v) {
return s.c > v.c;
}
bool cmp2(sb s, sb v) {
return s.c > v.c;
}
vector<int> g;
int s_a[N], s_b[N];
int main () {
cin>>n>>v;
int t, c;
for (int i = 0; i < n; i++) {
scanf("%d%d", &t, &c);
if (t == 1) a[ca].c = c, a[ca++].id = i + 1;
else b[cb].c = c, b[cb++].id = i + 1;
}
sort(a, a + ca, cmp1);
sort(b, b + cb, cmp2);
s_a[0] = 0;
for (int i = 0; i < ca; i++) {
s_a[i + 1] = s_a[i] + a[i].c;
}
s_b[0] = 0;
for (int i = 0; i < cb; i++) {
s_b[i + 1] = s_b[i] + b[i].c;
}
int na = 0, nb = 0;
int sum = 0;
int mx = 0;
for (int i = 0; i <= ca; i++) {
if (i > v) break;
int les = (v - i) / 2;
if (les >= cb) les = cb;
int tmp = s_a[i] + s_b[les];
if (tmp > mx) {
na = i, nb = les;
mx = tmp;
}
}
cout<<mx<<endl;
for (int i = 0; i < na; i++) printf("%d ", a[i].id);
for (int i = 0; i < nb; i++) printf("%d ", b[i].id);
cout<<endl;
return 0;
}

Problem E Commentator problem (几何, 模拟退火)

给定三个圆的圆心坐标$(x_i, y_i)$和半径$r_i$,求点使得在该点看三个圆的视角相同,如果有多个点,取视角最大的点。
数据范围:$-10^3{\leq}x_i, y_i{\leq}10^3, 1{\leq}r_i{\leq}10^3$
http://siofive.github.io/2014/11/07/拉练2_E/

更新日志

  • 2014-11-7 AK