https://atcoder.jp/contests/abc266/tasks

Ex - Snuke Panic (2D)

N个点会出现, 第i个,在ti时刻出现在(xi,yi), 大小为ai

Takahashi 0时刻在 (0,0)

一单位时间

方案1: 可以x 正向/负向移动1

方案2: y正向移动1

方案3: 不移动

恰好在ti时刻在xi,yi则可获得ai

求可获得的ai的总和的最大值

范围

n 1e5

ti 1e9

xi,yi [0,1e9]

ai [1,1e9]

5s 1024mb

我的思路

不妨把点按照时间ti排序

dp[i] = 要获得i, 前ti能得到的最大值, 显然有局部性,

dp[i] = a[i] + max(dp[j]), yj<=yi, abs(xi-xj)+(yi-yj) <= ti-tj

对限制进行处理

abs(xi-xj)+(yi-yj) <= ti-tj 去掉abs

xi-xj+(yi-yj) <= ti-tj 且 xj-xi+(yi-yj) <= ti-tj

分离i,j

ti-xi-yi >= tj-xj-yj 且 ti+xi-yi >= tj+xj-yj

也就是 (yi,ti-xi-yi,ti+xi-yi) 三维偏序中 最大的dp[j]

然而并不会去做三维偏序的

甚至二维偏序也不太会写

题解

一样的也是三维偏序

但实际上这里并不需要t !!!

因为如果无法达到, 则直接忽略

而 i -> j 可达 等价于 3维偏序的满足, 已经说明了 t[i]< t[j], !!!

所以干掉t以后, 就可以按y排序(另外两个也行), 反正其中一个排序,剩下就是二维偏序了

代码

https://atcoder.jp/contests/abc266/submissions/35639063

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

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

//prefix max
struct BIT{
  int n;
  unordered_map<int,ll>data;
  BIT():n(0){};
  BIT(int N):n(N){};
  void set(int i,ll val){ // i \in [0,n)
    for(i++;i<=n;i+=i&-i)data[i-1]=max(data[i-1],val);
  }
  ll prod(int i){
    ll ans=0;
    for(;i;i-=i&-i)ans=max(ans,data[i-1]);
    return ans;
  }
};

struct BIT2D{
  int h,w;
  vector<BIT>data;
  BIT2D(int H,int W):h(H),w(W),data(h,BIT(w)){};
  void set(int i,int y,ll val){ // i \in [0,n)
    for(i++;i<=h;i+=i&-i) data[i-1].set(y,val);
  }
  ll prod(int i,int j){ // < i, < j
    ll ans=0;
    for(;i;i-=i&-i)ans=max(ans,data[i-1].prod(j));
    return ans;
  }
};

int main(){
  int n=read();
  vector<array<int,4>>data; // y,t-x-y,t+x-y,a
  vector<int>P,Q;
  rep(i,0,n){
    int t=read();
    int x=read();
    int y=read();
    int a=read();
    if(t>=abs(x)+y){// 可达的
      data.push_back({y,t-x-y,t+x-y,a});
      P.push_back(t-x-y);
      Q.push_back(t+x-y);
    }
  }
  sort(data.begin(),data.end()); // 按y排序

  // 离散化
  P.push_back(0);
  sort(P.begin(),P.end());
  P.erase(unique(P.begin(),P.end()),P.end());

  Q.push_back(0);
  sort(Q.begin(),Q.end());
  Q.erase(unique(Q.begin(),Q.end()),Q.end());

  BIT2D bit2d(P.size(),Q.size());
  auto fp=[&](int x){return lower_bound(P.begin(),P.end(),x)-P.begin();};
  auto fq=[&](int y){return lower_bound(Q.begin(),Q.end(),y)-Q.begin();};
  ll ans=0;
  for(auto query:data){
    auto[y,p,q,val]=query;
    p=fp(p);
    q=fq(q);
    ll ret=bit2d.prod(p+1,q+1);
    ans=max(ans,ret+val);
    bit2d.set(p,q,ret+val);
  }
  printf("%lld\n",ans);
}

总结

现场做了, 推出了Ex是个三维偏序,但不会写..

Ex

一个是没发现这里 的t可以干掉, 这样3维可以控制顺序变成二维!!!

有道理啊, 学会了2d fenwick

因为相当于 (i,j) 只会写入 log(H)log(W)个位置, 那么n个点, 就只有 n log^2

