Atcoder abc344

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
F(DP)G(排序,排序维护)

https://atcoder.jp/contests/abc344

F - Earn to Advance

n x n的各自，要左上 走到右下， 每次 向右/向下/原地

移动需要花费 对应的 代价 R[i,j] D[i,j]

原地，获得金币p[i,j]

初始0元，过程保证金币非负，求最少 操作次数

n 80

r[i,j],d[i,j],p[i,j] 1e9

4s

1024mb

我的思路

直接的感觉就是dp,但是状态和转移不知道怎么设计

dp[i][j][coin] = t 在位置i,j剩余金币是coin的最小次数

然而这个coin的范围很大

换一个就是 dp[i][j][t] = coin， 而次数也可能很大

再想就是 如果当前在 [i][j] 那么 当前剩余金币coin 能移动到 [ni,nj]

而且 p[ni,nj] > p[i][j]

那么 如果 要从i,j 贡献到 ni,nj(因为也可能不去ni,nj), 那么一定不会在i,j停留，因为, 把同样停留次数在 ni,nj 上用，可以同样总次数，而总coin更多

从而 移动一定是从 p[i][j] -> 更大的p, 最后到终点

二分总次数好像也不可行

题解

考虑每次不够的时候，进行 增加 路径上最大的p, 而不是在p停留，从而不需要“预先停留”

dp[i][j][mi][mj] = 当前在 [i,j] 之前经过的最大的块是 [mi,mj] 的 （最小次数t，在该次数下最大金币coin）

这里得到一个“额外的性质”

也就是因为现在是需要时，才会 增加 路径的最大值

也就意味着，coin < p[mi][mj]

也就有了 假设不同的路径有

(t0,coin0)

(t1,coin1)

且 t0 < t1

那么 coin0 + (t1-t0) * p[mi][mj] >= coin0 + 1 * p[路径1最大] >= p[路径1最大] > coin1

因此 t 越小的越优！！！！！！ 所以这里 只用记录一个 (次数,coin)的组

G - Points and Comparison

给定平面n个点

Q个(a,b), f(a,b) = 满足 $ax+b \le y$ 的点的数量,

求 $\sum_{j=1}^Q f(A_j,B_j)$

因为q很大，所以通过生成的方式提供

$G_{n+1}=(48271 G_n) \mod (2^{31}-1)$

$A_j = -R_a+(G_{3j-2}\mod (2R_a+1))$

$B_j = -R_b+((G_{3j-1}(2^{31}-1)+G_{3j})\mod (2R_b+1))$

n 5000

q 1e7

$x_i,y_i \in [-10^8,10^8]$ 两两不共点

$G_0\in [0,2^{31})$

$R_a\in[0,10^8]$

$R_b\in[0,10^{16}]$

10s

1024mb

我的思路

这时间10s

然后q 1e7

唯一能看的就是 N

对于 满足 $ax+b\le y$的点，实际就是 $y=ax+b$这条线上方(包含)的点

想法是 把所有点 按照 斜率a的映射到 y轴上，再和b比大小

而实际上 n个点，两个点的顺序 $y_0-ax_0 = y_1-ax_1$, 至多1个 大小关系的分界$a$

所以 $n*(n-1)/2$ 个顺序可能

所以 划分这个$a$ 的 多个区间

那么对于给定 (a,b), 就可以 在对应区间a 做值二分，找b了

$O(q \log(n) \log(n))$, 先找 a对应区间, 再二分找首个大于 $b$ 的

???

这里的问题是， 对应区间了之后对应的顺序怎么确定，暴力预处理的话 是 $O(N^2 N \log N)$

离线+冒泡？？

写了一个 按照split 分割排序

然后每次 局部排序

大概 $O(q \log(n))$ 查询

$O(n^2)$ ?? 的所有排序代价和的

https://atcoder.jp/contests/abc344/submissions/52952519

然后TLE了

题解

也是维护 斜率切割点 + 2分搜索,

想了一下 核心还是 维护的问题

因为例如 

1
2
3
4
. . . . 
. . . .
. . . .
. . . .

