YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 3.4k 所需閱讀時間 ≈ 11 分鐘
G(数学, 欧拉定理,phi,miller-robin,pollard-rho)H(题意转化,DP,FFT,生成函数,拉格朗日反演,P-recursive )

G - 222

https://atcoder.jp/contests/abc222/tasks/abc222_g

在数列2,22,222,2222,22222,….中

N个X, 首个是 Xi的倍数的下标是?, 或者不存在

范围

N 200

Xi [1,1e8]

我的思路

一眼看上去很数学, 很像Project Euler的题

$2222222 = 2 * 1111111 = 2 * \frac{(10^7 - 1)}{9}$

其实就是问对于x

是否 2 * (10^7 - 1) = 9 k x

首先x的2的幂次为0/1

好像有点绕

$kx = 1111111 = 10^0+10^1+10^2+\cdots$

右边虽然项数为合数时可以拆分, 例如$6 = 3 * 2$, $111111 = 111 \cdot 1001 = 11 \cdot 10101$

但不知道是否能拆出所有

另一个就是对于比较小的11111的部分,可以pollard-rho分解

考虑长除法?

每次 除法取mod 乘10 加1

但1e8 不知道效率怎么样

PE 129 做过类似的, 但是问题是首个 让是它倍数的最小$111\cdots 111$长度超过百万的是哪个因子

而有一些可用的结论

除了上面$2,5$因子外$kx = 111\cdots 111$始终有解, 且$111\cdots 111$ 的长度不超过$n$ (因为模数随着长度变化成环)

因此 如果暴力的话, 期望值是在 $O(NAi)$ 的

想了下打表 超过1e6的记录下来, 未超过的现场算, 但很多 超过1e6的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int two(int v){
  int c = 0;
  ll m = 0;
  do{
    m*=10;
    m+=2;
    c++;
    m%=v;
  }while(m!=0);
  return c;
}

void calc(){
  rep(i,1000000, 100000000+1){
    if(i % 1000000 == 0) printf("progress %lld\n",i/1000000);
    if(i % 4 == 0 || i % 5 == 0)continue;
    int res = two(i);
    if(res > 1000000) printf("ans[%lld] = %d\n",i,res);
  }
}

另一个就是根据PE129的证明过程, 反正有$\phi(n)$ 或者$\phi(9n)$ 是一个解

那么可以找$\phi(n) , \phi(9n)$的因子尝试, 但这样是否能保证是最小的呢????? 根据倍数, 显然最小的是这个解的因子

$\phi(n) = n \cdot (1-1/p1) \cdot (1-1/p2) \cdots$

似乎可做?

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
F(树的直径)G(坐标转化,笛卡尔系)H(差分转化,前缀和,滑窗和,动态规划)

F - Diameter set

https://atcoder.jp/contests/abc221/tasks/abc221_f

N 点树, 找染色法, 染>=2个点为红色,让红色点两两之间距离为直径

方案数 mod 998244353

范围

N 2e5

2s

1024mb

我的思路

首先直径 是经典算法, 随机点u,找最远点v, 再以v找最远点 便是直径

如果选v

那么可以把v看作根, 相当于做树上dp

因为有深度和直径都知道, 那么对于到叶子距离2倍小于直径的分叉至多选一个,

而2倍大于直径的分叉(不可能都有直径,否则这样能得到更大的长度)

如果直径是偶数, 那么从v到1/2直径点u再到最远点, 这样的点u只有一个,并且这个u可以看成重心

因此可以从重心去找 直径/2 的距离做树上统计 即可

问题来到了奇数长度的直径, 如果直径是奇数, 选了v到最远点的方案 就是最远点的个数

任意两个直径 必有交点, 否则 两个直径上 p1..p2 有一个简单路径 取 p1 — 最远, p2 — 最远, p1-p2, 大于等于 直径/2向上取整 + 1

这样的话

任取一条来看,

v …. x - y…..t

