Codeforces Round #614 (Div. 2)
/ / 阅读耗时 14 分钟 Codeforces Round #614 (Div. 2)题解。第一次上蓝名(*>ᴗ<*)（话说比赛才打过几场。。。）
A. ConneR and the A.R.C. Markland-N
这个可以暴力扫，因为被选上的点一共才1000个，暴力的话也不会超过1000次。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
using namespace std;
int n, s, k;
set<int> ssp;
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &s, &k), ssp.clear();
for (int i = 1, x; i <= k; i++) {
scanf("%d", &x);
ssp.insert(x);
}
int ans = 0x7fffffff;
for (int i = s; i >= 1; i--) {
if (ssp.count(i) == 0) {
ans = s - i;
break;
}
}
for (int i = s + 1; i <= n; i++) {
if (ssp.count(i) == 0) {
ans = min(ans, i - s);
break;
}
}
printf("%d\n", ans);
}
return 0;
}
B. JOE is on TV!
这里需要一个$O(n^2)$的$DP$，方程是这样：
复杂度肯定不行，我们证明：
考虑数学归纳法，$dp(1)=1$没有任何问题。假设$i\leq k$均成立，则$i=k+1$时，有：
可以将上式看成$k+1$项的和，并且最后$t$项都是相同的。那么我们应该最小化分母才能取到较大值，这样$t=1$时值最大，得证。
然后本题$O(n)$解决，非常简单。1
2
3
4
5
6
7
8
9
10
11
using namespace std;
int main()
{
int n;
scanf("%d", &n);
double ans = 0;
for (int i = 1; i <= n; i++) ans = ans + 1.0 / i;
printf("%.10lf", ans);
return 0;
}
C. NEKO’s Maze Game
容易发现只有两行的备选点最小横向距离大于1时才可以通行。那么我们开数组记录这些点的状态，每一次修改点状态时更新其附近距离为1的位置的答案即可。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;
int n, q, t1[100005], t2[100005];
set<long long> ssp;
int main()
{
scanf("%d%d", &n, &q);
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
if (x == 1) {
if (t1[y]) {
t1[y] = 0;
for (int j = y - 1; j <= y + 1; j++) {
if (j >= 1 && j <= n && t2[j]) ssp.erase(ID(y, j));
}
}
else {
t1[y] = 1;
for (int j = y - 1; j <= y + 1; j++) {
if (j >= 1 && j <= n && t2[j]) ssp.insert(ID(y, j));
}
}
}
else {
if (t2[y]) {
t2[y] = 0;
for (int j = y - 1; j <= y + 1; j++) {
if (j >= 1 && j <= n && t1[j]) ssp.erase(ID(j, y));
}
}
else {
t2[y] = 1;
for (int j = y - 1; j <= y + 1; j++) {
if (j >= 1 && j <= n && t1[j]) ssp.insert(ID(j, y));
}
}
}
if (ssp.empty())
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
D. Aroma’s Search
由于$a\geq 2$，可知点的坐标指数级上升，数量不会太多（最多大约60个），我们暴力枚举点，找出距离起始点曼哈顿距离在$t$以内的点。
根据数学上的推导，编号相邻的两个点的曼哈顿距离随编号的增长呈指数级上升（每一次大约乘2），由于$\sum_{i=1}^n2^i=2^{n+1}-1$。这个结论告诉我们一个贪心思路：从某一个点开始，顺次访问编号比其小的点，可以最优化答案。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;
typedef long long LL;
LL x0, y0, ax, bx, ay, by, xs, ys, t;
vector<pair<LL, LL>> vec;
inline LL ABS(LL x)
{
return x > 0 ? x : -x;
}
int main()
{
cin >> x0 >> y0 >> ax >> ay >> bx >> by >> xs >> ys >> t;
LL x = x0, y = y0;
vec.push_back(make_pair(xs, ys));
while (true) {
if (ABS(x - xs) + ABS(y - ys) <= t) vec.push_back(make_pair(x, y));
x = ax * x + bx, y = ay * y + by;
if (x > xs + t || y > ys + t) break;
}
int ans = 0;
for (int i = 1; i < vec.size(); i++) {
LL tmp = t - ABS(vec[0].first - vec[i].first) - ABS(vec[0].second - vec[i].second);
int p = 1;
for (int j = i - 1; j >= 1; j--) {
if (tmp >= ABS(vec[j].first - vec[j + 1].first) + ABS(vec[j].second - vec[j + 1].second)) {
++p;
tmp -= ABS(vec[j].first - vec[j + 1].first) + ABS(vec[j].second - vec[j + 1].second);
}
}
if (p == i && i + 1 < vec.size() && tmp >= ABS(vec[1].first - vec[i + 1].first) + ABS(vec[1].second - vec[i + 1].second)) {
tmp -= ABS(vec[1].first - vec[i + 1].first) + ABS(vec[1].second - vec[i + 1].second);
++p;
for (int j = i + 2; j < vec.size(); j++) {
if (tmp >= ABS(vec[j].first - vec[j - 1].first) + ABS(vec[j].second - vec[j - 1].second)) {
++p;
tmp -= ABS(vec[j].first - vec[j - 1].first) + ABS(vec[j].second - vec[j - 1].second);
}
}
}
ans = max(ans, p);
}
printf("%d", ans);
return 0;
}
E. Xenon’s Attack on the Gangs
本题思路很巧妙。
先放0这个数，加入放到了$(a,b)$上，则答案贡献$sz(a)sz(b)$，这是一个对本题直观的认识。由此推知，这些数一定是从小到大放，不断延伸一条链，才能最大化答案。
定义$par(r,x)$为以$r$为根时，$x$的父节点，定义$sub(r,x)$为以$r$为根时，以$x$为根的子树上的节点数目。
定义$dp(a,b)$，$l$为链$(a,b)$上的边数，$dp(a,b)$表示在链$(a,b)$上放$0$到$l-1$，可以得到的最大值。那么有状态转移方程：
上面的$\max$表示将与$a$相连的树链上的邻边变为放$l-1$的边，或者将与$b$相连的边变为放$l-1$的边。
预处理$sub$以及$par$可以通过$n$遍$DFS$完成，其余直接$DP$即可。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
using namespace std;
struct Edge
{
int next, to;
} edge[N << 1];
int head[N], cnt = 1, n, par[N][N], sub[N][N], rt;
long long dp[N][N], ans;
inline void add(int x, int y)
{
edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
void DFS(int x, int fa)
{
par[rt][x] = fa, sub[rt][x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to != fa) DFS(edge[i].to, x), sub[rt][x] += sub[rt][edge[i].to];
}
}
long long DP(int x, int y)
{
if (x == y) return 0;
if (~dp[x][y]) return dp[x][y];
return dp[y][x] = dp[x][y] = 1ll * sub[x][y] * sub[y][x] + max(DP(par[y][x], y), DP(x, par[x][y]));
}
int main()
{
scanf("%d", &n), memset(dp, -1, sizeof(dp));
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
for (int i = 1; i <= n; i++) rt = i, DFS(i, 0);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) ans = max(ans, DP(i, j));
}
printf("%lld", ans);
return 0;
}
F. Chaotic V
容易知道这是一棵树，现在问题转化为找一个点，使得所有给定点与其距离和最小。
这个可以贪心求解，我们从根节点开始，每一次都去可以使答案减小的分支。
那么如何确定哪些数在哪些分支上？方法比较简单，对阶乘做质因数分解，然后从大到小（计入重数）的质因子就是它的分支。我们对其进行枚举，进而进入对应的树分支，即可得到答案。
注意这里的$n$非常大，但是阶乘5000比较小，我们应该计入每一个阶乘出现的次数，将处理放到这5000个阶乘上，而不是那$10^6$个数上，可以带来巨大的效率提升。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
using namespace std;
int b[5005], cnt, pr[800], f[800][5001], n, at[5005], sum[800][5001];
long long ans;
int ss[5005], tmp[5005], sa, st;
int main()
{
// freopen("in.txt", "r", stdin);
for (int i = 2; i <= 5000; i++) {
if (b[i]) continue;
for (int j = 2; j * i <= 5000; j++) b[i * j] = 1;
}
for (int i = 2; i <= 5000; i++)
if (b[i] == 0) pr[++cnt] = i;
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= 5000; j++) {
if (j >= pr[i]) f[i][j] = j / pr[i] + f[i][j / pr[i]];
sum[i][j] = sum[i - 1][j] + f[i][j];
}
}
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) {
scanf("%d", &x);
if (x == 0) x = 1;
++at[x];
ans += sum[cnt][x];
}
for (int i = 1; i <= 5000; i++)
if (at[i]) ss[++sa] = i;
for (int i = cnt; i >= 1;) {
int s = 0, minn = 0x7fffffff;
st = 0;
for (int j = 1, a; j <= sa; j++) {
a = ss[j];
if (f[i][a]) s += at[a], minn = min(minn, f[i][a]);
}
if (s > n - s) {
ans -= 1ll * minn * (s - n + s);
for (int j = 1, a; j <= sa; j++) {
a = ss[j];
if (f[i][a]) f[i][a] -= minn, tmp[++st] = a;
}
for (int i = 1; i <= st; i++) ss[i] = tmp[i];
sa = st;
}
else if (n - s > s) {
for (int j = 1, a; j <= sa; j++) {
a = ss[j];
if (!f[i][a]) tmp[++st] = a;
}
for (int i = 1; i <= st; i++) ss[i] = tmp[i];
sa = st;
--i;
}
else {
break;
}
}
printf("%lld", ans);
// PAUSE;
return 0;
}