2020 乐山师范学院程序设计大赛题解

比赛链接
交题要在题库搜索对应的题才能交

总结：

心态爆炸！！！

被 $F$ 卡 $int$

被 $C$ 卡$INF$

算完 $E$ 的复杂度不敢写

心态爆炸

A: 好数对

题意：

给定一个长度为 $n$ 的 $a$ 数组， 如果存在一个下标 $i,j,i<j$ 并且 $a[i]==a[j]$，就是好数对。求有多少个这样的数对

思路：

各种方法都行，直接通过下标计数法快速计算

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int cnt[maxn];

int main()
{
    IOS();
    int n;
    ll ans = 0;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ans += cnt[x];
        ++cnt[x];
    }
    cout << ans << endl;
    
    return 0;
}

B: 设计网页

题意：

给定一个 $n$， 问是否能找到 $a\ast b==n,a>1,b>1$，

思路：

直接判断 $n$ 是不是素数，因为素数的因子只有 $1$ 和本身

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    int flag = 1;
    for(int i = 2; i*i <= n; ++i)
        if(n % i == 0) {
            flag = 0;
            break;
        }
    if(flag == 1) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

C: 最大乘积

题意：

给定长度为 $n$ 的数组，问选 $5$ 个数相乘最大可以的结果是多少

思路：

其实是分情况讨论，但分情况讨论写起来很麻烦，直接暴力就

将数组从小到大排序，

前面选 $0$ 个, 后面选 $5$个

前面选 $1$ 个, 后面选 $4$个

前面选 $2$ 个, 后面选 $3$个

…

前面选 $5$ 个, 后面选 $0$个

所有结果选一个最大值即可

数据范围超出了 $int$，

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

ll num[maxn];

int main()
{
    IOS();
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        for(int i = 0; i < n; ++i)
            cin >> num[i];
        sort(num, num+n);
        ll ans = -INF;
        for(int i = 0; i <= 5; ++i) {
            ll sum = 1;
            for(int j = 0; j < i; ++j)
                sum *= num[j];
            for(int j = n-5+i; j < n; ++j)
                sum *= num[j];
            ans = max(ans, sum);
        }
        cout << ans << endl;
    }
    return 0;
}

D: 后缀语言

题意：

给定一个字符串，根据字符串的后缀判断是哪国语言

思路：

直接看最后一个字母就完了

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int main()
{
    IOS();
    int T;
    cin >> T;
    while(T--) {
        string s;
        cin >> s;
        char c = *s.rbegin();
        if(c == 'o') {
            cout << "FILIPINO\n";
        }
        else if(c == 'u') {
            cout << "JAPANESE\n";
        }
        else {
            cout << "KOREAN\n";
        }
    }
    return 0;
}

E: 分石头

题意：

给定一堆石头，每个石头都有重量，要求分成两堆，每堆之间的重量尽可能平均。

思路：

$01$ 背包，复杂度$O(n\ast n\ast w/2)=1.8\ast 10^8$

这题直接无语

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int dp[3000005];
int w[maxn];

int main()
{
    IOS();
    int n;
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> w[i];
        sum += w[i];
    }
    ll lim = sum/2;
    for(int i = 1; i <= n; ++i) {
        for(int j = lim; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j-w[i]]+w[i]);
    }
    ll ans = abs(sum-2*dp[lim]);
    cout << ans << endl;
    return 0;
}

F: 我的魔法

题意：

你有 $a$ 个红宝石 $b$ 个蓝宝石 $c$ 个红蓝宝石，红蓝宝石可以相互转成红色或蓝色，现在你要消耗 $x$ 个红宝石 $y$ 个蓝宝石 $z$ 个任意宝石，问够不够

思路：

先算红宝石够不够，不够从红蓝宝石扣除

如果够多余的就记着加到 $sum$ 上

蓝宝石同上

最后就是判断$c>=0andsum+c>=z$

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int main()
{
    IOS();
    ll a, b, c;
    ll x, y, z;
    cin >> a >> b >> c;
    cin >> x >> y >> z;
    ll sum = 0;
    if(a >= x)
        sum += a-x;
    else
        c -= x-a;
    if(b >= y)
        sum += b-y;
    else
        c -= y-b;
    if(c < 0 || c + sum < z) {
        cout << "There are no miracles in life\n";
    }
    else cout << "It is a kind of magic\n";
    
    
    return 0;
}

G: 最大公约数

题意：

给定一个数 $n$，另外任意整数 $a$ 和 $b$ 的最大公约数记为 $gcd(a,b)$，求解从 $1$ 到 $n$ 中的任意两个不相同的整数的最大公约数的最大值。

思路：

如果 $n$ 是偶数，那么 $a=n/2,b=n$，这样最大公因数就是 $n/2$，很明显这是最大的因为 $a<b$

如果 $n$ 是奇数，那么 $n-1$ 是偶数，那就回到第一条，所以答案就是 $n/2$。

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;

const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

ll num[maxn];

int main()
{
    IOS();
    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        cout << n/2 << endl;
    }
    return 0;
}

H: 最小公倍数

题意：

给定一个整数 $b$，另外 $a$ 表示 $1$ 到 $10^{18}$ 中的所有整数，计算式子 $[a,b]/a$ 有多少个不同的结果，这里 $[a,b]$ 表示整数 $a$ 与整数 $b$ 的最小公倍数。

思路：

化解公式 求

$lcm(a,b)/a=(a\ast b/gcd(a,b))/a=b/gcd(a,b)$

因为 $a$ 取值范围超过 $b$，所以 $gcd(a,b)$ 的结果就都是 $b$ 的因子

所以答案就转换成求 $b$ 有多少个因子

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

int main()
{
    IOS();
    ll b;
    cin >> b;
    ll cnt = 0;
    for(ll i = 1; i*i <= b; ++i) {
        if(b % i == 0) {
            ++cnt;
            if(b / i != i) ++cnt;
        }
    }
    cout << cnt << endl;
    
    return 0;
}

I: 绝对值游戏

题意：

有两个元素个数长度相等的数组 $a$ 和 $b$ , 每一轮都会从每个数组拿走一个数字，到最后只剩下一个数字结束。一个人希望剩下的数字绝对值之差最大，一个人希望最小，最后的绝对值是多少.

思路：

不管怎么操作一个数组总会剩下一个数，那么第二个人就会选择剩下对应绝对值最小的数，所以对第一个数组的每个数，第二个数组都能选到相应最小的，那答案很明显就是所有最小里面选最大的。

这其实就是对应关系，只要第一个数组不删这个数，那么第二个数组也不会删除让它答案最小的数，第一个删了第二个也就跟着删.

代码：

#include <bits/stdc++.h>
using namespace std;
#define me(a, b) memset(a, b, sizeof(a))
#define IOS() ios::sync_with_stdio(false), cin.tie(0)
#define endl '\n'

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

ll a[maxn], b[maxn];

int main()
{
    IOS();
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for(int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    ll ans = 0;
    for(int i = 0; i < n; ++i) {
        ll mi = INF;
        for(int j = 0; j < n; ++j)
            mi = min(mi, abs(a[i]-b[j]));
        ans = max(ans, mi);
    }
    cout << ans << endl;
    return 0;
}