题解 | 江西农业大学 GPLT 题解

A.Good Luck!

直接输出 "Fighting,Good Luck!" 即可

代码实现

#include<bits/stdc++.h>

using namespace std;

int main()
{
    cout << "Fighting,Good Luck!\n";
    return 0;
}

B.计算华氏摄氏

算出式子的值，加个 "Fahrenheit = " 再输出该值即可。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    cout << "Fahrenheit = " << 9 * n / 5 + 32 << endl;
    
    return 0;
}

C. 运动会

首先不存在套圈行为，所以超过了第 名后的答案唯一，那么超过第 名，那么自然排名就变成了 。

此时 一共跑了 米，那么一圈 米，所以已经跑了 圈，那么还差多少米跑完这圈，那么就可以先求出当前该圈跑了多少米，那么就是 , 然后用 减去 即可。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n , m ;
    cin >> n >> m;
    
    cout << n << endl;
    cout << m / 400 << " " << 400 - m % 400 << endl;
    
    return 0;
}

D.农大(easy)

对于长度为 的只包含 和 的字符串，而且只能改变首尾字符，所以要想变成 ，那么中间得一定是 , 那么首尾如果不等于，那么就进行答案计算即可。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main(){

    int q;
    cin >> q;
    
    while(q -- )
    {
        string s;
        cin >> s;
        
        if(s[1] != 'D')
            cout << "-1\n";
        else 
            cout << (s[0] != 'N') + (s[2] != 'D') << "\n";
    }
    
    return 0;
}

E. 简单的数字游戏

首先已知 , 那么易得知 一定是给出的七个整数中最小的那两个，那么最大的一定的 , 那么 直接用最大值减去 ，即可得到.

代码实现

#include <bits/stdc++.h>

using namespace std;

int a[10];

int main() {
    for(int i = 0 ; i < 7 ; i ++ )
        cin >> a[i];

    sort(a , a + 7);    

    cout << a[0] << " " << a[1] << " " << a[6] - a[0] - a[1] << endl;
    
    return 0; 
}

F.酒拳高手

直接根据题目意思模拟即可，注意只有当且仅当一个人喊出的数字等于两个人比划的数字之和，才能获胜。可以使用预处理将喊的文字替换成数字，再去判断输出即可.

代码实现

#include <bits/stdc++.h>

using namespace std;

//或者首个字也行
string q[11] = {"0",      "一条龙", "两家好", "三结义", "四喜财", "五魁首",
                "六六六", "七仙女", "八匹马", "九重天", "全来了"};

map<string, int> mp;

int main(){

    for (int i = 1; i <= 10; i++)
        mp[q[i]] = i;

    int n, m;
    string a, b;

    cin >> n >> a >> m >> b;

    int sum = n + m;

    if (sum == mp[a] && sum != mp[b])
        cout << "Swk go to drink beer!\n";
    else if (sum == mp[b] && sum != mp[a])
        cout << "Zf go to drink beer!\n";
    else
        cout << "go on!\n";

    return 0;
}

G.农大(hard)

根据第二个操作，只能删除第一个或者最后一个字符可得知，我们想要变成 字符串的话 就只能是连续的三个字符才能变成，那么就回到了 所以我们直接枚举该三个字符的起始位置，那么就和 的方法一样记录答案，注意同时我们只能保留三个字符，所以其他字符需要删除，所以答案得叠加 字符串的长度减 3

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int q;
    cin >> q;
    
    while(q -- )
    {
        string s;
        cin >> s;
        
        int ans = 1e9;
        for(int i = 0 ; i + 2 < s.size() ; i ++ )
        {
            string a = s.substr(i , 3);
            if(a[1] != 'D')
                continue;
            ans = min(ans ,(int)((a[0] != 'N') + (a[2] != 'D') + s.size() - 3));
        }
        
        if(ans == 1e9)
            cout << "-1\n";
        else cout << ans << endl;
    }
    
    return 0;
}

H.大学与区

首先搞清楚一对特殊大学的的定义，需要满足一对大学中的一个大学如果所在的区是另一个大学的前两个字母的话，而且是不同的区，那么就称为特殊大学，例如 大学 区为 , 大学 区为 ,就为一对特殊大学。

