UOJ Logo kczno1的博客

博客

【UER #6】逃跑的简单做法

2018-07-11 17:36:33 By kczno1

这是$jhr$优化得到的.

首先把求方差转化为求$E(x)$和$E(x^2)$($x$表示某个方案经过的不同位置数,$E$表示期望)

定义$f(i,x,y)$表示第$i$天第一次到达$(x,y)$的概率,$g(i,x,y)$表示第$i$天到达$(x,y)$的概率.

$g$很好算,$f$用$g$容斥一下就可以算了.

$E(x)$只用对$f$求和就好了.

$x^2=2{x \choose 2}+x$,所以$E(x^2)$转化为求$E({x \choose 2})$,然后就转化为$\sum_{x,y} x,y$都被经过的概率.

定义$h(i,x,y)$表示第$i$天第一次到达了一个点$(a,b)$,且之前经过了$(a-x,b-y)$的所有情况的概率和.

答案就是对$h$求和.

怎么计算$h(i,x,y)$呢?

先考虑$\sum_{j < i,a,b} f(j,a,b) \times f(i-j,x,y)$

它多算的情况就是,在经过$(a,b)$之前就已经经过了$(a+x,b+y)$

再减去$\sum_{j < i} h(j,-x,-y) \times f(i-j,x,y)$就好了.

时间$O(n^4)$

代码http://uoj.ac/submission/265113

【UER #7】套路的暴力做法

2018-07-09 11:26:48 By kczno1

令$s_{r}(i)$表示题面中的$s(i,r)$

注意到,对于一个$r$,$s_{r}(i)$不会超过$\sqrt m$种

从左到右枚举$r$,线段树维护$s_{r}$,然后再在线段树上$dfs$计算以$r$右端点的答案,就是当一个区间的$s_{r}(i)$一样时直接$check$一下区间左端点然后返回.

具体怎么维护线段树,就是枚举到$i$的时候

先令$s_{i}=s_{i-1}$,然后对于每个$j$,$s_{i}(1..j)$都对$abs(a_{i}-a_{j})$取$min$

但实际上有可能更新的$j$只有$log(m)$个

因为考虑$a_{j}>a_{i}$的情况,假设所有可能的$j$从大到小是$j_{1..m}$,则有$2 (a_{j_{k+1}}-a_{i}) < a_{j_{k}}-a_{i}$.

时间$O(nlog^2)+O(n \sqrt m log \frac{n}{\sqrt m} ))$

后面这个东西虽然带$log$但常数比较小(把线段树换成平衡树好像就不带$log$了)

代码:http://uoj.ac/submission/264123

UTR2的题解怎么没了

2018-07-05 22:09:01 By kczno1

小C的字符串的简单做法

2018-07-03 23:42:30 By kczno1

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1825

好久之前的坑.今天想了一下,忽然发现了一个简单做法.

记两个串为$a,b$,长度为$n,m$

设$dp[i][j]$表示$a_{1..i}$和$b_{1..j}$的$lcs$

考虑从$1$到$m$枚举$h$,动态维护无视$b_{1..h}$的$dp$数组(也就是$dp[i][j]$表示$a_{1..i}$和$b_{h+1..j}$的$lcs$)

假如现在枚举到$h$,对于$h$这一列,第一个变化的$dp[i][h]$必定满足$a[i]==b[h]$,并且$dp[i..n][h]$全部会减$1$.

再依次考虑列$h+1,..m$的变化,可以发现每一列变化的都是一个后缀,并且不长于前一列.

所以枚举每一列,维护后缀长度即可.

现在唯一的问题就是判断一个点可以从哪里转移过来.

每次变化的转移边只有轮廓上那些,所以可以轻松维护.

时间$O(n^2)$

(然而被卡常了...不是很懂为什么$n^2$要出成$5000$)

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

template <typename T> void chmin(T&x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}
typedef long long s64;
typedef unsigned long long u64;
typedef unsigned int u32;
typedef pair<int,int> pii;
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
#define rep0(i,l,r) for(int i=l;i<r;++i)
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
#undef gc

const int N=5000+5,D=998244353;
bool fr[N][N][3];
char s1[N],s2[N];
int dp[N][N],dpn[N];

int main()
{
#ifdef kcz
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
#endif
    scanf("%s%s",s1+1,s2+1);
    int n=strlen(s1+1),m=strlen(s2+1);
    rep(i,1,n)
    rep(j,1,m)
    {
        int a=dp[i][j-1],b=dp[i-1][j-1]+(s1[i]==s2[j]),c=dp[i-1][j];
        dp[i][j]=max(max(a,b),c);
        fr[i][j][0]=a==dp[i][j];
        fr[i][j][1]=b==dp[i][j];
        fr[i][j][2]=c==dp[i][j];
    }
    rep(j,1,m)dpn[j]=dp[n][j];
    s64 ans=0;
    rep(h,1,m)
    {
        rep(j,h,m)ans=(ans*233+dpn[j])%D;
        int i=1;
        while(fr[i][h][0]||fr[i][h][2])++i;
        if(i>n)continue;
        rep(j,h+1,m)
        {
            if(!fr[i][j][1]&&!fr[i][j][2])fr[i][j][1]=fr[i][j][2]=1;
            else
            {
                fr[i][j][0]=0;
                while(++i,fr[i][j][2])fr[i][j][0]=fr[i][j][1]=0;
                if(i>n)break;
                fr[i][j][2]=1;
            }
            --dpn[j];
        }
    }
    cout<<ans;
}

【UTR #3】去月球 的可持久化线段树做法

2018-06-30 22:19:32 By kczno1

令$ans_{l}(r)$表示$[l,r]$的答案,$dy(l)$表示$\min r$满足$[l+1,r-1]$可以消除

当$dy(l)$不存在时,$ans_{l}(r)=ans_{l+1}(r)$

否则,当$r < dy(l)$时,$ans_{l}(r)=ans_{l+1}(r)$;当$r \ge dy(l)$时,$ans_{l}(r)=ans_{dy(l)+1}(r)+ r-l+1$

可持久化线段树即可.

时间$O((n+q)log_{2}n)$

代码:http://uoj.ac/submission/261655

kczno1 Avatar