题面：http://codeforces.com/contest/801/problems
A. Vicious Keyboard
题意：给定一个仅由V和K组成字符串，你可以修改其中的一个字符，问最多可以有多少个VK子串。
解法：暴力
数据范围小，直接修改每个字符看VK出现次数即可。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
using namespace std;
const int maxn = 1e5 + 10;
int F(string s)
{
string p = "VK";
int res = 0, loc = s.find(p);
while(loc != -1)
{
res++;
loc = s.find(p, loc + 1);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string s;
cin >> s;
int len = s.length();
int ans = F(s);
for(int i = 0; i < len; i++)
{
char c = s[i];
if(c == 'V')
s[i] = 'K';
else
s[i] = 'V';
ans = max(ans, F(s));
s[i] = c;
}
cout << ans << endl;
return 0;
}
B. Valued Keys
题意：x和y为两个长度相等的字符串，定义$f(x, y)$为x和y对应每一位字典序小的字符所组合成的字符串。给定x和y，问是否存在$f(x, z)=y$，若存在输出z，否则输出-1
解法：随便判断一下就好了。首先判断是否y的每一位都小于x若不是则-1否则直接输出y1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
const int maxn = 1e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
string x, y;
cin >> x >> y;
for(int i = 0; i < x.length(); i++)
{
if(y[i] > x[i])
{
cout << -1 << endl;
return 0;
}
}
cout << y << endl;
return 0;
}
C. Voltage Keepsake
题意：有n台设备，每台设备的功率为$a_i$ ，每台设备初始具有功率$b_i$，有一台充电器具有功率p，它的功率可以分配给任意多台设备。问这些设备最多能同时工作多少秒，如果能一直工作下去则输出-1
解法：二分答案。
由于答案一定是具有单调性的，所以可以二分答案做。
判断能不能同时工作至少t秒，只需要计算t秒内充电器冲的功率加上原有的功率是否能支撑所有设备工作t秒。
至于判断是否会出现一直工作下去的情况，我们可以这样想，无论初始有多少的功率，最终肯定会被消耗完，所以充电器的功率必须大于所有设备的功率和。
二分的话右界需要开到$1e12$以上，否则会wa。做完了。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
using namespace std;
const int maxn = 1e5 + 10;
ll a[maxn], b[maxn];
ll n, p;
bool C(double mid)
{
double need = 0;
for(int i = 0; i < n; i++)
{
if(mid * a[i] < b[i])
continue;
else
need += mid * a[i] - b[i];
}
return need < mid * p;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
double l = 0, r = 1e12;
scanf("%lld%lld", &n, &p);
ll sum = 0;
for(int i = 0; i < n; i++)
{
scanf("%lld%lld", &a[i], &b[i]);
sum += a[i];
}
if(sum <= p)
{
printf("-1\n");
return 0;
}
for(int i = 0; i < 100; i++)
{
double mid = (l + r) / 2;
if(C(mid))
l = mid;
else
r = mid;
}
printf("%.10f\n", l);
return 0;
}
D. Volatile Kite
题意：给定一个凸包（凸多边形）每个点的坐标，每个点都可以移动任意距离，现在需要求出一个D使得一个给定的凸多边形任意点移动范围在半径为D的圆中，都不会构成一个凹多边形。
解法：或将成为做的第一题计算几何
考虑该多边形任意的三个点，这三点在同一条直线上时是极限情况，当中间的点再向里移动一点就了凹多边形了。所以对于任意三点，只要求出中间的点到左右两点所形成的直线的距离除以2就可以了。至于为什么要除以2，因为两边一起努力（脑补一下就好了）相互靠近
求点到直线的距离给出两种解法，一种是用叉积计算平行四边形面积再除以边长
也可以用用数量积计算余弦值再算正弦值再算高。
给出两种的代码。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//叉乘
using namespace std;
const int maxn = 1e5 + 10;
struct point{
double x, y;
point(double x = 0, double y = 0):x(x), y(y){}
}a[maxn];
double dis(point a, point b)
{
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
point operator-(point& a, point& b)
{
return point{a.x - b.x, a.y - b.y};
}
double cross(point a, point b)
{
return a.x * b.y - a.y * b.x;
}
double pointoline(point a, point b, point c)
{
return fabs(cross(b - a, c - a)) / dis(a, c);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].x >> a[i].y;
double ans = 1e12;
for(int i = 0; i < n; i++)
ans = min(pointoline(a[(i - 1 + n) % n], a[i], a[(i + 1) % n]) / 2, ans);
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
1 | //点乘 |