【题解】2019年安徽大学ACM/ICPC实验室新生赛（公开赛）

川长思鸟来 2023-06-19 05:27 14阅读 0赞

### 文章目录 ###

*  A - 素数分布（模拟）
 *  B - 食物分配（思维）
 *  C - AHUICPC (Easy Version)（构造）
 *  D - 不定方程（思维）
 *  E - 蕊蕊识数（思维）
 *  F - 蕊蕊乘车去上学（数学）
 *  G - AHUICPC (Hard Version)（思维）
 *  H - 无尽大军（数学）

# A - 素数分布（模拟） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/A][https_ac.nowcoder.com_acm_contest_2720_A]

*  **思路：** 数据范围很小，直接暴力判断是否为素数，然后计算素数的数目即可。

**Code（C++）：**

#include <iostream>
    using namespace std;
    bool isprime(int x){ 
        for(int i=2;i*i<=x;i++){ 
            if(x%i==0)   
               return false;
        }
        return true;
    }
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            int n;    cin>>n;
            int ans=0;
            for(int i=2;i<=n;i++){ 
                if(isprime(i))
                    ans++;
            }
            cout<<ans<<endl;
        }
        return 0;
    }

# B - 食物分配（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/B][https_ac.nowcoder.com_acm_contest_2720_B]

*  **题意：** 给定四个正整数，判断这四个正整数能否恰好被划分成三组，每一组数的和相等且每个正整数不可拆分。
 *  **思路：** 四个数划分为三组，肯定有两组数不需要划分，由单个数组成，剩下的两个数划分为一组，所以如果满足划分条件，必然有 A+B=C 且 C=D（A≤B≤C≤D）。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int main() { 
        int t;    cin>>t;
        while(t--){ 
            int a[5];
            cin>>a[1]>>a[2]>>a[3]>>a[4];
            sort(a+1,a+5);
            if(a[3]==a[4] && a[1]+a[2]==a[3])
                cout<<a[3]<<endl;
            else
                cout<<-1<<endl;
        }
        return 0;
    }

# C - AHUICPC (Easy Version)（构造） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/C][https_ac.nowcoder.com_acm_contest_2720_C]

*  **题意：** 构造题，求子序列 “AHUICPC” 数目为 n 的字符串。
 *  **思路：** 该题数据太小了，1 ≤ n ≤ 10，字符串长度不超过15，又 “AHUICPC” 长度为 7，所以如果只有 n 等于 10 的情况下暴力构造字符串长度会超出 15，可以分两种请况，n 为 1 ~ 9 和 10，分别暴力构造即可。

**Code（C++）：**

#include <iostream>
    using namespace std;
    int main() { 
        int n;    cin >> n;
        if (n <= 9) { 
            for (int i = 0; i < n; i++) cout << 'A';
            cout << "HUICPC\n";
        } else { 
            cout << "AAHHHHHUICPC\n";
        }
        return 0;
    }

# D - 不定方程（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/D][https_ac.nowcoder.com_acm_contest_2720_D]

*  **思路：** 由 c = ax = by，可知 cmin 为 a、b 的最小公倍数 a\*b / gcd(a,b) ，所以 x = b / gcd(a,b) ，y = a / gcd(a,b) ，即 x 和 y 是互质的，也就是他们的公约数为 1 ，那么我们只需要判断 x 和 y 的最小公约数是否为 1 即可。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    #define ll long long 
    using namespace std;
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            ll x,y;    cin>>x>>y;
            if(__gcd(x,y)>1)    cout<<-1<<endl;
            else    cout<<y<<" "<<x<<" "<<x*y<<endl;
        }
        return 0;
    }

# E - 蕊蕊识数（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/E][https_ac.nowcoder.com_acm_contest_2720_E]

*  **题意：** 将 n 的每一个位数相加起来得到一个新的数，一直重复这个操作直到只剩下一个位数，这个过程会产生很多个数，问是否存在一个数 m 能整除所产生的所有数，并且 m 要尽可能小且大于 1 。
 *  **思路：**

1.  用 ai 表示十进制数的各个数位，那么任意十进制非负整数都可以表示成 ∑ai \* 10k 的多项式形式。因为对于任意的 10k (k ≥ 0 且为整数)，其被3除的余数都是1，因此 a \* 10k 和 a 对3同余。所以任意十进制非负整数被3除的余数，都等于将它的各个十进制位的数相加后被3除的余数。
2.  由上所述可知 3 满足所有情况，那么比 3 小且比 1 大的就只有 2 了，所以只需要判断 2 是否满足，不满足的话直接输出 3 就可以了。

**Code（C++）：**

