[2017.4.7校内训练赛by hzwer]

时间：2023-03-09 00:24:47
[2017.4.7校内训练赛by hzwer]

来自FallDream的博客，未经允许，请勿转载，谢谢。

报警啦.......hzwer又出丧题虐人啦.....

4道ctsc...有一道前几天做过了，一道傻逼哈希还wa了十几次，勉强过了3题..我好菜啊都不会

A.[ctsc2014][bzoj3555]企鹅QQ

给定n个长度为l的字符串，两量不同，求有多少对字符串只有一个字符不同。  n<=300000  l<=200

这个很明显就是哈希啦......我写了几发都随便wa，然后怒而滚键盘才过了.map会T，用了个手写map

#include<iostream>

#include<cstdio>

#include<map>

#define orz 891172543311LL

#define mod 10000300000007LL

#define ditoly 10000002000009LL

#define lxh 23333

#define ll long long

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

map<ll,int> mp[];

int n,l,s,cnt=;

ll f[],g[];

ll ans=;

char st[];

int head[][lxh];

struct edge

{

    int ans;ll x;int next;

}e[]; 

void check(int num,ll hash)

{

    int d=hash%lxh;

    for(int i=head[num][d];i;i=e[i].next)

    if(e[i].x==hash){ans+=e[i].ans;++e[i].ans;return;}

    e[++cnt]=(edge){,hash,head[num][d]};head[num][d]=cnt;

}

int main()

{

    n=read();l=read();s=read();

    if(l<=) return *puts("");

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

    {

        scanf("%s",st+);

        for(int j=;j<=l;j++) f[j]=(1LL*f[j-]*11119LL+st[j])%orz;

        for(int j=l;j;j--) g[j]=(1LL*g[j+]*10537LL+st[j])%mod;

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

        {

            ll hash=(1701LL*f[j-]-107LL*g[j+])%ditoly;

            check(j,hash);

        }

    }

    printf("%lld\n",ans);

    return ;

}

B.[ctsc2007][bzoj1150]数据备份
前几天写的题...可以戳这里

#include<iostream>

#include<cstdio>

#include<queue>

#define INF 2000000000

#define MN 100000

#define pa pair<long long,int>

#define mp make_pair

using namespace std;

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}

    return x*f;

}

long long ans=;

int n,k,ne[MN+],la[MN+],a[MN+],len[MN+];

bool del[MN+];

priority_queue<pa,vector<pa>,greater<pa> > q;

int main()

{

    n=read();k=read();

    for(int i=;i<=n;i++)a[i]=read();

    for(int i=;i<=n+;i++)la[i+]=i,ne[i]=i+;

    la[]=;ne[n+]=;

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

        q.push(mp(len[i]=a[i]-a[i-],i));

    len[]=len[n+]=INF;

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

    {

        while(del[q.top().second])q.pop();

        ans+=q.top().first;int x=q.top().second;q.pop();

        int a=la[x],b=ne[x];

        del[a]=del[b]=;

        q.push(mp(len[x]=len[a]+len[b]-len[x],x));

        la[x]=la[a];ne[x]=ne[b];

        ne[la[a]]=x;la[ne[b]]=x;

    }

    cout<<ans;

    return ;

}

C.[Ctsc2015][bzoj4055]misc
题目好长啊...戳这里看题目

题解：我们用f[i][j]表示i到j的最短路径的宽度和，题目即求 $$ans[j]=\sum_{i\not=j\not=k}\frac{ai*ak*f(i,j)*f(j,k)}{f(i,k)}$$

整理一下得到    $$ans[j]=\sum_{i\not=j\not=k}ai*f(i,j)*\frac{ak*f(j,k)}{f(i,k)}$$

枚举点i，dij/spfa得到它的最短路括扑图，然后枚举点j，发现后面那一坨东西可以dp，令$g(x)={f(j,k)*ak/f(i,k)}$这家伙的转移可以通过乘以转移的那条边的宽度得到，所以这道题就做完了

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<cmath>

#define MN 1000

#define INF 2000000000000000000LL

