巧克力棒(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()) { //求v cur=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; else r=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