2017.9.17校内noip模拟赛解题报告

阅读量：5075 次

发布时间：2019-06-12

本文共 10633 字，大约阅读时间需要 35 分钟。

预计分数：100+60+60=220

实际分数：100+60+40=200

除了暴力什么都不会的我。。。。。

T1 2017.9.17巧克力棒(chocolate)

巧克力棒(chocolate)

Time Limit:1000ms Memory Limit:64MB

题目描述

LYK 找到了一根巧克力棒，但是这根巧克力棒太长了，LYK 无法一口吞进去。

具体地，这根巧克力棒长为 n，它想将这根巧克力棒折成 n 段长为 1 的巧克力棒，然后

慢慢享用。

它打算每次将一根长为 k 的巧克力棒折成两段长为 a 和 b 的巧克力棒，此时若 a=b，则

LYK 觉得它完成了一件非常困难的事，并会得到 1 点成就感。

LYK 想知道一根长度为 n 的巧克力棒能使它得到最多几点成就感。

输入格式(chocolate.in)

第一行一个数 n。

输出格式(chocolate.out)

一个数表示答案。

输入样例

输出样例

数据范围

对于 20%的数据 n<=5。

对于 50%的数据 n<=20。

对于 80%的数据 n<=2000。

对于 100%的数据 n<=1000000000。

样例解释

将 7 掰成 3+4，将 3 掰成 1+2，将 4 掰成 2+2 获得 1 点成就感，将剩下的所有 2 掰成 1+1

获得 3 点成就感。总共 4 点成就感。

这道题可能是这次考试中我唯一一道推了推结论的题，

对于一个数n,能获得多少成就感我们不知道，

但是我们知道 1+1 = 2一定是n=2的最优情况

那么n=4的时候的最优情况就是(2*1+1)

推广到一般情况，

对于一个n，对他进行二进制拆分，可以证明这样就是最优解。

那么具体怎么拆分呢？？

打个表就好啦

时间复杂度O(31)