所以即使是3维也可以搞

只需要内部用unordered_map 而不是vector,就可以解决空间了

参考

官方题解

https://atcoder.jp/contests/abc265/tasks

G - 012 Inversion

长n序列A, 元素只有0,1,2

q个询问

类型1, 输出A[l..r] 中逆序对个数

类型2, 同时 让A[l..r] 中 0->S,1->T,U->2

范围

n 1e5

q 1e5

5s

1024mb

我的思路

看起来, 就是 线段树 + 记录0,1,2个数 和逆需对个数

但是问题是, 虽然很容易计算 左侧选点 与右侧选点构成的逆需对个数

所以跨区间的容易计算

但是内部的 0,1,2 翻转 并不能只靠0,1,2个数就能得到

但如果记录 (0,1) (1,0) (0,2) (2,0) (1,2) (2,1) 个数

那么翻转就好计算了

甚至不需要记录逆对个数了, 直接统计(1,0) (2,0) (2,1) 个数即可

就过了..

https://atcoder.jp/contests/abc264/tasks

F - Monochromatic Path

给定 h行 w列 黑/白 格子

可以 支付R[i] 翻转第i行

可以 支付C[j] 翻转第j列

求最小代价,让从(1,1)到(h,w) 有一条同色只向下/右走的路径

范围

h,w 2000

ri,ci 1e9

2s

1024mb

我的思路

然后 记走到 dp[i][j][i行是否翻转 0/1][j列是否翻转0/1]的最小代价

dp[i][j][计算出是否翻转][sj] = dp[i-1][j][0/1][sj] 因为知道[i-1][j]的颜色和j的翻转状态

dp[i][j][si][计算出是否翻转] = dp[i][j-1][si][0/1] 因为知道[i][j-1]的颜色和i的翻转状态

那么 就没了?

https://atcoder.jp/contests/abc263/tasks

E - Sugoroku 3

n个格子,初始在1

1到n-1上面都有个骰子, 上面 [0..Ai] 等概率

在到N之前 每次移动 扔出的步数

求期望扔的次数

答案mod 998244353

范围

n 2e5

ai n-i 也就是不会超过n

2s

1024mb

我的思路

记 f(i) = 首次到i的期望次数

i -> j 的期望步数 = 1/(ai+1) + 2/(ai+1)^2 + 3/(ai+1)^3…

s = sum t/(ai+1)^t, t=1…

s/x = sum t/(x)^{t+1}, t=1…

s/x = -(sum 1/(x)^t)’, t=1…

s/x = -((1/x) 1/(1-1/x))’

s/x = -(1/(x-1))’

s/x = 1/(x-1)^2

s = x/(x-1)^2

s = x/(x-1)^2

s = (ai+1)/ai^2

f(i) = sum(f[j=0….i-1]+s[j], 若 j 能到i)

注意到 f[j]+s[j] 的贡献值与i无关, 只有是否贡献有关, 而是否贡献 还是连续的一段

所以用遍历记录贡献和 和失效处来算?

然而并不对, 样例都过不了

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

#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
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;}

mint ans[200010];
mint rm[200010];

int main(){
  int n = read();
  mint c=0;
  rep(i,0,n-1){
    int ai=read();
    ans[i] = c;
    c-=rm[i];
    mint s = ans[i] + mint(ai+1)/(mint(ai)*ai);
    rm[i+ai] += s;
    c+=s;
  }
  printf("%d\n",c.val());
  return 0;
}

https://atcoder.jp/contests/abc262/tasks

F - Erase and Rotate

给一个长n排列A

问不超过k次操作后能得到的最小字典序列

每次操作 可以删除一个数, 或循环右移1个单位

范围

n 2e5

k [0,n-1]

2s

1024mb

我的思路

考虑两种一个是不移动, 从左删除, 那么就是前 k个中取最小, 然后 后面塞入一个, minPQ维护

右侧移动, 也可以确定 首个数字是啥

问题是 当右侧移动时, 可能和删除是同一个, 这个感觉没啥简单的想法去记录

比如样例数据三

如果看成先移动,再删除, 其实会删除移动过的数字

不知道能不能移动+标记+贪心局部?

然后因为k可能比较大,可以从左侧删除和右侧移动 来得到, 所以考虑两个方向来算, 算完了比较?