YeXiaoRain Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(数学,数组,相邻无序对)G(GF(2),meet in middle,不懂证明)

F

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

给长度n的数组A和B

每次可以选择A数组中值相等两个数,把它们中间的区间颠倒顺序

求$n^2$次数内的方案得到B

范围

n 500

1s

256MB

题解

我的思路

没有思路

只知道首个和末个 有重复的数字的一定位置不会变,且它们两侧的也不会变

但如何记录翻转并不知道

可行的话, 首先每个值个数要一样

题解

数组不变量

首先a1和an是不会变的

然后是相邻元素构成无序对不变, 因为 区间 v…v颠倒,那么 中间和v连接的依然和v连接

必要显然

充分性, 我们具体构造

假设 前缀 a[..i] 和 b[..i] 相同, a[i] = x

a[i+1] = y

b[i+1] = z

如果存在 a[i..] = [x,y,...,z,x,...] 那么直接翻转 做1次

如果 a[i...] = [x,y,...,x,z,...], 如果 x,z 右侧还有x 则翻转2次

否则 x,z 的x是最后出现的x, 所以, x至少2个

如果x恰好2个, 且是连着 a[i..]= [x,y,x,z,...], b[i..] = [x,z,....y,x,y,...] , 这样转b

否则a[i..] 中 x相邻至少3对相邻

那么根据上面的,只有最后的那一个x的右侧不能通过,x本身交换 完成, 而a和b的操作是对称的

所以 3对中 最多2对无法交换,所以总存在一个相邻,可以0~2次 完成换到a[i..] = [x,?,...]

即只要满足,无序对的性质

那么a[0..i] 一致了 就有办法让b[0..i] 一致

直接暴力找 O(n^2)

注意到的是算法实际的次数是不超过4n的

而需要的是小于$n^2$的次数,所以考察 n=[1..4]的合法的数组的操作次数时候

n=1 0次

n=2 0次

n=3 0次

n=4 0次/1次

所以也满足次数要求

代码

https://codeforces.com/contest/1698/submission/162605498

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

#define MOD 1000000007
#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;)

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

int n;
int a[510];
int b[510];

// 翻转区间
void rev(int *arr,int i,int j){
  rep(k,i,j+1){
    int rk = j-(k-i);
    if(rk < k)break;
    swap(arr[k],arr[rk]);
  }
}

// 找arr[sti...]中 找 [x,y,...,z,x,...], 翻转成[x,z...]
bool op(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........z,x]
    // [sti............i]
    if(arr[i] == x && arr[i-1] == z){
      rev(arr, sti+1,i-1);
      ans.push_back({sti+1,i+1});
      return true;
    }
  }
  return false;
}

// 找arr[sti...]中 找 [x,y,...,x,z,...,x,...], 翻转成[x,z...]
bool oprev(int *arr,int sti,int z,vector<pair<int,int>> & ans){
  int x = arr[sti];
  rep(i,sti+1,n){
    // [x,y........x,z,.....x]
    // [sti..........i      j]
    if(arr[i] == z && arr[i-1] == x){
      rep(j,i+1,n){
        if(arr[j] == x){
          rev(arr, sti+1,j-1);
          ans.push_back({sti+1,j+1});
          return op(arr,sti,z,ans);
        }
      }
      return false;
    }
  }
  return false;
}

