Atcoder arc113

發表於 2021-02-22 更新於 2024-10-23 分類於 Atcoder ， ARC Disqus：文章字數： 4.2k 所需閱讀時間 ≈ 14 分鐘

E (数学+枚举+分类讨论)F(题意转化,排序,一次函数,概率论,定积分,)

E

https://atcoder.jp/contests/arc113/tasks/arc113_e

给字符串,仅由a和b组成

操作: 任意选择两个相同的字母，把它们之间的内容颠倒顺序，删掉这两个被选择的字母

你可以操作 0 到任意次

求字典序最大的结果

我的思路

显然，可以把a看作0,b看作1,也就是1尽量靠前且尽量多，而在满足1尽量多的时候，让0也尽量多

显然如果0有偶数个，可以不消耗任何1,让结果以1开始

如果以0结束，也同样可以不消耗任何1,让结果以1开始

…

那么就是如何分类是这个问题的关键，怎么尽量少的分化，覆盖所有情况。

比赛里做出的人不多，有些cf红名大佬都没出 XD

我在讨论时，从起始字符，终止字符，字符个数，连续字符个数多个方面去分类，想也不用想，没写出来,(之讨论到了部分情况)

题解

a结束

显然

如果前面的a偶数个，能不删除b变成 b*a+的形式

如果前面的a奇数个，能不删除b变成 b*a*的形式

那么我们其实要求的变成了，如何尽可能的少删除a

注意到因为完全不会删除b，所以不论b有多少个，它原本连接在一起就不会被拆开。

所以把连接在一起的b看作一个b，可以看作

(a+)b(a+)b(a+)b(a+)b(a+)b(a+) 的形式

那么我们一次删除a至少连接一次b，至多连接两次b。

选取一个b(a{2,})b 和 b(a+)b中的a进行删除能连接一次b

选取两个bab中的a进行删除能连接两次b

所以长度为1的a和长度为1的a先完成同时选择删除，最后处理剩余a

这样能做到总的操作次数最少 = a(len=1) / 2 + a(len=1)%2 + a(len>1) (不包括最后的a串)

例如 aaabababababaaaaaa ,a的连续串有4个1和1个3,所以删除次数 = 4/2 + 0 + 1 = 3, 剩余a的个数=原始个数-2x3

至此，对于a结束的情况可以解了

b 结束

abb 和 aabb 结果就很不一样，看着这些连局部性都没有的串，很难受

如果a是偶数个

那必定可以不损耗b，且损耗所有a

a是奇数个

现在的情况，奇数个a+结尾是b

继续讨论结尾

ab结尾

奇数个a，显然a删不完，那么这个ab结尾的b肯定无法移动到前面

对于b的个数，把字符串删来剩下一个a,可以不损耗b的情况得到b*ab

所以，前缀b最多是b的个数-1,也是可达到的。

这是可达也是最大可达的字符串，因为如果选了b，一定就变成个数-2,会比这个结果小

abb结尾

同上

我们可以得到 b*abb, 其中不会损耗任何b，前缀b的个数=b总个数-2

那我们任何选择b的操作都会导致b的个数 <= 总个数-2,

所以，这也是最大可达

bbb结尾

（这种情况，我没有在赛内讨论到方案）

你看 aaaaabbbbb,abaaaabbbb, 就很不一样

a+b+

显然，其实都没了翻转只有删除，那 ab+ 就是结果了

其它

a*b+a+b+

其中一定有ba

把它的b和末尾的b交换，一定能b少两个且以a结尾。(就是上面讨论过的情况)

从而 b的个数减2,以b开头是一个解

又字符串, 在不操作b的情况下，一定能变成 b+ab+，保留原始最后的a，这是能得到的最大的

也是比操作了b一次字典序小。（个数小于 b的个数减2）

所以，一定要操作且仅操作一次b。

答案一定是 b+a* 其中b的个数少两个

那么这种情况又是讨论，如何留下尽可能多的a

首先，操作b的时候一定选的是ba的b，因为其余情况，都无法让结尾变成a，而结尾不是a的情况如上，得不到更长的b的前缀。

注意到对于a结尾我们已经有了答案，最后一个b前面x个长为1的a和y个长大于1的a，那么x/2 + x%2 + y

