第一次做这种比赛，被自己坑的好惨。。。
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==0)puts(f<=d?"YES":"NO"); else if(d%l==0)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+1)/ku+((a+1)%ku!=0); puts(ti*ku>=(ll)l?"YES":"NO"); } } return 0; }
B.被自己的愚蠢坑死了
用gets()得到的01字符串最后是' '不是'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=550; 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*10]; int up1[N*N],down1[N*N],left1[N*N],right1[N*N]; const int dire[5][2]={{0,-1},{0,1},{1,0},{-1,0},{0,0}}; 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=0,fron=0; 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=0;i<4;i++) { int nrow=now.first+dire[i][0],ncol=now.second+dire[i][1]; if(nrow<=0 || nrow>h || ncol<=0 && ncol>w)continue; if(vis[nrow][ncol]==g)continue; if(mar[nrow][ncol]!='1')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,'0',sizeof(mar)); memset(vis,0,sizeof(vis)); scanf("%d%d",&h,&w);getchar(); int cnt=0; for(i=1;i<=h;i++) { gets(mar[i]+1); } for(j=1;j<=w;j++) { for(i=1;i<=h;i++) { if(vis[i][j]==0 && mar[i][j]=='1') { bfs(++cnt,i,j); printf("%d %d ",down1[cnt]-up1[cnt]+1,right1[cnt]-left1[cnt]+1); 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 0; }
C.D.?场上没做，之后研究之后出题解吧