P2163 水水淼题解

by 2021tyoi0037——2022-04-28 21:51:08

返回

我们把所有满足要求的真分数存到一个vector里，然后排序。 时间复杂度`O(n*n*log(n))` 什么？？？这么高的时间复杂度？？？ 莫慌，卡常安排上，秒A 下面放代码： （代码丑陋不堪，卡常手段有scanf,register,inline,O2,三目运算符） #pragma GCC optimize(2) #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include <cstdio> #include <algorithm> #include <vector> using namespace std; int n; struct node{ int a,b; }; vector<node> v; inline int gcd(int a,int b){ return (b==0)?a:gcd(b,a%b); } inline bool cmp(node a,node b){ return a.a*b.b<a.b*b.a; } int main(){ scanf("%d",&n); for(register int i=1;i<=n;i++){ for(register int j=1;j<i;j++){ if(gcd(i,j)==1){ v.push_back((node){j,i}); } } } sort(v.begin(),v.end(),cmp); printf("0/1\n"); for(int i=0;i<v.size();i++) printf("%d/%d\n",v[i].a,v[i].b); printf("1/1\n"); return 0; } 你看到这里了，那就悄悄告诉你，其实我的方法不是最优解， 只是一个投机取巧的方法，想看正解就建议看看题解

赞(8)

+1