void w(){
  n = read();
  rep(i,0,n) a[i] = read();
  rep(i,0,n) b[i] = read();
  if(a[0] != b[0]) {
    printf("NO\n");
    return ;
  }
  if(a[n-1] != b[n-1]){
    printf("NO\n");
    return ;
  }
  vector<pair<int,int>> pa;
  rep(i,1,n){
    int u = a[i-1];
    int v = a[i];
    if(u > v) swap(u,v);
    pa.push_back({u,v});
  }
  vector<pair<int,int>> pb;
  rep(i,1,n){
    int u = b[i-1];
    int v = b[i];
    if(u > v) swap(u,v);
    pb.push_back({u,v});
  }
  sort(pa.begin(),pa.end());
  sort(pb.begin(),pb.end());
  if(pa != pb){
    printf("NO\n");
    return ;
  }
  printf("YES\n");
  // 一定可以
  // -------------
  vector< pair<int,int> >ans; // 正向
  vector< pair<int,int> >revans; // 反向
  rep(i,0,n){
    if(a[i] != b[i]){
      int x = a[i-1];
      //
      if(op(   a,i-1,b[i],ans))continue;
      if(oprev(a,i-1,b[i],ans))continue;
      if(op(   b,i-1,a[i],revans))continue;
      if(oprev(b,i-1,a[i],revans))continue;
      int w = -1; // 找既不等于 b[i] 也不等于a[i]的 x相邻的, 至少存在一个
      rep(j,i+1,n){
        if(a[j] == x){
          if(a[j-1] != a[i] && a[j-1] != b[i]){
            w = a[j-1];
          }else if(a[j+1] != a[i] && a[j+1] != b[i]){
            w = a[j+1];
          }
          assert(w!=-1);
          break;
        }
      }
      assert(w!=-1);
      if(!op(a,i-1,w,ans)){
        assert(oprev(a,i-1,w,ans));
      }
      if(!op(b,i-1,w,revans)){
        assert(oprev(b,i-1,w,revans));
      }
    }
  }
  per(i,0,revans.size()) ans.push_back(revans[i]);
  printf("%d\n",(int)ans.size());
  for(auto [u,v]:ans){
    printf("%d %d\n",u,v);
  }
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

G

S 是长度n的0/1串

让S与任意个S的任意正位移 做xor

求 结果中1的个数恰好2个,且字符串表示下字典序最大的串中, 这两个1的位置

限制

n 35

2s

256MB

题解

我的思路

显然 第一次取S

然后把首个1以后的内容 的 首个1与S的首个1对齐 做xor, 直到后续剩余的只有1个1

这样的话,S的首个1和末个1各贡献一次, 位置就可以算了

为了简化运算,可以预处理掉S的前后缀0记录下来

然而n有35, 虽然无法估计精确复杂度,但这样做上限是2的35次方会超时,写出来也果然tle 6 了

官方

多项式问题

首先 忽略S前后缀0, 这些零在最后的结果中会加回来

那么把S看作在GF(2)域中多项式P(x)

Galois Field, 只有0,1二元及+（异或运算）×（与运算）

那么要求的是$P(x)Q(x) = x^k+1$ 的最小k

P(x)的常数项是1, Q是任意的, 所以一定存在

证明, 显然 $x^k$ 随着k增大$x^k \mod P(x)$ 成周期,且始终不为0, 那么周期的就是一个$x^k \mod P(x) = 1$的解

所以$k \le 2^{35}$ 依然很大

要用的方法是meet in middle?

emmmmm 就是直接除 然后meet in middle?

我没懂 这个prod 为何一定是 mod 为1, 以及GF(2)域上的相关性质

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
#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
#define all(x) (x).begin(), (x).end()

int n;
char s0[100];
ll mod;

// (i*j)%mod in GF(2)
ll mul(ll i, ll j) {
  ll res = 0;
  rep(x, 0, n-1) {
    if (i & (1LL << x)) res ^= j;
    j <<= 1;
    if (j & (1LL << (n - 1))) j ^= mod; // 取mod in GF(2)
  }
  return res;
}

// (2**i)%mod in GF(2)
ll pow2(ll pwr) {
  ll res = 1; // result
  ll b = 2; // base
  while (pwr) { // pwr
    if (pwr & 1) res = mul(res, b);
    b = mul(b, b);
    pwr >>= 1;
  }
  return res;
}

// v的二进制最高位1在2的多少幂次, high1(3) = 1
int high1(ll v){
  int leadz = __builtin_clzll(v); // x 前缀0个数
  return 63 - leadz;
}

int main() {
  char *s = s0;
  scanf("%s",s);
  n = strlen(s);
  vector<int> pos; // 只用来判断 <= 2的1
  rep(i,0,n){
    if (s[i] == '1') pos.push_back(i+1);
  }
  per(i,0,n) { // remove trailing zero
    if(s[i] != '0') break;
    s[i] = 0;
  }
  rep(i,0,n) { // remove prefix zero
    if(s[0] != '0') break;
    s++;
  }
  int offset = s - s0; // 前导0
  n = strlen(s);
  if (pos.size() == 0) { // all zero
    printf("-1\n");
    return 0;
  }
  if (pos.size() == 1) { // only 1 of 1
    printf("%d %d\n",pos[0],pos[0]+1);
    return 0;
  }
  if (pos.size() == 2) { // 恰好2个
    printf("%d %d\n",pos[0],pos[1]);
    return 0;
  }
  rep(i, 0, n) { // 正向和逆向结果一样的
    if (s[i] == '1') mod |= (1LL << i); // s.trim().tobinary()
  }
  printf("s: %lld\n",mod);

  int h = (n + 1) / 2; // 半长

  ll val = mod;
  ll prod = 1; // (2**h(x)-1)(2**h(x))**(pwr-1)
  rep(x, 3LL, 1 << h) { // GF(2)乘法还满足结合率
    if (!(x & 1)) continue; // x 末位是1
    int pwr = 0; // val = x^pwr * ... 相当于 计算GF(2) 中 val的因子和幂次
    while (true) {
      ll curr = val;
      ll other = 0;
      rep(bit, 0, n) {
        if (!(curr & (1LL << bit))) continue;
        curr ^= x << bit;
        other ^= 1LL << bit;
      }
      if (curr)  break;
      // val = x * other in GF(2)
      printf("%lld = %lld * %lld\n", val, x, other);
      val = other;
      pwr++;
    }
    if (pwr) { // x的pwr次方
      printf("=> %lld ** %d\n",x,pwr);
      printf("high1[%lld] =  %d\n",x,high1(x));
      // prod *= (10-1) * 10 * 10 ,        3**3
      prod *= (1LL << high1(x)) - 1;
      rep(y, 1, pwr) prod *= 1LL << high1(x);
    }
  }
  // val 的 一次方
  if (val > 1) prod *= (1LL << high1(val)) - 1;
  // mod => GF(2) => 基的幂次 乘积 => (2的幂次)的幂次和2的(幂次-1) 的 积

  ll ans = 1LL << 60;
  // printf("prod:%lld\n",prod);
  assert(pow2(prod) == 1); // 2**prod ???????????????????????????????????????????
  for (ll x = 1; x * x <= prod; x++) { // 长度一定是prod的因子 ????????????????????????????????
    if (prod % x ) continue;
    if (pow2(x) == 1) ans = min(ans, x);
    if (pow2(prod / x) == 1) ans = min(ans, prod / x);
  }
  printf("%d %lld\n",offset+1,offset+ans+1);
}

总结

F

这个交换性质 厉害了,之前并不了解,也没有自己推出

相等的位置的交换,必定让相邻无序对是不变的,而且是充要条件

还是不变量的思考

G

GF(2) 真的没有系统学过

通过这个题看起来 乘法还 满足 结合率

加减也是对称的 A+B= C, A-B=C

参考

官方

洛谷 GF(2)

發表於 更新於 分類於 ， Disqus： 文章字數： 711 所需閱讀時間 ≈ 2 分鐘
D(dfs,无向图无桥联通块,强连通分量)

哎 超时8min过了E,但这个D我还是不会

D

评分2229

题目

https://atcoder.jp/contests/arc143/tasks/arc143_d

左边1-n的点

右边1-n的点

左i-右i有边

给你m对数 (ai,bi), 你需要输出长度为m的0/1字符串

如果你要(左ai-右bi) 则第i个字符为0, 如果你要(左bi-右ai)则第i个字符是1

最终让图里的桥最少, 求一个字符串方案

范围

n 2e5

m 2e5

2s

1024mb

题解

我的思路

只想着贪心

首先如果一个边在任意环里那它就不是桥, 所以希望能贪心尽量让边进入环

统计给的m对数中, 每个值出现的次数

对于只出现一次的无药可救,先不管它

对于出现2次的,那就安排让它左右各连出一个

如果运算过程中某个点一侧被连了,另一侧没有连,还有关于这个点的数对,那么就去连另一测

已经两侧都连了的就不管

但就写的来看似乎有问题, 还蛮多人过了这个题

题解

一句话 把它当成一个未定向的有向图， 然后在图上找环， 并定向即可

首先考虑一个n个点, m边的无向图, 按照ai-bi的连接

如果有边在无向图中也是桥, 那么在题目问题中它只能是桥

对于无向图来说,移除了所有桥以后, 每个连通块可以单独独立处理

所以假设 拿到一个无向连通 无桥图

总有办法给所有边一个方向,让连通图变成强联通图

一个办法就是 直接做dfs树

代码

https://atcoder.jp/contests/arc143/submissions/32806181

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

#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back

int read(){int r;scanf("%intd",&r);return r;} // read
int n;
int m;

char s[200010]; // answer
pair<int,int> ab[200010];
vector<array<int,3>> u2[200010]; // {v, ab idx, '0','1'}
bool vis[200010];

void dfs(int u){
  vis[u] = true;
  for(auto [v,i,o]:u2[u]){
    if(s[i]) continue; // 边处理过
    s[i] = (char)o;
    if(!vis[v]) dfs(v);
  }
}


int main(){
  n = read();
  m = read();
  rep(i,0,m) ab[i].first = read();
  rep(i,0,m){
    int a = ab[i].first;
    int b = ab[i].second = read();
    u2[a].pb({b,i,(int)'0'});
    u2[b].pb({a,i,(int)'1'});
  }
  rep(i,1,n+1){
    if(vis[i])continue;
    dfs(i);
  }
  rep(i,0,m){
    if(!s[i]) s[i] = '0';
  }
  printf("%s\n",s);
  return 0;
}

总结

D

知道逻辑以后 10min 随便写了QAQ

我不知道应该怎么归类,信息提取,还是有向图无向图连通性质

我觉得有一点 算是 无向图的无桥联通块 能通过指定所有边 变成有向图的强连通分量这一点吧,但好像又是一个提炼性质

哎

参考

官方题解

發表於 更新於 分類於 ， Disqus： 文章字數： 1.6k 所需閱讀時間 ≈ 5 分鐘
G(线性规划,对偶,DP,矩阵乘法,segtree)H(TODO)

G

给一个长n数列

q个操作或询问

  1. 操作修改 a[i] = v
  2. 询问[l,r] 区间上, 最小处理代价(不真实的修改区间)

f(l,r) = 每次可以对 相邻元素,分别 (-xt,-yt) 或(-yt,-xt) 代价为t

问最小代价和让 a[l..r] 全部小于等于0

范围

n 2e5

q 2e5

x,y [1,1e6]

ai, v [1,1e6]

6s

1024MB

题解

我的思路

因为对称,不妨设 ( x < y)

开始没看到相邻以为任意,那么不就是维护区间和与区间最大值 = max(和/(x+y),最大值/y)

但是要相邻这样肯定不对了, 比如样例1, 不相邻可以3,相邻最少要3.5

单次询问怎么做?

题解

线性规划对偶

https://pic1.zhimg.com/80/v2-b780de4a3bd814944026ad22f51518f8_720w.jpg

$max \sum c_j x_j$

限制

$a_{ij} x_{j} \le b_i$

$x_j \ge 0$

$i=1\cdots m,j=1\cdots n$

它的对偶问题

$min \sum b_i y_i$

限制

$a_{ij} y_{i} \ge c_i$

$y_i \ge 0$

$i=1\cdots m,j=1\cdots n$

我看了很多直觉的举例,反而没有理解,通过公式倒是理解了大流程, 下面youtube链接 感觉很清晰

小写字母表示列向量,大写字母表示矩阵

$max (c^Tx)$

$Ax \le b$

$x \ge 0$

对于任意$y \ge 0$满足

$c^Tx \le y^TAx$

有 $c^Tx \le y^TAx \le y^Tb$, 所以所有都满足,那么它的最大 = 右边的最小

所以对于所有$c^T \le y^TA$, $max(c^Tx) = min(y^Tb)$

$c^T \le y^TA$ 即是$Ay \ge c$

更一般的转化

  1. min max 对换

  2. 列个数x 变成行个数y

  3. 右侧约束 和 表达式系数 兑换

  4. 偏序关系

同偏序: max 变量(xi) 与 0关系 和 min 约束(不等式组xi) 左与右 关系

反偏序: min 变量(xi) 与 0关系 和 max 约束(不等式组xi) 左与右 关系

约束等于 对应 变量无约束

回到题目

线性规划 问题

原数组A

最小化 $\sum_{1\le i < n} a_i+b_i $

限制

$Xa_1+Yb_1\ge A_1$

$Xa_i+Yb_i+Ya_{i-1}+Xb_{i-1}\ge A_i (2\le i < n) $

$Ya_{n-1}+Xb_{n-1}\ge A_n $

$a_i,b_i\ge 0$

那么对偶

最大化 $\sum_{1\le i \le n} A_iz_i $

限制

$xz_i + yz_{i+1} \le 1 (1 \le z < n)$

$yz_i + xz_{i+1} \le 1 (1 \le z < n)$

$z_i \ge 0$

很好的把上面要求的所有系数1变成了右侧的限制

所以$z_i$ 可能取值$0,\frac{1}{y},\frac{1}{x+y}$

如果只有两个, 线性规划很明显 https://www.wolframalpha.com/input?i=2x%2B3y+%3C%3D+1%2C+2y%2B3x+%3C%3D+1

去画3个的3d情况,你会发现,和2d一样虽然有些棱,但如果这个棱上最优,那么棱上的顶点也最优,但这些凸点的坐标都是这三个可能值中

然后就可以dp了

dp[i][0/1/2], 即是算 $max \sum_{j \le i} A_jz_j$

代码

jiangly 的, 他整个G只花了15min??????

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

#define SEG_ROOT 1,0,n
#define mid (l+r)/2
#define SEG_L 2*p
#define SEG_R 2*p+1
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid,r

ll read(){ll r;scanf("%lld",&r);return r;} // read

int n;

int a[200010];

template<class Info,
  class Merge = plus<Info> // 合并方法
  >
  struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4*n) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size()) {
      function<void(int, int, int)> build = [&](int p, int l, int r) { // [l,r) 左闭右开
        if (r - l == 1) { // 线段树叶子节点
          info[p] = init[l];
          return;
        }
        build(SEG_L_CHILD);
        build(SEG_R_CHILD);
        pull(p);
      };
      build(SEG_ROOT);
    }
    void pull(int p) {
      info[p] = merge(info[SEG_L], info[SEG_R]);
    }
    void modify(int p, int l, int r, int x, const Info &v) {
      if (r - l == 1) {
        info[p] = v;
        return;
      }
      if (x < mid) {
        modify(SEG_L_CHILD, x, v);
      } else {
        modify(SEG_R_CHILD, x, v);
      }
      pull(p);
    }
    void modify(int p, const Info &v) {
      modify(SEG_ROOT, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
      if (l >= y || r <= x) return Info(); // 直接省去范围判断, 超过范围提前 返回可参与计算的空状态
      if (l >= x && r <= y) return info[p];
      return merge(rangeQuery(SEG_L_CHILD, x, y), rangeQuery(SEG_R_CHILD, x, y));
    }
    Info rangeQuery(int l, int r) {
      return rangeQuery(SEG_ROOT, l, r);
    }
  };