#define ld long double

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int qx[MN+][MN+],top[MN+],tail;

ld h[MN+];

ld dis[MN+][MN+],ans[MN+],f[MN+][MN+];

ld g[MN+];

struct edge{int to,next;ld b,c;}e[];

int n,m,cnt=,head[MN+],a[MN+],in[MN+][MN+];

void ins(int f,int t,ld B,ld C)

{

    e[++cnt]=(edge){t,head[f],B,C};head[f]=cnt;

    e[++cnt]=(edge){f,head[t],B,C};head[t]=cnt;

}

queue<int> q;

void spfa(int from)

{

    for(int i=;i<=n;i++)dis[from][i]=INF;

    dis[from][from]=;

    q.push(from);

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            ld d=dis[from][u]+e[i].b;

            if(d<dis[from][e[i].to]) dis[from][e[i].to]=d,q.push(e[i].to);

        }

    }

}

void work(int from)

{

    qx[from][top[from]=]=from;tail=;

    f[from][from]=;

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

        for(int j=head[i];j;j=e[j].next)

            if(dis[from][i]+e[j].b==dis[from][e[j].to])

                in[from][e[j].to]++;

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

        if(!in[from][i]) q.push(i);

    while(top[from]>tail)

    {

        int u=qx[from][++tail];

        for(int j=head[u];j;j=e[j].next)

            if(dis[from][u]+e[j].b==dis[from][e[j].to])

            {

                if(!--in[from][e[j].to]) qx[from][++top[from]]=e[j].to;

                f[from][e[j].to]+=f[from][u]*e[j].c;

            }

    }

}

void dp(int from)

{

    memset(h,,sizeof(h));

    for(int j=top[from];j>;j--)

    {

        int x=qx[from][j];

        for(int i=head[x];i;i=e[i].next)

            if(dis[from][x]+e[i].b==dis[from][e[i].to])

            {

                int v=e[i].to;

                h[x]+=e[i].c*h[v];

            }

        ans[x]+=(ld)a[from]*f[from][x]*h[x];

        h[x]+=(ld)a[x]/f[from][x];

    }

}

int main()

{

    n=read();m=read();double B,C;

    for(int i=;i<=n;i++) a[i]=read();

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

    {

        int x=read(),y=read();scanf("%lf%lf",&B,&C);

        ins(x,y,(ld)B,(ld)C);

    }

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

        spfa(i),work(i),dp(i);

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

        printf("%.8lf\n",(double)ans[i]);

    return ;

}

D.[ctsc2015][bzoj4067]gender

题面实在是太神了，根本没法解释，戳这里。

这道题貌似会保证k条链都是并排的？问了善良的黄学长他说忘了qaq......标程没有处理，假装就是这样吧

题解：看到了那个计算答案的式子，发现$\lfloor ln(1+A)\rfloor$根本没法拆，但是k和n很小，A最大200，所以考虑暴力枚举它。

然后我们发现每一层其实都是独立的，也就是说我们可以把一层压到一起。同一层的答案我们考虑枚举状态，用最小割来计算。每个点与S连边表示改，与T连边表示不改，然后类似文理分科那样每个配对建出两个点分别和S,T相连，跑一遍最小割就能得出来。

所以我们得到了所有层所有状态的答案，接下来就可以状压dp了,f[i][j][k]表示前i层有j个不同，最后一层状态是k的最大获利，这个很好转移，最后更新答案。

然后发现对于同一个$\lfloor ln(1+A)\rfloor$，最小割的结果相同，只需要枚举一下A就行了    题目时限很宽，复杂度不好计算，就算是O(能过)呗。

(其实你可以发现用男女或者换不换都能表示状态，也就是说给定的初始性别可以是根本没用的)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#define INF 2000000000

#define ll long long

#define S 0

#define T 1001

#define MN 25000

using namespace std;

inline int read()

{

    int x =  , f = ; char ch = getchar();

    while(ch < '' || ch > ''){ if(ch == '-') f = -;  ch = getchar();}

    while(ch >= '' && ch <= ''){x = x *  + ch - '';ch = getchar();}

    return x * f;

}