我们直接定义，在处理之前的状态叫做预期答案，也定义为 x/2 + x%2 + y。

那么，那一次选择两个b的操作

.*b[(a+)b.*bb]b => .*[bbb.*b(a+)]

如果(a+) 的部分长是1，那么根据1个数的奇偶性，可能让预期答案减1或减少0

如果(a+) 的部分长度大于1, 那么让预期的答案减1

又如果先操作a，再操作b。

操作a时，产出和剩余预期的和为常量，且a的奇偶性不变

综上，存在b(a{2,}) 则换它的b

否则换ba的b

最后和1一样计算a的个数

代码

https://atcoder.jp/contests/arc113/submissions/20437840

#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-1;i>=a;i--)
#define pb push_back

ll t;

char s[200010];
char s1[200010];

int cnt[2] = {0,0};


int main(){
  cin>>t;
  while(t--){
    scanf("%s",s);
    int n = strlen(s);
    cnt[0] = 0;
    cnt[1] = 0;
    rep(i,0,n){
      cnt[s[i]-'a']++;
    }
    // all same
    if(cnt[1] == 0 || cnt[0] == 0){
      printf("%s\n",s);
      continue;
    }
    int a1 = 0; // a eq 1
    int ag1 = 0; // a greater than 1
    int cura = 0;
    per(i,0,n){
      if(s[i] == 'b'){
        per(j,-1,i){
          if(j >= 0 && s[j] == 'a'){
            cura++;
          }else{
            if(cura){
              if(cura == 1){
                a1 ++;
              }else{
                ag1 ++;
              }
              cura = 0;
            }
          }
        }
        break;
      }
    }
    // printf("[%d,%d]\n",a1,ag1);

    if(s[n-1] == 'a'){
      rep(i,0,cnt[1]){
        printf("b");
      }
      rep(i,0,cnt[0] - 2*(a1/2+a1%2+ag1)){
        printf("a");
      }
      printf("\n");
    }else if(cnt[0] % 2 == 0){
      rep(i,0,cnt[1]){
        printf("b");
      }
      printf("\n");
    }else if(s[n-2] == 'a'){ // even a and ends with ab
      rep(i,0,cnt[1]-1){
        printf("b");
      }
      printf("ab\n");
    }else if(s[n-3] == 'a'){ // even a and ends with abb
      rep(i,0,cnt[1]-2){
        printf("b");
      }
      printf("abb\n");
    }else{ // even a and ends with bbb
      ll la = 0;
      ll firstb = n;
      rep(i,0,n){
        if(s[i] == 'a'){
          la = max(la,i);
        }else{
          firstb = min(firstb,i);
        }
      }
      // a+b+
      if(firstb > la){
        printf("a");
        rep(i,0,cnt[1]){
          printf("b");
        }
        printf("\n");
      }else{ // .*b+a+b{3,}
        bool hasbaa = false;
        rep(i,0,n-2){
          if(s[i] == 'b' && s[i+1] == 'a' && s[i+2] == 'a'){
            hasbaa = true;
          }
        }
        if(hasbaa){
          rep(i,0,cnt[1]-2){
            printf("b");
          }
          if(ag1 > 0){
            rep(i,0,cnt[0] - 2*(a1/2+a1%2+ag1-1)){
              printf("a");
            }
          }else{
            rep(i,0,cnt[0] - 2*((a1-1)/2+(a1-1)%2)){
              printf("a");
            }
          }
          printf("\n");
        }else{ // a*(b+a)+b{3,}
          rep(i,0,cnt[1]-2){
            printf("b");
          }
          if(ag1 > 0){ // a{2,}(b+a)+b{3,}
            rep(i,0,cnt[0] - (a1/2)*2 - 2){
              printf("a");
            }
          }else{ // a?(b+a)+b{3,}
            printf("a");
          }
          printf("\n");
        }
      }
    }
  }
  return 0;
}

给长度N+1的整数序列 X, $X_0=0,X_i<X_{i+1}$

$N$个人, 第$i$个人会等概率出现在$[X_{i-1},X_{i}]$ 之间的实数位置

求 Exp(最近的两个人的距离) mod 998244353

$n \in [2, 20]$

$X_n\le 10^6$

1024mb

我的思路

exp + min, 第一个想的方向是 min-max容斥