假设,x和y是中间距离的两个点

那么不可能有不经过y的v..x…t1, 否则 t..x..t1 更长

换句话说

一定所有直径有x-y

类似的证明

已经证明了有公共点,

那么假设是y右侧的最近的某个p

同样v ….p…更长的一半, 将会比直径长

x对称同理

所以奇数情况,就是, x 去找距离的方案 乘上 y 去找距离的方案

似乎就推出来了?

閱讀全文 »

發表於 更新於 分類於 ， Disqus： 文章字數： 2k 所需閱讀時間 ≈ 7 分鐘
G(计算几何,排序,自定义排序)H(FWHT,FWT,meet-in-middle,bitmask)

G - Isosceles Trapezium

二维平面, N个点,坐标Xi,Yi, 权重Ci

选4个点, 形成 等腰梯形, 问选的4个点最大权重和

限制

N 1000

Xi,Yi [-1e9,1e9]

Ci [1,1e9]

无重点

3s

1024

我的思路

有点计算几何

N的样子,像是N^2的做法

如果是暴力找三个点, 确定平行边,那么剩下一个点就自然确定了, 这样的话是 N^3 log(N)

换个想法, 按对称轴来找

如果是垂于对称轴的一点,则找对称轴最远的两个点

这样 N^2 的对称轴, 其中相等的里面 按照垂点相同的最大的,找不同的两组就行了??

代码

https://atcoder.jp/contests/abc220/submissions/33799130

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 MOD 1000000007
#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;} // read

ll gcd(ll a,ll b){
  a = abs(a);
  b = abs(b);
  while(b!= 0) tie(a,b) = make_pair(b,a%b);
  return a;
}
const ll INF = 0x3f3f3f3f3f3f3f3f;
array<ll,3> xyv[1010];
map<tuple<ll,ll,ll>, vector<pair<int,int> > > cx;

void addp(int i,int j){
  auto [x0,y0,v0] = xyv[i];
  auto [x1,y1,v1] = xyv[j];
  // 对称轴, 标准化
  ll ky = 2*(y1-y0);
  ll kx = -2*(x1-x0);
  ll k  = (x1-x0)*(x1+x0) + (y1-y0)*(y1+y0);
  ll g = gcd(k,gcd(ky,kx));
  ky /= g;
  kx /= g;
  k  /= g;
  if(ky < 0){
    ky = -ky;
    kx = -kx;
    k  = -k;
  }else if(ky == 0 && kx < 0){
    kx = -kx;
    k  = -k;
  }
  cx[{ky,kx,k}].push_back({i,j});
}

int main(){
  int n = read();
  rep(i,0,n){
    int x = read();
    int y = read();
    int v = read();
    xyv[i] = {x,y,v};
  }
  rep(i,0,n) rep(j,i+1,n) addp(i,j);
  ll ans = -1;
  for(auto [_,vec]:cx){
    auto center = [=](const pair<int,int>&ij){
        auto [i0,j0] = ij;
        auto [x0,y0,v0] = xyv[i0];
        auto [x1,y1,v1] = xyv[j0];
        return make_pair(x0+x1,y0+y1);
    };
    sort(vec.begin(),vec.end(), [=](const auto &ij0,const auto &ij1){
        return center(ij0) < center(ij1);
    });
    ll lastmax = -INF;
    ll cur = -INF;
    rep(i,0,vec.size()){
      if(i == 0 || center(vec[i]) != center(vec[i-1])){
        lastmax = max(lastmax,cur);
        cur = 0;
      }
      auto [i0,j0] = vec[i];
      cur = max(cur, xyv[i0][2] + xyv[j0][2]);
      if(lastmax != -INF){
        ans = max(ans, lastmax + cur);
      }
    }
  }
  printf("%lld\n",ans);
  return 0;
}
// y = -(x1-x0)/(y1-y0) (x - (x0+x1)/2) + (y0+y1)/2
// 2(y1-y0) y = -2(x1-x0) x + (x1-x0)(x1+x0) + (y0+y1)(y1-y0)