233333

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int MAXN=400001;  8 inline void read(long long int &n) 9 {10     char c=getchar();n=0;bool flag=0;11     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();12     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;13 }14 long long int pow2[80]=15             {16             0,17             1,3,7,15,31,18             63,127,255,511,1023,19             2047,4095,8191,16383,32767,20             65535,131071,262143,524287,1048575,21             2097151,4194303,8388607,16777215,33554431,22             67108863,134217727,268435455,536870911,107374182323             ,2147483647};24 int main()25 {26     //freopen("chocolate.in","r",stdin);27     //freopen("chocolate.out","w",stdout);28     long long n;29     cin>>n;30     long long  ans=0;31     for(int i=31;i>=1;i--)32     {33         if(n>=(pow2[i]+1))34         {35             n=n-(pow2[i]+1);36             ans+=pow2[i];37         }38     }39     printf("%lld",ans);40     return 0;41 }

T2 2017.9.17LYK 快跑！(run)

题目描述

LYK 陷进了一个迷宫！这个迷宫是网格图形状的。 LYK 一开始在(1,1)位置，出口在(n,m)。

而且这个迷宫里有很多怪兽，若第 a 行第 b 列有一个怪兽，且此时 LYK 处于第 c 行 d 列，此

时这个怪兽对它的威胁程度为|a-c|+|b-d|。 LYK 想找到一条路径，使得它能从(1,1)到达(n,m)，且在途中对它威胁程度最小的怪兽的

威胁程度尽可能大。

当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终=0。

输入输出格式

输入格式：

第一行两个数 n,m。

接下来 n 行，每行 m 个数，如果该数为 0，则表示该位置没有怪兽，否则存在怪兽。

数据保证至少存在一个怪兽。

输入格式(run.out)

一个数表示答案。

输出格式：

输入输出样例

输入样例#1：

3 40 1 1 00 0 0 01 1 1 0

输出样例#1：

说明

对于 20%的数据 n=1。

对于 40%的数据 n<=2。

对于 60%的数据 n,m<=10。

对于 80%的数据 n,m<=100。

对于 90%的数据 n,m<=1000。

对于另外 10%的数据 n,m<=1000 且怪兽数量<=100。

一开始的思路是把每个点都拆开跑深搜，

于是乎n^4的做法就诞生了。

然后就开始破罐子破摔了，

反正预处理都n^4了，搜索也写深搜暴力吧，，，

无脑60分，，

正解：

反向考虑，对于一个有怪兽的点(i,j),对他周围的点遍历，

这样的预处理就降成了N^2.

然后爆搜就好了

1 nclude
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 const int MAXN=1001;  8 const int INF=0x7ffff; 9 inline void read(int &n)10 {11     char c=getchar();n=0;bool flag=0;12     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();n=flag==1?-n:n;14 }15 int map[MAXN][MAXN];16 int a[MAXN][MAXN];17 int xx[5]={-1,+1,0,0};18 int yy[5]={
    0,0,-1,+1};19 int n,m;20 int flag=0;21 int vis[MAXN][MAXN];22 void dfs(int nowx,int nowy,int val)23 {24     if(nowx==n&&nowy==m)    { flag=1;return ; }25     for(int i=0;i<4;i++)26     {27         int wx=nowx+xx[i];28         int wy=nowy+yy[i];29         if(map[wx][wy]>=val&&a[wx][wy]==0&&wx>0&&wy>0&&wx<=n&&wy<=m&&vis[wx][wy]==0)30         {31             vis[wx][wy]=1;32             dfs(wx,wy,val);33             vis[wx][wy]=0;34             if(flag==1)    return ;35         }36     }37 }38 bool check(int val)39 {40     flag=0;41     vis[1][1]=1;42     dfs(1,1,val) ;43     if(flag==1)    return 1;else return 0;    44 }45 int main()46 {47     //freopen("run.in","r",stdin);48     //freopen("run.out","w",stdout);49     read(n);read(m);50     for(int i=1;i<=n;i++)51         for(int j=1;j<=m;j++)52             read(a[i][j]);53     for(int i=1;i<=n;i++)54         for(int j=1;j<=m;j++)55             map[i][j]=INF;56     for(int i=1;i<=n;i++)57         for(int j=1;j<=m;j++)58             if(a[i][j])59                 map[i][j]=INF;60             else61                 for(int k=1;k<=n;k++)62                     for(int l=1;l<=m;l++)63                         if(a[k][l])64                             map[i][j]=min(map[i][j],abs(k-i)+abs(l-j));65     int l=0,r=(n*m);66     int ans=0;67     while(l<=r)68     {69         int mid=(l+r)>>1;70         if(check(mid))    l=mid+1,ans=mid;71         else r=mid-1;72     }73     printf("%d",ans);74     return 0;75 }

60分暴力

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int MAXN=2001; 9 const int INF=0x7ffff;10 inline void read(int &n)11 {12 char c=getchar();n=0;bool flag=0;13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();n=flag==1?-n:n;15 }16 int xx[5]={-1,+1,0,0};17 int yy[5]={ 0,0,-1,+1};18 int n,m;19 int a[MAXN][MAXN];20 struct POINT21 {22 int x,y;23 }point[MAXN*MAXN],p;24 queue
            
             q;25 int vis[MAXN][MAXN];26 int dis[MAXN][MAXN];27 bool check(int val)28 {29 queue
             
              q;30 POINT p;p.x=1;p.y=1;31 q.push(p);32 memset(vis,0,sizeof(vis));33 while(q.size()!=0)34 {35 POINT p=q.front();36 if(p.x==n&&p.y==m) return 1;37 q.pop();38 for(int i=0;i<4;i++)39 {40 POINT nxt;41 nxt.x=p.x+xx[i];42 nxt.y=p.y+yy[i];43 if(nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m&&vis[nxt.x][nxt.y]==0&&dis[nxt.x][nxt.y]>=val&&dis[nxt.x][nxt.y]!=INF)44 {45 vis[nxt.x][nxt.y]=1;46 q.push(nxt);47 }48 }49 }50 return 0;51 }52 int main()53 {54 read(n);read(m);55 for(int i=1;i<=n;i++)56 for(int j=1;j<=m;j++)57 dis[i][j]=INF;58 for(int i=1;i<=n;i++)59 for(int j=1;j<=m;j++)60 {61 read(a[i][j]);62 if(a[i][j]) 63 {64 dis[i][j]=0;65 p.x=i,p.y=j,q.push(p);66 }67 }68 69 while(q.size()!=0)70 {71 POINT p=q.front();72 q.pop();73 for(int i=0;i<4;i++)74 {75 POINT nxt;76 nxt.x=p.x+xx[i];77 nxt.y=p.y+yy[i];78 if(vis[nxt.x][nxt.y]==0&&nxt.x>0&&nxt.y>0&&nxt.x<=n&&nxt.y<=m)79 {80 vis[nxt.x][nxt.y]=1;81 dis[nxt.x][nxt.y]=min(dis[nxt.x][nxt.y],dis[p.x][p.y]+1);82 q.push(nxt);83 }84 }85 }86 int l=0,r=(n*m);87 int ans=0;88 while(l<=r)89 {90 int mid=(l+r)>>1;91 if(check(mid)) l=mid+1,ans=mid;92 else r=mid-1;93 }94 printf("%d",ans);95 return 0;96 }

100分AC

T3 2017.9.17仙人掌(cactus)

题目描述

LYK 在冲刺清华集训（THUSC）！于是它开始研究仙人掌，它想来和你一起分享它最近

研究的结果。

如果在一个无向连通图中任意一条边至多属于一个简单环（简单环的定义为每个点至多

经过一次），且不存在自环，我们称这个图为仙人掌。

LYK 觉得仙人掌还是太简单了，于是它定义了属于自己的仙人掌。

定义一张图为美妙的仙人掌，当且仅当这张图是一个仙人掌且对于任意两个不同的点 i,j，

存在一条从 i 出发到 j 的路径，且经过的点的个数为|j-i|+1 个。给定一张 n 个点 m 条边且没有自环的图，LYK 想知道美妙的仙人掌最多有多少条边。

数据保证整张图至少存在一个美妙的仙人掌。

输入输出格式

输入格式：

第一行两个数 n,m 表示这张图的点数和边数。

接下来 m 行，每行两个数 u,v 表示存在一条连接 u,v 的无向边。

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

4 61 21 31 42 32 43 4

输出样例#1：

4样例解释选择边 1-2,1-3,2-3,3-4，能组成美妙的仙人掌，且不存在其它美妙仙人掌有超过 4 条边。

说明

对于 20%的数据 n<=3。

对于 40%的数据 n<=5。

对于 60%的数据 n<=8。

对于 80%的数据 n<=1000。

对于 100%的数据 n<=100000 且 m<=min(200000,n*(n-1)/2)。

读题都读的我一脸蒙蔽

于是直接奔着n<=8的情况去了

直接暴力生成所有的图，

然后暴力判断可行不可行。

本来以为能得60分，结果只得了40分。。。

正解：

据某位玄学的大佬说。

i和i+1一定要选(贪心)

而且一定要选满n个点(贪心)

然后跑一边线段覆盖就可以A了(玄学)

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 using namespace std; 8 const int MAXN=101; 9 const int INF=0x7ffff; 10 inline void read(int &n) 11 { 12 char c=getchar();n=0;bool flag=0; 13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar(); 14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();n=flag==1?-n:n; 15 } 16 struct node 17 { 18 int u,v,w,nxt; 19 }edge[MAXN]; 20 int head[MAXN]; 21 int num=1; 22 inline void add_edge(int x,int y,int z) 23 { 24 edge[num].u=x; 25 edge[num].v=y; 26 edge[num].w=z; 27 edge[num].nxt=head[x]; 28 head[x]=num++; 29 } 30 int n,m; 31 int map[MAXN][MAXN]; 32 int vis[MAXN];// 每个边是否被访问 33 int vis2[MAXN];// 每个点是否被访问 34 int have[MAXN][MAXN];// 是否满足条件 35 int dfs2(int point ,int num) 36 { 37 for(int i=1;i<=n;i++) 38 if(abs(point-i)+1==num+1) 39 have[point][i]=1; 40 for(int i=1;i<=n;i++) 41 if(map[point][i]&&vis2[i]==0) 42 { 43 vis2[i]=1; 44 dfs2(i,num+1); 45 vis2[i]=0; 46 } 47 } 48 int nowans; 49 int out; 50 int vis3[MAXN]; 51 bool flag3=0; 52 void pd() 53 { 54 memset(have,0,sizeof(have)); 55 memset(map,0,sizeof(map)); 56 memset(vis2,0,sizeof(vis2)); 57 memset(vis3,0,sizeof(vis3)); 58 flag3=0; 59 for(int i=1;i<=m;i++) 60 { 61 if(vis[i]) 62 { 63 map[edge[i].u][edge[i].v]=1; 64 map[edge[i].v][edge[i].u]=1; 65 } 66 } 67 int tot=0; 68 for(int i=1;i<=m;i++) 69 if(vis[i]) tot++; 70 if(tot>n) return ; 71 for(int i=1;i<=n;i++) 72 { 73 vis2[i]=1; 74 dfs2(i,1); 75 vis2[i]=0; 76 } 77 78 for(int i=1;i<=n;i++) 79 for(int j=1;j<=n;j++) 80 if(have[i][j]==0&&(i!=j)) return ; 81 nowans=0; 82 for(int i=1;i<=m;i++) 83 if(vis[i]) 84 nowans++; 85 out=max(out,nowans); 86 } 87 void dfs(int now) 88 { 89 if(now==m+1) 90 { 91 pd(); 92 return ; 93 } 94 vis[now]=1; 95 dfs(now+1); 96 vis[now]=0; 97 dfs(now+1); 98 } 99 int main()100 {101 // freopen("cactus.in","r",stdin);102 //freopen("cactus.out","w",stdout);103 read(n);read(m);104 if(n==1)105 {106 printf("0");107 return 0;108 }109 if(n<=8)110 {111 for(int i=1;i<=m;i++)112 {113 int x,y;read(x);read(y);114 add_edge(x,y,1);115 }116 dfs(1);117 printf("%d",out); 118 }119 else120 {121 printf("%d",rand()%m);122 }123 return 0;124 }

40分暴力

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 const int MAXN=100001; 9 const int INF=0x7ffff;10 inline void read(int &n)11 {12 char c=getchar();n=0;bool flag=0;13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();n=flag==1?-n:n;15 }16 int n,m;17 struct node18 {19 int bg,ed;20 }point[MAXN];21 int tot=0;22 int comp(const node &a ,const node &b)23 {24 return a.ed
            
             y) swap(x,y);33 if(x!=y-1) point[++tot].bg=x,point[tot].ed=y;34 }35 sort(point,point+tot+1,comp);36 int cur=0;37 int ans=0;38 for(int i=1;i<=tot;i++)39 {40 if(cur<=point[i].bg)41 {42 cur=point[i].ed;43 ans++;44 }45 }46 printf("%d",ans+n-1);47 return 0;48 }