9.17模拟赛

T1 巧克力棒

题目描述

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

具体地，这根巧克力棒长为

它打算每次将一根长为

LYK 想知道一根长度为

输入输出格式

输入格式：

第一行一个数

输出格式：

一个数表示答案。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于 $20\%20%的数据，n leq 5n≤5。$

对于 $50\%50%的数据，n leq 20n≤20。$

对于 $80\%80%的数据，n leq 2000n≤2000。$

对于 $100\%100%的数据，n leq 1000000000n≤1000000000。$

样例解释

将

获得

题解:

考试80分dp,计算局部最优值枚举断点取最大

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,f[2017];
int main(){
    freopen("chocolate.in","r",stdin);
    freopen("chocolate.out","w",stdout);
    scanf("%d",&n);
    f[1]=0;f[2]=1;f[3]=1;
    for(int i=4;i<=n;i++){
        for(int j=0;j<=i;j++){
            f[i]=max(f[i],f[j]+f[i-j]);
        }
        if(i%2==0)f[i]=max(f[i],f[i/2]*2+1);
    }
    printf("%d
",f[n]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

正解：贪心

发现最后肯定分成n个长度为1，要求有贡献，那么长度为1的一定是由长度为2的分来的，分成长度为2 想要有贡献必须从长度为4分来的，分成

长度为4想要有贡献必须分成长度为8的.....所以将巧克力棒分成2^k得到的结果更优。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,ans,js;
void dfs(long long n){
    if(n==1||n==0)return;
    long long i;
    for( i=1;i*2<=n;i*=2);
    ans+=i-1;
    dfs(n-i);
}
int main(){
    scanf("%lld",&n);
    dfs(n);
    cout<<ans<<endl;
    return 0;
}

T2 LYK 快跑！

题目描述

LYK 陷进了一个迷宫！这个迷宫是网格图形状的。 LYK 一开始在

而且这个迷宫里有很多怪兽，若第

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

输入输出格式

输入格式：

第一行两个数

接下来

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

输出格式：

一个数表示答案。

输入输出样例

输入样例#1：

输出样例#1：

说明

对于 $20\%20%的数据n=1n=1。$

对于 $40\%40%的数据n leq 2n≤2。$

对于 $60\%60%的数据n,m leq 10n,m≤10。$

对于 $80\%80%的数据n,m leq100n,m≤100。$

对于 $90\%90%的数据n,m leq 1000n,m≤1000。$

对于另外 $10\%10%的数据n,m leq 1000n,m≤1000且怪兽数量leq 100≤100。$

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m,cnt,ans,js;
int map[102][102],vis[102][102];
int mx[4]={0,1,0,-1},
    my[4]={1,0,-1,0};
    
struct WW{
    int x,y;
}w[10005];

struct T{
    int x,y,minl;
}s[50003];

int zs(int x){
    if(x<0)return -x;
    return x;
}

void slove(){
    queue<T>q;T s;s.x=1;s.y=1;s.minl=0x7fffffff;
    q.push(s);
    while(!q.empty()){
        T now;
        now=q.front();q.pop();
        vis[now.x][now.y]=0;
        int minl=0x7ffffff;
        for(int i=1;i<=cnt;i++){
            int xx=w[i].x,yy=w[i].y;
            minl=min(minl,zs(xx-now.x)+zs(yy-now.y));
        }
        if(minl<now.minl)now.minl=minl;js++;
        cout<<now.x<<" "<<now.y<<"  "<<now.minl<<endl;
        if(js==10){
            exit(0);
        }
        if(now.x==n&&now.y==m)ans=max(ans,now.minl);
        for(int i=0;i<4;i++){
            int xx=now.x+mx[i],yy=now.y+my[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
                vis[xx][yy]=1;
                q.push((T){xx,yy,now.minl});
            }
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            if(x)w[++cnt].x=i,w[cnt].y=j;
            if((i==1&&j==1&&x)||(i==n&&j==m&&x)||n==1){
                printf("0
");
                return 0;
            }
        }
    }
    slove();
    printf("%d
",ans);
    return 0;
}

正解：bfs预处理到每个非怪兽节点的最近的怪兽的距离，然后二分答案。

队列要开大点

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,l,r,ans,map[1002][1002],vis[1002][1002],qx[1000000],qy[1000000],b[1002][1002];
int mx[4]={0,1,-1,0},
    my[4]={1,0,0,-1};
int head=1,tail;
bool check(int limt){
    memset(vis,0,sizeof(vis));
    memset(qx,0,sizeof(qx));
    memset(qy,0,sizeof(qy));
    head=1;tail=0;
    qx[++tail]=1;qy[tail]=1;vis[1][1]=1;
    while(head<=tail){
        int nowx=qx[head],nowy=qy[head++];
        for(int i=0;i<4;i++){
            int xx=nowx+mx[i],yy=nowy+my[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&b[xx][yy]>=limt){
                qx[++tail]=xx;qy[tail]=yy;
                vis[xx][yy]=1;
            }
        }
    }
    return vis[n][m];
}
void bfs(){
    while(head<=tail){
        int nowx=qx[head],nowy=qy[head++];
        for(int i=0;i<4;i++){
            int xx=nowx+mx[i],yy=nowy+my[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]&&!b[xx][yy]&&!map[xx][yy]){
                b[xx][yy]=b[nowx][nowy]+1;
                vis[xx][yy]=1;
                qx[++tail]=xx;qy[tail]=yy;
            }
        }
    }
    l=0;r=n*m;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;l=mid+1;
        }
        else r=mid-1;
    }
    printf("%d
",ans);
}
int main(){
    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]){
                qx[++tail]=i;
                qy[tail]=j;
            }
        }
    }
    if(map[1][1]||map[n][m]||n==1){
        printf("0
");
        return 0;
    }
    bfs();
    return 0;
}

T3 仙人掌(cactus)

题目描述

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

qwq

如果在一个无向连通图中任意一条边至多属于一个简单环（简单环的定义为每个点至多经过一次），且不存在自环，我们称这个图为仙人掌。

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

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

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

输入输出格式

输入格式：

第一行两个数

接下来

输出格式：

一个数表示答案

输入输出样例

输入样例#1：

输出样例#1：

说明

对于 $20\%20%的数据n leq 3n≤3。$

对于 $40\%40%的数据n leq 5n≤5。$

对于 $60\%60%的数据n leq 8n≤8。$

对于 $80\%80%的数据n leq 1000n≤1000。$

对于 $100\%100%的数据n leq 100000n≤100000且m leq min(200000,n*(n-1)/2)m≤min(200000,n∗(n−1)/2)。$

样例解释

选择边

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int main(){
    freopen("cactus.in","r",stdin);
    freopen("cactus.out","w",stdout);
    scanf("%d",&n);
    printf("%d
",n);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

正解：由于i--j满足节点数等于|i-j|+1,那么i和i+1一定由一条边直接连着，剩下的边用线段覆盖解决。

#include<cstdio>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,m,cnt;
struct node{
    int u,v;
    bool operator < (const node &x)const{
        return v<x.v;
    }
}e[maxn*2];
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;
}
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
",sum+n-1);
    return 0;
}