NOIP2016提高组 解题报告

D1

T1 玩具谜题

 1 //朝向内的人的向左为加，向右为减；朝向内的人则相反
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 struct node{
 6     int dir;
 7     char name[15];
 8 }peo[100001];
 9 int n,m,now;
10 inline int qread()
11 {
12     int x=0,j=1;
13     char ch=getchar();
14     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
15     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
16     return x*j;
17 }
18 int main()
19 {
20     freopen("toy.in","r",stdin);
21     freopen("toy.ans","w",stdout);
22     scanf("%d%d",&n,&m);
23     for(int i=0;i<=n-1;i++)
24     {
25         peo[i].dir=qread();
26         scanf("%s",peo[i].name);
27     }
28     int dir,step;
29     for(int i=1;i<=m;i++)
30     {
31         dir=qread();step=qread();
32         int t=peo[now].dir+dir;
33         if(t%2==0)now=(now-step+n)%n;
34         else now=(now+step)%n;
35     }
36     cout<<peo[now].name;
37     fclose(stdin);fclose(stdout);
38     return 0;
39 }
View Code

T2 天天爱跑步

非常懵的一道题

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 using namespace std;
  5 const int N=300401;
  6 struct Person{
  7     int s,t,lca;
  8 }peo[N];
  9 struct node{
 10     int v,nxt;
 11 }e[N<<1];
 12 int n,m,sz,tot,cnt;
 13 int fat[N],son[N],deep[N],bl[N],id[N],ans[N];
 14 int in[N],out[N],w[N];
 15 //deep表示节点的深度，w表示观察者的出现时间 
 16 int head[N];
 17 int root[N*3],lc[N*25],rc[N*25],sum[N*25];
 18 void Insert(int u,int v)
 19 {
 20     e[++cnt].v=v;
 21     e[cnt].nxt=head[u];
 22     head[u]=cnt;
 23 }
 24 void dfs1(int now)
 25 {
 26     son[now]++;
 27     for(int i=head[now];i;i=e[i].nxt)
 28     {
 29         if(e[i].v==fat[now])continue;
 30         deep[e[i].v]=deep[now]+1;
 31         fat[e[i].v]=now;
 32         dfs1(e[i].v);
 33         son[now]+=son[e[i].v];
 34     }
 35 }
 36 void dfs2(int now,int chain)
 37 {
 38     id[now]=++sz;
 39     in[now]=sz;
 40     bl[now]=chain;
 41     int y=0;
 42     for(int i=head[now];i;i=e[i].nxt)
 43     {
 44         if(e[i].v==fat[now])continue;
 45         if(son[e[i].v]>son[y])y=e[i].v;
 46     }
 47     if(!y) 
 48     {
 49         out[now]=sz;
 50         return;
 51     }
 52     dfs2(y,chain);
 53     for(int i=head[now];i;i=e[i].nxt)
 54     {
 55         if(e[i].v==fat[now] || e[i].v==y)continue;
 56         dfs2(e[i].v,e[i].v);
 57      }
 58      out[now]=sz;
 59 }
 60 int getlca(int u,int v)
 61 {
 62     while(bl[u]!=bl[v])
 63     {
 64         if(deep[bl[u]]<deep[bl[v]])swap(u,v);
 65         u=fat[bl[u]];
 66     }
 67     return deep[u]<deep[v]?u:v;
 68 }
 69 void modify(int &now,int l,int r,int pos,int w)
 70 {
 71     if(!pos)return;
 72     if(!now)now=++tot;
 73     sum[now]+=w;
 74     if(l==r)return;
 75     int mid=l+r>>1;
 76     if(pos<=mid)modify(lc[now],l,mid,pos,w);
 77     else modify(rc[now],mid+1,r,pos,w);
 78 }
 79 int query(int now,int l,int r,int nowl,int nowr)
 80 {
 81     if(!now)return 0;
 82     if(l==nowl && r==nowr)return sum[now];
 83     int mid=l+r>>1;
 84     if(nowr<=mid)return query(lc[now],l,mid,nowl,nowr);
 85     else if(nowl>mid)return query(rc[now],mid+1,r,nowl,nowr);
 86     else return query(lc[now],l,mid,nowl,mid)+query(rc[now],mid+1,r,mid+1,nowr);
 87 }
 88 void clear()
 89 {
 90     tot=0;
 91     memset(lc,0,sizeof(lc));
 92     memset(rc,0,sizeof(rc));
 93     memset(sum,0,sizeof(sum));
 94     memset(root,0,sizeof(root));
 95 }
 96 int main()
 97 {
 98     scanf("%d%d",&n,&m);
 99     int u,v;
100     for(int i=1;i<n;i++)
101     {
102         scanf("%d%d",&u,&v);
103         Insert(u,v);Insert(v,u);
104     }
105     for(int i=1;i<=n;i++)
106         scanf("%d",&w[i]);
107     for(int i=1;i<=m;i++)
108         scanf("%d%d",&peo[i].s,&peo[i].t);
109     dfs1(1);
110     dfs2(1,0);
111     for(int i=1;i<=m;i++)
112         peo[i].lca=getlca(peo[i].s,peo[i].t);
113     int now;
114     for(int i=1;i<=m;i++)
115     {
116         now=deep[peo[i].s];
117         modify(root[now],1,n,id[peo[i].s],1);
118         modify(root[now],1,n,id[fat[peo[i].lca]],-1);
119     }
120     for(int i=1;i<=n;i++)
121         ans[i]=query(root[deep[i]+w[i]],1,n,in[i],out[i]);
122     clear();
123     for(int i=1;i<=m;i++)
124     {
125         now=deep[peo[i].s]-deep[peo[i].lca]*2+n*2;
126         modify(root[now],1,n,id[peo[i].t],1);
127         modify(root[now],1,n,id[peo[i].lca],-1);
128     }
129     for(int i=1;i<=n;i++)
130         ans[i]+=query(root[w[i]-deep[i]+n*2],1,n,in[i],out[i]);
131     for(int i=1;i<=n;i++)
132         printf("%d ",ans[i]);
133     return 0;
134 }
View Code