H - Security Camera

N 点, M 边

选定一些点, 让边(至少一个点上有被选定的)的数量是偶数个

求合法方案数

限制

N 40

无重边,自环

2s

1024mb

我的思路

感觉题面就是个朴素的图论

40 呢, 对应边就是780

估计是个边平方~ 3次方 左右的算法, 或者点的5次方?

思路正向就是考虑局部可行方案加上插头状态

逆向就是 所有减去存在未选择的 做容斥

点数量40, 2^40 = 1099511627776

如果, 是一个一个安装的, 那么考虑对于个数的影响

增量是 相邻未安装的和

而对于这个连接出的点,相邻未安装的奇偶性发生颠倒

题解

2^20 = 1048576

折半

把拆成两个点集合S,T

L1[S,s] = 点集S的子集s 被选了, 覆盖的边数的奇偶性

L2[S,T,s] = 点集T中, 连向S\s的数量是奇数的点集? (因为偶数的话,首先不被s选,其次不论在T中是否被选不影响奇偶性

R[T,t] = 点集T的子集t被选了,覆盖的两端属于T的边的奇偶性

因为对于每个选中状态, 可以枚举剩下所有点, 所以 可以$O(|S|2^{|S|})$ 暴力算完

那么对于答案有贡献的

$L_1[s] \oplus ((\text{popcount} (L_2[s] & t) ) &1) \oplus R[t] = 0$

意义 s得到的奇数偶,t内部奇偶,和t向S\s的奇偶 = 最终奇偶

中间这玩意怪怪的,虽然很长意义也就是L2[s] & t 的1的个数的奇偶性

像个办法把右侧合并一下

$F[S,T,s] = \sum_{t \subset T} ((\text{popcount} (L_2[s] \& t) ) \& 1) \oplus R[t] $

注意到 求和部分,奇数贡献1, 偶数贡献0, 所以这里是对于给定s,在T的子集中, 让上述表达式贡献1的个数

那么贡献0的个数就是 $2^{|T|} - F[S,T,s]$

如果能求出来, 那么对于每个$s$, 有$L1[s]$ 的奇偶性, 直接加上对应贡献即可

问题变成是如何求出F[S,T,s]

这里记$t’ = L2[s]$, 这样一个s唯一对应一个t', 但t'可能有多个s 映射过来

记作$G[T,t’] = \sum_{t \subset T} ((\text{popcount} (t’ \& t) ) \&1) \oplus R[t] $

这样有个好处是,不再关心S和s, 只用管T中的即可

注意到 $FWHT$的变换公式是

$fwht[a]_ i = \sum_{(\text{popcount}(i \& j) \bmod 2 = 0}a_j - \sum_{(\text{popcount}(i\& j) \bmod 2 = 1}a_j$

对于给定 i

一个具体的j

左侧为0时, 原式子贡献是 R[j], 而fwht贡献是 a[j]

左侧为1时, 原式子贡献是 R[j]^1, 而fwht贡献是 -a[j]

如果让a[j] = R[j], 那么

左侧为0时, 原式子贡献是 0 , 而fwht贡献是 0

左侧为0时, 原式子贡献是 1 , 而fwht贡献是 1

左侧为1时, 原式子贡献是 0^1, 而fwht贡献是 -0

左侧为1时, 原式子贡献是 1^1, 而fwht贡献是 -1

左侧为0和为1各占一半, 总贡献会少掉$2^{|T|-1}$

加上即可?

另一个做法

所有边变成”有向”, 小点连出到大点

f[i][j][k] = 前i个点, 未覆盖的边的两端都在前i的边数为j(奇1/偶0), 一些未来不选的会影响未覆盖边的奇偶性的点的方案数

i+1选 f[i][j][k] 贡献 f[i+1][j][k高(i+2)位]

i+1不选 f[i][j][k] 贡献 f[i+1][j^(i+1是否在k中)][(k高(i+2)位) ^ (i+1 连出的边) ]

很神奇的是, 这样每个点对于每个上个状态最多分支出两个状态

那么前一半最多2^20个状态

而状态低i位都是0, 所以后面的一半也是最多2^20个状态

所以复杂度也是

n 2^{n/2}

从一定程度上也有meet-in-middle 的感觉,而没有了fwt的需要

代码

https://atcoder.jp/contests/abc220/submissions/33847519

1.7s 快超时了, 为什么有人6ms 啊

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

ll g[50]; // g[小点] = 大点的bit mask
// f[前i个点][两端均在前i个中的未覆盖的边的奇偶][mask中的点每不选一个奇偶性变化1]=方案数
unordered_map<ll,ll>f[50][2];
int main() {
  int n = read(); // 点
  int m = read(); // 边
  rep(i,0,m){
    int x = read() - 1;
    int y = read() - 1;
    if(x > y) swap(x,y);
    g[x] |= 1ll<<y; // 全是小 -> 大
  }
  f[0][0][0]=1; // 选 点0，所有点因为不选 未覆盖 的边都为0，为偶数。
  f[0][0][g[0]]++; // 不选 点0，0指向的点因为不选 未覆盖 的边+1.
  rep(i,0,n-1) rep(j,0,2) { // 枚举当前的未覆盖的边数的奇偶。
    for(auto [mask,cnt]:f[i][j]) { // 枚举上一层的所有状态，进行推磨式转移。
      ll bit = (mask >> (i+1)) & 1;// 确定 不选点i+1 未覆盖的边的 奇偶变化。
      //选 点i+1，所有点(i+1之后的点) 因为不选而未覆盖的边数的就不变。且j的状态不变。
      f[i+1][j][mask^(bit<<(i+1))]+=cnt;
      //不选 点i+1，j的状态 根据当前j 和 因为i不选要未覆盖的边数的就确定
      //并且改变之后的点因为不选而未覆盖的边的奇偶
      f[i+1][j^bit][mask^(bit<<(i+1))^g[i+1]] += cnt;
    }
  }
  ll ans=0;
  for(auto [_,cnt]:f[n-1][m&1]) ans += cnt; // m&1 未覆盖的奇偶和总边一样,则覆盖了的为偶数
  printf("%lld",ans);
  return 0;
}

总结

G

没啥难的

简单的计算几何,排序,自定义排序

H

一个是40的一半是20, 2^20 是可以范围内的

另一个是拆的时候,可以按点拆分,一半是有点就包含,另一半是需要两端都属于集合

参考

官方题解

csdn 逆天峰 H

發表於 更新於 分類於 ， Disqus： 文章字數： 2.4k 所需閱讀時間 ≈ 8 分鐘
F(排序,分组)G(根号分类,分类)H(区间DP,问题转化)

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

1
2
3
4
5
xxx
x
x
e
sxx

那么下一次增量是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;} // read

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){ // 保证在 (-pi/2,pi/2]
    dx = -dx;
    dy = -dy;
  }else if(dx == 0 && dy < 0){ // <- bug dx == 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){ // dx >= 0
      t = x/dx;
      x -= t * dx;
      y -= t * dy;
      if(x < 0){
        t --;
        x += dx;
        y += dy;
      }
    }else if(dy != 0){ // dx == 0, dy >= 0
      t = y/dy;
      y -= t * dy;
      if(y < 0){
        t --;
        y += dy;
      }
    }
    pos.push_back({ { x , y } , t}); // 没空格 hexo 炸了
  }
  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;} // read

