开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 林湾村男子铁路技术职业学院2022年5月ACM校赛题解 -> 正文阅读

[数据结构与算法]林湾村男子铁路技术职业学院2022年5月ACM校赛题解

传送门：SWJTUOJ

A题

Bob每次最多走一格，最多走300步，而起始位置在0~300之间，所以最多也就走到600这样子，那么只需要记录最低600位就可以了。

每次乘的时候，时间复杂度为:

$T\left ( n \right )=O\left ( n^{2} \right )$

其中n最多为600，然后因为要乘300次，总操作次数大约为300*300*600，约为5e7，不会TLE，而每次乘完之后判断是否有位置可以给Bob容身即可。

AC码如下：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;
bool fff=true;
vector<bool>safe(605,false);
vector<bool>num0(605,0);
void init()
{
    num0[0]=1;
    cin>>m;
    safe[m]=true;
}
void solve()
{
    string str;
    cin>>str;
    vector<int>num1(605,0);
    for(int i=0;i<str.size();i++)
    {
        if(str[str.size()-i-1]=='1')
        {
            for(int j=0;i+j<605;j++)
                num1[i+j]+=num0[j];
        }
    }
    for(int i=0;i<604;i++)
    {
        num1[i+1]+=(num1[i]>>1);
        num1[i]&=1;
    }
    bool flag=false;
    vector<bool>safenext(605,false);
    for(int i=0;i<605;i++)
    {
        if(num1[i]||num0[i])
            continue;
        if(safe[i+1]||safe[i]||(i>0&&safe[i-1]))
            flag=safenext[i]=true;
    }
    safe=safenext;
    for(int i=0;i<604;i++)
        num0[i]=num1[i];
    num0[604]=num1[604]&1;
    fff=flag;
    return ;
}

signed main()
{
    cin>>T;
    init();
    while(T--&&fff)solve();
    if(fff)
        cout<<'Y';
    else
        cout<<'N';
    return 0;
}

B题

因为有绝对值不等式

所以

$ans=\sum \left | a_{i}-a_{i-1} \right |\leq \sum \left | a_{i}-c \right |+\sum \left | a_{i-1}-c \right |=\sum \left | a_{i}-c \right |-\left | a_{1}-c \right |-\left | a_{n}-c \right |$

?当且仅当

$\left ( a_{i}-c \right )*\left ( a_{i-1}-c \right )\leq 0$

时成立，

保证不等式的等号成立的同时，还要保证被剪掉的部分尽可能小，于是只能取c为数组的中位数，且a1和an分别为不超过c的最大数和不低于c的最小数（可以有一个和c相同），显然当数组个数为奇数的时，需要特殊判断一下，取哪个数为c才能令另一个数与c距离最近。

AC码如下：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;

void init()
{

}#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;

void solve()
{
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    int base=a[n/2];
    int ans=0;
    for(int i=0;i<n/2;i++)
        ans+=abs(a[i]-base)*2;
    for(int i=n/2+1;i<n;i++)
        ans+=abs(a[i]-base)*2;
    if(n&1)
        ans-=min(abs(base-a[n/2-1]),abs(base-a[n/2+1]));
    else
        ans-=abs(base-a[n/2-1]);
    cout<<ans;
}

signed main()
{
    T=1;
    init();
    while(T--)solve();
    return 0;
}

void solve()
{
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    int base=a[n/2];
    int ans=0;
    for(int i=0;i<n/2;i++)
        ans+=abs(a[i]-base)*2;
    for(int i=n/2+1;i<n;i++)
        ans+=abs(a[i]-base)*2;
    if(n&1)
        ans-=min(abs(base-a[n/2-1]),abs(base-a[n/2+1]));
    else
        ans-=abs(base-a[n/2-1]);
    cout<<ans;
}

signed main()
{
    T=1;
    init();
    while(T--)solve();
    return 0;
}

C题

枚举两数之差，发现若差为奇数q，则只有形如a=(k+1)q，b=kq的ab满足(a+b)|(a-b),若差为偶数p，则只有形如a=(k+1)p，b=kp和形如a=(k+1.5)p，b=(k+0.5)p的ab满足(a+b)|(a-b)。

所以可以先统计每个数出现的次数，然后枚举两数之差，在统计好的数组中查询形如上述的ab，当枚举两数之差为x时，需要遍历的次数为1e6/x，总时间复杂度为

$T\left ( n \right )=O\left (n* \sum 1/i \right )=O(e n)$

AC码如下：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;

signed main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin>>n;
    vector<int>a(1000003);
    int buf;
    for(int i=0;i<n;i++)
    {
        cin>>buf;
        a[buf]++;
    }
    int ans=0;
    for(int i=1;i<=1000000;i++)
    {
        if(i&1)for(int j=i;j<=1000000;j+=i)
        {
            if(j+i>1000000)break;
            else ans+=a[j]*a[i+j];
        }
        else for(int j=i>>1;j<=1000000;j+=(i>>1))
        {
            if(j+i>1000000)break;
            else ans+=a[j]*a[i+j];
        }

    }
    cout<<ans;
    return 0;
}

