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

F - Transportation

n 个点

Xi 价格 点i 修 airport

Yi 价格 点i 修 harbor

Zi 修路 ui<->vi, m条

最小代价 所有点连通

范围

n 2e5

m 2e5

xi,yi,zi[1,1e9]

4s

1024mb

我的思路

如果没有airport/harbor, 那么就是 最小生成树

如果有

则会有两个点同时有 两种交通工具, 或者一个点同时三个交通工具

如果能确定基础代价, 那么增加连通代价 要么是路, 要么是某个交通工具

n这么大 也不能bitmask

如果只有一种

那么就是 先考虑所有都建立, 然后每次可以拆一个 贡献 -Xu + min(road[u,v?])

不会了

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

G - Reversible Cards 2

给定n张卡, 每张 正面ai,反面bi

初始都正面

问对于 k=0..m 的每个取值

让 可见面=k的最小翻转次数

所有 ai+bi 和为m, 所有ai,bi 在[0,m] 之间的整数

范围

n 2e5

m 2e5

3s

1024mb

我的思路

先想的是分治

f[i..j][v] 表示[i..j] 这一段 可见面=v的最小翻转次数

f[i..j][v] = min(f[i..mid][x]+f[mid+1..j][v-x])

似乎 需要min卷积 并不会

想过网络流, 但这里没有最大最小什么的, 唯一的最小就是最小次数, 但感觉网络流上 去等于k 看起来更像是费用和,

预处理, 先计算所有Ai的和, 然后翻转 看成 Bi-Ai 的增量

问题变成 有n个变量, 问和 = k-sum(A) 的最小选择个数

一股 spfa的感觉?

不会

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

G - Random Student ID

n个学生 姓名为小写字母,互不相同

问对于所有 a-z 的排列 决定的字典序下

每个学生 的 名字排名顺序期望

范围

名字长度和 5e5

3s

1024mb

我的思路

先估计一下n

1*26+2*26**2+3*26**3+4*26**3*7 = 546234 > 5e5

n < 26+26**2+26**3+26**3*7 = 141310

显然也不能两两计算

感觉可以 基数排序 先计算每个字符串, 的每一位所在的区间大小

而排序 可以看成 首位的期望偏移 + 第二位的期望偏移 + 第三位的期望偏移

可拆!

例如首位是a, 那么 a > b 则有b的长度贡献, a > c 则有c的长度贡献, 而和b与c的大小无关

1

abcde

a: (len(b)/2+len(c)/2+len(d)/2+…)

ab: a前缀中 空 + len(a)/2 + len(c)/2 + len(d)/2+…

abc: abc前缀中 空 + len(a)/2 + len(b)/2 + len(d)/2+…

其实就是 前缀中 : 空 + (all-len(cur))/2

注意 为前缀只是长度大小导致的不等关系

似乎就AC了

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

G - Increasing K Times

给一个长度为n的序列A

问有多少个 对它重排的方式 p, 满足 a_[p_i], 恰好有k个相邻严格递增

范围

n 5000

2s

1024mb

我的思路

首先A的顺序无关,不妨把a排个序

然后我们只要大于关系为k个,所以不妨设末尾为0

然后考虑把相同的值看成整体

考虑每次在上次运算的基础上, 计算增加了 多个 最大值

f[前i大][j个小于关系] = 方案数

f[i][j+k] = sum f[i-1][j] * count(前i-1个)-(j+1)选k个空隙,插入p个*j+1个缝隙 插入sz(i)-p个` * sz(i)!

binom(sumf(i-1)-(j+1),k) * binom(p-1,k-1) * binom(sz(i)-p-1,j)

1
2
3

k<=sumf(i-1)-(j+1)
k<=p
j<=sz(i)-p-1

这限制关系有点多变量也多, 虽然状态是满足, 但转移代价太大

另一个就是不要多个最大值去看, 而是一个一个加入

f[前i个][j个小于关系] = 方案数

发现 当第i个 > 第i-1个时, 插入 小于关系中, 不会影响j, 插入= 和 大于关系, 会增加1

f[i][j] = f[i-1][j] * j + f[i-1][j-1] * ((i-1)-(j-1))

当第i个=第i-1个时, 插入小于关系, 或=第i个的值的后面时, 不影响j, 设[0..i-1]中有sz个和第i个相等的

f[i][j] = f[i-1][j] * (j+sz(i)) + f[i-1][j-1] * ((i-1)-(j-1)-sz(i))

似乎就没了?

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,就可以解决空间了

参考

官方题解