的点阵，其中 很多点都会在多个排序中出现，而，我靠[l,r] 的sort也会包含很多“不需要排序的部分

1
2
3
4
5
                 .
                  .
   中间多个点
. 
 .

左侧 和 右侧 斜率等，但中间的不需要重新排序

而 题解的操作更简单，直接只维护 当前序列中 相邻的元素之间 的 触发 交换 的时间点！！！

这样还避免了 同时触发多个排序的问题！

代码

https://atcoder.jp/contests/abc344/submissions/52953085

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
#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;}

using yx=pair<ll,ll>;
using yxi=pair<yx,ll>;

ll g;
const ll md=((1ll<<31)-1);
ll gen(){ return g = (48271*g) % md; }

ll comp_yx(yx a,yx b){
  auto [y0,x0]=a;
  auto [y1,x1]=b;
  return y0*x1-x0*y1; // sign(y0/x0 - y1/x1)
}
class Compare {
public:
  bool operator()(yxi a, yxi b) {
    ll cp=comp_yx(a.first,b.first);
    if(cp==0){return (a.second>b.second);}
    return cp > 0;
  }
};

int main(){
  ll n=read();
  vector<yx> p(n); // point
  rep(i,0,n) p[i]={read(),read()};
  sort(p.begin(),p.end()); // 按照x排序，实际对应-infity
  priority_queue<yxi,vector<yxi>, Compare> pq; // 存储 当前相邻的分界触发条件 {{dy,dx},i}
  auto dydx=[&](int i)->yx{return {p[i].second-p[i-1].second,p[i].first-p[i-1].first};}; // i-1,i
  auto add=[&](int i){ if(i>0 and i<(int)p.size() and p[i-1].first<p[i].first) pq.push({dydx(i),i}); }; // i-1,i
  rep(i,1,n) add(i);

  ll q=read();
  g=read();
  ll ra=read();
  ll rb=read();

  vector<yx> ask;
  rep(i,0,q) {
    ll g1=gen();
    ll g2=gen();
    ll g3=gen();
    ask.push_back({ -ra + (g1%(2*ra+1)), -rb + ((g2*md+g3)%(2*rb+1)) });
  }
  sort(ask.begin(),ask.end());

  ll ans=0;
  for(auto [a,b]:ask){
    while(!pq.empty()) {
      auto [cp,i] = pq.top();
      if(cp != dydx(i)){ // 清除 过期的
        pq.pop();
        continue;
      }
      if(comp_yx(cp,{a,1}) >= 0) break;
      pq.pop();
      swap(p[i-1],p[i]);
      // 注意到 如果增加 则肯定大于a, 因为之前两点 按照-infity排序到现在未交换过，未来infity总是可交换
      add(i-1); // 新增切割
      add(i+1); // 新增切割
    }
    ll l=0,r=n-1;
    while(l<=r){
      ll mid=(l+r)/2;
      if(p[mid].second >= a*p[mid].first+b){r=mid-1;}
      else{l=mid+1;}
    }
    ans+=(n-1-r);
  }
  printf("%lld\n",ans);
  return 0;
}

总结

abc341~343 都自己做了，除了 abc343的蓝题7x7x7 让我脑子炸了以外其它都很正常

F: 又卡蓝题了

cf有个类似的题 https://codeforces.com/problemset/problem/1801/D

csp-j 2023 公路 https://www.luogu.com.cn/problem/P9749

其实最关键的我觉得还是 这样做了以后能得到的额外状态，因为如果记录所有 （t,coin) 那么状态肯定不够，所以其实核心问题是 如何解决 (t,coin)之间的关系

而这样的 需要时再增加的设计，能够限制coin的范围，从而导致 t越小 的方案越优！！！！

还是感觉很妙，很妙

G:

哎 所有关键要素都想到了，但是把它们有机的组合起来却没有，而真正的组合还没我想的复杂

就简单的维护 相邻的触发 颠倒顺序的 分界就完了 啊 哎.

用priority_queue 维护, 注意清除无效的