但这这里感觉实际选择的位置互相影响，没有啥直接的想法

然后就是N=20,有想 bitmask或者 bitmask + meet-in-middle

这个问题是状态的最后一个人的位置是实数，不是整点

除非能得到一个关于最后一个位置的简单的函数，把“实数”的内容抛掉，不然的话实数是没法作为状态的定义域的部分的，状态的值域的部分

然后就是把点表示成 整数点+[0,1) 的值，这样可以先排除一下无效的大值

似乎也没有啥用

题解

$F(x) = P(X\ge x)=\int_{x}^{\infty} p(x) dx$

$E(x) = \int_0^{\infty} yp(y)dy = \int_0^{\infty} \int_0^yp(y)dxdy = \int_0^{\infty} \int_x^{\infty}p(y)dydx = \int_0^{\infty} F(x)dx$

$f(z)=$ 答案 $\ge z$的概率

考虑新的 N个区间$A_i=[x_i-(i-1)z,x_{i+1}-(i-1)z]$

那么需要找 $y_i$ 单调递增且属于对应区间

因为属于区间保证了 $y_i+(i-1)z$就对应了实际的选点

单调递增保证了$(y_{i+1}+iz)-(y_{i}+(i-1)z)=(y_{i+1}-y_{i})+z > z$

令$v =$上面区间的$2n$个端点从小到大排列

$dp[i][j][k] =$ 前$i$个点中, 和$i$在同一个区间的有$k$个点,且区间为$(v_j,v_{j+1}]$ 的概率

$f(z) = \sum dp[n][\forall][\forall]$

对于转移

考虑第$i+1$个点和第$i$不在一个区间

$dp[i+1][j][1] = \frac{|v_{j+1}-v_{j}|}{|A_{i+1}|} \sum_{j_0 < j, k=1\cdots i} dp[i][j_0][k], [v_j,v_{j+1}]\subset A_{i+1}$

考虑第$i+1$个点和第$i$在一个区间

注意到这是 $dp[i][j][k] \to dp[i+1][j][k+1]$的变化

那么变化的是 $[v_{j},v_{j+1}]$ 中点个数的变化,原来是$k$个有序,变为$k+1$个有序，也就是从$\frac{1}{k!}$变为$\frac{1}{(k+1)!}$ 所以还需要多乘上$\frac{1}{k+1}$， 而且需要最后k+1个都能放进这个区间且倒数第k+2个可以放出这个区间

因此对于给定$z$, 可以多项式时间计算出, 大概是$N^3$状态数和$N$的转移，也就是$O(N^4)$的时间复杂度的样子

然后对于不固定的$z$, 那么同样的方法, 端点序列是一个$a-bz$ 的形式，且 $a,b$是确定的

而 v中内部顺序变化最多$O(n^2)$次，所以枚举排序关系$O(n^2)$次,计算出关于$z$ 的多项式

$\mathrm{ans}=\int f(z) dz = \int \sum dp[n][\forall][\forall] dz$

计算所有影响v顺序的$z$分界线的 $\displaystyle \frac{x_{\mathrm{diff}}}{i_{\mathrm{diff}}}$

枚举 v顺序，对应的分界线区间$[z_l,z_r]$

计算关于$z$的概率函数注意到所有的dp过程都会乘上$\prod \frac{1}{|A_i|}$, 所以这个最后可以统一处理

去掉以后

$dp[i+1][j][1] += |v_{j+1}-v_{j}|\left( \sum_{j_0 < j, k=1\cdots i} dp[i][j_0][k]\right), [v_j,v_{j+1}]\subset A_{i+1}$

$dp[i+1][j][k+1] += \frac{|v_{j+1}-v_{j}|}{k+1}\left( dp[i][j][k]\right), [v_j,v_{j+1}]\subset A_{i+1}$

然后这里$v_{j+1}-v_j = b_j+k_jz$ 的替换

而上面的第二个转移可以发现

$\displaystyle dp[i+1][j][k+1] = \frac{|v_{j+1}-v_{j}|^k}{(k+1)!}\left( dp[i-k+1][j][1]\right), [v_j,v_{j+1}]\subset A_{i+1}$

