学大伟业 2017 国庆 Day1

期望得分：100+100+20=220

实际得分：100+100+20=220

（好久没有期望==实际了，~\(≧▽≦)/~）

对于 a。。。。。。。。a

如果第1个a 后面出现的第1个b~z 是右端点，且在第2个a之前，那么有贡献

如果第2个a 前面出现的第1个b~z 是左端点，且在第1个a之后，那么有贡献

最后的贡献/2

#include<cstdio>

#include<cstring>

#define N 100001

using namespace std;

char s[N];

int LAST[],last[N],pre[N][],suf[N][];

bool w[N],c[];

int main()

{

    freopen("cross.in","r",stdin);

    freopen("cross.out","w",stdout);

    scanf("%s",s+);

    int len=strlen(s+),ans=,ch;

    for(int i=;i<=len;i++)

        for(int j=;j<;j++)

            if(s[i]-'a'==j) pre[i][j]=i;

            else pre[i][j]=pre[i-][j];

    for(int i=;i<;i++) suf[len][i]=len+;

    suf[len][s[len]-'a']=len;

    for(int i=len-;i;i--)

        for(int j=;j<;j++)

            if(s[i]-'a'==j) suf[i][j]=i;

            else suf[i][j]=suf[i+][j];

    for(int i=;i<=len;i++)

    {

        ch=s[i]-'a';

        c[ch]^=; w[i]=!c[ch];

        if(c[ch]) LAST[ch]=i;

        else last[i]=LAST[ch];

    }

    for(int i=;i<=len;i++)

        if(w[i])

        {

            for(int j=;j<;j++)

                if(j!=s[i]-'a')

                {

                    if(suf[last[i]][j]<i && w[suf[last[i]][j]]) ans++;

                    if(pre[i][j]>last[i] && !w[pre[i][j]]) ans++;

                }

        }

    printf("%d",ans>>);

}

dis[i][j] 表示到第i个点，用了j次传送的最快时间

堆优化的dijkstra

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 501

#define M 2001

int n,m,g,k;

int front[N],to[M<<],nxt[M<<],val[M<<],tot;

bool fly[M<<];

int DIS[N][];

struct node

{

    int tim,dis,num;

    bool operator < (node p) const

    {

        return dis>p.dis;

    }

}cur,nt;

priority_queue<node>q;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v,int w,bool fl)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w; fly[tot]=fl;

}

void init()

{

    read(n); read(m); read(g); read(k);

    int u,v,w;

    k=min(g,k);

    while(m--)

    {

        read(u); read(v); read(w);

        add(u,v,w,);

    }

    while(g--)

    {

        read(u); read(v); read(w);

        add(u,v,w,);

    }

}

void dijkstra()

{

    memset(DIS,,sizeof(DIS));

    cur.dis=; cur.num=; cur.tim=;

    DIS[][]=;

    q.push(cur);

    while(!q.empty())

    {

        cur=q.top(); q.pop();

        if(cur.num==n)

        {

            printf("%d",cur.dis);

            return;

        }

        if(DIS[cur.num][cur.tim]!=cur.dis) continue;

        for(int i=front[cur.num];i;i=nxt[i])

        {

            if(DIS[to[i]][cur.tim+fly[i]]<cur.dis+val[i]) continue;

            if(cur.tim+fly[i]>k) continue;

            DIS[to[i]][cur.tim+fly[i]]=cur.dis+val[i];

            nt.dis=cur.dis+val[i];

            nt.tim=cur.tim+fly[i];

            nt.num=to[i];

            q.push(nt);

        }

    }

    printf("-1");

}

int main()

{

    freopen("move.in","r",stdin);

    freopen("move.out","w",stdout);

    init();

    dijkstra();

    return ;

}

相当于把树分成许多块，每一个块的大小>=k，求分块方案数

树上背包

dp[i][j] 以i为根子树内，块的大小为j的方案数

g[j] 当前大小为j的块的方案数

cnt[i] 以i为根节点的块，大小>=k的方案数

假设当前正在合并u的子节点 v

v所在块如果本身就>=k，那么v可以不并入u，g[j]=cnt[v]*dp[u][j]

枚举已经与u合并的块的大小j

枚举v所在块的大小h

g[j+h]+=dp[x][j]*dp[v][h]

合并u和v，把g赋给dp

最后处理完u的时候更新cnt

注意师最后合并，这样可以使时间复杂度降到 n^2

相当于每对点只在LCA处有贡献

#include<cstdio>

#include<iostream>

using namespace std;

#define N 5001

#define mod 786433

int front[N],to[N<<],nxt[N<<],tot;

int siz[N],dp[N][N],g[N],cnt[N];

int k;

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;

}

void init()

{

    int n;

    read(n); read(k);

    int u,v;

    for(int i=;i<n;i++)

    {

        read(u); read(v);

        add(u,v);

    }

}

void dfs(int x,int y)

{

    siz[x]=;

    dp[x][]=;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=y)

        {

            dfs(to[i],x);

            for(int j=;j<=siz[x]+siz[to[i]];j++) g[j]=;

            for(int j=;j<=siz[x];j++) g[j]=1ll*cnt[to[i]]*dp[x][j]%mod;

            for(int j=;j<=siz[x];j++)

                for(int h=;h<=siz[to[i]];h++)

                    g[j+h]=(g[j+h]+1ll*dp[x][j]*dp[to[i]][h]%mod)%mod;

            for(int j=;j<=siz[x]+siz[to[i]];j++) dp[x][j]=g[j];

            siz[x]+=siz[to[i]];

        }

    for(int i=k;i<=siz[x];i++) cnt[x]+=dp[x][i],cnt[x]%=mod;

}

int main()

{

    freopen("cut.in","r",stdin);

    freopen("cut.out","w",stdout);

    init();

    dfs(,);

    int ans=;

    for(int i=k;i<=siz[];i++) ans+=dp[][i],ans%=mod;

    printf("%d",ans);

}

2^n 20分暴力

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

#define N 5001

int n,k;

int front[N],to[N<<],nxt[N<<],from[N<<],tot;

int ans,cnt;

bool use[N];

int siz[N];

void read(int &x)

{

    x=; char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar(); }

}

void add(int u,int v)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v;

}

void init()

{

    read(n); read(k);

    int u,v;

    for(int i=;i<n;i++)

    {

        read(u); read(v);

        add(u,v);

    }

}

void dfs2(int x,int y)

{

    cnt++;

    for(int i=front[x];i;i=nxt[i])

        if(to[i]!=y && use[i]) dfs2(to[i],x);

}

void judge()

{

    for(int i=;i<=n;i++)

    {

        cnt=;

        dfs2(i,);

        if(cnt<k) return;

    }

    ans++;

}

void dfs(int x)

{

    if(x==(n-)*+)

    {

        judge();

        return;

    }

    dfs(x+);

    use[x]=use[x+]=true; dfs(x+); use[x]=use[x+]=false;

}

int main()

{

    freopen("cut.in","r",stdin);

    freopen("cut.out","w",stdout);

    init();

    dfs();

    printf("%d",ans);

}

巴特西

学大伟业 2017 国庆 Day1

最新文章

热门文章