vector<int>p2[200010];
vector<int>pl[200010]; // linked large
bool large[200010]; // is large
pair<int,int> distr[200010]; // [u] = {value, time}

int a[200010]; // value
int t[200010]; // time

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}]

修改一下问题

  1. 蜡烛可以负数长度
  2. 你可以在起始时移除一些蜡烛

显然新答案不会比原答案更大,而如果有一个答案的方案你照着走,然后把是会是负数的在一开始就移除,那么也可以达到这个原答案的最大值

那么

  1. 初始 分 = 0
  2. 计数 C 去 [0,N] 之间的一个值, 相当于剩余的蜡烛个数,但是不知道具体是哪C个蜡烛
  3. Hi等于对应蜡烛的高度
  4. 每次移动坐标变化1, 分数 -= C
  5. 对于走到一个未访问过的点, 且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;} // read

const int N = 300;

ll dp[N+10][N+10][2][N+10];
pair<int,int> ph[N+10]; // pos height 起点 {0,0}
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; // center i 起始点
  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) {
    //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])`
    //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])`
    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的感知还是没有问题, 虽然在没有前面转化的情况下用处不大

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
G(DP,树,multiset)H(王钦石二分,Alien Trick)

G - Game on Tree 2

https://atcoder.jp/contests/abc218/tasks/abc218_g

n点, 树, 点i上有数字Ai

初始 棋子在点1, 交替玩, 每次移动到未访问过的相邻点, 直到无法移动为止

先手 希望最大化访问过的中位数, 后手希望最小化中位数

如果他们都最优方案, 求这个中位数

限制

N 1e5

Ai [2,1e9]

我的思路

既然是树, 相当于1作为根, 走到叶节点结束, 路径上的中位数就是结果

换句话说, 每个叶节点 可以存储结果

如果能够算出每个从根到叶的结果, 那么简单的根据深度树上dp就完了(根 同的2倍深度 选最大, 根%2不同深度选最小)

想到的是相当于从中间剖开,那么dfs维护一个大根堆,一个小根堆,让它们元素个数差最多是1即可

代码

https://atcoder.jp/contests/abc218/submissions/33755229

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
#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 pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

int A[100010];
vector<int> e[100010];

template<typename T> using maxSet = multiset<T, greater<T>>;
template<typename T> using minSet = multiset<T>;

int mid[100010];

template<typename T>
void balance(maxSet<T> &small,minSet<T> &large){
  while(large.size() > small.size()){
    small.insert(*large.begin());
    large.erase(large.begin());
  }
  while(small.size() >= large.size() + 2){
    large.insert(*small.begin());
    small.erase(small.begin());
  }
}

template<typename T>
int dfs(int u,int f,maxSet<T> &small,minSet<T> &large, int dep){
  // 插入
  if(small.size() == 0 || *small.begin() >= A[u]){
    small.insert(A[u]);
  }else{
    large.insert(A[u]);
  }
  balance(small,large);

  int res = 0;
  if(u != 1 && e[u].size() == 1){ // leaf
    res = (small.size() == large.size()) ? (*small.begin() + *large.begin())/2 : *small.begin();
  }else{
    vector<int> vals;
    for(auto v:e[u]) if(v != f) vals.push_back(dfs(v,u,small,large,dep^1));
    res = (dep==0)? *max_element(vals.begin(),vals.end()) : *min_element(vals.begin(),vals.end());
  }
  // 删除
  auto sptr = small.find(A[u]);
  if(sptr != small.end()){
    small.erase(sptr);
  }else{
    auto lptr = large.find(A[u]);
    assert(lptr != large.end());
    large.erase(lptr);
  }
  balance(small,large);
  return res;
}

int main(){
  int n = read();
  rep(i,1,n+1) A[i] = read();
  rep(i,1,n){
    int u = read();
    int v = read();
    e[u].pb(v);
    e[v].pb(u);
  }
  maxSet<int> small ; // 前一半
  minSet<int> large ;
  printf("%d\n",dfs(1,1,small,large,0));
  return 0;
}

H - Red and Blue Lamps

https://atcoder.jp/contests/abc218/tasks/abc218_h

N个灯, 你需要让R个红色,N-R个蓝色

如果 i 和 i+1 不同色 则有Ai的贡献

求最大的贡献

范围

N 2e5

R [1,N-1]

Ai [1,1e9]

2s

1024mb

我的思路

显然有个n^2的dp

dp[i][j][c] = 前i个有j个红色,第i个颜色为c,的最大贡献

dp[i][j][red] = max(dp[i-1][j-1][red] , dp[i-1][j-1][blue] + A[i])

dp[i][j][blue] = max(dp[i-1][j][red] +A[i], dp[i-1][j][blue])

但肯定超时

题解

如果红色比蓝色多, 则交换颜色数量

那么尽量多的两两不同,显然红色不相邻

那么把 A[i]+A[i+1] 看作整体

构造B[i] = A[i]+A[i+1] 数组

变成在B中选r个不相邻的元素使得总价值最大, 类似的dp[i][j][0/1] = 前i个,选了j个,第i个是否选的最大值

dp[i][j][1] = dp[i-1][j-1][0] + B[i]

dp[i][j][0] = max(dp[i-1][j][1],dp[i-1][j][0])

复杂度依然不能接受

但是有简单的性质: 可以王钦石二分

王钦石二分

  1. 当可选的越多(虽然题目要你求具体的), 那么总收益越大(单增)
  2. 当选的越多, 增量非严格递减凹函数(上凸)
  3. 不限制个数,容器得到最优方案

反过来, 如果我们指定一个最大收益, 那么可以快速算出需要可选的最少数量

如果变成二维图,是凹(上凸)函数,

方法是二分斜率, 对斜率找和凹函数的切点(切线)

而显然切线在y轴截距最大, f(x) = g(x) - k x, 原函数g(x), 截距函数f(x)

问题变成 给k, 找最大f(x), 而 g(x) - k x 从另一个角度看, 就是每个值-k 以后选x, 对于x没有限制时, 容易求的话,那就容易得到f(x) 和 x

求的话因为干掉了一个记录当前有多少个的限制, 从而可以简单dp

然后…. 我被卡double /long double 了

现实是,本身斜率就是 每次增量, 答案不会有小数,而切点对切线斜率也是单调影响, 所以,全整数就行了

代码

https://atcoder.jp/contests/abc218/submissions/33768310

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;
ll a[200010];

pair<ll,int> f(ll v){ // f(斜率) => {最大截距, 横坐标(选的个数)}
  auto dp = vector(n,vector(2,pair<ll,int>{0,0})); // dp[i][第i个 选/不选] = {最大截距,个数}
  rep(i,1,n){
    auto [y0, c0] = dp[i-1][0];
    dp[i][1] = {y0 + (a[i-1] - v), c0 + 1}; // 当前选, 则上一个不选
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]); // 当前不选, 则上一个可选可不选
  }
  return max(dp[n-1][0],dp[n-1][1]);
}

int main(){
  n = read();
  int x = read();
  x = min(x, n-x);
  rep(i,0,n-1) a[i] = read(); // [0..n-2]
  rep(i,0,n-1) a[i] += a[i+1]; // [0..n-2], 看成多了末尾多了一个0, 对最大值无影响
  ll L = 0, R = 3000'000'000; // 斜率
  // 二分, 这里可能 有多个点 让同一个斜率最大, 保证 斜率R < x <= 斜率L 即可, 注意到这这里可能 f(R).pos < f(L).pos < x, 但f(L).pos 只是斜率L上的任意一点 但只要x 斜率不大于 L即可
  while(L + 1 < R) (f((L+R)/2).second < x ? R : L) = mid;
  printf("%lld\n", f(L).first + x * L);
}

总结

G

没啥难的

H

感觉有的时候还是有点 PE的味道,偏数学一点

这里涉及 王钦石二分, 也是凸(凹)函数和二分相关的知识

然后这里double还不行,得long double

参考

官方题解

王钦石二分

0%