那么从暴力的角度，我们可以枚举 第 大学，那么 从 ~ , 去判断第 和 第 个大学是否满足条件，那么容易发现，该数量其实就是前 个大学中 与 第 个大学 是否满足 名称的前两个是 第 的区，区是 第 个大学名称的前两个字母。所以我们可以直接用 去记录数量就好了。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    map<pair<string , string> , int> mp;
    int n;
    cin >> n;
    int ans = 0;
    for(int i = 0 ; i < n ; i ++ )
    {
        string a , b;
        cin >> a >> b;

        a = a.substr(0 , 2);
        if(a != b)
            ans += mp[{b , a}];

        mp[{a , b}] ++;
    }

    cout << ans << endl;
    return 0;
}

I.幸运数字Seven

考虑到区间和 ，那么常常用到前缀和进行处理，那么假设 数组 为 数组 的前缀和数组（即 ）,那么前 个和对 取模的话就等于 ,那么如果 再找到一个 使得满足 ,所以就满足区间 区间和是 的倍数，由于我们只需尽可能使得区间长度更大，那么我们只需找到第一个满足条件的 即可，所以我们可以用数组去记录前缀和 后第一次出现的下标即可。

代码实现

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1 ; i <= n ; i ++ )
        cin >> a[i];

     vector<int> b(7 , n + 1);
     // 初始化为 n + 1 , 可以避免还没出现过的模后的数
     
     long long  sum = 0;
     int ans = -1;
     b[0] = 0;// 前0个数字时，mod 后的值为 0，且最小的下标也为0
     
     for(int i = 1 ; i <= n ; i ++ )
     {
        sum += a[i];
        ans = max(ans , i - b[sum % 7]);//更新答案
        b[sum % 7] = min(b[sum % 7] , i);//更新最早出现的下标
     }   

     
      cout << ans << endl;

    return 0;
}

J.串糖葫芦

该题是一个大模拟，注意细节，具体细节在代码中标注。

代码实现

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
stack<int> A, B;

void func()// 用于判断 A串是否串满
{
    if (A.size() == k)
    {
        vector<int> ans;
        while (!A.empty())
        {
            ans.push_back(A.top());
            A.pop();
        }
        for (int i = ans.size() - 1; i >= 0; i--)
            cout << ans[i] << " ";
        cout << endl;
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if (A.empty() || A.top() < x)
        {
            A.push(x);//注意每次串入都需特判
            func();
        }
        else if (B.empty() || B.size() < m && B.top() > x)
        {
            B.push(x);
        }
        else
        {
            vector<int> ans;
            while (!A.empty())
            {
                ans.push_back(A.top());
                A.pop();
            }
            for (int i = ans.size() - 1; i >= 0; i--)
                cout << ans[i] << " ";
            cout << endl;

            while (!B.empty() && B.top() < x)
            {
                A.push(B.top());//注意每次串入都需特判
                func();
                B.pop();
            }
            A.push(x);//注意每次串入都需特判
            func();
        }
    }

    vector<int> ans;
    while (!A.empty())
    {
        ans.push_back(A.top());
        A.pop();
    }
    for (int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i] << " ";
        
    if (ans.size())//有可能会存在最后时刻A串为空的，所以不能进行换行
        cout << endl;
        
    while (!B.empty())
    {
        cout << B.top() << " ";
        B.pop();
    }

    return 0;
}

K.三角形

先从爆搜的思路出发，，三个参数，分别代表枚举到第 个木棍，一条边的长度为 , 另一条边的长度为 ，假设所有的木棍长度之和为 ,那么自然而然第三条边就为 ,每一次我们有三种策略，第一种将 分配给 , 第二种 将 分配给 , 第三种就分配给第三条边，即进行 ，那么对于每种情况我们对其进行面积的计算更新答案即可，但是时间复杂度远远不够通过此题，那么考虑到记忆化搜索，状态 中的 代表与上述 相同，发现边的最长为 ,那么就最多存在 个状态 ,那么 内是能够跑完的。

