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;
}