关于Wdoi第一题的问题
  • 板块学术版
  • 楼主数学小王子
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/18 18:34
  • 上次更新2023/11/4 10:10:56
查看原帖
关于Wdoi第一题的问题
367146
数学小王子楼主2021/8/18 18:34

RT,求助

#include<iostream>
#include<cstdio>
#define N 1000005
#define int unsigned long long
using namespace std;
struct Node{
	int t;
	int x;
	int y;
}arr[N];
int n,k,minn=0x3f3f3f3f3f3f3f3f,tmp,tmp2;
inline int read(){
	int ans=0,sym=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')sym=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
	return ans*sym;
}
int gcd(int x,int y){
	if(y==0)return x;
	return gcd(y,x%y);
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=k;i++){
		arr[i].t=read();
		arr[i].x=read();
		arr[i].y=read();
		arr[i].x%=n;
		arr[i].y%=n;
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			tmp=arr[i].t*arr[j].t/gcd(arr[i].t,arr[j].t);
			for(int tmp2=tmp;tmp2<=n;tmp2+=tmp){
				if((arr[i].x+(tmp2/arr[i].t-1)*arr[i].y)%n==(arr[j].x+(tmp2/arr[j].t-1)*arr[j].y)%n)continue;
				minn=min(minn,tmp2);
				break;
			}
		}
	}
	if(minn!=0x3f3f3f3f3f3f3f3f)cout<<minn-1;
	else cout<<"Mystia will cook forever...";
	return 0;
}

这份代码只有10分,会WA很多个点。但是如果把for循环改成while循环,如下:

#include<iostream>
#include<cstdio>
#define N 1000005
#define int unsigned long long
using namespace std;
struct Node{
	int t;
	int x;
	int y;
}arr[N];
int n,k,minn=0x3f3f3f3f3f3f3f3f,tmp,tmp2;
inline int read(){
	int ans=0,sym=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')sym=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
	return ans*sym;
}
int gcd(int x,int y){
	if(y==0)return x;
	return gcd(y,x%y);
}
signed main(){
	n=read(),k=read();
	for(int i=1;i<=k;i++){
		arr[i].t=read();
		arr[i].x=read();
		arr[i].y=read();
		arr[i].x%=n;
		arr[i].y%=n;
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			tmp2=0;
			tmp=arr[i].t*arr[j].t/gcd(arr[i].t,arr[j].t);
			while(tmp2<=n){
				tmp2+=tmp;
				if((arr[i].x+(tmp2/arr[i].t-1)*arr[i].y)%n==(arr[j].x+(tmp2/arr[j].t-1)*arr[j].y)%n)continue;
				minn=min(minn,tmp2);
				break;
			}
		}
	}
	if(minn!=0x3f3f3f3f3f3f3f3f)cout<<minn-1;
	else cout<<"Mystia will cook forever...";
	return 0;
}

就可以AC。这两份代码不是一样的吗,人都傻了

2021/8/18 18:34
加载中...