洛谷上AC,UVA上WA求助
查看原帖
洛谷上AC,UVA上WA求助
443675
紊莫turtle楼主2023/1/3 07:20

P1763 的AC代码到UVA上就WA? 可能是行末空格/换行的问题吗?或者其他【】错误。
大佬尽情喷。

//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define int long long
using namespace std;

inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(int x){write(x);putchar('\n');}
inline void writesp(int x){write(x);putchar(' ');}
inline int lowbit(int x) {return x&(-x);}
int a,b,m,flag;
vector<int> ans,now;
unordered_map<int,int> cannot_be_used;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
void dfs(int p,int last,int fz,int fm)
{
	if(p==m) {
		int x=fz,q=fm,g=gcd(x,q);
		x/=g,q/=g;
		if(x==1&&q>last){
			now.push_back(q);
			if(flag){
				for(int i=m-1;i>=0;i--){
					if(now[i]<ans[i]){ans=now;now.pop_back();return ;}
					else if(now[i]>ans[i]){
						now.pop_back();
						return ;
					}
				}
			}
			if(!flag){
				flag=1;ans=now;
			}
			now.pop_back();
			return ;
		}
		return ;
	}
	for(int i=max(last+1,fm/fz+1);i<=ceil(fm*1.0*(m-p+1)/fz);i++){
		if(cannot_be_used[i]) continue;
		int x=fz*i-fm,y=fm*i,g=gcd(x,y);
		x/=g;y/=g;
		now.push_back(i);
		dfs(p+1,i,x,y);
		now.pop_back();
	}
}
signed main(){
	int T=read(),ca=0;
	while(T--){
		flag=0;
		a=read(),b=read();
		printf("Case %d: %d/%d=",++ca,a,b);
		int k=read();
		cannot_be_used.clear();
		while(k--) cannot_be_used[read()]=1;
		ans.clear();now.clear();
		for(m=1;!flag;m++)
		{
			dfs(1,0,a,b);
			if(flag) break;
		}
		for(int i=0;i<ans.size()-1;i++) printf("%d/%d+",1,ans[i]);
		printf("%d/%d",1,ans[ans.size()-1]);
		if(T) printf("\n");  
	}
    return 0;
}

2023/1/3 07:20
加载中...