NOIP2014提高组 解题报告

D1

T1 生活大爆炸版石头剪刀布

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,na,nb,ans1,ans2;
 5 int a[201],b[201];
 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     scanf("%d%d%d",&n,&na,&nb);
17     for(int i=1;i<=na;i++)
18         a[i]=qread();
19     for(int i=1;i<=nb;i++)
20         b[i]=qread();
21     int tot=na,cnt=nb;
22     int j=1;
23     while(tot<=n)
24     {
25         if(j>na)j=1;
26         a[++tot]=a[j++];
27     }
28     j=1;
29     while(cnt<=n)
30     {
31         if(j>nb)j=1;
32         b[++cnt]=b[j++];
33     }
34     for(int i=1;i<=n;i++)
35     {
36         if(a[i]==b[i])continue;
37         if(a[i]==0)
38             if(b[i]==2 || b[i]==3)ans1++;
39             else ans2++;
40         if(a[i]==1)
41             if(b[i]==0 || b[i]==3)ans1++;
42             else ans2++;
43         if(a[i]==2)
44             if(b[i]==1 || b[i]==4)ans1++;
45             else ans2++;
46         if(a[i]==3)
47             if(b[i]==2 || b[i]==4)ans1++;
48             else ans2++;
49         if(a[i]==4)
50             if(b[i]==0 || b[i]==1)ans1++;
51             else ans2++;
52     }
53     printf("%d %d
",ans1,ans2);
54     return 0;
55 }
View Code

T2 联合权值

70分的暴力

枚举所有点，与其相连的点(距离为一)的相连的点(不包括自己 距离为二)。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int mod=10007;
 5 const int N=200001;
 6 struct node{
 7     int v,nxt;
 8 }e[N<<1];
 9 int n,maxn,sum,num;
10 int w[N],head[N],fat[N];
11 inline int qread()
12 {
13     int x=0,j=1;
14     char ch=getchar();
15     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
16     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
17     return x*j;
18 }
19 void Insert(int u,int v)
20 {
21     e[++num].v=v;
22     e[num].nxt=head[u];
23     head[u]=num;
24 }
25 void calc(int u)
26 {
27     for(int i=head[u];i;i=e[i].nxt)
28     {
29         int v=e[i].v;
30         for(int j=head[v];j;j=e[j].nxt)
31             if(u!=e[j].v)
32             {
33                 maxn=max(maxn,w[u]*w[e[j].v]);
34                 sum+=w[u]*w[e[j].v];
35                 sum%=mod;
36             }
37     }
38 }
39 int main()
40 {
41     scanf("%d",&n);
42     int u,v;
43     for(int i=1;i<=n-1;i++)
44     {
45         u=qread();v=qread();
46         Insert(u,v);
47         Insert(v,u);
48     }
49     for(int i=1;i<=n;i++)
50         w[i]=qread();
51     for(int i=1;i<=n;i++)
52         calc(i);
53     printf("%d %d",maxn,sum);
54     return 0;
55 }
View Code

正解

 1 //过一点的最大联合权值为经过该点的最大点权乘以次大点权 
 2 //过一点的联合权值和为经过该点的所有点的点权和的平方减去平方和 
 3 #include<iostream>
 4 #include<cstdio>
 5 using namespace std;
 6 const int mod=10007;
 7 const int N=200001;
 8 struct node{
 9     int v,nxt;
10 }e[N<<1];
11 int n,maxn,num,ans,max1,max2,tot;
12 int w[N],head[N],fat[N];
13 inline int qread()
14 {
15     int x=0,j=1;
16     char ch=getchar();
17     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
18     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
19     return x*j;
20 }
21 void Insert(int u,int v)
22 {
23     e[++num].v=v;
24     e[num].nxt=head[u];
25     head[u]=num;
26 }
27 int main()
28 {
29     //freopen("link.in","r",stdin);
30     //freopen("link.out","w",stdout);
31     scanf("%d",&n);
32     int u,v;
33     for(int i=1;i<=n-1;i++)
34     {
35         u=qread();v=qread();
36         Insert(u,v);
37         Insert(v,u);
38     }
39     for(int i=1;i<=n;i++)
40         w[i]=qread();
41     for(int i=1;i<=n;i++)
42     {
43         max1=max2=num=tot=0;
44         for(int j=head[i];j;j=e[j].nxt)
45         {
46             int v=e[j].v;
47             if(w[v]>max2)
48             {
49                 max2=w[v];
50                 if(max2>max1)swap(max2,max1);
51             }
52             tot=(tot+(w[v]*w[v])%mod)%mod;
53             num=(num+w[v])%mod;
54         }
55         maxn=max(maxn,max1*max2);
56         ans=(ans+(num*num-tot)%mod)%mod;
57     }
58     printf("%d %d",maxn,ans);
59     //fclose(stdin);fclose(stdout);
60     return 0;
61 }
View Code