#include <iostream>
    #include <cstring>
    using namespace std;
    int main(){ 
        int t;    cin>>t;
        while(t--){ 
            string str;    cin>>str;
            int num=0,len=str.length();
            for(int i=0;i<len;i++)   
                num+=(str[i]-'0');
            int k=(str[len-1]-'0')%2;   
            int vis=1;   
            while(num>=10){    
                if(num%2!=k){     
                    vis=0;
                    break;
                }
                str=to_string(num);  
                num=0;    
                for(int i=0;i<str.length();i++)
                    num+=(str[i]-'0');
            }
            if(vis && num%2 == k)   
                cout<<2<<endl;
            else
                cout<<3<<endl;
        }
        return 0;
    }

# F - 蕊蕊乘车去上学（数学） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/F][https_ac.nowcoder.com_acm_contest_2720_F]

*  **思路：** 每分钟就有一名乘客等车，问乘客排队的平均队伍长度，其实就是要求等车时间的数学期望（数学渣渣的我）。设 pa 表示遇到发车间隔为 a 的公交车的概率，pb 表示遇到发车间隔为 b 的公交车的概率，那么该数学期望就是 pa\* a + pb \* b 。又因为两车发车间隔出现的可能性是相等的，所以遇到发车时间是 a 的公交的概率是 a / (a+b) ，遇到发车时间是 b 的公交的概率是 b / (a+b) ，那么数学期望就是 (a \* a + b \* b) / (a + b) 。

**Code（C++）：**

#include <iostream>
    #include <iomanip>
    using namespace std;
    int main(){ 
        int a,b;    cin>>a>>b;
        cout<<fixed<<setprecision(2)<<(double)(a*a+b*b)/(a+b)<<endl;
        return 0;
    }

# G - AHUICPC (Hard Version)（思维） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/G][https_ac.nowcoder.com_acm_contest_2720_G]

*  **思路：** 先构造出所有的恰好有 ai \* bi 个 “AH” 的字符串，然后在其后面再构造 n - ai \* bi 个 ‘A’ 字符，最后面再接字符串 “HUICPC”，这两段构造成的 “AHUICPC” 字符串数目相加即为 n 。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int main(){ 
        int n;    cin>>n;
        int p=sqrt(n);
        int n1=p, n2=p;
        int x=n-p*p;
        if(x>=p)    x-=p,n1++;
        for(int i=1;i<=n1;i++)    cout<<'A';
        for(int i=1;i<n2;i++)    cout<<'H';    //后面还有一个H，故这里要少一个
        for(int i=1;i<=x;i++)    cout<<'A';
        cout<<"HUICPC"<<endl;
        return 0;
    }

# H - 无尽大军（数学） #

> **原题链接：**[https://ac.nowcoder.com/acm/contest/2720/H][https_ac.nowcoder.com_acm_contest_2720_H]

*  **思路：**

1.  这道题感觉就是考你的题目理解能力和数学能力。对于起始的队伍只有 1 个士兵，可以消耗2使其翻倍，即乘以2。然后既可以选择消耗 2 使其再乘以2，也可以消耗 1 使得上一次乘以 x 的操作变为乘以 x+1（为什么是 x，因为不断进行此操作的话就不断加 k ，也就是在第一次操作时乘以 2，后面的操作乘以的数就是上个数 +1 ）。
2.  所以其实就是一个等式 a1 \* a2 \* a3 \* … \* am = n （最小的 ai 为 2 ）。要使消耗的最小，a1 、a2 、a3 、… 、am 就都是 n 的质因数。所以答案其实就是 n 的所有质因数之和。

**Code（C++）：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        ll n;    cin>>n;
        ll ans=0;
        for(ll i=2;i*i<=n;i++){     //这里的i也要·定义为long long型的
            while(n%i==0){ 
                ans+=i;
                n/=i;
            }
        }
        if(n>1)    ans+=n;
        cout<<ans<<endl;
        return 0;
    }

[https_ac.nowcoder.com_acm_contest_2720_A]: https://ac.nowcoder.com/acm/contest/2720/A
[https_ac.nowcoder.com_acm_contest_2720_B]: https://ac.nowcoder.com/acm/contest/2720/B
[https_ac.nowcoder.com_acm_contest_2720_C]: https://ac.nowcoder.com/acm/contest/2720/C
[https_ac.nowcoder.com_acm_contest_2720_D]: https://ac.nowcoder.com/acm/contest/2720/D
[https_ac.nowcoder.com_acm_contest_2720_E]: https://ac.nowcoder.com/acm/contest/2720/E
[https_ac.nowcoder.com_acm_contest_2720_F]: https://ac.nowcoder.com/acm/contest/2720/F
[https_ac.nowcoder.com_acm_contest_2720_G]: https://ac.nowcoder.com/acm/contest/2720/G
[https_ac.nowcoder.com_acm_contest_2720_H]: https://ac.nowcoder.com/acm/contest/2720/H