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

發表於 更新於 分類於 ， Disqus： 文章字數： 2.8k 所需閱讀時間 ≈ 9 分鐘
D(正确读题就能做)G(kmp+DP)Ex(概率论,生成函数)

D

天天卡D我服了,EF都过了就是卡D

题解这次出得好慢

题目

https://atcoder.jp/contests/abc257/tasks/abc257_d

平面n个点

每个点一个倍率Pi

每个点可到达 PiS 曼哈顿距离以内的点

问最小的整数S让 可以选择某一点, 让其它点都可从此点跳跃到达,(不需要一次路径)

范围

n 200

坐标 x,y [-1e9,1e9]

p [1..1e9]

3s

1024mb

题解

我的思路

一眼 二分答案+tarjan+拓扑排序

关键这是abc的D题不应该,而且N也就200

不会这么难, 想不出啊,接近2k人比赛里过了,心态有点炸,还好跳了去做了EF,而且本来abc我也不算分了

题解

不要读错题,

我读成选点 跳跃经过所有点

代码

无

G

https://atcoder.jp/contests/abc257/tasks/abc257_g

两个只有小写字母的字符串S,T

让T 为 S的k个前缀的拼接

求最小的k 或报不可能

范围

|S| 5e5

|T| 5e5

题解

我的想法

一眼像是kmp,但kmp写得真的少,

而且不确定kmp 怎么具体做,去计算t每个位置作为起始的最大长度

题解

dp[i] = T[0..i] 和S匹配的答案

如果 T[i-p…i] == S[1..p], 那么有 dp[i] = min(dp[i-p]+1), p 可能有多种, 没有答案就INF

单调性

dp[i] <= dp[i+1]

否则你把 dp[i+1]的方案中最后一个字符去掉,dp[i] 就能变小

因此你只需要关心最长的前缀匹配

终究还是来到了kmp

经典的# 拼接

代码

https://atcoder.jp/contests/abc257/submissions/32786655

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

class KMP {
  private :
    vector<int> f; // 比它小的最长前缀的长度
    char *s;
    int sz;
  public:
    KMP(char *s,int sz):s(s),sz(sz){
      f = vector<int>(sz,0);
      int fa = 0;
      rep(i,1,sz){
        while (fa && s[i] != s[fa]) fa = f[fa-1];
        if (s[i] == s[fa]) fa++;
        f[i] = fa;
      }
    }
    vector<int> getPrefixLen(){
      return f;
    }
    int posIn(char *t,int szt) {
      int fa = 0;
      rep(i,0,szt) {
        while (fa && t[i] != s[fa]) fa = f[fa-1];
        if (t[i] == s[fa]) fa++;
        if (fa == sz) return i-fa+1;
      }
      return -1;
    }
};

char s[1000010];

int ns;
int nt;
const int INF = 0x3f3f3f3f;

int main(){
  scanf("%s",s);
  int ns = strlen(s);
  s[ns] = '#';
  scanf("%s",s+ns+1);
  int nt = strlen(s+ns+1);
  int n = ns+1+nt;
  vector<int> dp(nt+1,INF);
  dp[0] = 0;
  KMP kmp(s, n);
  auto pl = kmp.getPrefixLen();
  // rep(i,0,nt){
  //   printf("%lld: %d\n",i,pl[i+ns+1]);
  // }

  rep(i,1,nt+1){
    dp[i] = dp[i-pl[i+ns]]+1;
    // printf("dp[%lld] = %d\n",i,dp[i]);
  }
  printf("%d\n", dp[nt] >= INF?-1:dp[nt]);

  return 0;
}

// k 个S前缀拼成 T
// KMP?

Ex

https://atcoder.jp/contests/abc257/tasks/abc257_h

n个6面dice, 每个上面6个给定数字aij, 每个价格Ci

恰好买k个,

在最优状况下选K个, 期望sum(扔的数字)^2 - sum(价格) 最大

输出 期望mod 998244353

范围

n 1e3

k [1..N]

ci [1,1e5]

aij [1,1e5]

题解

我的思路

先期望转化

假设当前方案中k-1个确定了, 然后在剩下的中要让答案尽量大

max E((sumA+xi)^2 - Ci)

= E(sumA^2+2 sumA xi+xi^2) - Ci

= xi^2 - Ci + 2 xi E(sumA) + E(sumA^2)

但是这样是否每次替换就能得到最优呢? (局部最优=全局最优?)

题解

假设指定了 用哪k个, 先考虑E怎么计算

生成函数$f_i(x) =\frac{1}{6}(\sum_{j=1}^{6} x^{A_{i,j} })$ 相当于每一面选都是1/6 倍数的贡献

那么显然, 令$F(x) = \prod_{i=1}^K f_i(x)$,则$[x^k]F(x)$ 为k次的概率

