2017.9.17 小测试小整理

2017.9.17 小测试小整理

巧克力棒(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)

一个数表示答案。

输入样例

7

输出样例

4

数据范围

对于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点成就感。

思路:

根据样例解释来看，容易发现把这个巧克力棒分成2^k的长度可以获得更大的成就感，所以可以用贪心来做

上代码:

#include <iostream>
#include <cstdio>
using namespace std;int main() {freopen("chocolate.in","r",stdin);freopen("chocolate.out","w",stdout);int n,ans=0;scanf("%d",&n);while(n) {n/=2;ans+=n;}/*//原理同上 ans=n;while(n) {ans-=n%2;n/=2;}*/printf("%d",ans);return 0;
}

LYK快跑！(run)

Time Limit:5000ms   Memory Limit:64MB

题目描述

LYK陷进了一个迷宫！这个迷宫是网格图形状的。LYK一开始在(1,1)位置，出口在(n,m)。而且这个迷宫里有很多怪兽，若第a行第b列有一个怪兽，且此时LYK处于第c行d列，此时这个怪兽对它的威胁程度为|a-c|+|b-d|。
LYK想找到一条路径，使得它能从(1,1)到达(n,m)，且在途中对它威胁程度最小的怪兽的威胁程度尽可能大。
当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终=0。

输入格式(run.in)

第一行两个数n,m。
接下来n行，每行m个数，如果该数为0，则表示该位置没有怪兽，否则存在怪兽。数据保证至少存在一个怪兽。

输入格式(run.out)

一个数表示答案。

输入样例

3 4
0 1 1 0
0 0 0 0
1 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。

思路:

典型的二分答案，先预处理一遍(所有怪兽到达某个点最短距离)，然后放进queue里面跑bfs

上代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;const int M = 1010;
int n,m,cnt,ans;
int map[M][M],v[M][M];
bool vis[M][M];
int dx[4] = {0, 0,1,-1},dy[4] = {1,-1,0, 0};
struct A {int x,y;
} cur,nxt;
queue<A>q;bool check(int lim) {while(!q.empty()) q.pop();memset(vis,false,sizeof(vis));cur.x=1,cur.y=1;q.push(cur);while(!q.empty()) {cur=q.front();q.pop();int nx=cur.x,ny=cur.y;if(nx==n && ny==m) //到达终点,成功return true;for(int i=0; i<4; ++i) {int x=nx+dx[i],y=ny+dy[i];if(x>=1 && y>=1 && x<=n && y<=m && !map[x][y] && !vis[x][y] && v[x][y]>=lim) {vis[x][y]=true;nxt.x=x,nxt.y=y;q.push(nxt);}}}return false;
}int main() {freopen("run.in","r",stdin);freopen("run.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j) {scanf("%d",&map[i][j]);if(map[i][j]) //存储怪兽出现的位置cur.x=i,cur.y=j,q.push(cur);}if(map[1][1] || map[n][m] || n==1) {printf("0");return 0;}while(!q.empty()) { //求vcur=q.front();q.pop();int nx=cur.x,ny=cur.y;for(int i=0; i<4; ++i) {int x=nx+dx[i],y=ny+dy[i];if(x>=1 && y>=1 && x<=n && y<=m && !map[x][y] && !v[x][y]) {v[x][y]=v[nx][ny]+1;nxt.x=x,nxt.y=y;q.push(nxt);}}}int l=0,r=n*m,mid;while(l<=r) { //二分答案(最小值最大)mid=(l+r)>>1;if(check(mid))l=mid+1,ans=mid;elser=mid-1;}printf("%d",ans);return 0;
}

仙人掌(cactus)

Time Limit:1000ms   Memory Limit:64MB

题目描述

LYK在冲刺清华集训（THUSC）！于是它开始研究仙人掌，它想来和你一起分享它最近研究的结果。如果在一个无向连通图中任意一条边至多属于一个简单环（简单环的定义为每个点至多经过一次），且不存在自环，我们称这个图为仙人掌。
LYK觉得仙人掌还是太简单了，于是它定义了属于自己的仙人掌。
定义一张图为美妙的仙人掌，当且仅当这张图是一个仙人掌且对于任意两个不同的点i,j，存在一条从i出发到j的路径，且经过的点的个数为|j-i|+1个。
给定一张n个点m条边且没有自环的图，LYK想知道美妙的仙人掌最多有多少条边。
数据保证整张图至少存在一个美妙的仙人掌。

输入格式(cactus.in)

第一行两个数n,m表示这张图的点数和边数。
接下来m行，每行两个数u,v表示存在一条连接u,v的无向边。

输出格式(cactus.out)

一个数表示答案

输入样例

4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例

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)。

思路:

　　暂时不填坑233

转载于:.html