Atcoder abc257

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