D题

这是宋老板放的一道郑老板都表示不会的钓鱼题，网上的假题解链接如下：

swjtucpc—嘉然今天吃什么_qq_41251052的博客-CSDN博客

我们会在第一时间查找所有有错误代码的提交，并且给予他delete的奖励。

具体这道题该怎么写，可以参考假题解中的连接，自行学习一下，英朗表示真的不会无能为力了。

E题

这是宋老板送给大家的签到题，需要在ksm函数最末尾加一句

return z;

然后倒数第四行加个分号就能AC了，你有没有成功AC呢？

这道题也可以自己写，但是时间可能会很长，郑老板贴心的把判题时间调的比较长，以鼓励自己写FFT的同学。

F题

这道题主要考察堆栈的用法，并且部分同时使用cin和cout的同学可能过不了，当当前元素与栈顶元素可以配对时，就弹出，否则就入栈（不配对的元素不参与这个过程）即可，当识别到不能入栈且不能配对的元素。最终若字符串读完时，栈不空就说明字符串不合法，否则字符串合法。

STD码如下：

#include<bits/stdc++.h>
#define cc char,char
#define c char
using namespace std;
const int maxn=5e6+3;

string vs[]={"()","{}","[]","/\\","<>","pq","bd"};
string sa(" !^*-_+=|:.\'\"AHIMOTUVWXYilovwx08");


set<c>s1,s2;//s1存前键s2存自对称
map<cc> mp;
void init()
{
    for(int i=0;i<sa.size();i++)
        s2.insert(sa[i]);
    for(int i=0;i<7;i++)
    {
        c m=min(vs[i][0],vs[i][1]);
        c M=max(vs[i][0],vs[i][1]);
        s1.insert(m);
        mp.insert(pair<cc>(M,m));
    }
}

char str[5000003];

void solve()
{
    stack <c> s;
    cin.getline(str,5000003,'\n');
    int i=0;
    do{
        char ch=str[i
        if(!s.empty()&&s.top()=='\'')
        {
            if(ch=='\'')
                s.pop();
        }
        else if(s2.find(ch)!=s2.end())
        {
            if(!s.empty()&&s.top()==ch)
                s.pop();
            else
                s.push(ch);
        }
        else if(s1.find(ch)!=s1.end())
            s.push(ch);
        else if(mp.find(ch)!=mp.end())
        {
            if(!s.empty()&&s.top()!=mp[ch])
            {
                printf("N\n");
                return ;
            }
            s.pop();
        }
    }while(str[++i]!='\0');

    printf("%c\n",s.empty()?'Y':'N');
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
  	getchar();
    while(T--)
        solve();
}

G题

将一个大数分开成a*8+b*9+c*10的形式。

首先，任何一个数都可以写成n*8+k的形式，其中n是整数，k是小于8的整数。

9可以看做8+1，10可以看做8+2，那么让k全部分给前边的n个8，前边的n个8最多接收2n，所以当k>2n的时候无解，应输出-1。

随后随意分解k使满足题意即可。

AC码如下：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;
void solve()
{
    int n;
    cin>>n;
    int cnt=n/8;
    if(n-cnt*8>cnt*2)
    {
        cout<<-1<<endl;
        return ;
    }
    int last=n-cnt*8;
    int c=last/2;
    int b=last&1;
    int a=cnt-b-c;
    cout<<a<<' '<<b<<' '<<c<<endl;
}

signed main()
{
    cin>>T;
    init();
    while(T--)solve();
    return 0;
}

H题

显然，应该选取架子上左右两边的高达模型，但是在统计距离和的时候，应该要有所优化地统计，直接二维暴利枚举会TLE

AC码如下：

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
int n,m,T;
vi a;

signed main()
{
    cin>>n>>m;
    a.resize(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a.begin(),a.end());
    int l=0,r=n-1;
    int ans=0;
    while(m>>1)
    {
        ans+=(m-1)*(a[r]-a[l]);
        m-=2;
        l++;
        r--;
    }
    cout<<ans;
    return 0;
}

I题

用平方时间复杂度枚举两行，两行做按位与运算，统计运算后1的个数，就可以算出这两行中，有多少对数作为列可以构成四环。时间复杂度为三次方，可能会被卡常

AC码如下：

#include <bits/stdc++.h>
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
const int maxn=1e6+3;
using namespace std;
bool a[1000][1000];
int n,m,T;

signed main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        for(int j=0;j<n;j++)
        {
            if(str[j]=='1')
                a[i][j]=true;
        }
    }
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int cnt=0;
            for(int k=0;k<n;k++)
                cnt+=(a[i][k]&a[j][k]);
            ans+=(cnt*(cnt-1)/2);
        }
    }
    cout<<ans;
    return 0;
}