int fa[T+],n,k,m,p,bel[T+],d[MN],q[MN],head[MN],cnt,top,c[MN],C[T+],ln[T+],old[T+];

struct edge{int to,next,w;}e[T*T+];

struct pair{int u,v,s;double d;}s[];

char st[MN];

ll g[][],f[][][],ans;

inline int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}

void ins(int f,int t,int w)

{

    e[++cnt]=(edge){t,head[f],w};head[f]=cnt;

    e[++cnt]=(edge){f,head[t],};head[t]=cnt;

}

int dfs(int x,int f)

{

    if(x==T)return f;

    int used=;

    for(int&i=c[x];i;i=e[i].next)

        if(e[i].w&&d[e[i].to]==d[x]+)

        {

            int w=dfs(e[i].to,min(f-used,e[i].w));

            used+=w;e[i].w-=w;e[i^].w+=w;

            if(used==f)return used;

        }

    return d[x]=-,used;

}

bool bfs()

{

    memset(d,,sizeof(d));int i,j;

    for(d[q[top=i=]=S]=;i<=top;i++)

        for(j=c[q[i]]=head[q[i]];j;j=e[j].next)

            if(e[j].w&&!d[e[j].to])

                d[q[++top]=e[j].to]=d[q[i]]+;

    return d[T];

}

void solve(int A,int t,int now)

{

    memset(head,,sizeof(head));cnt=;ll sum=;

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

        if(old[i]==t)

        {

            if(bel[i])

            {

                if((now&(<<bel[i]-))>)

                    ins(S,i,INF),sum-=C[i];

                else ins(i,T,INF);

            }

            else

                ins(i,T,C[i]);

        }

    int id=T+;

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

        if(old[s[i].u]==t&&old[s[i].v]==t)

        {

            int c1=A*s[i].s,c2=A*(int)(s[i].s*s[i].d);

            sum+=c1+c2;

            ++id;ins(id,T,c1);

            ins(s[i].u,id,INF);ins(s[i].v,id,INF);

            ++id;ins(S,id,c2);

            ins(id,s[i].u,INF);ins(id,s[i].v,INF);

        }

    while(bfs()) sum-=dfs(S,INF);

    g[t][now]=sum;

}

int calc(int x,int y)

{

    int sum=;

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

        if((x&j)!=(y&j)) ++sum;

    return sum;

}

void dp(int l)

{

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

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

            for(int x=;x<<<k;x++)

                f[i][j][x]=-INF;

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

        f[][][i]=max(f[][][i],g[][i]);

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

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

            for(int x=;x<(<<k);++x)if(f[i][j][x]!=-INF)

                for(int y=;y<(<<k);++y)

                {

                    int now=calc(x,y)+j;

                    f[i+][now][y]=max(f[i+][now][y],f[i][j][x]+g[i+][y]);

                }

}

int main()

{

    n=read();k=read();m=read();p=read();

    scanf("%s",st+);

    for(int i=;i<=m;i++) C[i]=read();

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

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

        {

            int x=read();

            bel[x]=i;old[x]=j;

        }

    for(int i=;i<=m;i++) fa[i]=i;

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

    {

        s[i].u=read();s[i].v=read();

        s[i].s=read();scanf("%lf",&s[i].d);

        fa[getfa(s[i].u)]=getfa(s[i].v);

    }

    for(int i=;i<=m;i++)if(old[i]) old[getfa(i)]=old[i];

    for(int i=;i<=m;i++)old[i]=old[getfa(i)];

    for(int i=;i<=m;i++)if(!old[i]) old[i]=;

    for(int i=;i<=;i++) ln[i]=(int)(log(i+)*);

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

    {

        if(ln[i]!=ln[i-])

        {

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

                for(int K=;K<(<<k);K++)

                    solve(ln[i],j,K);

            dp(i);

        }

        for(int j=;j<(<<k);j++) ans=max(ans,f[n][i][j]);

    }

    printf("%lld\n",ans);

    return ;

}

相关文章