【NOIP2016TG】solution

传送门：https://www.luogu.org/problem/lists?name=&orderitem=pid&tag=83%7C33

D1T1(toys)

题意：有n个小人，给你M条指令，每条指令可顺可逆(时针)，问你操作后的位置在哪。

解题思路：裸模拟即可。

#include<stdio.h>

using namespace std;

#define MN 100005

char a[MN][];

int n,m;

bool b[MN];

inline int in(){

    int x=;char ch=getchar();

    while(ch<''||ch>'') ch=getchar();

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

    return x;

}

int main(){

    n=in();m=in();

    for (int i=; i<n; ++i){b[i]=in();scanf("%s",a[i]);}

    b[]=in();scanf("%s",a[]);

    int nt=;

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

        int x=(in()^b[nt])?:-,k=in();nt+=k*x;

        if (nt<) nt+=*n;nt%=n;

    }

    puts(a[nt]);

}

D1T2(running)

大丧题，解题思路已经存在博客中了，这里放一下传送门，顺便贴个代码。

传送门：http://www.cnblogs.com/Melacau/p/NOIP2016_running.html

贴代码：

#include<stdio.h>

#define MN 300005

#define nt edge[i].to

struct zxy{int to,next;}edge[MN*];//链表（把多个链表都塞进去了)

int cnt,h[MN],q[MN],adh1[MN],deh1[MN],adh2[MN],deh2[MN];//各链表表头

int qans[MN],tim[MN],deep[MN],n,m,chafen[MN*],fa[MN],ans[MN],x[MN],y[MN];

bool vis[MN];

inline void ins(int *h,int x,int y){edge[++cnt].next=h[x],edge[cnt].to=y,h[x]=cnt;}//构造链表

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

inline int in(){

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

    while(ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

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

    return x*f;

}

inline void tjlca(int x,int d){

    deep[x]=d;vis[x]=;

    for (register int i=h[x]; i; i=edge[i].next)

        if (!vis[nt])tjlca(nt,d+),fa[nt]=x;

    for (register int i=q[x]; i; i=edge[i].next)

        if (qans[nt]) qans[nt]=getfa(qans[nt]);

        else qans[nt]=x;

}//tarjan算法求LCA

inline void dfs1(int u){

    vis[u]=;ans[u]-=chafen[deep[u]-tim[u]];

    for (register int i=h[u]; i; i=edge[i].next) if (vis[nt]) dfs1(nt);

    for (register int i=adh1[u]; i; i=edge[i].next) ++chafen[nt];

    ans[u]+=chafen[deep[u]-tim[u]];

    for (register int i=deh1[u]; i; i=edge[i].next) --chafen[nt];

}//dfs处理S->f的

inline void dfs2(int u){

    vis[u]=;ans[u]-=chafen[deep[u]+tim[u]];

    for (register int i=h[u]; i; i=edge[i].next) if (!vis[nt]) dfs2(nt);

    for (register int i=adh2[u]; i; i=edge[i].next) ++chafen[nt];

    ans[u]+=chafen[deep[u]+tim[u]];

    for (register int i=deh2[u]; i; i=edge[i].next) --chafen[nt];

}//dfs处理f->T的

void read(){

    n=in(),m=in();int u,v;

    for (int i=; i<n; ++i) u=in(),v=in(),ins(h,u,v),ins(h,v,u);

    for (register int i=; i<=n; ++i) tim[i]=in()-MN;//为了防止减法出现负数，所以我们要这么做。

    for (register int i=; i<=m; ++i) x[i]=in(),y[i]=in(),ins(q,x[i],i),ins(q,y[i],i);

}//输入

void init(){

    tjlca(,);

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

        int f=qans[i],u=x[i],v=y[i];

        if (f==v) ins(adh2,u,deep[u]+MN),ins(deh2,v,deep[u]+MN);

        else{

            if (f==u) ins(adh1,v,deep[u]+MN),ins(deh1,u,deep[u]+MN);

            else{

                ins(adh2,u,deep[u]+MN);

                ins(deh2,f,deep[u]+MN);

                ins(adh1,v,(deep[f]<<)-deep[u]+MN);

                ins(deh1,f,(deep[f]<<)-deep[u]+MN);

                if(deep[f]==deep[u]-tim[f]-MN) --ans[f];

            }

        }

    }

}//处理差分位置

