过程

虚假的构造题.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;
}

网站*

加入讨论吧...