比赛时只完成了A-C, C题FST, 于是掉回两场前的rating...... 题解: 5/5 # A. Vicious Keyboard 字符集为{'V', 'K'}. 给一个长度不超过100的字符串, 问修改0或1个字母后子串"VK"的最大个数.
暴力一下......
Editorial说还可以观察性质. 首先, 设不修改时子串"VK"的数目为x, 则最终答案为x或(x+1). 把s[i]='V'修改为'K', 如果s[i-1]='V', 则答案+1, 如果s[i+1]='K', 则答案-1. 把'K'修改为'V'同理. 于是, 当且仅当存在子串'VVV', 'VV$', 'KKK', 或'^KK'时, 答案为(x+1).
const int N = 100;
char s[N+1];
int cal()
{
int cnt = 0;
for (int i = 1; s[i]; ++i)
cnt += s[i] == 'K' && s[i-1] == 'V';
return cnt;
}
int main()
{
scanf("%s", s);
int ans = cal();
for (int i = 0; s[i]; ++i) {
s[i] = s[i] == 'V' ? 'K' : 'V';
ans = max(ans, cal());
s[i] = s[i] == 'V' ? 'K' : 'V';
}
printf("%d\n", ans);
return 0;
}B. Valued Keys
字符集为全体小写英文字母. 函数f接受两个等长字符串s1,s2, 返回一个等长字符串s, s[i] = min(s1[i], s2[i]). 已知s1,s, 构造一个s2, 或判断无解. 字符串非空且长度不超过100.
如果存在s[i] > s1[i], 则无解. 否则, s即为一个可行解.
const int N = 100;
char x[N+1], y[N+1], z[N+1];
int main()
{
scanf("%s%s", x, z);
for (int i = 0; z[i]; ++i) {
if (z[i] <= x[i])
y[i] = z[i];
else {
puts("-1");
return 0;
}
}
puts(y);
return 0;
}C. Voltage Keepsake
有n台设备, 第i台设备每秒消耗ai单位能量, 初始能量为bi. 有一个充电器, 每秒可提供p单位能量, 一次只能为一台设备充电, 忽略插拔时间. 所有设备同时开始工作, 求某台设备能量降为0之前, 工作的最长时间 (要求相对误差不超过10^-4), 或报告可以永远工作. (1≤n,ai,bi≤10^5, 1≤p≤10^9)
看起来可以二分. 约束条件是充电总时间不超过工作时间. 但是不知道上界该设为多少, 也不知道怎么判断无解......根据数据范围逆推一下, 二分100次好像比较合理, 上界设为10^26可以满足精度要求, 如果答案和上界很接近就输出永远工作, 就这么办吧......过了pretest, 但是判无解出了点问题, WA掉了. 可以面向数据重新重新设置一下阈值. 我也不知道是为什么 QAQ 难道出了精度问题?
按照正常的思路重新叙述一下. 把n台设备看成一个系统, 则 Σai 是输出功率, p是输入功率. 当 p ≥ Σai 时, 可以永远工作. 否则, 设工作时间为 t, 第i台设备需要额外的能量 max(t ai - bi, 0), 将需要的总能量与 pt 做比较即可.
假设所有设备的能量均为0时才结束工作, 则 Σbi + pt = Σai t => t = Σbi / (Σai - p), 于是, 10^10是一个上界. 这个上界是紧的, 考虑这样的数据:
100000 99999
1 100000
1 100000
...
1 100000本题忽略充电器的插拔时间, 所以有些情况实际上是不可行的.
做这道题好像有点艰难, 大概是因为我缺乏物理思维......
typedef long double ld;
typedef long long ll;
const int N = 1e5;
int a[N], b[N];
int main()
{
int n, p;
ll out = 0;
scanf("%d%d", &n, &p);
rep (i, 0, n) {
scanf("%d%d", &a[i], &b[i]);
out += a[i];
}
if (p >= out) {
puts("-1");
return 0;
}
ld l = 0, r = 1e11;
int T = 60;
while (T--) {
ld m = (l+r)/2, s = 0;
rep (i, 0, n)
s += max(a[i]*m - b[i], (ld)0);
if (s <= m*p) l = m;
else r = m;
}
printf("%.6f\n", double((l+r)/2));
return 0;
}D. Volatile Kite
给一个严格凸n边形, 求一个实数D, 使得每个点移动至多距离D之后, 多边形仍然是凸的而且不自交. 点以顺时针顺序给出. 要求相对误差不超过10^-6. (4≤n≤1000)
先找一下必要条件. 考虑相邻的三个点所能移动到的最不凸的情形. 需要求两个圆的公切线吗? 需要判断圆和直线的位置关系吗? 需要二分答案吗? 还是看Editorial吧......
不用求公切线, 可以直接把临界值解出来. 考虑所有相邻的三个点, 取个 min, 就是答案了. 不知道通常计算几何中怎样求点到直线的距离, 我用了一下海伦公式.
怎么这么简单, 太打击人了 QAQ
#define x first
#define y second
typedef long double ld;
typedef pair<ld, ld> Point;
const int N = 1000;
Point P[N];
inline ld square(ld x)
{
return x*x;
}
inline ld dis(const Point& p, const Point& q)
{
return sqrt(square(p.x-q.x) + square(p.y-q.y));
}
int main()
{
int n;
scanf("%d", &n);
rep (i, 0, n) {
int x, y;
scanf("%d%d", &x, &y);
P[i] = Point(x, y);
}
ld d = 1e10;
rep (i, 0, n) {
int j = (i+1)%n, k = (i+2)%n;
ld a = dis(P[i], P[j]), b = dis(P[j], P[k]), c = dis(P[k], P[i]),
p = (a+b+c)/2;
d = min(d, sqrt(p*(p-a)*(p-b)*(p-c))/c);
}
printf("%.8f\n", (double)d);
return 0;
}E. Vulnerable Kerbals
给一个正整数m和n个[0,m-1]内的不同整数, 构造一个尽量长的序列, 满足 - 每个元素是[0,m-1]内的整数. - 所有前缀积模m是不同的. - 没有前缀积等于给定的n个数之一.
(0≤n<m≤2*10^5)
设a为常量, x为变量, 令 d = gcd(a, m), 则 ax mod m 可以且只能取到 m/d 个不同的值: 0, d, 2d, ..., m-d. gcd(ax, m) 一定是 gcd(a, m) 的倍数, 并且这是 x 存在的充分条件. 考虑 m 的所有正因子, 把它们作为点, 每个因子向它的倍数连有向边, 不在表中且满足 gcd(b, m) = d 的 b 的个数作为 d 的点权, 则问题转化为 DAG 上的最长路. DP求出路径, 再用扩展欧几里德 (或任何一种其他解模线性方程的算法) 解出 ax mod m = b 的一个 x 即可.
乘法炸 int, WA了两发.
说到其他解模线性方程的算法, Editorial是这样搞的: ax = b (mod m) <= (a/gcd(a,b))x = b/gcd(a,b) (mod m)
设 d = gcd(a,m), 则 d|a, d|b => d|gcd(a,b), 所以 a'=a/gcd(a,b) 与 m 互质, 存在逆元.
const int M = 2e5;
bool ban[M], vis[M+1];
int m, nxt[M+1], f[M+1];
vector<int> e[M+1];
int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}
int exgcd(int a, int b, int& x, int& y)
{
int d;
if (b) {
d = exgcd(b, a%b, y, x);
y -= a/b*x;
} else {
x = 1;
y = 0;
d = a;
}
return d;
}
inline int solve(int a, int b)
{
int x, y, d = exgcd(a, m, x, y);
assert(b % d == 0);
return (long long)b / d * (x+m) % m;
}
int dfs(int x)
{
if (vis[x]) return f[x];
vis[x] = true;
f[x] = e[x].size();
nxt[x] = -1;
for (int y = 2*x; y <= m; y += x)
if (m % y == 0) {
int t = e[x].size() + dfs(y);
if (t > f[x]) {
f[x] = t;
nxt[x] = y;
}
}
return f[x];
}
int main()
{
int n;
scanf("%d%d", &n, &m);
rep (i, 0, n) {
int x;
scanf("%d", &x);
ban[x] = true;
}
rep (i, 0, m)
if (!ban[i])
e[gcd(i, m)].push_back(i);
dfs(1);
printf("%d\n", f[1]);
int p = 1;
for (int x = 1; x != -1; x = nxt[x]) {
rep (i, 0, e[x].size()) {
int t = solve(p, e[x][i]);
printf("%d ", t);
p = e[x][i];
}
}
if (f[1])
puts("");
return 0;
}