https://atcoder.jp/contests/abc233/tasks
G - Strongest Takahashi
n x n 格子
# 不可通行,. 可通行
选一个[1,N]中的数字D, 选择DxD的区域,花费代价D移除所有#
问移除所有#的最小代价
范围
N 50
2s
1024mb
我的思路
显然选一个最大的就是n
什么时候不是n?
(n-1)x(n-1) 覆盖不完
那有没有可能 (n-1)x(n-1) 不能覆盖完,但是可以拆成更小的
另一个想法是从小向大合并
有相邻,则合并成更大的
但是方向选择上?, 不一定能确定
1
2
3
4
5
6
| .....#
......
###...
......
...#..
...#..
|
考虑dp
dp[i][j][d] 表示,覆盖掉i,j 开始d x d的范围的最小代价
但感觉不会转移
看上去,不会出现多个小块 让不能同时行分割和列分割, 但不会证明?
1
2
3
4
5
6
7
8
9
| x
x xxxxxxx
x
x x
x x
x
xxxxxx x
x
x
|
如果是这种, 那么直接用大块覆盖更好
因此 区域覆盖= min(纵切割和,横切割和,一个正方形全覆盖的和)
题解
考虑DP+分割成子矩形
而子矩形,一定可以用max(width,height) 覆盖掉, !!!!! 这里不需要找min 哎蠢了
然后也就是上面我猜的结论的证明, 如果可被切割,那么至少一个空行或空列,得证
剩下就暴力
代码
https://atcoder.jp/contests/abc233/submissions/34644602
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
char s[60][60];
int dp[60][60][60][60];
int main(){
int n = read();
rep(i,0,n) scanf("%s",s[i]);
rep(di,0,n) rep(dj,0,n) rep(i,0,n) if(i+di<n) rep(j,0,n) if(j+dj<n){
int i1 = i+di;
int j1 = j+dj;
int &r = dp[i][j][i1][j1];
if(di == 0 && dj == 0){
r = s[i][j] == '#';
}else{
r = std::max(di+1,dj+1);
rep(mj,j,j1) r = std::min(r,dp[i][j][i1][mj]+dp[i][mj+1][i1][j1]);
rep(mi,i,i1) r = std::min(r,dp[i][j][mi][j1]+dp[mi+1][j][i1][j1]);
}
}
printf("%d\n",dp[0][0][n-1][n-1]);
return 0;
}
|
Ex - Manhattan Christmas Tree
N个圣诞树, 二维平面,坐标(xi,yi)
q个询问,(ai,bi) 的manhattan距离第ki个树的manhattan距离
范围
n 1e5
xi,yi [0,1e5]
q 1e5
ai,bi [0,1e5]
7s
1024mb
我的思路
这题,一眼看上去是个二维数据结构, manhattan距离 需要处理掉绝对值
|a-x|+|b-y|
= max(a-x,x-a)+max(b-y,y-b)
= max(a-x,x-a)+max(b-y,y-b)
= max(a+b-x-y,a-b-x+y,x+y-a-b,x-y-a+b)
= max(|(a+b)-(x+y)|, |(a-b)-(x-y)|)
二分距离+二维线段树, 找点个数?
题解
哦 题目说旋转坐标轴, 其实本质上和代数转换是类似的, 解决的问题i是,把曼哈顿距离和 切比雪夫距离做转化
然后还真就 二分距离
二维面,也就是 求矩形内点个数
然后真就因为x,y 本身也不大, 就树状数组+vector
(x+y)为横坐标,(0…2e5, 通过所有x+=1,答案不变,这个可以1-index),(x-y)为纵坐标
想法是, 原来树状数组记录的是[i-(i&-i)+1,i]的和信息
现在直接,直接记录这些(x-y)的点,对应子区间里的点, 然后y有序, 则可以二分查找
代码
https://atcoder.jp/contests/abc233/submissions/34645408
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
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
const int N=2e5;
pair<int,int> a[N+10];
vector<int> tr[N+10];
int n;
void add(int x,int y) {
for(int i=x;i<=N+1;i+=(i&-i)) tr[i].push_back(y);
}
int sum(int x,int l,int r) {
int res=0;
for(int i=x;i ;i-=(i&-i)) res += upper_bound(tr[i].begin(),tr[i].end(),r)
-lower_bound(tr[i].begin(),tr[i].end(),l);
return res;
}
bool check(int x,int y,int k,int d){
int x0 = max(1 ,x-d);
int x1 = min(N+1,x+d);
int y0 = y-d;
int y1 = y+d;
return (sum(x1,y0,y1)-sum(x0-1,y0,y1)) >= k;
}
int main() {
int n = read();
rep(i,0,n){
int x = read()+1;
int y = read();
a[i] = {x+y,x-y};
}
sort(a,a+n,[](auto v0,auto v1){return v0.second < v1.second;});
rep(i,0,n) add(a[i].first,a[i].second);
int q = read();
while(q--) {
int x = read()+1;
int y = read();
int k = read();
if(check(x+y,x-y,k,0)){
printf("%d\n",0);
continue;
}
int l=0,r=2e5+10;
while(l+1<r) {
int mid=(l+r)/2;
(check(x+y,x-y,k,mid)?r:l) = mid;
}
printf("%d\n",r);
}
return 0;
}
|
总结
G
两点: 通过特例猜到结论但不会证, 以及这里不需要min而是max就可以了
H
又学了个树状数组的实际用法
参考
官方题解