$\displaystyle =\frac{|v_{j+1}-v_{j}|^{k+1} }{(k+1)!} \left( \sum_{j_0 < j} dp[i][j_0][\forall]\right), [v_j,v_{j+1}]\subset A_{i+1}$

即

$\displaystyle dp[i][j][k]=\frac{|v_{j+1}-v_{j}|^{k} }{k!} \left( \sum_{j_0 < j} dp[i-1][j_0][\forall]\right), [v_j,v_{j+1}]\subset A_{i+1}$

这里需要注意的是:

$k$的取值$\ge 1$，需要最后k个可以放入$[v_j,v_{j+1}]$
且倒数第$k+1$个要能放到之前，而根据dp转移关系，这一点是在 $[1] = ()$时保证的，所以前置的dp结果都保证了这一条

令 $\displaystyle g[i][j]=\left( \sum dp[i][j][\forall]\right)$

$\displaystyle \mathrm{ans}=\sum \int_{z_l}^{z_r} (\sum g[n][\forall] ) dz$, 其中$[z_l,z_r]$是钦定端点排序后对应的$z$的区间

$\displaystyle dp[i][j][k]=\frac{|v_{j+1}-v_{j}|^{k} }{k!} \sum g[i-1][<j], [v_j,v_{j+1}]\subset A_{i+1}$

$\displaystyle g[i][j]=dp[i][j][\forall]=\left(\sum_{k=1}^{k_{i,j,\max }}\frac{|v_{j+1}-v_{j}|^{k} }{k!} \right)\sum g[i-1][<j], [v_j,v_{j+1}]\subset A_{i+1}$
其中$k_{i,j,\max}=$ 从$i$向前最多多少连续个点都能够放进$[v_j,v_{j+1}]$

而多项式积分$\displaystyle \int_{l}^{r} \sum_{a_i}x^i dx = \displaystyle \sum \frac{a_i}{i+1}x^{i+1}|_l^{r}$

代码

https://atcoder.jp/contests/arc113/submissions/50545493

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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);)
ll read(){ll r;scanf("%lld",&r);return r;}
struct fra{ll a,b;}; // z的分割 a/b, a>0,b>0 1e6, 最简分数
bool operator <(const fra&x,const fra&y){return x.a*y.b<x.b*y.a;}
bool operator ==(const fra&x,const fra&y){return x.a==y.a and x.b==y.b;};
using linear=array<ll,2>; // {b,k}: bx^0+kx^1
linear operator-(const linear&x,const linear&y){return {x[0]-y[0],x[1]-y[1]};}
using poly=vector<mint>;
poly& operator+=(poly&p0,const poly&p1){ // 多项式加法
  if(p1.size() > p0.size()) p0.resize(p1.size());
  rep(i,0,size(p1)) p0[i]+=p1[i];
  return p0;
}
poly operator*(const poly&p0,const poly&p1){ return convolution(p0,p1); }

#define N 22
// mint dp[N][N*2][N];// [i][j][k] 前i个 和i同区间的有k个,它们在[vj..vj+1]这区间里 概率
poly g[N][N*2];// [i][j][k]=sum dp[i][j][forall] 前i个和i同区间的有任意个,它们在[vj..vj+1]这区间里z^k的系数
mint inv[N];
linear sr[N*2];
tuple<double,int,linear> fr[N*2]; // {新端点, idx +左 -右, xi-? z的0次1次系数}

