蓝桥杯省赛2013 带分数

小灰灰 2024-03-30 12:05 109阅读 0赞

[P8599 \[蓝桥杯 2013 省 B\] 带分数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P8599 _ 2013 _ B_ _ - _ _ _ _luogu.com.cn]

题意：

![dd7200ee6d4a40409724229232739246.png][]

思路：

看到数据范围，可以想到纯暴力枚举

先去枚举整数部分，再去枚举全排列来把分数组合枚举出来，遇到满足条件的就统计答案

**坑点：**

**对于同一个整数部分，可能有多个分数的组合！！**

**整数部分不能含有0，且数位不能有重复！！**

不懂，为什么一旦有坑我就能准确无误地跳进坑里，十分钟写完题，一小时调样例，最后才发现有这俩坑....

所以写完程序第一件事就是去读几遍题和读几遍程序，一句一句读，万无一失了再交qwq

Code：

#include <bits/stdc++.h>
    using namespace std;
    map<int,int> mp;
    vector<int> v;
    int n,ans=0;
    int calc(int p){
        int s1=0,s2=0;
        for(int i=0;i<=p;i++) s1=s1*10+v[i];
        for(int i=p+1;i<=v.size()-1;i++) s2=s2*10+v[i];
        if(s1%s2!=0) return -1;
        return s1/s2;
    }
    void init(){
        mp.clear(),v.clear();
    }
    int check(int x){
        int cnt=0;
        init();
        string t=to_string(x);
        int res=n-x;
        for(int i=0;i<t.size();i++) mp[t[i]-'0']=1;
        for(int i=1;i<=9;i++){
            if(!mp[i]) v.push_back(i);
        }
        sort(v.begin(),v.end());
        do{
            for(int i=0;i<=v.size()-2;i++){
                if(calc(i)==res) cnt++;
            }
        }while(next_permutation(v.begin(),v.end()));
        return cnt;
    }
    bool check2(int x){
        string s=to_string(x);
        map<int,int> w;
        for(int i=0;i<s.size();i++){
            if(s[i]=='0') return false;
            if(w[s[i]]) return false;
            w[s[i]]=1;
        }
        return true;
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n-1;i++){
            if(!check2(i)) continue;
            ans+=check(i);
            //if(check(i)) cout<<i<<'\n';
        }
        cout<<ans<<'\n';
    }

[P8599 _ 2013 _ B_ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P8599
[dd7200ee6d4a40409724229232739246.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9490ed7f8bb84686a36a21afa760e73b.png