hihocoder [Offer收割]编程练习赛8

时间：2025-01-09 13:35:56

第一次做这种比赛，被自己坑的好惨。。。

A.这道题的关键其实是如果有k和n满足kD+F>nL>kD则不能走无限远，分支看似难整理，其实比较简单，F>L根本就不用算了，明摆着就是Bsi强迫症的

L和D有倍数约数关系的也比较简单

剩下的就可以规约为kD%L>L-F，如果有k能让此式成立，那强迫症就被Bsi。

注意到kD%L的排布有倍数规律，一定是gcd(D,L-D)的倍数

然后求模数是否能到达L-F就是了

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

typedef long long ll;

int main()

{

    int t,f,l,d;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d%d",&l,&f,&d);

        if(l%d==)puts(f<=d?"YES":"NO");

        else if(d%l==)puts(f<=l?"YES":"NO");

        else if(f>l)puts("NO");

        else

        {

            d=d%l;

            int a=l-f;

            int my=l-d;

            ll ku=__gcd(d,my);

            ll ti=(a+)/ku+((a+)%ku!=);

            puts(ti*ku>=(ll)l?"YES":"NO");

        }

    }

    return ;

}

B.被自己的愚蠢坑死了

用gets()得到的01字符串最后是'\0'不是'0'，判定是否可达这么写：=='0'就不进去，结果答案多了一条最右边的。。。

联通分量最大可达500*500/2，但是储存序号用的char，导致程序遍历了不该遍历的，因为用的pair<>，出错信息难定位，换做struct pair才发现

还有最后要先列后行循环，我却像往常一样先行后列循环，结果顺序错误

其实本题没有什么太多的坑点，只是联通分量加01矩阵，输出联通分量时不要输出此时间戳以外的分量就是了

///O(n)做法

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<ctime>

using namespace std;

typedef long long ll;

const int N=;

char mar[N][N];

int vis[N][N];

int h,w;

typedef struct mypair

{

    int first,second;

    mypair(int a,int b){first=a,second=b;}

    mypair(){}

    mypair(mypair& a){first=a.first;second=a.second;}

}mypair;

mypair queue[N*N*];

int up1[N*N],down1[N*N],left1[N*N],right1[N*N];

const int dire[][]={{,-},{,},{,},{-,},{,}};

int max(int a,int b){return a>b?a:b;}

int min(int a,int b){return a<b?a:b;}

void bfs(int g,int row,int col)

{

    int rear=,fron=;

    queue[rear++]=mypair(row,col);

    up1[g]=down1[g]=row;

    left1[g]=right1[g]=col;

    vis[row][col]=g;

    while(fron<rear)

    {

        mypair now=queue[fron++];

        for(int i=;i<;i++)

        {

            int nrow=now.first+dire[i][],ncol=now.second+dire[i][];

            if(nrow<= || nrow>h || ncol<= && ncol>w)continue;

            if(vis[nrow][ncol]==g)continue;

            if(mar[nrow][ncol]!='')continue;

            queue[rear++]=mypair(nrow,ncol);

            up1[g]=min(up1[g],nrow);

            down1[g]=max(down1[g],nrow);

            left1[g]=min(left1[g],ncol);

            right1[g]=max(right1[g],ncol);

            vis[nrow][ncol]=g;

        }

    }

}

int main()

{

    int te,i,j;

    memset(mar,'',sizeof(mar));

    memset(vis,,sizeof(vis));

    scanf("%d%d",&h,&w);getchar();

    int cnt=;

    for(i=;i<=h;i++)

    {

        gets(mar[i]+);

    }

    for(j=;j<=w;j++)

    {

        for(i=;i<=h;i++)

        {

            if(vis[i][j]== && mar[i][j]=='')

            {

                bfs(++cnt,i,j);

                printf("%d %d\n",down1[cnt]-up1[cnt]+,right1[cnt]-left1[cnt]+);

                for(int ai=up1[cnt];ai<=down1[cnt];ai++)

                {

                    for(int aj=left1[cnt];aj<=right1[cnt];aj++)

                    {

                        printf("%d",vis[ai][aj]==cnt);

                    }

                    puts("");

                }

            }

        }

    }

    return ;

}

C.D.?场上没做，之后研究之后出题解吧

相关文章