江西农业大学 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.光纤通讯

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

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

对于这个图，将 之间断开，那么其他任意两点的连接方式介是唯一。

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

代码实现

#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;
}
全部评论

相关推荐

头像 头像
flamingSnake
05-13 21:09
东南大学 计算机类
【暑期实习末班车】美团 平台技术 后端二面
时长：50min聊项目（20min）Kafka为什么能有这么高的吞吐？一般的RPC框架是怎么运行的，介绍一下？介绍一下IO多路复用，epoll为什么高效？ET模式与LT模式介绍一下如果使用ET模式，你应该怎么处理网络事件，写一下相关的伪代码介绍一下高性能网络模型，如果你自己设计会怎么做？现在我有一个高QPS的接口，需要做到毫秒级响应，介绍一下你能想到的所有优化手法&nbsp;（这里面试官讲了一下主要的链路，让我分析一下性能优化）了解DAG调度框架吗，介绍一下？如果让你设计一个分布式的HashMap你会怎么设计，如何保证数据的一致性、可靠性？现在我有一个stl容器，你如何设计序列化方式使得...
我的实习求职记录 我的实习日记
点赞 评论 收藏
转发
头像
火鸡帽
05-15 15:18
已编辑
环保技工学校 计算机类
点赞 评论 收藏
转发
头像
幸运sir
04-19 22:39
已编辑
绿盟_渗透测试工程师(实习员工)
腾讯云智
😭😭😭
投递腾讯云智研发等公司6个岗位
点赞 评论 收藏
转发
头像
在吃瓜的青提很用心
05-13 11:05
博世_视觉算法工程师(准入职员工)
博世暑期实习内推
大家好！全球100强企业——博世中国暑期实习开始啦！25届也可以用这个内推码，大家可以收藏一下。注意岗位特点：专业不限岗位注意多介绍自己个人经验合综合素质，多围绕实习和岗位工作内容来展开，岗位写的xx专业优先建议把项目和大赛经验发在重点介绍&nbsp;。关键词：外企&nbsp;大厂&nbsp;WLB你是否渴望工作生活平衡的工作，你是否想加入跨国公司与全球各地的伙伴一起协作，你是否想加入一家百年企业感受永不上市的文化。这里就是博世！欢迎你的加入！作为校招加入博世的应届生，当时最打动我的还是招聘者的一句话：确实，入职以来，听到最多的是“合规”，创始人罗伯特·博世的“宁失利，勿失信”令我印象深刻。作为全球汽车供应商的龙头老大...
投递博世等公司6个岗位 >
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议
# 牛客帮帮团来啦！有问必答 #
778248次浏览 12200人参与
# 机械制造薪资爆料 #
313937次浏览 3617人参与
# 海康威视求职进展汇总 #
97688次浏览 1176人参与
# 0offer是寒冬太冷还是我太菜 #
421214次浏览 4876人参与
# 投了多少份简历才上岸 #
59070次浏览 966人参与
# 荣耀求职进展汇总 #
68007次浏览 682人参与
# 提前批过来人的忠告 #
21285次浏览 437人参与
# 你的工作大概什么时候入职？ #
4306次浏览 52人参与
# 毕业租房也有小确幸 #
26760次浏览 1481人参与
# 简历无回复，你会继续海投还是优化再投？ #
22449次浏览 316人参与
# 晒一晒我的offer #
3417386次浏览 54770人参与
# 非技术岗是怎么找实习的 #
77077次浏览 1430人参与
# 工作压力大怎么缓解 #
10524次浏览 148人参与
# 产品人求职现状 #
51844次浏览 762人参与
# 实习生应该准时下班吗 #
79530次浏览 587人参与
# 宁德时代求职进展汇总 #
36380次浏览 401人参与
# 找工作中的意难平 #
194323次浏览 3441人参与
# 产品实习，你更倾向大公司or小公司 #
38579次浏览 594人参与
# 如何写一份好简历 #
270227次浏览 4041人参与
# 你觉得找工作该拿大厂还是小厂练手 #
60141次浏览 847人参与
牛客网
牛客企业服务