2023GPLT选拔题解-526互联

看到没有题解我就给大家浅浅的写一篇吧，如果有错误，希望大家可以帮我指出来哦，创作不易，如果大家给个关注，点个赞就更好了

1：

著名开源操作系统Linux的核心创始人Linus有一句经典名言：”Talk is cheap. Show me the code.“

说出这句话时是2000年8月25日，那天有人在Linus的Linux论坛上留言讨论关于线程优化的问题，有个用户提出了一个他自认为非常高效的方案。但是Linus不认同，并且为他是在打嘴炮，于是说出了这句话反击那位用户。

这句话受到了大多数程序员的认可，于是流传至今，成为程序员抨击键盘侠的武器。

把这句话翻译过来大概是：”代码胜于雄辩。“，当然也有人会翻译成：”废话少说，放码过来。“，怎么翻译都可以，只要能让大家都看懂。

当然……这个题目并不是要你把这句话翻译，或是让你回答出关于Linux线程优化的问题。

现在只需要你将”Talk is cheap. Show me the code.“中的标点符号、空格都去掉，并且把所有字母都改为小写，然后在一行内输出出来。

代码：

talkischeapshowmethecode

2：
小学三年级的小明刚接触英语，这天老师正在教如何用英文单词表示数字。

而小明没有认真听课，TA只在乎每个数字需要用到多少个字母。

例如数字

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6+10;
ll a[N];
ll b[21] = {0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8,6};
int  main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= 20;i ++)
        a[i] = b[i];
    for(int i = 21;i < 30;i ++)
    {
        a[i] = 6 + b[i%10];
    }
    a[30] = 6;
    for(int i = 31;i < 40;i ++)
    {
        a[i] = 6 + b[i%10];
    }
    a[40] = 5;
    for(int i = 41;i < 50;i ++)
    {
        a[i] = 5 + b[i%10];
    }
    a[50] = 5;
    a[60] = 5;
    for(int i = 51;i < 60;i ++)
    {
        a[i] = 5 + b[i%10];
    }for(int i = 61;i < 70;i ++)
    {
        a[i] = 5 + b[i%10];
    }
    a[70] = 7;
    for(int i = 71;i < 80;i ++)
    {
        a[i] = 7 + b[i%10];
    }
    a[80] = 6;
    for(int i = 81;i < 90;i ++)
    {
        a[i] = 6 + b[i%10];
    }
    a[90] = 6;
    for(int i = 91;i < 100;i ++)
    {
        a[i] = 6 + b[i%10];
    }
    a[100] = 10;
    for(int i = 101;i < 200;i ++)
    {
        a[i] = 13 + a[i%100];
    }
    a[200] = 10;
    for(int i = 201;i < 300;i ++)
    {
        a[i] = 13 + a[i%100];
    }
    a[300] = 12;
    for(int i = 301;i < 400;i ++)
    {
        a[i] = 15 + a[i%100];
    }
    a[400] = 11;
    for(int i = 401;i < 500;i ++)
    {
        a[i] = 14 + a[i%100];
    }
    a[500] = 11;
    for(int i = 501;i < 600;i ++)
    {
        a[i] = 14 + a[i%100];
    }
    a[600] = 10;
    for(int i = 601;i < 700;i ++)
    {
        a[i] = 13 + a[i%100];
    }
    a[700] = 12;
    for(int i = 701;i < 800;i ++)
    {
        a[i] = 15 + a[i%100];
    }
    a[800] = 12;
    for(int i = 801;i < 900;i ++)
    {
        a[i] = 15 + a[i%100];
    }
    a[900] = 11;
    for(int i = 901;i < 1000;i ++)
    {
        a[i] = 14 + a[i%100];
    }
    a[1000] = 11;
    ll ans = 0;
    //cout << a[115] << '\n';
    for(int i = 1;i <= n;i ++)
        ans += a[i];
    printf("%lld\n",ans);
}

再贴一个好看一点的，21级同学没有写出来的可以看看这个

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[] = {0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7,7,9,8,8};
int b[] = {0,0,6,6,5,5,5,7,6,6};
int n,s;
signed main()
{
    cin>>n;
    
    for(int i=1;i<=n;i++)
    {
        if(i>=1&&i<20)
            s+=a[i];
        else if(i>=20&&i<100)
        {
            s+=b[i/10]+a[i%10];
        }
        else if(i>=100&&i<1000)
        {
            if(i%100==0)
                s+=a[i/100]+7;
            else if(i%100>=1&&i%100<20)
                s+=a[i/100]+10+a[i%100];
            else if(i%100>=20&&i%100<100)
                s+=a[i/100]+10+a[i%10]+b[i/10%10];
        }
        else s+=11;
    }
    
    cout << s << '\n';
}

3：
小明现在上六年级了，数学老师很喜欢聪明的TA，想邀请小明参加数学奥林匹克竞赛。

但小明从小就有很强的欲望参加信息学奥林匹克竞赛，TA的数学老师觉得编程也能解决一些数学难题，于是给小明出了一道六年级的奥数题：

