Codeforces Global Round 24

發表於 更新於 分類於 ， Disqus： 文章字數： 1.7k 所需閱讀時間 ≈ 6 分鐘
E(数学)F(树)G(TODO)H(TODO)

https://codeforces.com/contest/1764

E. Doremy’s Number Line

给 a[1..n],b[1..n]

每次只能一种操作

把 [0,a[i]] 中某个未染色的染色为i

或者

如果 有 v <= a[i] 已经染色, 则可以把 [0,v+b[i]] 中 某个未染色的染色为 i

问 k 能否染色成 1

i的顺序 任意, 但每个i最多选一次

范围

n 1e5

k 1e9

ai,bi [1,1e9]

2s

256mb

我的思路

转换成当前最大的可达的值, a[1] 最后操作

如果前面操作了, 那么 后面的操作 按照a[i]+b[i]顺序, 不会更差

但不知道怎么处理第一个的选择, 如果第一个的值 >= 排序后的 a[first], 可以dp[n][放弃了一个 >=的 还是 没有放弃的]

但这个只能处理特殊情况的处理不了所有

题解

一样的结论, 如果 k可以,那么[0..k] 都可以, 所以需要求的实际是 颜色1 最大能达到多少, 显然也是 k <= a[1]+b[1]

如果 a[1] 不是最大的, 那么直接 选 a[?] >= a[1] , 然后 [0..a[1]+b[1]] 都可达了

如果 a[1] 是最大的

  • 只有一个 [0…a[1]]
  • 如果 a[j] 不是 a[2..n] 中严格(存在 a[i] == a[j])最大的, 那么 a[j]+b[j] 一定可达, 那么至多一个 a[i]+b[i] 不一定可达, 这种情况 就是 min{x[j]+y[j],x[1]} + y[1]
  • 最后考虑 a[i] 是严格最大的, 问题变成 [2..n], 中除了 i的元素 能不能达到 a[i] 的递归子问题了

按a排序

f(arr) = 能达到的最大, = max(arr[0..sz-2].(a+b), min(f(arr[0..sz-1]),a.back()) + b.back())

代码

https://codeforces.com/contest/1764/submission/182731716

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

bool w(){
  int n=read()-1;
  int k=read();
  int A=read(); // a[1]
  int B=read(); // b[1]
  vector<array<int,2>> ab(n);
  vector<int> mx(n); // 前缀 max { a+b }
  vector<int> f(n); // [0..i] 能得到的最大值
  rep(i,0,n) {
    int a=read();
    int b=read();
    ab[i]={a,b};
  }
  sort(begin(ab), end(ab));
  if (k <= A) return true; // 直接 k
  if (n == 0) return false;
  mx[0] = ab[0][0]+ ab[0][1];
  f[0] = ab[0][0];
  rep(i,1,n){
    auto [a,b]=ab[i];
    mx[i] = max(mx[i-1], a+b);
    f[i] = max({mx[i-1]/*a[i]放最前面*/, min(f[i-1],a) + b /*i放最后*/, ab[i][0]/*i放最后*/});
  }
  return min(f[n-1],A) + B >= k;
}

int main() {
  int q=read();
  while(q--)printf("%s\n",w()?"YES":"NO");
  return 0;
}

F. Doremy’s Experimental Tree

n点, 有边长w的树, 进行 n(n+1)/2个独立实验

每次 选 $j \le i$, 用长度=1的边连接它们, 这样存在一个环(可能是自环), f(i,j) = 每个点到环的最短距离

现在给你 所有$(i,j,f(i,j))$ 点对, 请还原一个树, 保证存在方案

范围

n 2000

wi [1..1e9]

f(i,j) [0..2e15]

2.5 s

256mb

我的思路

n 2000, 那就是 n^2, n^2 log n 之类的算法, 而光是读入就已经O(n^2)了

考虑先给定了 树 和 i,j , 如何计算

i-1-j-....-i, 那么显然环上的点的对f的距离贡献都是0, 而非环上的点u = 到环上v的距离 = u..v = u..v..i - v..i

