巧克力棒(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 点成就感。

 结论没推出来 Dfs+map 不过还是0ms

#include
      
       #include
       
        #include
        
         #include
         
        
       
      

 

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。

bfs

#include
      
       #include
       
        #include
        
         #define pa pair
         
          #define mk make_pair#define X first#define Y second#define maxn 1010using namespace std;int n,m,k,ans,g[maxn][maxn],s[maxn][maxn],f[maxn][maxn];queue
          
           q;int xx[4]={
    0,0,1,-1};int yy[4]={
    1,-1,0,0};int init(){    int x=0,f=1;char s=getchar();    while(s<'0'||s>'9'){
    if(s=='-')f=-1;s=getchar();}    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}    return x*f;}bool Judge(int S){    if(s[1][1]
           
            =1&&nx<=n&&ny>=1&&ny<=m&&f[nx][ny]==0&&s[nx][ny]>=S){ f[nx][ny]=1;q.push(mk(nx,ny)); } } } return 0;}int main(){ freopen("run.in","r",stdin); freopen("run.out","w",stdout); n=init();m=init(); memset(s,127/3,sizeof(s)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ g[i][j]=init(); if(g[i][j]){ q.push(mk(i,j)); s[i][j]=0;f[i][j]=1; } } if(g[1][1]==1||g[n][m]==1){ printf("0\n");return 0; } while(!q.empty()){ int x=q.front().X; int y=q.front().Y; q.pop(); for(int i=0;i<4;i++){ int nx=x+xx[i]; int ny=y+yy[i]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&f[nx][ny]==0){ s[nx][ny]=min(s[nx][ny],s[x][y]+1); f[nx][ny]=1;q.push(mk(nx,ny)); } } } int l=0,r=n*m; while(l<=r){ int mid=l+r>>1; if(Judge(mid)){ l=mid+1;ans=mid; } else r=mid-1; } printf("%d\n",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)。

考试的时候骗了40 2333

正解比较裸

/*飘渺的题意....美妙的仙人掌包含了1-n所有的点题目中要求任意ij满足条件 那么每个i和i+1一定先连边这里的ij是整张图的ij 不是仅仅包括仙人掌的哪一坨那1-n就构成了一条链 考虑剩下的边 每连两条 u1u2 v1v2看做两端区间 如果重叠的话 就不是仙人掌了也就是说 先保证满足条件 （连成一条链）然后选尽量多的边就成了线段覆盖*/#include
      
       #include
       
        #define maxn 100010using namespace std;int n,m,cnt;struct node{    int u,v;    bool operator < (const node &x)const{        return v
        
         '9'){
    if(s=='-')f=-1;s=getchar();}    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}    return x*f;}int main(){    freopen("cactus.in","r",stdin);    freopen("cactus.out","w",stdout);    n=init();m=init();    int u,v;    for(int i=1;i<=m;i++){        u=init();v=init();        if(u>v)swap(u,v);        if(u!=v-1){                e[++cnt].u=u;e[cnt].v=v;        }    }    sort(e+1,e+1+cnt);    int r=0,sum=0;    for(int i=1;i<=cnt;i++)        if(e[i].u>=r){            sum++;r=e[i].v;        }    printf("%d\n",sum+n-1);    return 0;}