void solve(){

    dfs1();//进行第一次遍历统计答案

    for (register int i=; i<=n; ++i) tim[i]+=MN<<;//这个处理很关键！

    dfs2();

    for (register int i=; i<n; ++i) printf("%d ",ans[i]); printf("%d",ans[n]);

}

int main(){

    read();

    init();

    solve();

}

D1T3(classroom)

题意：给你V个点，你一共要执行N个阶段，每个阶段可能在任意2个点上进行，不同点的概率不同，求执行完所有阶段的期望。

解题思路：floyd预处理最短路，然后跑期望DP。(注意精度控制）

#include <stdio.h>

#include <string.h>

#define min(a,b) (a<b?a:b)

#define inf 1e9

#define MN 2001

#define MV 301

using namespace std;

int n,m,v,e,cnt,dis[MV][MV],c[MN],d[MN];

double qw[MN],ans=inf,f[MN][MN][];

inline int in(){

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

    while(c<''||c>'') f=c=='-'?-:,c=getchar();

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

    return x*f;

}

void init(){

    n=in(),m=in(),v=in(),e=in();

    for (int i=; i<=n; ++i) c[i]=in();

    for (register int i=; i<=n; ++i) d[i]=in();

    for (register int i=; i<=n; ++i) scanf("%lf",&qw[i]);

    for(register int i=; i<=v; ++i)

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

            dis[i][j]=inf;

            if(!(i^j))dis[i][j]=;

        }

    for (register int i=; i<=e; ++i){register int x=in(),y=in(),c=in();dis[x][y]=dis[y][x]=min(dis[x][y],c);}

}

void floyd(){

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

        for (register int i=; i<=v; ++i)

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

                if (i^j&&i^k&&j^k)

                    if(dis[i][j]>dis[i][k]+dis[k][j])

                        dis[i][j]=dis[i][k]+dis[k][j];

}

void dp(){

    if (n==) {puts("0.00");return;}

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

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

        for (register int j=; j<=min(i,m); ++j){

            f[i][j][]=f[i][j][]=inf;

            if(i^j){

                if((i-)^j) f[i][j][]=min(f[i][j][],f[i-][j][]+dis[c[i-]][c[i]]);

                if(j) f[i][j][]=min(f[i][j][],f[i-][j][]+qw[i-]*dis[d[i-]][c[i]]+(-qw[i-])*dis[c[i-]][c[i]]);

                if (!(i^n)) ans=min(ans,f[i][j][]);

            }

            if(j){

                if(j>) f[i][j][]=f[i-][j-][]+qw[i-]*qw[i]*dis[d[i-]][d[i]]+qw[i-]*(-qw[i])*dis[d[i-]][c[i]]+(-qw[i-])*qw[i]*dis[c[i-]][d[i]]+(-qw[i-])*(-qw[i])*dis[c[i-]][c[i]];

                if(i^j) f[i][j][]=min(f[i][j][],f[i-][j-][]+qw[i]*dis[c[i-]][d[i]]+(-qw[i])*dis[c[i-]][c[i]]);

                if (!(i^n)) ans=min(ans,f[i][j][]);

            }

        }

    printf("%.2lf",ans);

}

int main(){init();floyd();dp();return ;}

D2T1(problem)

题意：自己看题目。

解题思路：杨辉三角形递推预处理即可，注意对k取余。

#include<stdio.h>

#define max(a,b) (a>b?a:b)

int t,k,n[],m[],mn,f[],ans[];

inline int in(){

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

    while(c<''||c>'') f=c=='-'?-:,c=getchar();

    while(c>=''&&c<='') x=x*+c-,c=getchar();

    return x*f;

}

inline int doit(int n,int m){return n*(n+)/+m;}

void init(){

    t=in(),k=in();

    for (register int i=; i<=t; ++i){n[i]=in();m[i]=in();mn=max(n[i],mn);}

    for (register int i=; i<=mn; ++i) f[doit(i,)]=;

    for (register int i=; i<=mn; ++i)

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

            if(i^j){

                ans[doit(i,j)]=ans[doit(i-,j)]+ans[doit(i,j-)]-ans[doit(i-,j-)];

                f[doit(i,j)]=(f[doit(i-,j-)]+f[doit(i-,j)])%k;

                if (!(f[doit(i,j)]%k)) ans[doit(i,j)]++;

            }

            else{

                ans[doit(i,j)]=ans[doit(i,j-)];

                f[doit(i,j)]=f[doit(i-,j-)];

                if (!(f[doit(i,j)]%k)) ans[doit(i,j)]++;

            }

}