int main() {
  int n=read();
  vector<int> x(n+1);
  rep(i,0,n+1) x[i]=read();
  rep(i,1,n+1) inv[i]=mint(i).inv();
  vector<fra> tp;
  auto addfrac=[&](int x,int y) { int g=gcd(x,y); tp.push_back({x/g,y/g}); };
  addfrac(0,1); // 0=0/1, 不用加无限点是因为 最右[maxz,\infity)的区间方案为0, 可以省略
  rep(i,0,n+1) rep(j,i+1,n+1) { // [xi-iz,x{i+1}-iz] [xj-jz,x{j+1}-jz]
    int dx=x[j]-x[i];
    int di=j-i;
    addfrac(dx,di); // 头对头，尾对尾
    if(di>1) addfrac(dx,di-1); // xi-iz, xj-(j-1)z
    addfrac(dx,di+1); // xi-{i-1}z, xj-jz
  }
  sort(begin(tp),end(tp),[&](const fra&a,const fra&b){return a < b;}); // 排序+去重
  tp.resize(unique(begin(tp),end(tp))-begin(tp));
  mint ans=0;
  vector<int>lb(n+1,0),rb(n+1,0); // lb[区间id]=左端点顺序idx,rb[区间id]=右端点顺序idx
  rep(i,1,size(tp)) { // tp[i-1]~tp[i] 之间的排序
    double sp=(1.0*tp[i-1].a/tp[i-1].b+1.0*tp[i].a/tp[i].b)/2; // 取区间中点 来完成排序, 也可以不用double通过双端点比较完成
    rep(j,1,n+1) { // 区间[x[j-1]-jz, x[j]-jz]的端点
      fr[j*2-1]={x[j-1]-j*sp, j,{x[j-1],-j}};
      fr[j*2-0]={x[j  ]-j*sp,-j,{x[j  ],-j}};
    }
    sort(fr+1,fr+n*2+1); // 排序所有端点
    rep(j,1,n*2+1) {
      int id=get<1>(fr[j]);
      if(id>0)lb[id]=j; // 左端点
      else rb[-id]=j;
    }
    rep(j,1,n*2) sr[j] = get<2>(fr[j+1])-get<2>(fr[j]); // 区间长度 = dx+di*z
    rep(j,0,n+1) rep(k,1,n*2+1) g[j][k] = {0}; // clear;
    g[0][0] = {1};
    //g[i][j]=(sum_{c=1..maxc}(a0+a1x)^c/c!) sum g[i-1][<j],maxc=i前最多连续?个坐标在tp[i-1..i]可选
    rep(j,1,n+1) {
      poly su = {0}; // sum g[i-1][<j]
      rep(k,1,n*2+1) { // 第j个放在 第k个端点区间
        su += g[j-1][k-1];
        poly tmp = su;
        auto [a0,a1] = sr[k]; // 区间长度的 0次系数 1次系数
        rep(l,j,n+1) {
          if(k<lb[l] or rb[l]<=k)break; // lb[l] <= k < rb[l]
          tmp = tmp * poly{a0*inv[l-j+1],a1*inv[l-j+1]}; // *(a0+a1x)/(l-j+1)
          g[l][k] += tmp; // g[l][k] += (a0+a1x)^c/c! (sum g[j-1][<k]), c=l-j+1
          assert((int)g[l][k].size() <= l+1);
        }
      }
    }
    poly su = vector<mint>(n+1,0); // su = sum g[n][<k]
    rep(k,1,n*2+1) su += g[n][k];

    mint li=mint(tp[i-1].a)/tp[i-1].b;
    mint ri=mint(tp[i].a)/tp[i].b;
    rep(k,0,n+1) ans += su[k]*(ri.pow(k+1)-li.pow(k+1))/(k+1); // \int \sum a_i x^i = \sum a_i/(i+1) x^{i+1}
  }
  rep(i,0,n) ans/=(x[i+1]-x[i]); // 统一处理分母
  printf("%d\n",ans.val());
  return 0;
}

Ref

https://atcoder.jp/contests/arc113/editorial/

总结

分类有点难，其实上面几种情况全都有推过，但是我在类型分化时加上了起始的字符，这样的题解看下来，是不太需要讨论起始字符的。但是在推的过程中不知道怎么排除。

第二是我分类的时候，奇偶的分类顺序比结束字符的高，又导致了过多的分类分叉 QAQ

然后我还有想转换（从情况某某+操作转换到情况某某），这样看来这题也不太需要转换

另外其实对于代码上做分类，不太怕重复，毕竟如果两个非类方式有重复，进任何一种都可以，怕的是漏掉了分类。

Ex:

这个区间缩小没想到太不应该了

这里对点排序而不是缩减处理得很好，因为缩减涉及到min/max操作，对于批量计算来说无法处理

连续分布函数的期望表达式还是不熟

然后就是 1次方程的顺序n^2个老生长谈的东西

然后就是关于v的多项式，其实有dp后面就相对显然，

稍微做一下状态压缩，

E

我的思路

题解

a结束

b 结束

如果a是偶数个

a是奇数个

ab结尾

abb结尾

bbb结尾

a+b+

其它

代码

F - Social Distance

我的思路

题解

代码

Ref

总结