令$G(x) = (x F’(x))$, 相当于(p(k次的概率)*k x^k)’ = p(k次的概率)*k^2 x^{k-1}

那么期望为$G(1)=E(k^2)=\sum p(k) k^2$

注意到$f_i(1)=1$ 因为就是概率和,所以有 $F’(x) = \sum_{i=1}^K f_i’(x)$

$F’’(x) = \sum_{i=1}^K f_i’’(x) + \sum_{i=1}^K\sum_{j=1,j\ne i}^K f_i’(x)f_j’(x) $

$G(x) = F’(x)+xF’’(x)$

令 $A_i = f_i’(1), B_i = f_i’’(1)$

$G(1) = F’(1)+1F’’(1) $

$= \sum_{i=1}^K f_i’(x) + \sum_{i=1}^K\sum_{j=1,j\ne i}^K f_i’(x)f_j’(x) + \sum_{i=1}^K f_i’’(x)$

$= \sum_{i=1}^K A_i +2 \sum_{i =1}^{K-1}\sum_{j=i+1}^{K} A_i A_j + \sum_{i=1}^K B_i$

$= \sum_{i=1}^K A_i +\big( \sum_{i=1}^K A_i\big) ^ 2 - \sum_{i=1}^K A_i^2 + \sum_{i=1}^K B_i$

$= \big( \sum_{i=1}^K A_i\big) ^ 2+ \sum_{i=1}^K (A_i + B_i - A_i ^2)$

因此 令$x_i = A_i, y_i = A_i + B_i - A_i ^2 - C_i$, 感觉概率论的话应该不需要生成函数也能推, 但这也看出生成函数能干这活

问题就是给n个二元组$(x,y)$找序列$p$求 $\max((\sum_{i=1}^K x_{p_i})^2 + \sum_{i=1}^K y_{p_i})$

对于一个具体的最优方案: $\max((\sum_{i=1}^K x_{p_i})^2 + \sum_{i=1}^K y_{p_i})$ 是最大的, 需要有什么性质(必要但非充分性质)

那么把其中 一个$\sum_{i=1}^K x_{p_i}$看成$c$