int x, y;

// 0: 0
// 1: 1/(x+y)
// 2: 1/y
// 线段树每个节点
struct Info {
  double f[3][3];
  Info(ll v = 0) {
    rep(i,0,3){
      rep(j,0,3){
        if (i + j > 2) {
          f[i][j] = -1E18; // 不合法
        } else { // 这里直接 值 * z_i(0,1/(x+y),1/y), 因为转移方程里始终要乘 值
          f[i][j] = (j == 0 ? 0.0 : 1.0 * v / (j == 1 ? x + y : y));
        }
      }
    }
  }
};

// 实现合并方法
Info operator+(const Info &a, const Info &b) {
  Info c;
  rep(i,0,3){
    rep(j,0,3){
      c.f[i][j] = -1E18; // 不合法
      rep(k,0,3){
        // max 矩阵乘法
        c.f[i][j] = max(c.f[i][j], a.f[i][k] + b.f[k][j]);
      }
    }
  }
  return c;
}

int main() {
  int n = read();
  int q = read();

  x = read();
  y = read();
  if (x > y) swap(x, y); // 保证 x<=y

  vector<int> b(n);
  rep(i,0,n) b[i] = read();

  SegmentTree seg(vector<Info>(b.begin(), b.end())); // v => Info(v) => segtree(vector<info()>)

  while(q--) {
    int t = read();
    if (t == 1) {
      int k = read() - 1;
      int v = read();
      seg.modify(k, v);
    } else {
      int l = read() - 1;
      int r = read();
      auto info = seg.rangeQuery(l, r) + Info(); // + Info() 整合最大值,否则需要手动for 去取max
      printf("%.15lf\n",info.f[0][0]);
    }
  }

  return 0;
}

