NOIP2015提高组 解题报告

D1

T1 神奇的幻方

一道大水题

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n;
 5 int ans[40][40];
 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 void dfs(int i,int j,int num)
15 {
16     ans[i][j]=num;
17     if(num==n*n)
18         return;
19     if(i==1 && j!=n)
20     {
21         dfs(n,j+1,num+1);
22         return;
23     }
24     if(i!=1 && j==n)
25     {
26         dfs(i-1,1,num+1);
27         return;
28     }
29     if(i==1 && j==n)
30     {
31         dfs(i+1,j,num+1);
32         return;
33     }
34     if(i!=1 && j!=n)
35         if(!ans[i-1][j+1])
36         {
37             dfs(i-1,j+1,num+1);
38             return;
39         }
40         else
41         {
42             dfs(i+1,j,num+1);
43             return;
44         }
45 }
46 int main()
47 {
48     freopen("magic.in","r",stdin);
49     freopen("magic.out","w",stdout);
50     scanf("%d",&n);
51     dfs(1,n/2+1,1);
52     for(int i=1;i<=n;i++)
53     {
54         for(int j=1;j<=n;j++)
55             printf("%d ",ans[i][j]);
56         putchar('
');
57     }
58     fclose(stdin);fclose(stdout);
59     return 0;
60 }
View Code

T2 信息传递

要想从别人那里知道自己的信息，就必须存在环。所以问题就转换成了求最小环
可以用拓扑排序去掉所有不在环中的点，再dfs找环

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 const int N=200001;
 6 int n,ans=0x3f3f3f,num;
 7 int son[N],in[N];
 8 bool vis[N];
 9 queue<int>q;
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 void dfs(int x)
19 {
20     num++;
21     vis[x]=1;
22     if(!vis[son[x]])
23         dfs(son[x]);
24 }
25 int main()
26 {
27     scanf("%d",&n);
28     for(int i=1;i<=n;i++)
29     {
30         son[i]=qread();
31         in[son[i]]++;
32     }
33     for(int i=1;i<=n;i++)
34         if(!in[i])
35         {
36             q.push(i);
37             vis[i]=1;
38         }
39     while(!q.empty())
40     {
41         int u=q.front();
42         q.pop();
43         in[son[u]]--;
44         if(!in[son[u]])
45         {
46             q.push(son[u]);
47             vis[son[u]]=1;
48         }
49     }
50     for(int i=1;i<=n;i++)
51     {
52         num=0;
53         if(!vis[i])
54             dfs(i);
55         if(num)ans=min(ans,num);
56     }
57     printf("%d
",ans);
58     return 0;
59 }
View Code

T3 斗地主

第一大大的模拟+搜索

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 using namespace std;
  5 int T,n,ans;
  6 int num[20],num2[10];
  7 //num记录i大的牌的数量 
  8 //num2表示有数量为i的牌的数量 
  9 inline int qread()
 10 {
 11     int x=0,j=1;
 12     char ch=getchar();
 13     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
 14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 15     return x*j;
 16 }
 17 int calc()
 18 {
 19     memset(num2,0,sizeof(num2));
 20     for(int i=0;i<=13;i++)
 21         num2[num[i]]++;
 22     int tot=0;
 23     while(num2[4] && num2[2]>=2)//四带两对 
 24     {
 25         num2[4]--;
 26         num2[2]-=2;
 27         tot++;
 28     }
 29     while(num2[4] && num2[1]>=2)//四带两单 
 30     {
 31         num2[4]--;
 32         num2[1]-=2;
 33         tot++;
 34     }
 35     while(num2[4] && num2[2])//四带一对 
 36     {
 37         num2[4]--;
 38         num2[2]--;
 39         tot++;
 40     }
 41     while(num2[3] && num2[2])//三带一对 
 42     {
 43         num2[3]--;
 44         num2[2]--;
 45         tot++;
 46     }
 47     while(num2[3] && num2[1])//三带一 
 48     {
 49         num2[3]--;
 50         num2[1]--;
 51         tot++;
 52     }
 53     return tot+num2[1]+num2[2]+num2[3]+num2[4];
 54 }
 55 void dfs(int step)
 56 {
 57     if(step>=ans)return;
 58     int tmp=calc();
 59     if(step+tmp<ans)ans=step+tmp;
 60     for(int i=2;i<=13;i++)//三顺 
 61     {
 62         int j=i;
 63         while(num[j]>=3)
 64             j++;
 65         if(j-i>=2)
 66             for(int k=i+1;k<=j-1;k++)
 67             {
 68                 for(int l=i;l<=k;l++)
 69                     num[l]-=3;
 70                 dfs(step+1);
 71                 for(int l=i;l<=k;l++)
 72                     num[l]+=3;
 73             }
 74     }
 75     for(int i=2;i<=13;i++)//双顺 
 76     {
 77         int j=i;
 78         while(num[j]>=2)
 79             j++;
 80         if(j-i>=3)
 81             for(int k=i+2;k<=j-1;k++)
 82             {
 83                 for(int l=i;l<=k;l++)
 84                     num[l]-=2;
 85                 dfs(step+1);
 86                 for(int l=i;l<=k;l++)
 87                     num[l]+=2;
 88             }
 89     }
 90     for(int i=2;i<=13;i++)//单顺 
 91     {
 92         int j=i;
 93         while(num[j]>=1)
 94             j++;
 95         if(j-i>=5)
 96             for(int k=i+4;k<=j-1;k++)
 97             {
 98                 for(int l=i;l<=k;l++)
 99                     num[l]--;
100                 dfs(step+1);
101                 for(int l=i;l<=k;l++)
102                     num[l]++;
103             }
104     }
105 }
106 int main()
107 {
108     freopen("landlords.in","r",stdin);
109     freopen("landlords.out","w",stdout);
110     scanf("%d%d",&T,&n);
111     while(T--)
112     {
113         memset(num,0,sizeof(num));
114         ans=0x3f3f3f3f;
115         for(int i=1;i<=n;i++)
116         {
117             int x=qread(),y=qread();
118             if(x==1)x=13;
119             else if(x)x--;
120             num[x]++;
121         }
122         dfs(0);
123         printf("%d
",ans);
124     }
125     fclose(stdin);fclose(stdout);
126     return 0;
127 }
View Code

D2

T1 跳石头

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int L,n,m;
 5 int d[50001];
 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 bool check(int x)
15 {
16     int tot=0,now;
17     for(int i=0;i<=n;i=now)
18     {
19         now=i+1;
20         while(d[now]-d[i]<x && now<=n+1)
21             now++;
22         tot+=now-i-1;
23     }
24     if(tot<=m)return 1;
25     return 0;
26 }
27 int main()
28 {
29     freopen("stone.in","r",stdin);
30     freopen("stone.out","w",stdout);
31     scanf("%d%d%d",&L,&n,&m);
32     d[n+1]=L;
33     for(int i=1;i<=n;i++)
34         d[i]=qread();
35     int l=0,r=L;
36     while(l<=r)
37     {
38         int mid=(l+r)>>1;
39         if(check(mid))l=mid+1;
40         else r=mid-1;
41     }
42     printf("%d
",r);
43     fclose(stdin);fclose(stdout);
44     return 0;
45 }
View Code

T2 子串

解析改自dalao博客，http://www.cnblogs.com/TheRoadToTheGold/p/6750111.html

 1 /*
 2 f[i][j][k][l]表示a串匹配到i，b串匹配到j，用了k个子串，a[l]用/不用的方案数 
 3 1.若a[i]不用，f[i][j][k][0]=f[i-1][j][k][0]+f[i-1][j][k][1] 
 4 2.若a[i]用，那么可以选择a[i]自己分在一个子串，或者与a[i-1]分在一个子串 
 5 若a[i]自己分在一个子串，那么又分为a[i-1]用了和a[i-1]没用两种 
 6 所以f[i][j][k][1]=f[i-1][j-1][k-1][1](自成一串，前一个用了)
 7                     +f[i-1][j-1][k-1][0](自成一串，前一个没用)
 8                         +f[i-1][j-1][k][1](与前一个合为一串，前一个必须用了) 
 9 */
10 #include<iostream>
11 #include<cstdio>
12 using namespace std;
13 const int mod=1e9+7;
14 int n,m,p,s,ans;
15 int f[2][201][201][2];
16 char a[1001],b[201];
17 int main()
18 {
19     scanf("%d%d%d",&n,&m,&p);
20     scanf("%s%s",a+1,b+1);
21     f[0][0][0][0]=f[1][0][0][0]=1;
22     for(int i=1;i<=n;i++)
23     {
24         int tmp=(i+1)%2;
25         for(int j=1;j<=min(i,m);j++)
26             for(int k=1;k<=min(j,p);k++)
27             {
28                 f[i%2][j][k][0]=(f[tmp][j][k][0]+f[tmp][j][k][1])%mod;
29                 if(a[i]==b[j])
30                     f[i%2][j][k][1]=((f[tmp][j-1][k-1][0]+f[tmp][j-1][k-1][1])%mod+f[tmp][j-1][k][1])%mod;
31                 else f[i%2][j][k][1]=0;
32             }
33         ans+=f[i%2][m][p][1];
34         ans%=mod;
35     }
36     printf("%d
",ans);
37     return 0;
38 }
View Code

T3 运输计划

LCA+差分+二分+前缀和

  1 /*
  2 可以预处理出要查询的点的lca和边权的前缀和O(1)查询距离 
  3 二分答案 
  4 对于距离>=mid的路线(假设共有k条)，需在他们上面搞一个虫洞 
  5 对于每一个线路都需要搞一个虫洞，那么一定是在这k条线路的交点上搞这个这个虫洞 
  6 所以现在的问题是如何求这k条线路的交点 
  7 a[i]表示第i条边被多少条线路覆盖，如果a[i]=k，说明这就是要找的边 
  8 对于所有a[i]=k的边，把长度最长的那条变成虫洞 
  9 然后再看变成黑洞以后，这k条线路是否都变合法，继续二分 
 10 树上前缀和快速覆盖k条线路 
 11 注意是对边进行修改，而不是点 
 12 change[i]表示对i到根节点所有点的修改。即如果change[i]+=1，相当于是对i到根节点的所有边都+=1 
 13 这样如果我要对x到y这条路径上所有的边都加1，只需要change[x]+=1,change[y]+=1,change[Lca(x,y)]-=2 
 14 最后再求一下子树前缀和就可以了 
 15 */
 16 #include<iostream>
 17 #include<cstdio>
 18 #include<cstring>
 19 using namespace std;
 20 const int N=300500;
 21 struct node{
 22     int v,w,nxt;
 23 }e[N*2];
 24 int n,m,num;
 25 int su[N],ev[N],head[N],change[N],sum[N];
 26 int deep[N],fat[N][22],lca[N];
 27 inline int qread()
 28 {
 29     int x=0,j=1;
 30     char ch=getchar();
 31     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
 32     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 33     return x*j;
 34 }
 35 inline void Insert(int u,int v,int w)
 36 {
 37     e[++num].v=v;
 38     e[num].w=w;
 39     e[num].nxt=head[u];
 40     head[u]=num;
 41 }
 42 void find_deep(int x)
 43 {
 44     for(int i=head[x];i;i=e[i].nxt)
 45     {
 46         int v=e[i].v;
 47         if(v==fat[x][0])continue;
 48         deep[v]=deep[x]+1;
 49         sum[v]=sum[x]+e[i].w;//距离前缀和 
 50         fat[v][0]=x;
 51         find_deep(v);
 52     }
 53 }
 54 void find_father()
 55 {
 56     for(int j=1;j<=20;j++)
 57         for(int i=1;i<=n;i++)
 58             fat[i][j]=fat[fat[i][j-1]][j-1];
 59 }
 60 int get(int a,int delta)
 61 {
 62     for(int i=0;i<=21;i++)
 63         if(delta&(1<<i))
 64             a=fat[a][i];
 65     return a;
 66 }
 67 inline int Lca(int a,int b)
 68 {
 69     if(deep[a]<deep[b])swap(a,b);
 70     a=get(a,deep[a]-deep[b]);
 71     if(a==b)return a;
 72     for(int i=21;i>=0;i--)
 73         if(fat[a][i]!=fat[b][i])
 74         {
 75             a=fat[a][i];
 76             b=fat[b][i];
 77         }
 78     return fat[a][0];
 79 }
 80 void calc(int x)//求change前缀和 
 81 {
 82     for(long long i=head[x];i;i=e[i].nxt)
 83     {
 84         int v=e[i].v;
 85         if(v==fat[x][0])continue;
 86         calc(v);
 87         change[x]+=change[v];
 88     }
 89 }
 90 bool check(int x)
 91 {
 92     memset(change,0,sizeof(change));
 93     int tot=0,maxn=0,maxdis=0;
 94     for(int i=1;i<=n;i++)
 95         if(sum[su[i]]+sum[ev[i]]-2*sum[lca[i]]>x)
 96         {
 97             tot++;
 98             maxdis=max(maxdis,sum[su[i]]+sum[ev[i]]-2*sum[lca[i]]);
 99             change[su[i]]++;
100             change[ev[i]]++;
101             change[lca[i]]-=2;
102         }
103     if(!tot)return 0;
104     calc(1);
105     for(int i=2;i<=n;i++)
106         if(change[i]>=tot && sum[i]-sum[fat[i][0]]>maxn)//找边的交集中最长的那条 
107             maxn=sum[i]-sum[fat[i][0]];
108     if(maxdis-maxn>x)
109         return 1;
110     return 0;
111 }
112 int main()
113 {
114 //    freopen("transport.in","r",stdin);
115 //    freopen("transport.out","w",stdout);
116     scanf("%d%d",&n,&m);
117     int u,v,w;
118     for(int i=1;i<=n-1;i++)
119     {
120         u=qread(),v=qread();w=qread();
121         Insert(u,v,w);
122         Insert(v,u,w);
123     }
124     find_deep(1);
125     find_father();
126     for(int i=1;i<=m;i++)
127     {
128         su[i]=qread();ev[i]=qread();
129         lca[i]=Lca(su[i],ev[i]);
130     }
131     int l=0,r=3e8;
132     while(l<=r)
133     {
134         int mid=(l+r)>>1;
135         if(check(mid))l=mid+1;
136         else r=mid-1;
137     }
138     printf("%d
",l);
139 //    fclose(stdin);fclose(stdout);
140     return 0;
141 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/1078713946t/p/7662986.html