林湾村男子铁路技术职业学院2022年5月ACM校赛题解

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

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

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

AC码如下：

#include 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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;
vectorsafe(605,false);
vectornum0(605,0);
void init()
{
    num0[0]=1;
    cin>>m;
    safe[m]=true;
}
void solve()
{
    string str;
    cin>>str;
    vectornum1(605,0);
    for(int i=0;i>1);
        num1[i]&=1;
    }
    bool flag=false;
    vectorsafenext(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;
}

因为有绝对值不等式

所以

 当且仅当

时成立，

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

AC码如下：

#include 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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;
    vectora(n);
    for(int i=0;i>a[i];
    sort(a.begin(),a.end());
    int base=a[n/2];
    int ans=0;
    for(int i=0;in;
    vectora(n);
    for(int i=0;i>a[i];
    sort(a.begin(),a.end());
    int base=a[n/2];
    int ans=0;
    for(int i=0;i 
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，总时间复杂度为
 
 
AC码如下：
 
#include 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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;
    vectora(1000003);
    int buf;
    for(int i=0;i>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<
 
D题 
这是宋老板放的一道郑老板都表示不会的钓鱼题，网上的假题解链接如下：
 
swjtucpc—嘉然今天吃什么_qq_41251052的博客-CSDN博客
 
我们会在第一时间查找所有有错误代码的提交，并且给予他delete的奖励。
 
具体这道题该怎么写， 可以参考假题解中的连接，自行学习一下，英朗表示真的不会无能为力了。
 
E题 
这是宋老板送给大家的签到题，需要在ksm函数最末尾加一句
 
return z;
 
然后倒数第四行加个分号就能AC了，你有没有成功AC呢？
 
这道题也可以自己写，但是时间可能会很长，郑老板贴心的把判题时间调的比较长，以鼓励自己写FFT的同学。
 
F题 
这道题主要考察堆栈的用法，并且部分同时使用cin和cout的同学可能过不了，当当前元素与栈顶元素可以配对时，就弹出，否则就入栈（不配对的元素不参与这个过程）即可，当识别到不能入栈且不能配对的元素。最终若字符串读完时，栈不空就说明字符串不合法，否则字符串合法。
 
STD码如下：
 
#include
#define cc char,char
#define c char
using namespace std;
const int maxn=5e6+3;

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


sets1,s2;//s1存前键s2存自对称
map mp;
void init()
{
    for(int i=0;i(M,m));
    }
}

char str[5000003];

void solve()
{
    stack  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("Nn");
                return ;
            }
            s.pop();
        }
    }while(str[++i]!='');

    printf("%cn",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 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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<T;
    init();
    while(T--)solve();
    return 0;
}
 
H题 
显然，应该选取架子上左右两边的高达模型，但是在统计距离和的时候，应该要有所优化地统计，直接二维暴利枚举会TLE
 
AC码如下：
 
#include 
#define int long long
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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>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<
 
I题 
用平方时间复杂度枚举两行，两行做按位与运算，统计运算后1的个数，就可以算出这两行中，有多少对数作为列可以构成四环。时间复杂度为三次方，可能会被卡常
 
AC码如下：
 
#include 
#define pii pair
#define mii map
#define vi vector
#define vvi vector>
#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>str;
        for(int j=0;j