void solve(){

    for (register int i=; i<=t; ++i)

        if (n[i]<m[i]) printf("%d\n",ans[doit(n[i],n[i])]);

        else printf("%d\n",ans[doit(n[i],m[i])]);

}

int main(){init();solve();return ;}

D2T2(earthworm)

题意：就是你每次会选一堆东西中最长的出来，然后切成2部分再扔回去，叫你模拟出这个过程。

解题思路：正常的想法是扔个堆，然后按题意搞，时间会T(\(O((n+m)\lg (n+m) )\))。容易发现切出来的东西其实是有单调性的= =，然后就可以用3个队列(1个初始队列，2个切出来的队列）愉快的优化了，时间效率是\(O(n \lg n+m ) \)

/*代码在luogu上T了1个点。。。估计评测机太慢= =，BZOJ上过了，就假装没问题吧。*/

#include <stdio.h>

#include <algorithm>

#include <math.h>

#include <iostream>

#define MN 100005

#define MM 7000005

#define ll long long

#define inf 0x7fffffffffffffffLL

#define max(a,b) (a>b?a:b)

using namespace std;

int h[],t[],m,tt,dl;

ll que[][MN+MM],q,u,v;

inline int in(){

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

    while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();

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

    return x*f;

}

inline ll get_top(){

    ll ma=-inf;dl=-;

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

        if (h[i]<=t[i]&&que[i][h[i]]>ma) ma=que[i][h[i]],dl=i;

    if (dl!=-) ++h[dl];return ma;

}

void init(){

    t[]=in(),m=in(),q=in(),u=in(),v=in(),tt=in();

    for (int i=; i<=t[]; ++i) que[][i]=in();

    sort(que[]+,que[]++t[],greater<int>());

    h[]=h[]=h[]=;

}

void solve(){

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

        ll w=get_top()+(i-)*q;

        if (i%tt==) if (i/tt==) printf("%lld",w);

                    else printf("% lld",w);

        que[][++t[]]=w*u/v-i*q;

        que[][++t[]]=w-(w*u/v)-i*q;

    }putchar('\n');

    for (register int i=; ; ++i){

        ll w=get_top()+m*q;

        if (dl==-) break;

        if (i%tt==) if (i/tt==) printf("%lld",w);else printf("% lld",w);

    }

}

int main(){init();solve();return ;}

D2T3(angrybirds)

题意：给你n个点，你需要用最少的过原点的抛物线将这些点覆盖，求最少的抛物线数。

解题思路：首先，3点定抛物线，因为过原点，所以是2点定抛物线，然后暴力算任意2点连的抛物线，接着在此基础上O(n)算出这条抛物线直接经过了多少个点，最后根据这个跑一次状压DP即可。

#include <stdio.h>

#include <string.h>

#define eps 1e-8

#define abs(x) (x<0?(-1)*(x):x)

#define MN 18

double x[MN],y[MN];

int f[MN][MN],dp[<<MN],n,m;

inline void init(){

    scanf("%d%*d",&n);

    for (register int i=; i<n; ++i) scanf("%lf%lf",&x[i],&y[i]),y[i]/=x[i];

    memset(f,,sizeof(f));

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

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

            if (i^j){

                register double a=(y[i]-y[j])/(x[i]-x[j]); if (a>=) continue;

                register double b=(x[i]*y[j]-x[j]*y[i])/(x[i]-x[j]);

                for (register int k=n-; k+; --k)

                    f[i][j]=(f[i][j]<<)+(abs(a*x[k]+b-y[k])<eps);

            }

}

inline void solve(){

    memset(dp,0x3f,sizeof(dp));dp[]=;

    for (register int i=; i<(<<n)-; ++i){

        register int j=;for (; i&(<<j); ++j);

        if (dp[i]+<dp[i|(<<j)]) dp[i|(<<j)]=dp[i]+;

        for (register int k=; k<n; ++k)

            if (dp[i]+<dp[i|f[j][k]])    dp[i|f[j][k]]=dp[i]+;

    }

    printf("%d\n",dp[(<<n)-]);

}

int main(){int T;scanf("%d",&T);while(T--) init(),solve();return ;}

巴特西

【NOIP2016TG】solution

最新文章

热门文章