代码实现

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;
const int NR = 1605;
int N, C, L[NR], ans = 0;
bool flag[NR][NR][50];

double S(int a, int b, int c)
{
    return 25.0 * sqrt((double)C * (a + b - c) * (a + c - b) * (b + c - a));
}

void dfs(int a, int b, int indx)
{
    if (flag[a][b][indx])
        return;
    flag[a][b][indx] = true;

    int c = C - a - b;
    if (b + c > a && a + b > c && a + c > b)// 满足两边之和大于第三边
    { // it's triangle
        ans = max((int)(S(a, b, C - a - b)), ans);
    }
    if (indx == N + 1)
        return;
    dfs(a, b, indx + 1);
    dfs(a + L[indx], b, indx + 1);
    dfs(a, b + L[indx], indx + 1);
    return;
}

int main()
{
    int t;
    cin >> t;

    while(t -- )
    {
        cin >> N;
        C = 0 , ans = -1;
        memset(flag , false , sizeof flag);//每次需要将记忆化数组初始化
        for (int i = 1; i <= N; i++)
        {
            cin >> L[i];
            C += L[i];
        }
        dfs(0, 0, 1);
        cout << ans << endl;
    }
    // system("pause");
    return 0;
}

L. 最大W值

显然在没有操作之前，数组 为 数组 的从小到大排序时，能够使得 ，那么进行操作将 替换成 , 我们将其分成两部分，先将 移除，再将 插入。

因为数组 是数组 的从小到大的排序，所以我们能够二分找到 在数组 中下标 (即 )，那么对于原式 , 删除掉 后，对于前 ~ 的数，位置没有变化，所以对 的值 没有影响，对于 ， 需要减去 ，对于 ~ 的数，位置需要往前移动一位，即原式 , 那么两者相减 ,那么就完成了删除部分。

那么同样的需要满足 是单调不递减 才使得 ,所以我们将插入到数组 中第一个大于 的元素前面，即可满足条件。

那么在数组 中找到第一个大于 的元素下标 , 同样对于 位置 ~ 的元素无影响，放到下标 的前面，那么 就变成了下标 , ~ 的元素都将往后移，即需要加上 ，但是如果 ，在 的后面的位置都需向前，所以 ，否则 ,那么原来的 会存在于 ~ 这一段中，则需要减去 。

处理两部分之和则就是答案。区间和使用前缀和数组维护。

代码实现

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

// Sunwking 2024/03

void solved()
{
    int n;
    cin >> n;

    vector<LL> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    b = a;

    sort(b.begin() , b.end());
    
    vector<LL> s(n + 1);
    LL W = 0; //无操作前的W最大值
    for (int i = 1; i <= n; i++)
    {
        W += 1ll * i * b[i];
        s[i] = s[i - 1] + b[i];
    }

    int q;
    cin >> q;

    while (q--)
    {
        LL x, y;
        cin >> x >> y;

        LL ans = W;
        //找到第一个大于等于 a[x] 的下标 j
        auto j = lower_bound(b.begin() , b.end() , a[x]) - b.begin();
        //找到第一个大于 y 的下标 it
        auto it = upper_bound(b.begin() , b.end(), y) - b.begin();

		//移除 a[x] 部分
        ans -= b[j] * j;
        ans -= s[n] - s[j];
        
        //插入 y 部分
        ans += y * it;
        ans += s[n] - s[it - 1];
        
        if (it <= j)
            ans -= a[x];
        else ans -= y;

        cout << ans << endl;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;

    while (t--)
        solved();

    return 0;
}

M.光纤通讯

一共 ~ 的房子编号，将其看成圆环，对于需要 和 ，实现通讯，那么就有两种连接方式，一种是优弧，一种是劣弧。

显而易见，如果我们想要将 ~ 的房子之间都实现通讯，我们最多只需要 条边，圆环相邻点之间有 条边，所以存在一条边不用连接，那么我们可以去枚举是不连接的这条边，那么对于 要实现通讯，那么就只有唯一连接方式。 对于这个图，将 之间断开，那么其他任意两点的连接方式介是唯一。

所以我们只需枚举断边除，再去枚举 个要求，取最小答案岂可。对于每个要求需要连接一段，那么我们可以用差分进行 处理，所以总的时间复杂度是

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e3 + 10, M = 1e4 + 10;

struct T
{
    int a, b;
} gA[M];

int gDis[N];

void Add(int l, int r)
{
    gDis[l]++;
    gDis[r + 1]--;
}

signed main()
{

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> gA[i].a >> gA[i].b;
        if (gA[i].a > gA[i].b)
            swap(gA[i].a, gA[i].b);
    }

    int mn = n - 1;
    for (int i = 1; i <= n; i++) //表示 i ~ i + 1边断开
    {
        for (int j = 1; j <= m; j++)
            if (gA[j].a <= i && i < gA[j].b) //如果正向内部有 i ~ i + 1边，那么只能反向
                Add(1, gA[j].a - 1), Add(gA[j].b, n);
            else // 正向
                Add(gA[j].a, gA[j].b - 1);

        for (int j = 1; j <= n; j++)
            gDis[j] += gDis[j - 1];

        int sum = 0;
        for (int j = 1; j <= n; j++)
            sum += (gDis[j] > 0); //如果大于0，则需要连接边

        mn = min(mn, sum);

        memset(gDis, 0, sizeof(gDis)); // BUGBUG dis
    }

    cout << mn << endl;
    return 0;
}