T3 飞扬的小鸟

神奇的背包

 1 //在往上飞的时候是完全背包，往下掉的时候是01背包
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cstring>
 5 using namespace std;
 6 const int INF=0x3f3f3f3f;
 7 const int N=10001;
 8 int n,m,k,ans=INF,tot;
 9 int up[N],down[N],topp[N],endd[N],f[N][1001];
10 //f[i][j]表示到达第i行j高度时点击屏幕的最小次数 
11 bool have[N];
12 inline int qread()
13 {
14     int x=0,j=1;
15     char ch=getchar();
16     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
17     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
18     return x*j;
19 }
20 int Min(int a,int b)
21 {
22     if(a<b)return a;
23     return b;
24 }
25 int main()
26 {
27 //    freopen("bird.in","r",stdin);
28 //    freopen("bird.out","w",stdout);
29     scanf("%d%d%d",&n,&m,&k);
30     for(int i=0;i<=n-1;i++)
31     {
32         up[i]=qread();
33         down[i]=qread();
34     }
35     for(int i=0;i<=n;i++)
36         topp[i]=m+1;
37     int x;
38     for(int i=1;i<=k;i++)
39     {
40         x=qread();
41         endd[x]=qread();topp[x]=qread();
42         have[x]=1;
43     }
44     memset(f,0x3f,sizeof(f));
45     for(int i=1;i<=m;i++)
46         f[0][i]=0;//除第0列外的所有第0行次数都为零 
47     for(int i=1;i<=n;i++)
48     {
49         for(int j=up[i-1];j<=m;j++)//上升 
50         {
51             f[i][j]=Min(f[i][j],Min(f[i-1][j-up[i-1]]+1,f[i][j-up[i-1]]+1));
52             if(j==m)//特判，因为高度不超过m，所以有多种转移 
53                 for(int l=m-up[i-1];l<=m;l++)
54                     f[i][m]=Min(f[i][m],Min(f[i-1][l]+1,f[i][l]+1));
55         }
56         for(int j=endd[i]+1;j<=topp[i]-1;j++)//下降 
57             if(j+down[i-1]<=m)
58                 f[i][j]=Min(f[i][j],f[i-1][j+down[i-1]]);
59         for(int j=1;j<=endd[i];j++)//考虑水管，去掉不合法解 
60             f[i][j]=INF;
61         for(int j=topp[i];j<=m;j++)
62             f[i][j]=INF;
63     }
64     tot=k;
65     for(int i=n;i;i--)
66     {
67         for(int j=endd[i]+1;j<=topp[i]-1;j++)
68             ans=Min(ans,f[i][j]);
69         if(ans!=INF)break;
70         if(have[i])tot--;//有水管且未更新答案 
71     }
72     if(tot==k)printf("1
%d
",ans);
73     else printf("0
%d
",tot);
74     fclose(stdin);fclose(stdout);
75     return 0;
76 }
View Code

D2

T1 无线网络发射器选址

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int d,n,ans,num;
 5 int a[150][150],x[21],y[21];
 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("wireless.in","r",stdin);
17 //    freopen("wireless.out","w",stdout);
18     scanf("%d%d",&d,&n);
19     for(int i=1;i<=n;i++)
20     {
21         x[i]=qread();y[i]=qread();
22         a[x[i]][y[i]]=qread();
23     }
24     for(int i=0;i<=128;i++)
25         for(int j=0;j<=128;j++)
26         {
27             int now=0;
28             for(int k=1;k<=n;k++)
29                 if(x[k]>=i-d && x[k]<=i+d && y[k]>=j-d && y[k]<=j+d)
30                     now+=a[x[k]][y[k]];
31             if(now==ans)num++;
32             if(now>ans)
33             {
34                 ans=now;
35                 num=1;
36             }
37         }
38     printf("%d %d
",num,ans);
39 //    fclose(stdin);fclose(stdout);
40     return 0;
41 }
View Code

T2 寻找道路

如果想到反向bfs找能到达终点的点的话，这道题并不是很难做(我就没有想到Orz)

  1 //从终点反向建图bfs找能到达终点的点 
  2 //再正向建图SPFA求最短路 
  3 #include<iostream>
  4 #include<cstdio>
  5 #include<queue>
  6 #include<cstring>
  7 using namespace std;
  8 const int N=2e5+9;
  9 struct node{
 10     int v,nxt;
 11 }e[N];
 12 int n,m,s,t,Enum;
 13 int dis[10001],u[N],v[N],head[N];
 14 bool vis[10001];
 15 queue<int>q;
 16 inline int qread()
 17 {
 18     int x=0,j=1;
 19     char ch=getchar();
 20     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
 21     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 22     return x*j;
 23 }
 24 void Insert(int u,int v)
 25 {
 26     e[++Enum].v=v;
 27     e[Enum].nxt=head[u];
 28     head[u]=Enum;
 29 }
 30 void bfs1()
 31 //反向图中终点能到达的点在正向图中就能终点 
 32 //将其进行标记 
 33 {
 34     q.push(t);
 35     vis[t]=1;
 36     while(!q.empty())
 37     {
 38         int u=q.front();
 39         q.pop();
 40         for(int i=head[u];i;i=e[i].nxt)
 41         {
 42             int v=e[i].v;
 43             if(!vis[v])
 44             {
 45                 vis[v]=1;
 46                 q.push(v);
 47             }
 48         }
 49     }
 50 }
 51 bool check(int x)
 52 {
 53     for(int i=head[x];i;i=e[i].nxt)
 54         if(!vis[e[i].v])
 55             return 0;
 56     return 1;
 57 }
 58 bool SPFA()
 59 {
 60     q.push(s);
 61     dis[s]=0;
 62     while(!q.empty())
 63     {
 64         int u=q.front();
 65         q.pop();
 66         if(!check(u))continue;
 67         for(int i=head[u];i;i=e[i].nxt)
 68         {
 69             int v=e[i].v;
 70             if(!dis[v])
 71             {
 72                 dis[v]=dis[u]+1;
 73                 q.push(v);
 74                 if(v==t)
 75                 {
 76                     printf("%d
",dis[t]);
 77                     return 1;
 78                 }
 79             }
 80         }
 81     }
 82     return 0;
 83 }
 84 int main()
 85 {
 86     scanf("%d%d",&n,&m);
 87     for(int i=1;i<=m;i++)
 88     {
 89         u[i]=qread();v[i]=qread();
 90         if(u[i]!=v[i])//有自环 
 91             Insert(v[i],u[i]);//反向建图 
 92     }
 93     scanf("%d%d",&s,&t);
 94     bfs1();
 95     Enum=0;
 96     memset(head,0,sizeof(head));
 97     for(int i=1;i<=m;i++)
 98         if(u[i]!=v[i])
 99             Insert(u[i],v[i]);//正向建图找最短路 
100     if(!vis[s])
101     {
102         printf("-1
");
103         return 0;
104     }
105     if(!SPFA())printf("-1
");
106     return 0;
107 }
View Code

T3 解方程

秦久韶算法

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int mod=1e9+7;
 5 int n,m,num;
 6 long long sum;
 7 int a[100001],ans[1000001];
 8 int qread()
 9 {
10     long long x=0,j=1;
11     char ch=getchar();
12     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
13     while(ch>='0' && ch<='9'){x=x*10+ch-'0';x%=mod;ch=getchar();}
14     return x*j;
15 }
16 bool calc(int x)
17 {
18     sum=0;
19     for(int j=n;j>=0;j--)
20         sum=((a[j]+sum)*x)%mod;
21     if(!sum)return 1;
22     return 0;
23 }
24 int main()
25 {
26 //    freopen("equation.in","r",stdin);
27 //    freopen("equation.out","w",stdout);
28     scanf("%d%d",&n,&m);
29     for(int i=0;i<=n;i++)
30         a[i]=qread();
31     for(int i=1;i<=m;i++)
32         if(calc(i))
33             ans[++num]=i;
34     printf("%d
",num);
35     for(int i=1;i<=num;i++)
36         printf("%d
",ans[i]);
37 //    fclose(stdin);fclose(stdout);
38     return 0;
39 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/1078713946t/p/7677426.html