Problem #2957 - ECNU Online Judge

Li Dao

7 年，6 月前

关键是如何去重
本来是想把分数最为一个有序二元组放入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;
}

回复 1 0

Twisted9

4 年，6 月前

朴实无华

include

using namespace std;

int GCD(int a,int b)
{
return b==0?a:GCD(b,a%b);
}
int main()
{
int a,n,T;
set S;
cin >> T;

for(int i = 0;i < T;i++)
{
    cin >> n;
    for(int j = 0;j < n;j++)
    {
        cin >> a;
        S.insert(a);
    }
    int ans = 0;
    while(S.size() > 1)
    {
        auto p = S.begin();
        int t = *p;
        S.erase(p);
        for(auto x : S)
        {
            if(GCD(x,t) == 1)
                ans++;
        }

    }
    cout << "case #" << i << ":" << endl;
    cout << ans << endl;
    S.clear();
}

}

回复 1 0

Andrew-Malcom

3 年，10 月前

#include<bits/stdc++.h>
using namespace std;
set<int>S;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
    int T;cin>>T;
    for(int i=0;i<T;i++){
        int n;cin>>n;
        for(int _=0;_<n;_++){
            int num;cin>>num;
            S.insert(num);
        }
        int ans=0;
        while(S.size()>1){
            set<int>::iterator it=S.begin();
            int p = *it;
            it++;
            for(;it!=S.end();it++){
                if(gcd(p,*it)==1){
                    ans++;
                }   
            }
            S.erase(p);
        }
        cout<<"case #"<<i<<":\n"<<ans<<endl;
        S.clear();
    }
}

回复 1 0

10165101104

7 年，4 月前

这题差点做哭了，N个超时，N个wa；

回复 0 0

10175102262 LarsPendragon

6 年，6 月前

这题其实就是排序去重。本来以为题目要求的最简真分数指的是化简，后来发现不对，是要求本身就是最简。于是这道题就更简单了……
附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;
}

回复 0 0

Fifnmar

4 年，10 月前

很多同学以为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';
    }
}

回复 0 0

CCXXXI_

4 年，10 月前

[已删除]

Fifnmar

4 年，10 月前

你说得很有道理

（点赞）

回复 0 0

Commando

2 年，10 月前

#include <bits/stdc++.h>

using namespace std;

int solve(const set<int>& s) {
    int res = 0;
    for (auto i = s.begin(); i != s.end(); ++i) {
        for (auto j = next(i); j != s.end(); ++j) {
            int m = *i, n = *j;
            if (m < n && gcd(m, n) == 1) ++res;
        }
    }
    return res;
}

int main() {
    int T, N, num, n = 0;

    cin >> T;
    while (T--) {
        cin >> N;

        set<int> s;
        while (N--) cin >> num, s.insert(num);
        printf("case #%d:\n%d\n", n++, solve(s));
    }
}

回复 0 0

Master X

6 年，5 月前

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

回复 0 0

speen123

4 年，6 月前

思路：
1.首先使用set集合来自动位元素去重以及从小到大进行排序。
2.使用 getgcd求两个元素之间的最大公约数，若最大公约数为1则表示两者可以组成最简真分数。
3.遍历整个set元素，规则是从前往后元素进行配对。

include

using namespace std;

int getgcd(int a,int b){
int gcd;
int t1,t2;
t1 = a;
t2 = b;
gcd = t1 % t2;
while(gcd != 0){
t1 = t2;
t2 = gcd;
gcd = t1 % t2;
}
return t2;
}

int main()
{
int T = 0;
int n = 0;
int num = 0;
int count = 0;
set number_set;
scanf(“%d”,&T);
for(int i = 0;i < T;i++){
count = 0;
number_set.clear();
scanf(“%d”,&n);
for(int j = 0 ;j < n;j++){
scanf(“%d”,&num);
number_set.insert(num);
}

    for(set<int>::iterator iter_i = number_set.begin(); iter_i != number_set.end();iter_i++){
        for(set<int>::iterator iter_j = iter_i;iter_j != number_set.end();iter_j++){
            if(iter_i != iter_j){
                if(getgcd(*iter_i,*iter_j) == 1){
                    count++;
                }
            }
        }
    }
    printf("case #%d:\n",i);
    printf("%d\n",count);
}
return 0;

}

回复 0 0

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

include

include

include

include

include

服务

开源

关于我们