O.寻找那个他

不妨假设到达 点时的贡献，其曼哈顿距离的 次方为 ，想要到达该点，我们需要进行 步才可到达，但是需要我们确切的进行 次向左 和 向下，那么方案数为 , 总的方案数为 ，所以对于 点 对答案的贡献为 .对于该式子可以暴力求解，预处理组合数则能达到

设

如果我们枚举 ,那么 则为定值，所以以上式子变为 ，对于前两项皆为定值，所以只需处理最后一项 对于 的值，那么就能得出 的界 . 然后只需求 . 不过简单发现，当 时 ， ,所以我们可以修改上下界，，于是原式变成 ，设 , 所以

所以使用 递推求出次式子，于是总的复杂度为

代码实现

#include <iostream>

using namespace std;
using LL = long long;

const int N = 1e7 + 10, Mod = 1e9 + 7;

 int n, m, k;
LL fac[N], ifac[N];
LL f[N] , pw[N];//pw[i] 为 i ^ k % Mod 的值
int p[N] , cnt = 0;
bool st[N];

LL qmi(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1)
            res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

void init(int n) {

    pw[1] = 1;
    for(int i = 2 ; i <= n ; i ++ )
    {
        if(!st[i])
        {
            p[cnt ++ ] = i;
            pw[i] = qmi(i , k);
        }
        for(int j = 0 ; p[j] <= n / i ; j ++ )
        {
            st[i * p[j]] = true;
            pw[i * p[j]] = pw[i] * pw[p[j]] % Mod;
            if(i % p[j] == 0)
                break;
        }
    }

    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % Mod;

    ifac[n] = qmi(fac[n], Mod - 2);
    for (int i = n - 1; i >= 1; i--)
        ifac[i] = ifac[i + 1] * (i + 1) % Mod;
}

LL C(int a, int b) {
    if (b < 0 || b > a)
        return 0;

    return fac[a] * ifac[b] % Mod * ifac[a - b] % Mod;
}

int main() {

    cin >> n >> m >> k;

    init(N - 1);
    LL _2 = qmi(2, Mod - 2);
    LL ans = 0;

    // T = n + m - x - y
    f[0] = 1;
    LL _2p = 1;
    
    for (int T = 0; T <= n + m; T++) {
        LL a = _2p * pw[n + m - T] % Mod;

        _2p = _2 * _2p % Mod;
        if (T)
            f[T] = ((2 * f[T - 1] - C(T - 1, T - 1 - m) - C(T - 1, n)) % Mod + Mod) % Mod;
        ans = (ans + a * f[T] % Mod) % Mod;
    }

    cout << ans << endl;
}