给定 $nnn个数字a1,a2,a3,...,ana_1,a_2,a_3,...,a_na1,a2,a3,...,an求 (∑l=1n∑r=ln∑i=lrai)mod 109+7(\sum_{l=1}^{n}\sum_{r=l}^{n}\sum_{i=l}^{r} a_i) \mod {10}^9+7(∑l=1n∑r=ln∑i=lrai)mod109+7$

数学老师担心小明看不懂数学符号，于是给了一点提示，上述公式转换为C++语言后的代码差不多是：

int ans = 0, MOD = 1e9 + 7;
for (int l = 1; l <= n; ++l) {
    for (int r = l; r <= n; ++r) {
        for (int i = l; i <= r; ++i) {
            ans = (ans + a[i]) % MOD;
        }
    }
}

但是数学老师说这份代码不足以在

思路：我们把题给的代码先写出来

如图

这个时候我们可以发现他成一个阶梯，因此公式就可以推出来了

ans = a[1]*n+a[2]*(n-1)*2 + ....+a[n]*n;

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
ll a[N],b[N],c[N];
const int md = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        ans =(ans + a[i]*(n-(i-1))*i%md)%md;
    }
    
    cout << ans << '\n';
}

注意取模和longlong

4：

链接：https://ac.nowcoder.com/acm/contest/55146/D
来源：牛客网

小明高中毕业了，TA平时很喜欢看一些军旅节目，向往着军队的生活，也希望能到部队里磨练一下自己的意志，于是TA报名了义务参军。

小明被分配到了一个非常神秘的部队，这个部队算上小明有 $如果你看不懂，可以理解为有nnn（nnn必然为偶数）个数，对于每一个aia_iai，有且仅有一个j≠ij \neq ij=i，使得ai=aja_i = a_jai=aj。部队里这些人都是新兵蛋子，而且碰上了一个很特殊的教官，教官在新兵每天早晨训练前都要做这么一件事： - 将nnn个人均分为两队，每队mmm（m=n2m = \frac{n}{2}m=2n）人，从左到右一字排开，即把a1,a2,a3,...,ana_1,a_2,a_3,...,a_na1,a2,a3,...,an随机分成x1,x2,x3,...,xmx_1,x_2,x_3,...,x_mx1,x2,x3,...,xm和y1,y2,y3,...,ymy_1,y_2,y_3,...,y_my1,y2,y3,...,ym。 - 让一部分人出列，其他人的相对位置不变，使得两队都变成完美队列。教官对于完美队列的定义：人数必须是偶数（包括000），且从左到右每两个人的编号都恰好是一样的，形如a,a,b,b,c,c,...a,a,b,b,c,c,...a,a,b,b,c,c,...。举个例子，2,2,3,3,8,82, 2, 3, 3, 8, 82,2,3,3,8,8就是完美队列，而2,2,3,8,82,2,3,8,82,2,3,8,8则不是。教官每天会指派所有出列的人中编号最大的人作为今天的助教，并奖励冰水一瓶，但是教官同时又希望这个人编号尽可能的小。教官听说小明会编程，于是想请小明帮忙设计一个程序，给定已经分好的两队人的编号和顺序，要求出最小的助教编号。小明每天都很辛苦训练，没有多少时间再涉略编程知识，部队里也没有电脑可以用，于是TA决定求助你来实现这个程序。$

$思路一：二分答案，这个没有什么好说的，这里我不想写了，就贴了一个代码$

$代码：$

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
int a[N],b[N],n;
vector<int> c;
bool check(int x)
{
    c.clear();
    for(int i = 1; i <= n; i ++) if(a[i] > x) c.pb(a[i]);
    int m = c.size();
    if(m & 1) return false;
    for(int i = 0; i < m; i += 2) if(c[i] != c[i+1]) return false;
    c.clear();
    for(int i = 1; i <= n; i ++) if(b[i] > x) c.pb(b[i]);
    m = c.size();
    if(m & 1) return false;
    for(int i = 0; i < m; i += 2) if(c[i] != c[i+1]) return false;
    return true;
}
signed main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    int l = 0, r = N;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

思路二：贪心，先把单个的提出来取最大，在把每一个数组当个比较，小的出队，取最大，要注意的是这个思路可行，但是这里数据弱，我交原数据的话不能用map和undered map，他会卡常，这个时候你只要手写一个哈希就可以了

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
ll a1[N],b1[N];
unordered_map<int,int>mp1,mp2;
int main()
{
    int n;
    scanf("%d",&n);
    ll ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        scanf("%lld",&a1[i]);
        mp1[a1[i]]++;
    }
    for(int j = 1;j <= n;j ++)
    {
        scanf("%lld",&b1[j]);
        mp2[b1[j]]++;
    }
    vector<int>a,b;
    for(int i = 1;i <= n;i ++)
    {
        if(mp1[a1[i]]>=2)
            a.push_back(a1[i]);
        else
        {
            if(ans < a1[i])
                ans = a1[i];
        }
        if(mp2[b1[i]]>=2)
            b.push_back(b1[i]);
    }
    int x = 0;
    int res = 0;
