F - Cleaning Robot
https://atcoder.jp/contests/abc219/tasks/abc219_f
给序列 从点(0,0) 出发,上下左右走n个点,
重复序列k次, 问经过次数>=1的点有几个
限制
n 2e5
k 1e12
2s
1024mb
我的思路
可以看成 一个图形, 每次平移固定向量, k次,问覆盖的图形面积
似乎脑补可得: 每次计算增量, 如果增量不变, 则往后都是这个增量
但不知道如何判断 达到了最小增量
如果是这个形状, s -> e
那么下一次增量是5, 下下次增量也是5, 但是 这不是最小增量, 最小是3
所以可能要变成去计算每个点首次不产生贡献的时刻, 而不产生贡献,也就是沿着 e -> s 的向量方向如果存在点
所以考虑对点归类, 能够通过向量 e -> s 到达的 归类
然后比较时刻和所有点的首次不产生贡献的时间即可
不产生时刻 = 同类别最近的方向向量 / 向量
好像就过了
代码
https://atcoder.jp/contests/abc219/submissions/33772772
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
char s[200010];
int ch[256];
int di[] = {-1,1,0,0};
int dj[] = {0,0,-1,1};
vector<pair<pair<ll,ll>,ll> > pos;
int main(){
ch[(int)'L'] = 0;
ch[(int)'R'] = 1;
ch[(int)'U'] = 2;
ch[(int)'D'] = 3;
scanf("%s",s);
int n = strlen(s);
ll k = read();
ll dx = 0;
ll dy = 0;
vector<pair<ll,ll> > vis = {{dx,dy}};
rep(i,0,n){
dx += di[ch[(int)s[i]]];
dy += dj[ch[(int)s[i]]];
vis.push_back({dx, dy});
}
if(dx < 0){
dx = -dx;
dy = -dy;
}else if(dx == 0 && dy < 0){
dy = -dy;
}
sort(vis.begin(),vis.end());
rep(i,0,vis.size()) if(i == 0 || vis[i] != vis[i-1]){
auto [x,y] = vis[i];
ll t = 0;
if(dx != 0){
t = x/dx;
x -= t * dx;
y -= t * dy;
if(x < 0){
t --;
x += dx;
y += dy;
}
}else if(dy != 0){
t = y/dy;
y -= t * dy;
if(y < 0){
t --;
y += dy;
}
}
pos.push_back({ { x , y } , t});
}
sort(pos.begin(),pos.end());
ll ans = 0;
if(dx == 0 && dy == 0){
ans = pos.size();
}else{
rep(i,0,pos.size()){
if(i == 0 || pos[i].first != pos[i-1].first){
ans += k;
}else{
ans += min(k, pos[i].second - pos[i-1].second);
}
}
}
printf("%lld\n",ans);
return 0;
}
|
G - Propagation
https://atcoder.jp/contests/abc219/tasks/abc219_g
n个点,m跳边的图, 点i上写的i
q次操作
每次让点xi 上的值扩散给它的所有相邻节点
输出最终每个点上的值
范围
n 2e5
m 2e5
q 2e5
无重边 自环
2s
1024mb
我的思路
直接模拟? 如果出现2层菊花形状 每次一个外层染进来,中心扩散, 那么可能就是QN的量级
那么思路方向一个如何批量 或者 lazy的表示
另一个就是有没有可能倒着做
如果把做为修改中心的, 作为点, 按时间顺序和依赖关系 可以建立树(森林), 但不太知道怎么去建
题解
分度处理
对于度小于 $\sqrt{m}$, 直接修改周围的点, 而对于 $\ge \sqrt{m}$的度的点, 在点上标识
对于查询, 可以查询所有, 相当于边访问2次
而每次 处理前, 需要遍历一次周围度大于等于$\sqrt{m}$ 的
复杂度分析
修改就不用说了显然
而就每次获取最新状态时, 因为要遍历相邻的所有度$\sqrt{m}$
那么假设有$w$个, 那么即使边来自它们之间 $\frac{w \sqrt{m}}{2} leq m$, 即$w \leq {2\sqrt{m}}$, 说明也是$O(\sqrt{m})$ 级别的访问
中间复杂度$O(q\sqrt{m})$, 最后查询复杂度$O(n\sqrt{m})$
代码
https://atcoder.jp/contests/abc219/submissions/33773300
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
vector<int>p2[200010];
vector<int>pl[200010];
bool large[200010];
pair<int,int> distr[200010];
int a[200010];
int t[200010];
int getV(int u){
int val = a[u];
int ti = t[u];
for(auto v:pl[u]) if(distr[v].second > ti) tie(val,ti) = distr[v];
return val;
}
int main(){
int n = read();
ll m = read();
int q = read();
rep(i,0,m){
int u = read();
int v = read();
p2[u].pb(v);
p2[v].pb(u);
}
iota(a+1,a+n+1,1);
rep(i,1,n+1) large[i] = (ll)p2[i].size() * (ll)p2[i].size() > m;
rep(u,1,n+1){
for(auto v:p2[u]){
if(large[v]) pl[u].push_back(v);
}
}
rep(ti,1,q+1){
int u = read();
int val = getV(u);
a[u] = val;
t[u] = ti;
if(large[u]){
distr[u] = {val, ti};
}else{
for(auto v:p2[u]){
a[v] = val;
t[v] = ti;
}
}
}
rep(i,1,n+1) printf("%d ",getV(i));
return 0;
}
|
H - Candles
https://atcoder.jp/contests/abc219/tasks/abc219_h
N 个蜡烛, 第i个在Xi, 长度Ai
每分钟, 点燃的蜡烛长度-1, 直到 = 0, 而没点燃的不变化
初始在0,每分钟可以移动+1/-1, 如果当前位置有任何蜡烛,可以扑灭(不耗时)
求所有蜡烛长度剩余和的最大值
范围
N 300
xi [-1e9,1e9]
Ai [1,1e9]
我的思路
第一感觉是, 向左走 然后一直向右, 或者向右然后一直向左, 找这个折反点
问题是,会不会出现 左右左的情况?
例如-1上有10个, 2上有10个, -4 上1个, 都足够的长
那么 0 -> -1 -> 2 -> -4 的损失是21 * 1 + 11 * 3 + 1 * 6, 是最小的
这样证否了贪心折返
注意到N很小
甚至能接受 n^3, 考虑dp
dp[i..j][0] = [i,j] 区间内全部熄灭(烧完), 停在i 的 {最大长度, 时间}
问题是, 这种状态设计下, 最大长度和时间是有一致性吗?
题解
也是说, 仅从访问来看
如果已经访问过的区间是[X_i,X_j] 那么下一次 一定是[X_{i-1},X_j] 或[X_i,X_{j+1}]
修改一下问题
- 蜡烛可以负数长度
- 你可以在起始时移除一些蜡烛
显然新答案不会比原答案更大,而如果有一个答案的方案你照着走,然后把是会是负数的在一开始就移除,那么也可以达到这个原答案的最大值
那么
- 初始 分 = 0
- 计数 C 去 [0,N] 之间的一个值, 相当于剩余的蜡烛个数,但是不知道具体是哪C个蜡烛
- Hi等于对应蜡烛的高度
- 每次移动坐标变化1, 分数 -= C
- 对于走到一个未访问过的点, 且C > 0, 可以选择 C-=1, 分 += Hi
求最大分
显然最优解和答案是一样的
// 咦 我怎么看到上凸函数的影子
然后就可以dp了
dp[i][j][flag][k] = 已获的最大分数, $[X_i,X_j]$ 已经访问,$flag = 0$ 在$X_i$,$flag = 1$ 在$X_j$, $k$ 是剩余的要去熄灭的蜡烛个数
那么转移方程, 走到$X_i$
dp[i][j][0][k] = max(dp[i+1][j][0/1][k] - 距离 * k, dp[i+1][j][0/1][k+1] - 距离 * (k+1) + H[i])
转移方程, 走到$X_j$
dp[i][j][1][k] = max(dp[i][j-1][0/1][k] - 距离 * k, dp[i][j-1][0/1][k+1] - 距离 * (k+1) + H[i])
最后答案就是dp[0][n-1][0/1][0]
代码
https://atcoder.jp/contests/abc219/submissions/33780170
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
const int N = 300;
ll dp[N+10][N+10][2][N+10];
pair<int,int> ph[N+10];
const ll INF = 0x3f3f3f3f3f3f3f3f;
void setMax(ll &v0,ll v1){ if(v1 > v0) v0 = v1; }
int main(){
int n = read();
rep(i,1,n+1){
auto p = read();
auto h = read();
ph[i] = {p,h};
}
sort(ph,ph+n+1);
int ci = -1;
rep(i,0,n+1){
if(ph[i] == make_pair(0,0)){
ci = i;
break;
}
}
rep(i,0,n+1) rep(j,0,n+1) rep(f,0,2) rep(c,0,n+1) dp[i][j][f][c] = -INF;
rep(f,0,2) rep(c,0,n+1) dp[ci][ci][f][c] = 0;
per(i,0,ci+1) rep(j,ci,n+1) {
if(i == j) continue;
rep(c,0,n+1) rep(f,0,2) {
if(i < ci) {
auto [x,h] = ph[i];
const ll pos[] = {i+1, j};
ll &res = dp[i][j][0][c];
setMax(res, dp[pos[0]][pos[1]][f][c] - (ph[pos[f]].first - x) * c);
if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (ph[pos[f]].first - x) * (c+1) + h);
}
if(j > ci){
auto [x,h] = ph[j];
const ll pos[] = {i, j-1};
ll &res = dp[i][j][1][c];
setMax(res, dp[pos[0]][pos[1]][f][c] - (x - ph[pos[f]].first) * c);
if(c < n) setMax(res, dp[pos[0]][pos[1]][f][c+1] - (x - ph[pos[f]].first) * (c+1) + h);
}
}
}
printf("%lld\n", max(dp[0][n][0][0], dp[0][n][1][0]));
return 0;
}
|
总结
F
一眼题
G
分类处理, 根号分治
做了不少分类的,又忘了分类
H
一个是题目转化去掉限制的技巧不会啊, 如果直接是转化后的题面, 那我还是会区间DP的, 但这个转化感觉遇到多了学一学转化
其实就是这里每分钟下降 燃烧着的个数, 会因为=0而难以维护, 通过支持负数 和可预先移除来让每分钟下降易于维护, 同时保持新的最大答案 = 原答案
n^3和dp的感知还是没有问题, 虽然在没有前面转化的情况下用处不大
参考
官方题解