T3 换教室

Floyd+期望dp
 1 /*1.当前的课不换的情况:
 2 (1)上一节课也没换;
 3 (2)上一节课换了----成功or不成功;
 4 2.当前的课换的情况:
 5 (1)当前课成功换了:
 6 a.上一节课换了----上一节课成功or不成功;
 7 b.上一节课没换;
 8 (2)当前的课换了失败:
 9 a.上一节课换了----上一节课成功or不成功;
10 b.上一节课没换*/
11 #include<iostream>
12 #include<cstdio>
13 #include<cstring>
14 using namespace std;
15 const int N=2001;
16 const int INF=1e9+7;
17 int n,m,v,e;
18 int c[N],d[N],dis[301][301];
19 double k[N],f[N][N][2];
20 //f[i][j][k]表示当前在第i个时间段,申请了j个教室,k==0表示申请不通过,k==1表示申请通过,最小耗费体力的期望值 
21 inline int qread()
22 {
23     int x=0,j=1;
24     char ch=getchar();
25     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
26     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
27     return x*j;
28 }
29 void init()
30 {
31     for(int i=0;i<301;i++)
32         for(int j=0;j<301;j++)
33             if(i==j)
34                 dis[i][j]=0;
35             else dis[i][j]=INF;
36     for (int i=0;i<2001;i++)
37         for (int j=0;j<2001;j++)
38             f[i][j][0]=f[i][j][1]=INF;
39     f[1][0][0]=0;
40     f[1][1][1]=0;
41 }
42 void floyd()
43 {
44     for(int k=1;k<=v;k++)
45         for(int i=1;i<=v;i++)
46             for(int j=1;j<=v;j++)
47                 if(dis[i][j]>dis[i][k]+dis[k][j])
48                     dis[i][j]=dis[i][k]+dis[k][j];
49 }
50 int main()
51 {
52     freopen("classroom.in","r",stdin);
53     freopen("classroom.ans","w",stdout);
54     init();
55     scanf("%d%d%d%d",&n,&m,&v,&e);
56     for(int i=1;i<=n;i++)
57         c[i]=qread();
58     for(int i=1;i<=n;i++)
59         d[i]=qread();
60     for(int i=1;i<=n;i++)
61         scanf("%lf",&k[i]);
62     for(int i=1;i<=e;i++)
63     {
64         int u=qread(),v=qread(),w=qread();
65         if(w<dis[u][v])
66             dis[u][v]=dis[v][u]=w;
67     }
68     floyd();
69     for(int i=2;i<=n;i++)
70     {
71         f[i][0][0]=f[i-1][0][0]+dis[c[i-1]][c[i]];
72         for(int j=1;j<=min(i,m);j++)
73         {
74             f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]],
75                 f[i-1][j][1]+(1-k[i-1])*dis[c[i-1]][c[i]]+k[i-1]*dis[d[i-1]][c[i]]);
76             f[i][j][1]=min(f[i-1][j-1][0]+k[i]*dis[c[i-1]][d[i]]+(1-k[i])*dis[c[i-1]][c[i]],
77                 f[i-1][j-1][1]+k[i-1]*k[i]*dis[d[i-1]][d[i]]+(1-k[i-1])*k[i]*dis[c[i-1]][d[i]]
78                 +k[i-1]*(1-k[i])*dis[d[i-1]][c[i]]+(1-k[i-1])*(1-k[i])*dis[c[i-1]][c[i]]);
79         }
80     }
81     double ans=f[n][0][0];
82     for(int i=1;i<=m;i++)
83         ans=min(ans,min(f[n][i][0],f[n][i][1]));
84     printf("%.2lf
",ans);
85     fclose(stdin);fclose(stdout);
86     return 0;
87 }
View Code