变成: $\max(\sum_{i=1}^K (cx_{p_i}+y_{p_i}))$ 是最大的 (这里不是和其它方案比大小, 因为其它方案的和不一定是c, 这里是自身需要满足的条件

所以 如果选了$k$个的和为$c$, 那么只有当$cx_{p_i}+y_{p_i}$ 是最大的$k$个时, 它才有可能是最优解!!!!!

换句话说c的取值范围只可能是k个x_i的和,

假设 考虑c从小到大取值时$cx_i+y_i$和$cx_j+y_j$大小关系至多变化一次, 变化时就是相等时

$cx_i+y_i=cx_j+y_j$

$c=(y_j-y_i)/(x_i-x_j)$ 时

如果$x_i=x_j$, 那么它们大小关系不会变化

因此 不是去枚举$c = $ k个的和, 而是 $c = $ 变化前后的位置, 因此只会有$\le n^2$ 种排序

还有个问题是 最优解 虽然是最大的k个, 但是最大的k个一定能取到最优解吗?

也就是 在最优解的 cx+y 排序下, 虽然对应答案的$k$个是最大的$k$个,但是可能出现一段$cx+y$的值相等, 而因为相等的影响, 选择出来的k个可能不是对应最优解的$c$吗?

设最优解 为 $X_0^2+Y_0$, 若通过某个$c$ 找到非最优解满足

$X_1 c + Y_1 \ge X_0 c +Y_0$ 且 $X_1^2+Y_1 < X_0^2+Y_0$

$(X_0 - X_1) c \le Y_1 - Y_0 < X_0^2-X_1^2$

显然 非最优解的 $X_1 \neq X_0$ 否则 $0 = 0$

那么 考虑一条斜率上如果多个点, 不可能中间选的点 让答案优于两侧的点

$x_i < x_j < x_k$

$c = S+x_j$

$c(S+x_i)+ S_y+y_i=c(S+x_j)+ S_y+y_j=c(S+x_k)+ S_y+y_k$, 属于比大小时等价可以选的点

$(S+x_j)^2 + S_y + y_j > (S+x_i)^2 + S_y + y_i$, 要中间优于两侧

$(S+x_j)^2 + S_y + y_j > (S+x_k)^2 + S_y + y_k$

等价替换 $c(S+x_i)+ S_y+y_i > (S+x_i)^2 + S_y + y_i$

$c > (S+x_i)$

$x_j > x_i$

$x_j > x_k$

和前提矛盾, 因此不可中间的同时比两边优, 所以如果在一条斜率上的点, 要么等价, 要么单侧连续

而通过枚举$c$, 总能让 在一条线上(相当于跨过 小于k个 和 大于k个 的那条线)的点 变来 正序或逆序

因为在$c$ 处发生变化, 所以考虑排序 $c$ 后 去取 相邻$c$的均值

问题再变化, 就是n个点(xi,yi), 和n^2个数单调递增的序列c

对每个c 求 (cxi+yi) 的最大的k个的 (sum xi)^2 + yi 的和

考虑n个点的图, 然后 有向边 表示 u 比 v大,

注意到会有(x,y) 一样的点, 简单起见 用下标来决定大小(这样保证了两两不等, 且全部可排序)

那么每次 经过 c, 会颠倒一些边的指向, 而前k 大的就是入度小于k 的

然后因为 实际上写的时候 少用浮点数,

$A_i=\frac{1}{6}\sum_{t=1}^6 a_{i,t} = \frac{1}{6}{\alpha_i}$

$B_i=\frac{1}{6}\sum_{t=1}^6 a_{i,t}(a_{i,t}-1)=\frac{1}{6}{\beta_i}$

$\mathrm{ans} = \big( \sum_{i=1}^K A_i\big) ^ 2+ \sum_{i=1}^K (A_i + B_i - A_i ^2 - C_i) = \frac{\big( \sum_{i=1}^K \alpha_i\big) ^ 2+ \sum_{i=1}^K (6\alpha_i + 6\beta_i - \alpha_i ^2 - 36C_i)}{36}$

代码

https://atcoder.jp/contests/abc257/submissions/36106424

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;
typedef long long ll;
typedef __int128 lll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
ll C[1010];

// return t0/b0 < t1/b1
bool lt(pair<ll,ll> frac0,pair<ll,ll>frac1){ // less than
  auto [t0,b0]=frac0;
  auto [t1,b1]=frac1;
  assert(b0!=0&&b1!=0);
  if(b0<0){
    t0*=-1;
    b0*=-1;
  }
  if(b1<0){
    t1*=-1;
    b1*=-1;
  }
  return ((lll)t0)*b1 < ((lll)t1)*b0; // 估计不到范围 甩个128吧
}

bool great[1010][1010]; // great[i][j] : cx_i+y_i > cx_j+y_j
int incnt[1010]; // 入度

int main(){
  int n=read();
  int k=read();
  rep(i,0,n)C[i]=read();
  vector<pair<ll,ll>>xy; // {6e5,~36e10}
  rep(i,0,n){
    ll a=0; // fi'(1), alpha, 6e5
    ll b=0; // fi''(1) beta, 6e10
    rep(j,0,6){
      ll v=read();
      a+=v;
      b+=v*(v-1);
    }
    xy.push_back({a,6*a+6*b-a*a-36*C[i]}); // {6e5, ~36e10}
  }
  // c=-infinity
  rep(i,0,n)rep(j,i+1,n){
    auto [xi,yi]=xy[i];
    auto [xj,yj]=xy[j];
    if(xi==xj){ // 不受c影响
      if(yi==yj){ // 完全相等 用index比大小
        great[j][i] = true;
        incnt[i]++;
      }else if(yi<yj){
        great[j][i] = true;
        incnt[i]++;
      }else{
        great[i][j] = true;
        incnt[j]++;
      }
    }else{ // c负无限大且x不想等时 不受y 影响, xi c < xj c  则 xi > xj
      if(xi < xj){ // xic > xjc
        great[i][j] = true;
        incnt[j]++;
      }else{
        great[j][i] = true;
        incnt[i]++;
      }
    }
  }
  ll Sx=0; // 1000 * 6e5 = 6e8
  ll Sy=0; // 1000 * ~36e10 = ~36e13
  auto add=[&](int idx,int t=1){
    Sx+=t*xy[idx].first;
    Sy+=t*xy[idx].second;
  };
  rep(i,0,n) if(incnt[i]<k) add(i);
  ll ans=Sx*Sx+Sy; // 72e13
  vector<pair<pair<ll,ll>,pair<int,int>> > c; // 记录每次翻转的, {{~36e10,12e5},{1e5,1e5}}
  rep(i,0,n)rep(j,i+1,n){
    auto [xi,yi]=xy[i];
    auto [xj,yj]=xy[j]; // c=(yj-yi)/(xi-xj)
    if(xi==xj)continue;
    c.push_back({{yj-yi,xi-xj},{i,j}});
  }
  sort(c.begin(),c.end(),[](auto&v0,auto&v1){return lt(v0.first,v1.first);});
  vector<vector<pair<int,int>>> ijs; // 同斜率合并
  rep(i,0,c.size()){
    if(i==0||lt(c[i-1].first,c[i].first)){
      ijs.push_back({c[i].second});
    }else{
      ijs.back().push_back({c[i].second});
    }
  }
  for(auto ij:ijs){
    for(auto [i,j]:ij){
      if(great[j][i]) swap(i,j); // assert(i > j)
      great[i][j]=false; // 可以省略great的修改, 因为只有incnt真的参与计算, 之后swap也不会再有i,j
      if(incnt[j]--==k) add(j); // k => k-1 原来没j 现在有j
      great[j][i]=true;
      if(++incnt[i]==k) add(i,-1); // k-1 => k 原来有i 现在无i
    }
    ans=max(ans,Sx*Sx+Sy);
  }
  printf("%d\n",(mint(ans)/36).val());
  return 0;
}

总结

D

读错题好难受啊

G

然后我也更新了一下我的kmp板子多加了个外置函数

Ex

概率论完全不会, 虽然它用了生成函数推了半天,但是似乎印象中就是期望的各种运算法则,太久没用了忘得差不多了

然后这个是概率论+生成函数求导的组合使用, 感觉这样的话, E(x^3)也是类似的思路

这个二次转1次的, 完全没想到, 而且我感觉这样证明有点复杂了, 不懂有啥简便的证明方法

然后这个完全图的入度小于k表示前k大的!

参考

KMP

發表於 更新於 分類於 ， Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
D(树,DP)

D

评分2900,远高于C的难度

题目

https://atcoder.jp/contests/arc142/tasks/arc142_d

给你一个树,要上面放一些棋子

每个时间周期,所有棋子要向它相邻的任意一个点移动,确保移动时每条边最大负债1,移动后每个点最多棋子1个

且保证任意个时间周期的结果唯一

问所有合法放置方案数

范围

n 2e5

2s

1024mb

题解

我的思路

要唯一,考虑做树上dp

dp[from][to][tofa] 每个点2x2x2=8 最多8个状态

from表示根原来有或没, to表示移动一次后有或没, tofa表示移动一次以后对父节点是否有贡献

但转移感觉只有手动推一推, 不知道自动怎么算

题解

注意到是唯一的反复跳 u->v->u->v

那么实际上树是由多个不相交的链组成的

如果分叉角度说

a-b a-c a-d

a总有一轮是1, 两轮都是0是不可能的(这样有多个摆放方案

那么移动一次后一是到b,c,d中的一个

而下一次会移动回来

说明a至多和两个位置跳来跳去剩下的就是和a不相关的链了

那么1110110, 这样的看作两条链

问题就是如何划分链

potato167 的blog上画了很多方便理解的图

注意到每个独立的链都是 111110 的形式, 而不相交的相邻链是 1和0 相临的, 且独立的链最小长度为2

然后一条链的端点也不能和另一条链的中间点相邻, 但两条链的中点可以相邻

所以对于一个点来讲,它可以是头0,头1或者中间的1,

dp上 就考虑根的状态了

0 端点 ( 另一个端点是这个端点的后代

1 端点 ( 另一个端点不是这个端点的后代

2 非端点, 且连接父节点

3 非端点, 且连接两个子节点

这里的状态划分也不再关心是端点是0还是1,因为你只需要保证端点之和端点相邻(相邻的端点相互决定),这样只用关心有多少自由端点的个数n即可, $2^n$

手推4种状态

0: 1个子节点1/2, 剩余都是0

1: 所有子节点都是0

2: 1个子节点1/2, 剩余都是3

3: 2个子节点1/2, 剩余都是3

除了状态转移, 还需要统计自由度

中间的3 和 根的0 会让自由度+1

自由度+1, 相当于答案乘2, 所以直接统计答案比记录自由度更方便

计算

0:

一种方案是

sum (dp[v][1]+dp[v][2]) * ((sum dp[..][0]) - dp[v][0])

sum (dp[v][1]+dp[v][2]) * (sum dp[..][0]) - sum (dp[v][1]+dp[v][2]) * dp[v][0])

(sum1+sum2)*sum0 - sum( (v1+v2)(v0))

另一种按照循环增加的算法是

res = (res * dp[v][0]) + (dp[v][1] + dp[v][2])*(before all 0)

1: all0

2: 类似0的计算方法 采取循环子节点 的方法

res = (res * dp[v][3]) + (dp[v][1] + dp[v][2])*(before all 3)

3: 相当于双状态转移

res[2个满足子节点] = res[2] * dp3 + (dp1+dp2)*(before res[1])

res[1个满足子节点] = res[1] * dp3 + (dp1+dp2)*(before res[0] = before all 3)

最后记得3还要再乘2

当然注意到 1和2只有过程中的计算才是分开的, 父子之间处理是一起使用的, 还可以降低一个状态,虽然意义不大

代码

https://atcoder.jp/contests/arc142/submissions/32681890

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
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define MOD 998244353
#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> G[200010];
 
int main() {
  int n = read();
  rep(i,1,n){
    int u = read() - 1;
    int v = read() - 1;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  vector<int> fa(n,-1); // 父节点?
  vector<int> order={0}; // 树上bfs 顺序, 反序就是树上dp
  rep(i,0,n) {
    int u = order[i];
    for(auto v:G[u]){
      if(v == fa[u]) continue;
      fa[v] = u;
      order.push_back(v);
    }
  }
 
  vector<vector<ll>> dp(n,vector<ll>(4));
  per(i,0,n){
    int u = order[i];
    ll all0 = 1;
    ll all3 = 1;
    ll pre1 = 0;
    for(auto v:G[u]){
      if(fa[v]!=u) continue;
      ll s12 = (dp[v][1]+dp[v][2])%MOD;
      // 0
      dp[u][0] = (dp[u][0] * dp[v][0] % MOD + all0 * s12 % MOD)%MOD;
      // 2
      dp[u][2] = (dp[u][2] * dp[v][3] % MOD + all3 * s12 % MOD)%MOD;
      // 3
      dp[u][3] = (dp[u][3] * dp[v][3] % MOD + pre1 * s12 % MOD)%MOD;
      pre1     = (pre1     * dp[v][3] % MOD + all3 * s12 % MOD)%MOD;

      (all0 *= dp[v][0]) %= MOD;
      (all3 *= dp[v][3]) %= MOD;
    }
    // 1
    dp[u][1] = all0;
    (dp[u][3] *= 2) %= MOD;
  }
  printf("%lld\n",(dp[0][0] * 2 % MOD + dp[0][3])%MOD);
}

如果再压缩1和2的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<vector<ll>> dp(n,vector<ll>(3)); // 0:0, 1:1&2, 2:3
per(i,0,n){
  int u = order[i];
  ll all0 = 1;
  ll all3 = 1;
  ll pre1 = 0;
  for(auto v:G[u]){
    if(fa[v]!=u) continue;
    dp[u][0] = (dp[u][0] * dp[v][0] % MOD + all0 * dp[v][1] % MOD)%MOD; // 0
    dp[u][1] = (dp[u][1] * dp[v][2] % MOD + all3 * dp[v][1] % MOD)%MOD; // 2
    dp[u][2] = (dp[u][2] * dp[v][2] % MOD + pre1 * dp[v][1] % MOD)%MOD; // 3
    pre1     = (pre1     * dp[v][2] % MOD + all3 * dp[v][1] % MOD)%MOD;
    (all0 *= dp[v][0]) %= MOD;
    (all3 *= dp[v][2]) %= MOD;
  }
  (dp[u][1] += all0) %= MOD; // 1 & 2
  (dp[u][2] *= 2) %= MOD;
}
printf("%lld\n",(dp[0][0] * 2 % MOD + dp[0][2])%MOD);

E

n 个巫师,

ai 能力

打败 bi 怪物

对任意巫师增加任意次1能力

(i,j) is good when (a[i] >= bi and a[j] >= bj) or (a[i] >= b[j] and a[j] >= b[i])

相当于直接打败或交叉打败

给你m 个 (x,y)

要最小增加能力, 让所有(x,y) 是good

范围

n 100

ai bi [1,100]

题解

思路

如果自己打败自己,那很好算,但是不一定是答案,但是答案上界至少是

考虑结果总有个每个巫师的大小顺序

如果(a[i] - a[j])*(b[i]-b[j]) >= 0 , 且存在限制 (x,y) = (i,j)

那么 必然a[i] >= b[i] a[j] >= b[j] , 如果

因为如果(i,j) good ,也就是 min(a[i],a[j]) >= min(b[i],b[j]) , max(a[i],a[j]) >= max(b[i],b[j])

但是n是100 不可能去枚举顺序

题解

首先, a[x],a[y] >= min(a[x],a[y]) 这是必要的, 所以可以预处理掉这个

X 为 能力 小于 monter的 集合, 且在(x,y)中出现了的巫师

Y 是 其它的巫师

对于(x,y) 且 x属于X, y属于Y, 结果上期望 a[y] >= b[x] 或 a[x] >= b[x]

因为有预处理, 所以b[x] > b[y], 因为如果 b[x] <= b[y] 那么必然有 a[x] >= min(b[x],b[y]) = b[x], x不会属于X,

也就是X-Y的连接, 一定y中的b更小

b[x] > a[x] >= b[y] 的顺序, a[y] >= b[y]

对于Y-Y的连接,不需要考虑,因为a只会增大,原来满足增加后还是满足

对于X-X的链接,不会存在,因为有了预处理, 这两个a大于min(b), 所以一定有一个属于Y

回到X-Y

a[y] >= b[x] > a[x] >= b[y] 直接合法

b[x] > (a[x],a[y]) >= b[y] 考虑上面是让a[y] >= b[x] 还是 a[x] >= b[x]

建图

点:

S源,T汇

X每个x一个点

Y每个y,100个点(y,i = 1..100)

边

S -> x 权重b[x] - a[x]

(y,i) -> T 权重1

(y,i) -> (y,i-1) 权重无限大

x -> (y,b[x] - a[y]) 权重无限大

意义

先看假设只有一对

S-(bx-ax)->x-(无限)-> (y, b[x]-a[y])-(1)-> T, 然后还有些(y,i)->(y,i-1)的边

S->X这边限制了不会大于bx-ax, 右边限制了不会大于bx-ay

最小割一定是 S->x和(y,i)->T 中的边,不会是那些无限的边

而如果S->x 不在最小割里,说明右侧对应的(y,b[x]-a[y]) -> T, 以及更小的i的(y,i) 全部填满, 否则可至少可以再+1, 填满也就说明选择满足

这个最小割的建图,我也是真不会啊(最大流,最小割还是会写)

代码

https://atcoder.jp/contests/arc142/submissions/32759166

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#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

#define N 100
#define INF 0x3f3f3f3f
int n,m;
int a[N+10];
int b[N+10];
vector<int> p2[110]; // 双向关系

int S = 0;
int T = 1;

// S,T,[2..101],[102...201][202..301][302..401]
//
int nodex(int x) {
  assert(x >=0 && x< 100);
  return 2+x;
}

int nodey(int y,int value) {
  assert(y >=0 && y< 100);
  assert(value >=1 && value <= 100);
  return 101 + y*100 + value;
}

class MinCut{
  int sz ;
  // TODO 优化成正反边下标
  vector<unordered_map<int,ll> > G; // {idx,weight}
  vector<int> d; // bfs 距离

public:
  MinCut(int n):sz(n){
    G = vector<unordered_map<int,ll> >(sz);
  }

  void path(int u,int v,ll w){
    assert(u != v);
    G[u][v] += w;
  }

  int dfs(int u,int en, ll s){
    if (u == en)return s;
    for(auto [v,w]:G[u]){
      if(w == 0) continue;
      if(d[v] != d[u]+1) continue;
      int r = dfs(v,en,min(s,w));
      if(r){
        G[u][v] -= r;
        G[v][u] += r;
        return r;
      }
    }
    d[u] = 0; // 标记无效 替代vis
    return 0;
  }

  bool bfs(int st,int en){
    d = vector<int>(sz+10,-1);
    vector<int> q = {st};
    d[st] = 0;
    rep(i,0,q.size()){
      int u = q[i];
      for(auto [v,w]: G[u]){ // u -> v, weight =w
        if(d[v] != -1) continue;
        if(w == 0) continue;
        d[v] = d[u] +1;
        q.pb(v);
      }
    }
    return d[en] >= 0;
  }
  // 一次性计算
  ll calc(int st,int en){
    int ans = 0;
    while (bfs(st, en)) ans += dfs(st, en, INF);
    return ans;
  }
};

int main(){
  n = read();
  S = 0;
  T = 1;

  rep(i,0,n){
    a[i] = read();
    b[i] = read();
  }
  m = read();
  int ans = 0;
  // 预处理 和 建边
  rep(i,0,m){
    int x = read() - 1;
    int y = read() - 1;
    int minv = min(b[x],b[y]);
    ans += max(0,minv - a[x]);
    a[x] = max(a[x],minv);
    ans += max(0,minv - a[y]);
    a[y] = max(a[y],minv);

    p2[x].pb(y);
    p2[y].pb(x);
  }
  MinCut mc(20000);
  rep(i,0,n) {
    if(a[i] < b[i]){ // i in X
      mc.path(S,nodex(i),b[i] - a[i]);
      for(auto u:p2[i]){ // u in Y
        if(a[u] >= b[i]) continue;
        mc.path(nodex(i),nodey(u,b[i]-a[u]),INF);
      }
    }else{ // i in Y
      rep(j,1,101){
        mc.path(nodey(i,j),T,1);
        if(j > 1){
          mc.path(nodey(i,j),nodey(i,j-1),INF);
        }
      }
    }
  }
  printf("%lld\n",ans + mc.calc(S,T) );
  return 0;
}

总结

D

我突然觉得我的dp[from][to][tofa] 是不是也可能可以做?? 看起来是完全不同的思路

虽然想到反复横跳,但拆成链以及链的链接合法方式完全没想过

而且即使是拆成链,看了积分代码, 所做的树上dp也不相同, 能拆成这样四个也是很需要功力的

看potato167的代码学了一手非递归的树上dp, 通过先建立order,再逆序做

E

光是这个预处理就很厉害,解决了分类的问题, 能证明但完全没能自己挖掘出这个性质

然后这个建图我也是不会, 虽然学过最大流最小割,但是为啥这样想,没做过这种, 顺便整两个mincut板子

参考

官方题解

potato167 D

發表於 更新於 分類於 Disqus： 文章字數： 781 所需閱讀時間 ≈ 3 分鐘
P5.MINXORSEG(XOR,fenwick)

MINXORSEG

评分 3087, tourist 也没做出

给你长度n数组, q个询问,每次问区间[l,r]中任意两个数的异或的最小值

范围

n 2e5

q 2e5

ai 2^30

3s

400MB

题解

离线, 按查询的右端点排序

简单的扫描加入 是n方?

x=a[l]^a[r]

假设x最高位1在p位,那么高于p的bit,a[l]和a[r]一样

如果[l..r] 之间有同样的高于p的bit和它们一样的t,那么(l,r)这一对一定不是最小值,因为 (l,t) 或 (t,r) 比它小

如果区间有3个高w位一样,那么答案至少是高w位为0, 所以答案最小的只存两个高w一样,或者存在两个相等的数

这个观察很神奇,也就是说如果ai和aj高w位相同,那么要让它们可能是答案的必要条件是,它们中间没有高w位和它们相同的

换句话说, a[i]如果和它前面某个a[j]高w相同,贡献了最小xor,那么a[i]的w相同的前面最近的就是a[j]

所以直接记录每个数前面和它高0,1,2,3..位相同的最近的下标即可, 这可以简单的排序记录

最后扫描+fenwick一下

其中把每对的左点为index,异或和为值,做后缀min fenwick 就可以了, 这样每次询问就是[l… 中的最小值

代码

https://www.codechef.com/viewsolution/67421139

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

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const ll INF = 0x3f3f3f3f3f3f;

ll read(){ll r;scanf("%lld",&r);return r;} // read
ll a[200010];
int idxs[200010];

struct fenwick_tree {
  vector<ll> bit;
  int n;
  fenwick_tree(int n) : n(n) {
    bit = vector<ll> (n + 1, INF); // 后缀min fenwick
  }
  void update(int u, ll v) {
    for (u++; u > 0; u -= u & -u) bit[u] = min(bit[u], v);
  }

  int query(int u) {
    ll r = INF;
    for (u++; u <= n; u += u & -u) r = min(r, bit[u]);
    return r;
  }
};

int main() {
  int n = read();
  int q = read();
  vector<vector<int>> lst(n);
  vector<vector<pair<int, int>>> que(n);
  rep(i,0,n) a[i] = read();
  rep(b,0,30+1) { // 低位到高位
    // 按高 30-p 位排序
    iota(idxs,idxs+n,0);
    sort(idxs,idxs+n,[=](int i,int j){return make_pair((a[i] >> b),i) < make_pair((a[j] >> b),j); });
    rep(i,1,n) {
      if ((a[idxs[i]] >> b) == (a[idxs[i-1]] >> b)) { // 高位相同,建立可能对最小值贡献的关系
        lst[idxs[i]].push_back(idxs[i-1]);
      }
    }
  }
  vector<int> ans(q);
  rep(i,0,q) {
    int l = read() - 1;
    int r = read() - 1;
    que[r].push_back({l, i});
  }
  fenwick_tree fen(n);
  rep(i, 0, n) {
    for (int v : lst[i]) fen.update(v, a[v] ^ a[i]);
    for (auto [l, ind] : que[i]) ans[ind] = fen.query(l);
  }
  for(auto v:ans) printf("%d\n", v);
}

// n 2e5 个数
// q询问,2e5
// 查区间内 最小的两个值的 xor

代码

总结

MINXORSEG

这个观察最小的可能贡献很厉害啊, 应该属于xor的一个神奇的知识点了?

另一个就是, 这种非统计的, 最大最小也是可以从”可能贡献”的角度去思考,这个我没有思路过,学到了

fenwick这个还有后缀写法,不需要做颠倒原数组的动作

参考

官方

發表於 更新於 分類於 ， Disqus： 文章字數： 745 所需閱讀時間 ≈ 2 分鐘
总体观察,数学,贪心

E(总体观察,数学),F(贪心)

E

https://codeforces.com/contest/1700/problem/E

给你一个矩阵,每个数字都不相同

然后让你依次取1,2,3,4,… 取完所有

取的块需要和之前取过的至少一个4临

直接可取输出0

需要还是交换两个位置(可以不相邻)后可取,输出1 方案数

还是都不行输出2

范围

矩阵大小4e5

2s

256MB

题解

我的思路

0很好判断,vis染色+bfs

其实就是1的时候怎么算个数

不妨设按找上述方法最开始失败的是x

意味着, 小于x的连在一起了,

那么有两种方案

  1. 交换x和小于x的外边界,这样小于等于x就连在一起了,
  2. 交换小于x的某一个和x的四临

但是这两种如果一个一个检验是时间复杂度会炸掉的

考虑可交换的,对于第一种没有什么思路

对于第二种,你可以考察每个依赖于它的是否仅依赖于它, 但也不一定

1
2
3
4
145
2.6
3?7
.8.

比如上面这样,7仅依赖于6,而6也可以移动

不知道怎么搞了

题解

不要看一步一步,看总览性质

如果一个位置，它的四个邻居有比他小的，那么它就能连到小于它的数。矩阵为可遍历当且仅当所有点（除了1）的四个邻居都有比他小的。

这归纳法可证明

所以判断可行,也不再需要vis+bfs, 而直接判断count(badpos)== 0

所以badpos 需要交换它或者它的邻居

两两不相同,显然badpos不相邻, 因为badpos需要小于4临, 说明4临都不是badpos

两两不同,说明交换以后的两个位置,一个比原来大,一个比原来小,

比原来大的位置4邻之前一定不是badpos,

比原来小的本身一定不是badpos

综上, badpos最多5个, 一个中心一个4临

5x5x4, 种

代码

无

F

题目

https://codeforces.com/contest/1700/problem/F

2 * n 的01矩阵,两个

每次交换第一个中相邻位置的01,求最小次数得到第二个矩阵

范围

n 2e5

1s

256mb

题解

我的思路

写了个假的

两个变量记录未匹配的,然后进入则+,退出则-

发生 一正一负则消耗1抵消

竟然官方数据弱还过了system test

然后有错误样例

1
2
3
4
5
0 1 0
1 0 0

0 1 0
0 0 1

我的匹配会

1
2
3
4
5
0 b 0
a 0 0

0 a 0
0 0 b

代价为4, 最小的是2

官方

直接可配消耗掉即可…….

代码

无

总结

E

这个总体观察没想到, 一直在想细节的步, 总体只想到vis+bfs 而不是这个充分性质

jiangly 也TLE了好像

F

贪心细节还是没想到啊

参考

官方

發表於 更新於 分類於 Disqus： 文章字數： 434 所需閱讀時間 ≈ 1 分鐘

D https://ac.nowcoder.com/acm/contest/11201/D

总思路没问题, dijkstra不能带log, 2s时间卡时限了

没有log的也800ms, 稍微一个3倍都过不了

所以需要的是点的值要么是初始的要么是推导(当前最大值-定值k)生成的, 双队列+指针实现

没过这题也能+3

代码

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
#define pb push_back
#define c(a,b) ((a)*(m)+(b))

int read(){int r; scanf("%d", &r);return r;} // read

int a[500010];
int n,m,k;

bool vis[500010];

const int di[] = {-1,1,0,0,-1,1};
const int dj[] = {0,0,-1,1,1,-1};

vector< array<int,3> > startvij;

ll cost(int diff){
  fill(vis,vis + n*m,false);
  vector< array<int,3> > vp = {}; // 优先队列等含有log的会TLE
  ll sk = 0 ;
  vp = {};
  int i0 = 0;
  int i1 = 0;
  while(i0 < startvij.size() || i1 < vp.size()){
    int v = 0;
    int i = -1;
    int j = -1;
    if(i0 < startvij.size() && i1 < vp.size()){
      if(startvij[i0][0] >= vp[i1][0]){
        v = startvij[i0][0];
        i = startvij[i0][1];
        j = startvij[i0][2];
        i0++;
      }else{
        v = vp[i1][0];
        i = vp[i1][1];
        j = vp[i1][2];
        i1++;
      }
    }else if(i0 < startvij.size()){
      v = startvij[i0][0];
      i = startvij[i0][1];
      j = startvij[i0][2];
      i0++;
    }else {
      v = vp[i1][0];
      i = vp[i1][1];
      j = vp[i1][2];
      i1++;
    }
    if(vis[c(i,j)])continue;
    vis[c(i,j)] = true;
    sk += v - a[c(i,j)];
    rep(w,0,6){
      int ni = i + di[w];
      int nj = j + dj[w];
      if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
      if(a[c(ni,nj)] == -1) continue;
      if(vis[c(ni,nj)]) continue;
      if(v - diff > a[c(ni,nj)]){
        vp.pb({v - diff,ni,nj});
      }
    }
  }
  return sk;
}

int main(){
  n = read();
  m = read();
  k = read();

  rep(i,0,n){
    rep(j,0,m){
      a[c(i,j)] = read();
      if(a[c(i,j)] != -1) startvij.pb({a[c(i,j)],i,j});
    }
  }
  sort(startvij.begin(), startvij.end(), greater<array<int,3>>());

  int l = 0;
  int r = 1000;
  int ans = 1000;
  while(l <= r){
    int mid = (l+r)/2;
    if(cost(mid) <= k){
      ans = mid;
      r = mid - 1;
    }else{
      l = mid + 1;
    }
  }
  cout<<ans<<endl;
  return 0;
}
0%