2957. 统计不同的最简真分数的个数

Li Dao

关键是如何去重
本来是想把分数最为一个有序二元组放入set中,重载小于运算符,set自带去重,但是速度太慢超时了。

超时代码如下:

include

using namespace std;
int T,n;
int a[1010];
struct Point
{
int xx,yy;
bool operator<(const Point& bb) const
{
if(xx!=bb.xx) return xx S;
int gcd(int aa,int bb)
{
if(aa=bb) return 0;
return 1;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
S.clear();
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(ok(a[i],a[j])) S.insert((Point){a[i],a[j]});
if(ok(a[j],a[i])) S.insert((Point){a[j],a[i]});
}
printf(“case #%d:\n%d\n”,step,S.size());
}
return 0;
}

后来发现,只要先把n个数排序,去重,这n个数没有重复了,产生的分数也不会重复
而且因为都是最简分数,不会出现1/2=2/4重复的情况

代码如下:

include

using namespace std;
int T,n;
vector a,b;

int gcd(int aa,int bb)
{
if(aa=bb) return 0;
return 1;
}
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
int ans=0;
a.clear();
for(int i=1;i<=n;i++)
{
int xx;
cin>>xx;
a.push_back(xx);
}
sort(a.begin(),a.end());
b.clear();
unique_copy(a.begin(),a.end(),back_inserter(b));
for(int i=0;i<b.size();i++)
for(int j=i+1;j<b.size();j++)
{
if(ok(b[i],b[j])) ++ans;
if(ok(b[j],b[i])) ++ans;
}
printf(“case #%d:\n%d\n”,step,ans);
}
return 0;
}

Master X

就是排序去重,你想想既然互质直接最简,又没有重复呀。
当然你想挑战EOJ的速度也行……

10165101104

这题差点做哭了,N个超时,N个wa;

10175102262 LarsPendragon

这题其实就是排序去重。本来以为题目要求的最简真分数指的是化简,后来发现不对,是要求本身就是最简。于是这道题就更简单了……
附C代码:

#include <stdio.h>
#include <stdlib.h>
int gcd(int a, int b)
{
    if(a%b) return gcd(b,a%b);
    else return b;
}
int cmp(const void*a, const void*b)
{
    int *p1=(int*)a, *p2=(int*)b;
    return *p1-*p2;
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, j, x, num[1000], cnt=0;
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d",&num[i]);
            for(j=0; j<i; j++) if(num[j]==num[i]) {n--; i--; break;}
        }
        qsort(num, n, sizeof(int), cmp);
        for(i=0; i<n-1; i++)
            for(j=i+1; j<n; j++)
            {
                if(!(num[i]-num[j])) continue;
                x=gcd(num[j], num[i]);
                if(x==1) cnt++;
            }
        printf("case #%d:\n%d\n",I,cnt);
    }
    return 0;
}
Deuchie

很多同学以为C++不如Python Java 等语言好写,虽然有一定正确的地方,但还有可能是没有了解C++的STL。

不久C++20就出来了,那时候C++将成为真正好写又好用的语言。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>

using namespace std;

struct Fraction {
    int numerator;
    int denominator;
    bool operator<(Fraction const &frac) const {
        return numerator * frac.denominator < frac.numerator * denominator;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        set<Fraction> pool;
        vector<int> nums(n);
        for (auto &i : nums)
            cin >> i;
        sort(nums.begin(), nums.end());
        for (int j = 0; j < n; ++j)
            for (int k = j + 1; k < n; ++k)
                if (gcd(nums[k], nums[j]) == 1)
                    pool.insert({nums[j], nums[k]});
        pool.erase({1, 1});
        cout << "case #" << i << ":\n" << pool.size() << '\n';
    }
}
CCXXXI_

这复杂度不是靠STL或者C++20的新特性能消去的,很多地方是在以编写者的时间换计算机的时间;要是什么时候c++有Python Java 等语言好写——那它跑起来一定和后者一样慢

既然指名python来比较,那就上代码看一下

这是c++在开始输入之前需要做的准备:

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>

using namespace std;

struct Fraction {
    int numerator;
    int denominator;
    bool operator<(Fraction const &frac) const {
        return numerator * frac.denominator < frac.numerator * denominator;
    }
};

int main() {
    ios::sync_with_stdio(false);

然后,这是py在开始输入之前需要做的准备:

from math import gcd

这是c++输入数据并预处理的过程:

    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        set<Fraction> pool;
        vector<int> nums(n);
        for (auto &i : nums)
            cin >> i;
        sort(nums.begin(), nums.end());

这是py输入数据并预处理的过程:

T = int(input())
for I in range(T):
    input()
    lst = list({int(a) for a in input().split()})

后面计数部分都是两层循环并调用自带的gcd,复杂程度相差无几;

c++功能之强大,应用范围之广泛,运行效率之高,注定它不可能和python这种追求Beautiful、Simple、Readable的东西比好写;

最后,语言只是工具;用电锯砍树,用瑞士军刀开罐头,这是合适的;但要是手上只有把瑞士军刀,就算是带了木锯的升级款,想用它砍树也必然是不如电锯好用的.

Deuchie

你说得很有道理

(点赞)

你当前正在回复 博客/题目
存在问题!