注意到这个减法的两个路径都是树上的,跟新加的边(i,j)无关

所以 f(i,j) = i到所有点的距离和 - j到i简单路径上 到i的距离和 的加权值, 权重就是 u到i 最先遇到的环上的点v

即 f(i,j) = g(i) - h(i,j) = g(j) - h(j,i) ,

注意到这里 有自环, 而(i,i) 自环 的结果是f(i,i) = g(i), 所以h(i,j) 可以容易得到

如果(i,j) 相邻 , 那么 h(i,j) = len(i,j) * 所有先到j的点, h(j,i) = len(i,j) * 所有先到i的点

所以h(i,j) + h(j,i) = len(i,j) * n

说明 如果 h(i,j) 是所有h(i,*) 中最小的那么 i,j 相邻 (反过来并不一定, 因为i可能和多个相邻, 因此这些边和边长能得到

所以按照 h(i,j) + h(j,i) 排序就好了

这样每个点能找到一条相邻边, 但是可能重复 不一定能找到所有的边 比如 a-short-b-long-c-short-d, 这样long 找不到

下面问题就是 多个联通块里面如何连通, 其实也可以看成每个联通块缩成节点, 还是树, 那么问题也是一样的, 每次找最短的

而在i中最短的,可以所有不同的i一起比较, 找所有中最短的(保证亮点目前不在一个联通块)(也一定是某个i中最短的), 所以就是并查集就没了

代码

n2 logn

C++20 2418ms https://codeforces.com/contest/1764/submission/182952379

C++17 920 ms https://codeforces.com/contest/1764/submission/182954224

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

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

ll read(){ll r;scanf("%lld",&r);return r;}
ll f[2010][2010];
tuple<int,int,int> pq[2000010]; // {d,i,j}
int fa[2010];
int sz[2010];
int n;
int getfa(int u){return u==fa[u]?u:(fa[u]=getfa(fa[u])); }
bool merge(int u,int v){
  int fu=getfa(u);
  int fv=getfa(v);
  if(fu==fv) return false;
  if(sz[fu] > sz[fv]) swap(fu,fv); // 大小启发式合并
  fa[fu] = fv;
  sz[fv] += sz[fu];
  return true;
}

int main(){
  n=read();
  rep(i,0,n) rep(j,0,i+1) f[i][j]=read();
  int off=0;
  rep(i,0,n) rep(j,0,i) {
    ll dis = ((f[i][i]-f[i][j])+(f[j][j]-f[i][j]));
    if(dis%n==0 && dis/n <= 1000000000) pq[off++]={dis/n,j,i};
  }
  iota(fa,fa+n,0);
  fill(sz,sz+n,1);
  sort(pq,pq+off);
  int edge=n-1;
  rep(idx,0,off){
    auto [d,i,j]=pq[idx];
    if(!merge(i,j)) continue;
    printf("%d %d %d\n",i+1,j+1,d);
    if(--edge == 0) return 0;
  }
  return 0;
}

G

H. Doremy’s Paint 2

长n数组,初始化a[i]=i

m个操作 op[i]={li,ri}, 每次可以 a[l[i]+1…r[i]] = a[l[i]]

给定k

回答m个值, 第i=0..m-1 是 上面从 i开始连续k个操作后, 最终[1..n] 的不同的数 的值

范围

n 2e5

m 2e5

4s

256mb

我的思路

总结

E

简而言之就是菜

数学的 分析和推导 完全不会

想了半天排序, 但是连 a[i]+b[i] 只要a[i] 不是严格最大就一定可达都没发现, 唉…

F

F这是卡时间的题吗? 似乎在卡的是 c++ 的fsanitize , 跟n2还是n2 log n无关

官方代码 C++20 也是 2464 ms 然后时限是 2.5s (https://codeforces.com/contest/1764/submission/182954105) ????

虽然C++17很快(982ms https://codeforces.com/contest/1764/submission/182954544)

如果按c++17, 那F比E简单啊

参考

官方