【解题报告】Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)
A. Vicious Keyboard(Codeforces 801A)
思路
本题的入手点在于,由于最多只能修改一个字符,所以可以枚举被修改的字符。
枚举被修改的字符,然后统计
代码
#include <bits/stdc++.h>
using namespace std;
string s;
int cnt, ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> s;
// 枚举被修改的字符
for(int i = 0; i < s.size(); i++) {
// 修改字符
if(s[i] == 'V') {
s[i] = 'K';
}
else {
s[i] = 'V';
}
cnt = 0;
for(int j = 0; j < s.size() - 1; j++) {
if(s[j] == 'V' && s[j + 1] == 'K') {
cnt++;
}
}
ans = max(ans, cnt);
// 还原被修改的字符
if(s[i] == 'V') {
s[i] = 'K';
}
else {
s[i] = 'V';
}
}
cnt = 0;
// 统计不修改的情况
for(int j = 0; j < s.size() - 1; j++) {
if(s[j] == 'V' && s[j + 1] == 'K') {
cnt++;
}
}
ans = max(ans, cnt);
cout << ans << endl;
return 0;
}
B. Valued Keys(Codeforces 801B)
思路
本题的入手点在于寻找最特殊的构造方式。
设输入的字符串为
代码
#include <bits/stdc++.h>
using namespace std;
string x, z;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> x >> z;
for(int i = 0; i < x.size(); i++) {
if(x[i] < z[i]) {
cout << -1 << endl;
return 0;
}
}
cout << z << endl;
return 0;
}
C. Voltage Keepsake(Codeforces 801C)
思路
本题的入手点是,寻找最值比较麻烦,但判定值是否满足条件比较容易。于是可以利用二分查找来解决问题。
首先先判断什么时候有无穷解。显然,当充电的速度大于设备的耗电速度之和的时候可以用无限地使用设备。
在剩下的有解的情况中,寻找最值是比较麻烦了,但判定某个解
利用这个函数进行二分查找,不断地通过判断答案区间中点的解是否满足条件来缩小答案区间,知道最后得到问题的解。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const double eps = 1e-10, INF = 1e10 + 10;
int n, p, a[maxn], b[maxn];
ll sum;
double l, r, mid;
// 防止精度出错的a <= b的判断
bool LE(double a, double b) {
return a - b < eps;
}
// 判断所有设备是否能运行时间t
bool ok(double t) {
double timeUsed, all = 0;
for(int i = 1; i <= n; i++) {
// 计算单个设备需要占用的充电时间
timeUsed = (1.0 * a[i] * t - b[i]) / (1.0 * p);
if(timeUsed > eps) {
all += timeUsed;
}
}
return LE(all, t);
}
int main() {
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
sum += a[i];
}
if(sum <= p) {
cout << -1 << endl;
return 0;
}
// 二分查找
l = 0;
r = INF;
for(int i = 1; i <= 100; i++) {
mid = (l + r) / 2;
if(ok(mid) == true) {
l = mid;
}
else {
r = mid;
}
}
printf("%.9f\n", l);
return 0;
}
D. Volatile Kite(Codeforces 801D)
思路
本题的入手点是,所有点的可移动距离为
所有点可以移动到某个圆的边界和圆内的所有点所在的位置,那么请看下图:
(图片来源(http://codeforces.com/blog/entry/51598))
我们现在来探究多边形不凹的条件。对于任意三个点
因为对于任意三个点都是如此,所以只要求出任意三点
枚举三个点肯定是会超时的,所以必须另辟蹊径。我们注意到,最后的答案一定在
代码
#include <bits/stdc++.h>
using namespace std;
// 一些常数的定义
const double eps = 1e-8;
const double INF = 2e9 + 10;
inline int cmp(double x) {
return x < -eps ? -1 : (x > eps);
}
// 平方及安全开方函数
inline double sqr(double x) {
return x * x;
}
inline double Sqrt(double n) {
return sqrt(max(0.0, n));
}
// 表示点的结构体
struct Point {
double x, y;
Point() {}
Point(double x, double y): x(x), y(y) {}
void input() {
scanf("%lf%lf", &x, &y);
}
friend Point operator - (const Point& a, const Point& b) {
return Point(a.x - b.x, a.y - b.y);
}
double norm() {
return Sqrt(sqr(x) + sqr(y));
}
};
// 计算叉积(外积)
double det(const Point& a, const Point& b) {
return a.x * b.y - a.y * b.x;
}
// 计算点积(内积)
double dot(const Point &a, const Point& b) {
return a.x * b.x + a.y * b.y;
}
// 计算点到线段的距离
double disPointToSegment(const Point p, const Point s, const Point t) {
if(cmp(dot(p - s, t - s)) < 0) {
return (p - s).norm();
}
if(cmp(dot(p - t, s - t)) < 0) {
return (p - t).norm();
}
return fabs(det(s - p, t - p) / (s - t).norm());
}
const int maxn = 1010;
int n;
Point ps[maxn];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
ps[i].input();
}
ps[n + 1] = ps[1];
ps[n + 2] = ps[2];
double Min = INF;
// 枚举点A
for(int i = 1; i <= n; i++) {
Point A = ps[i];
Point B = ps[i + 1];
Point C = ps[i + 2];
double d = disPointToSegment(B, A, C);
Min = min(Min, d);
}
printf("%.10f\n", Min / 2);
return 0;
}
推荐阅读
-
Codeforces Round #423 (Div. 2, rated, based on VK Cup Finals) E. DNA Evolution(多颗树状数组+思维)
-
【解题报告】Codeforces Round #409 (rated, Div. 2, based on VK Cup 2017 Round 2)
-
Codeforces Round #505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final) D. Recovering BST(区间DP)
-
Codeforces Round #470 (rated, Div. 2, based on VK Cup 2018 Round 1) D. Perfect Security