JZSIM 3.5

Author Avatar
空気浮遊 2019年03月05日
  • 在其它设备中阅读本文章

没考完我先过来吐槽一波吧..

过程

虚假的构造题.jpg
虚假的字符串题.jpg
真正的字符串题.jpg

你家省选模拟是一道构造 + 两道字符串?

T1 First

挺傻逼的构造,签到题罢..

T2 Second

学到了打表是成功的一半,然后剩下就毛都推不出了...

估计八成是由字符串推出的一堆结论 +SA

T3 Third

兄啊你都本质不同了写明了是自动机吧...

你这让我这种字符串苦手选手怎么活呀...

查了下序列自动机是什么,又因为正在考试虚了,没敢继续看了


虽然还没出成绩但先估个 164 吧... 按照惯例会被狠狠的打脸啊。

如果 T3 确实是序列自动机那我顶格也就 164 了差不多。当然如果是真正的省选的话我应该还会坚持治疗。

然后我猜一下:
你醒啦?大众分 290,你垫底啦.jpg

或者:
你醒啦?你爆零啦.jpg


还好,164,估的稳,排名不在前也不在后,舒服了。

更正

T2 Second

反向建 SAM,然后利用 parent 树每个树的 LCA 都是每个后缀的公共前缀来 dp。

即从矩阵的方向考虑,最优的合并过程。

涉及到重要的结论:如果有 $\sum k_i=1$,且要使 $\max \limits_i k_iF_i$ 最小,则一定是 $k_iF_i$ 全部相等。因此有 $k_iF_i$ 之比等于一,因此有 $k_i$ 之比等于 $\frac{1}{F_i}$ 之比。

因此我们在合并数个矩阵的时候,要使 $X_iF_i+(1-X_i)len$ 最小,则 $X_i$ 必须为 $F_i-len$ 的反比。

要给 parent 树补全没有被补全的后缀。

确实会有 $F_i-len=0$ 的情况,但反正能够被奇怪的纳入程序的考虑范围之内。

cty 的程序在下暂时还没法理解...

题神人傻.jpg

// Code by ajcxsu
// Problem: second

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
double f[N<<1];
int h[N<<1], nexp[N<<1], to[N<<1], out[N<<1], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++, out[a]++; }

struct Node {
    int len, fa, ch[26];
} nd[N<<1];
int idx=1, lst=1, siz[N<<1];

void add(int c) {
    int p=lst, np=lst=++idx; siz[idx]=1;
    nd[np].len=nd[p].len+1;
    for(; p && !nd[p].ch[c]; p=nd[p].fa) nd[p].ch[c]=np;
    if(!p) nd[np].fa=1;
    else {
        int q=nd[p].ch[c];
        if(nd[q].len==nd[p].len+1) nd[np].fa=q;
        else {
            int nq=++idx; nd[nq]=nd[q];
            nd[nq].len=nd[p].len+1, nd[q].fa=nd[np].fa=nq;
            for(; p && nd[p].ch[c]==q; p=nd[p].fa) nd[p].ch[c]=nq;
        }
    } 
}

char ch[N];
void dfs(int x) {
    if(!out[x]) { f[x]=nd[x].len; return; }
    double ret=0.0, tot=0.0;
    for(int u=h[x];u;u=nexp[u])
        dfs(to[u]);
    for(int u=h[x];u;u=nexp[u]) tot+=1.0/(f[to[u]]-nd[x].len);
    for(int u=h[x];u;u=nexp[u]) ret=max(ret, 1.0/tot+nd[x].len);
    f[x]=ret;
}
int main() {
    #ifndef LOCAL
    freopen("second.in","r",stdin);
    freopen("second.out","w",stdout);
    #endif
    scanf("%s", ch);
    int n=strlen(ch);
    reverse(ch, ch+n);
    for(int i=0; i<n; i++) add(ch[i]-'a');
    int nidx=idx;
    for(int i=2; i<=nidx; i++)
        ins(nd[i].fa, i);
    for(int i=2; i<=nidx; i++)
        if(siz[i] && out[i]) {
            ins(i, ++idx);
            nd[idx].len=nd[i].len;
        }
    dfs(1);
    printf("%.6lf", f[1]);
    return 0;
}

T3 Third

朴素的子序列 dp 方程状态:$f_{i,c}$ 为前 $i$ 个字符以 $c$ 结尾的本质不同子序列个数。那么如果该位有 $a_i$,则有 $f_{i,a_i}=\sum f_{i-1,j}$,否则直接等于上一个。以及以空字符结尾的子序列应该算一个。

发现可以矩乘优化。又发现对于一个矩阵,左乘或右乘转移矩阵可以做到 $O(m)$ 变换(因为转移矩阵比较特殊,可以特殊地处理),我们又已知任意转移矩阵的逆矩阵形式,所以就可以先处理一遍整体右乘,然后再逐步左乘逆矩阵,左方再补上右乘,然后将前后缀得出,排序离线处理询问。

题神人傻.jpg

// Code by ajcxsu
// Problem: third

#include<bits/stdc++.h>
#define MOD (998244353)
using namespace std;

template<typename T> inline void gn(T &x) {
    char ch=getchar(), pl=0; x=0;
    while(!isdigit(ch)) pl=(ch=='-'), ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int M=205, N=2e5+5;
int f[M][M], g[M][M], sum[M], tag[M], tmp[M];
int a[N];

struct Query { int b, c, d, id; } q[N];
int ans[N];
bool cmp(const Query &a, const Query &b) { return a.b<b.b; }

int main() {
    #ifndef LOCAL
    freopen("third.in","r",stdin);
    freopen("third.out","w",stdout);
    #endif
    int n, m, t;
    gn(n), gn(m), gn(t);
    for(int i=1; i<=n; i++) gn(a[i]);
    for(int i=0; i<t; i++) gn(q[i].b), gn(q[i].c), gn(q[i].d), q[i].id=i;
    sort(q, q+t, cmp);
    for(int i=0; i<=m; i++) f[i][i]=1, sum[i]=1;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            int ad=(sum[j]-f[j][a[i]]+MOD)%MOD;
            (f[j][a[i]]+=ad)%=MOD;
            (sum[j]+=ad)%=MOD;
        }
    }
    for(int i=0; i<=m; i++) sum[i]=1, g[i][i]=1;
    for(int i=1, k=0; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            int temp=tag[j];
            tag[j]=f[a[i]][j];
            f[a[i]][j]=(2ll*f[a[i]][j]-temp+MOD)%MOD;
        }
        while(q[k].b==i && k<t) {
            int c=q[k].c, d=q[k].d, res=0;
            for(int j=0; j<=m; j++) tmp[j]=((f[0][j]+f[c][j]-2ll*tag[j])%MOD+MOD)%MOD;
            for(int j=0; j<=m; j++) res=(res+1ll*tmp[j]*g[j][d]%MOD)%MOD;
            ans[q[k].id]=res;
            k++;
        }
        for(int j=0; j<=m; j++) {
            int ad=(sum[j]-g[j][a[i]]+MOD)%MOD;
            (g[j][a[i]]+=ad)%=MOD;
            (sum[j]+=ad)%=MOD;
        }
    }
    for(int i=0; i<t; i++) printf("%d\n", ans[i]);
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/jzsim-3-5.html
本文采用 CC BY 4.0 许可协议 进行许可。你可以自由分享和修改文章内容,只需注明出处即可。