D2

T1 组合数问题

先写几组小数据发现是杨辉三角，那么与处理处杨辉三角的值，再用矩阵前缀和维护答案，最后O(1)查询答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,m,t,k,tot;
 5 int f[2011][2011],ans[2017][2017];
 6 inline int qread()
 7 {
 8     int x=0,j=1;
 9     char ch=getchar();
10     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*j;
13 }
14 int main()
15 {
16 //    freopen("problem.in","r",stdin);
17 //    freopen("problem.out","w",stdout);
18     scanf("%d%d",&t,&k);
19     f[1][1]=1;
20     for(int i=2;i<=2000;i++)
21         for(int j=1;j<=i;j++)
22             f[i][j]=(f[i-1][j-1]+f[i-1][j])%k;
23     for(int i=1;i<=2000;i++)
24     {
25         for(int j=1;j<i;j++)
26             ans[i][j]=ans[i][j-1]+ans[i-1][j]-ans[i-1][j-1]+(f[i][j]==0);
27         ans[i][i]=ans[i][i-1];
28     }
29     while(t--)
30     {
31         n=qread();m=qread();
32         if(m>n)m=n;
33         printf("%d
",ans[n+1][m+1]);
34     }
35     fclose(stdin);fclose(stdout);
36     return 0;
37 }
View Code

T2 蚯蚓

 1 /*
 2 搞三个队列 
 3 将蚯蚓从大到小放到第一个队列里 
 4 每一次砍3个队列中队首最大的蚯蚓 
 5 然后计算出来和之后分别将这两个蚯蚓放到第2个和第3个队列里 
 6 可以发现这样的话这三个队列都是分别单调的 
 7 由于每一次其余的蚯蚓都要+tot，那么就将新得到的两个蚯蚓-tot之后再加入队列就可以了 
 8 */
 9 #include<iostream>
10 #include<cstdio>
11 #include<cmath>
12 #include<algorithm>
13 using namespace std;
14 const int INF=0x7fffffff;
15 int n,m,tot,u,v,t,add,k,now;
16 long long a[100001],q[4][10000005],head[4],tail[4];
17 inline int qread()
18 {
19     int x=0,j=1;
20     char ch=getchar();
21     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
22     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
23     return x*j;
24 }
25 int main()
26 {
27     //freopen("earthworm.in","r",stdin);
28     //freopen("earthworm.out","w",stdout);
29     scanf("%d%d%d%d%d%d",&n,&m,&tot,&u,&v,&t);
30     head[1]=head[2]=head[3]=1;
31     for(int i=1;i<=n;i++)
32         a[i]=qread();
33     sort(a+1,a+n+1);
34     for(int i=n;i>=1;i--)
35         q[1][++tail[1]]=a[i];
36     for(int i=1;i<=m;i++)
37     {
38         now=-INF;
39         for(int j=1;j<=3;j++)
40             if(head[j]<=tail[j] && q[j][head[j]]>now)
41             {
42                 now=q[j][head[j]];
43                 k=j;
44             }
45         now+=add;
46         if(i%t==0)
47             printf("%d ",now);
48         int nxt1=(long long)now*u/v,nxt2=now-nxt1;
49         add+=tot;
50         q[2][++tail[2]]=nxt1-add;
51         q[3][++tail[3]]=nxt2-add;
52         head[k]++;
53     }
54     putchar('
');
55     for(int i=1;i<=n+m;i++)
56     {
57         now=-INF;
58         for(int j=1;j<=3;j++)
59             if(head[j]<=tail[j] && q[j][head[j]]>now)
60             {
61                 now=q[j][head[j]];
62                 k=j;
63             }
64         now+=add;
65         if(i%t==0)
66             printf("%d ",now);
67         head[k]++;
68     }
69     fclose(stdin);fclose(stdout);
70     return 0;
71 }
View Code

T3 愤怒的小鸟

 1 /*
 2 状压dp
 3 预处理一个数组canshe[i][j]表示连接i，j两点做抛物线的时候能打到的小猪
 4 特别的，canshe[i][i]只能打到自己，能打到的小猪分别是谁这个用二进制表示
 5 然后进行dp
 6 f[i|canshe[j][k]]=min(f[i|canshe[j][k]],f[i]+1)
 7 但是这样只能得85分
 8 需要优化一下 
 9 当(i&(1<<(j-1))时，也就是说枚举的小猪之前打过，那么这种枚举之前以一定枚举过
10 所以我们只需要加上一个if(!(i&(1<<(j-1))))特判就能过 
11 */
12 #include<iostream>
13 #include<cstdio>
14 #include<algorithm>
15 #include<cstring>
16 using namespace std;
17 const double eps=1e-8;
18 struct node{
19     double x,y;
20 }pig[19];
21 int canshe[19][19];//用二进制表示  连接这两个点的抛物线能够打掉哪些点 
22 int f[1<<19];//表示打掉二进制位的当前状态的小鸟的最少花费 
23 int t,n,m; 
24 double a,b;
25 void calc(int x,int y)
26 {
27     double xa=pig[x].x,ya=pig[x].y,xb=pig[y].x,yb=pig[y].y;
28     double xaa=xa*xa,xbb=xb*xb;
29     double op=xb/xa;
30     xaa*=op;
31     xa*=op;
32     ya*=op;
33     a=(ya-yb)/(xaa-xbb);
34     b=(yb-a*xbb)/xb;
35 }
36 int main()
37 {
38     freopen("angrybirds.in","r",stdin);
39     freopen("angrybirds.out","w",stdout);
40     scanf("%d",&t);
41     while(t--)
42     {
43         scanf("%d%d",&n,&m);
44         memset(canshe,0,sizeof(canshe));
45         memset(f,0x3e,sizeof(f));
46         f[0]=0;
47         for(int i=1;i<=n;i++)
48             scanf("%lf%lf",&pig[i].x,&pig[i].y);
49         for(int i=1;i<=n;i++)
50         {
51             canshe[i][i]=1<<(i-1);
52             for(int j=i+1;j<=n;j++)
53             {
54                 calc(i,j);
55                 if(a>0)continue;
56                 for(int k=1;k<=n;k++)
57                 {
58                     double ans=pig[k].x*a*pig[k].x+pig[k].x*b;
59                     double tmp=ans-pig[k].y;
60                     if(tmp<0)tmp=-tmp;
61                     if(tmp<=eps)
62                         canshe[i][j]|=(1<<(k-1));
63                 }
64             }
65         }
66         for(int i=0;i<=(1<<n)-1;i++)
67             for(int j=1;j<=n;j++)
68                 if(i&(1<<(j-1))==0)
69                     for(int k=j;k<=n;k++)
70                         f[i|canshe[j][k]]=min(f[i|canshe[j][k]],f[i]+1);
71         printf("%d
",f[(1<<n)-1]);
72     }
73     fclose(stdin);fclose(stdout);
74     return 0;
75 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/1078713946t/p/7661558.html