//     for(int i = 0;i < a.size();i ++)
//         cout << a[i] << " \n"[i == a.size()-1];
//     for(int i = 0;i < b.size();i ++)
//         cout << b[i] << " \n"[i == b.size()-1];
    for(int i = 1;i < a.size();i ++)
    {
        if(a[res] == a[i])
        {
            res = i+1;
            i ++;
        }
        else
        {
            if(a[res] > a[i])
            {
                x = max(a[i],x);
            }
            else
            {
                x = max(a[res],x);
                res = i;
            }
        }
    }
    int y = 0;
    int pos = 0;
    for(int i = 1;i < b.size();i ++)
    {
        if(b[pos] == b[i])
        {
            pos = i+1;
            i ++;
        }
        else
        {
            if(b[pos] > b[i])
            {
                y = max(b[i],y);
            }
            else
            {
                y = max(b[pos],y);
                pos = i;
            }
        }
    }
    if(x<y)
        x = y;
    if(ans<x)
        ans = x;
    printf("%lld\n",ans);
}

5：

小明所在的部队正准备来张大合照，合照的场地可以看作一个

例如（`S`为士兵，`.`为空地）这一种排列方式是合法的：

SSS
...
SSS

而这一种是不合法的，由于右下角的

S.S
.S.
S..

除此之外，士兵的排列方式没有任何限制。

部队人很多，多到所有网格如果都站一名士兵恰好够，但碍于规则，肯定不能让所有的士兵都进行合照。

每个网格上都有一个让照片增添色彩的美丽度，坐标为

(i,j)(i,j)(i,j)的网格如果站有一名士兵的话，该网格的美丽度便为ai,ja_{i,j}ai,j​，否则为000，照片的美丽度为每个网格的美丽度之和。 领导希望让这张合照的美丽度最大，请问在满足规则的情况下最大的美丽度为多少？

我们发现这多种情况都可以化为两种，就是行相隔或者列相隔，因此取最大就可以了

代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N = 1e3 + 10;
int a[N][N];
signed main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
            cin >> a[i][j];
    }
    
    int res = 0,pos = 0;
    for(int i = 1;i <= n;i ++)
    {
        map<int,int>mp;
        for(int j = 1;j <= n;j ++)
        {
            mp[j&1]+=a[i][j];
        }
        res += max(mp[0],mp[1]);
    }
    
    for(int i = 1;i <= n;i ++)
    {
        map<int,int>mp;
        for(int j = 1;j <= n;j ++)
        {
            mp[j&1]+=a[j][i];
        }
        pos += max(mp[0],mp[1]);
    }
    
    int ans = max(res,pos);
    
    cout << ans << '\n';
}

6：
小明的女朋友共有 $假设将头发从[1,n][1,n][1,n]编号，编号为iii的头发长度为aia_iai。 - 同时满足i<ji<ji<j和ai>aja_i>a_jai>aj的所有二元组(i,j)(i,j)(i,j)的数量（即逆序对数）。例如，有555根头发，长度分别为{3,2,3,3,0}\{3,2,3,3,0\}{3,2,3,3,0}，那么发型的不良度为555，因为有555个二元组满足要求：(1,2)(1,2)(1,2)，(1,5)(1,5)(1,5)，(2,5)(2,5)(2,5)，(3,5)(3,5)(3,5)和(4,5)(4,5)(4,5)。为了维持自己的形象，她决定到家楼下的理发店剪头发，这家店可以将所有长度大于kkk的头发都减为kkk，而其他的头发长度不变。小明的女朋友想知道kkk从[0,n−1][0,n-1][0,n−1]变化的时候，发型不良度分别应该是多少？$

思路;这题有点诈骗啊，我开始还想直接贴个求逆序对的模板后面才发现，完全没有关系，我们只要求在每一位前有多少个大于他的数就可以了

代码：

#include <bits/stdc++.h>
#define lowbit(x) (x)&(-x)
using namespace std;
#define int long long
const int maxn = 1e6+10;
int t[maxn],n,result;

void add(int x)
{
    while(x<=maxn)
    {
        t[x]++;
        x += lowbit(x);
       // cout << x << '\n';
    }
    //cout << "ww" << '\n';
}

int query(int x)
{
    int ans=0;
    for (;x;x-=lowbit(x))
        ans+=t[x];
    return ans;
}
int a[maxn];
signed main()
{
    int temp;
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> temp;
        add(temp+1);
        a[temp+1] += query(n+1) - query(temp+1);
    }
    for(int i = 0;i < n;i ++)
    {
        result += a[i];
        cout << result << '\n';
    }
    return 0;
}

到此所以题目就结束了，给我的感觉就是这么自己这么菜，要加训了，呜呜呜

大家也要一起加油呀QAQ