H

https://codeforces.com/contest/1696/problem/H

给一个正整数k

大小为n,元素可重复的集合A

f(集合S) = S中恰好选出k个元素能得到的最大乘积

求 A所有元素个数不小于k的子集B,的f(B)的和

mod 1e9+7

范围

n 600

ai [-1e9,1e9

1.5s

512 MB

题解

我的思路

如果全非负, 则最大k个的乘积

如果全负

k为偶数, 则最小k个的乘积

k为奇数, 则最大k个的乘积

如果有负有非负

k为偶数, 则负 和 非负 分两组, 每组按照绝对值 从大到小,两两成对 构成新的乘积, 一对一对选

如果k 为奇数, 取一个最大非负, 剩下的 和偶数方案一样处理

所以肯定要对原来的集合拍个序

但贡献怎么统计没有思路

题解

选k个指定它们最大? 计算会出现在多少个集合中??

总结

G

低分题做多了, 太久没遇到线性规划了,很久以前学过, 但好像也是系数多限制多变量少的,

然后这个对偶学了一下, 希望下次能有用到的地方???

最后转化可以描述为矩阵max乘法,可以用segtree维护

参考

官方

https://sites.math.washington.edu/~burke/crs/407/notes/section3.pdf

https://www.youtube.com/watch?v=yU8updOR87c

https://blog.csdn.net/qq_43539633/article/details/109150749

發表於 更新於 分類於 ， 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

0%