Edu169

做得很糟糕。。。

A

只有\(n=2\)且两者之间的距离大于1时才可以插入。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=998244353;
void solve()
{
    int n;  cin>>n;
    std::vector<int> v(n,0);
    for(auto &t: v) cin>>t;
    if(n>2)
    {
        cout<<"NO\n";
        return;
    }
    if(v[1]-v[0]<2)
    {
        cout<<"No\n";
        return;
    }
    cout<<"YES\n";
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

B

直接找最小的区间即可。需要考虑左右端点不重合的情况，另外加一。

此外还需要特判不重合的情况，直接为1即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=998244353;
void solve()
{
    int l,r;    cin>>l>>r;
    int L,R;    cin>>L>>R;
    if(r<L || R<l)
    {
        cout<<1<<"\n";
        return;
    }
    int ans=min(R,r)-max(L,l);
    if(R!=r)    ans++;
    if(l!=L)    ans++;
    cout<<ans<<"\n";    
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

C

博弈论，显然需要先排个序，然后依次取。

需要考虑的是，偶数位的数字是Bob可以修改的，但是要考虑前提是修改后不能大于前一位数字（也就是Alice取的），否则顺序会颠倒。

用差分计算每一个偶数位最多可以加的数，根据\(k\)辅助判断即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=998244353;
void solve()
{
    ll n,k;    cin>>n>>k;
    std::vector<ll> v(n,0);
    for(int i=0;i<n;i++)    cin>>v[i];
    sort(v.begin(),v.end(),[&](ll x,ll y){return x>y;});
    ll a=0,b=0;
    std::vector<ll> need;
    for(int i=0;i<n;i++)
    {
        if(i%2==0)  a+=v[i];
        else    b+=v[i];
        if(i%2)
        {
            need.push_back(v[i-1]-v[i]);
        }
    }
    ll d=a-b;
    for(auto &t: need)
    {
        if(k>=t && d-t>=0)  k-=t,d-=t;
        else if(d-t>=0 && k<t)
        {
            d-=k;
            break;
        }
    }
    cout<<d<<"\n";

}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

D

可以学到一些\(trick\)的好题，这里可以使用位运算进行处理颜色。

我们要的是距离最小，可以维护每一个城市的左右边，拥有不同颜色且可以直接到达的城市（也就是一个颜色相同、一个颜色不同）。通过中间点，不断的跳跃，可以计算得到需要的距离。

需要预处理的就是\(left\)数组和\(right\)数组，可以使用类似\(dp\)的过程进行处理。

以\(right\)数组为例，如果\(city_i\)与\(city_{i+1}\)有完全相同的颜色或者没有相同的颜色，

那么\(right_i=right_{i+1}\)，因为如果相同，那么直接继承即可。否则，根据\(right\)数组的定义，肯定有一个颜色是\(city_i\)和\(city_{right[i+1]}\)都有的，\(left\)数组也是类似的推导。

需要注意的是：跳跃是通过中间点的，一些细节还是看代码。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=2e5+10;
const ll mod=998244353;
void solve()
{
    //B1 G2 R3 Y4 
    int n,q;    cin>>n>>q;
    std::vector<int> city(n);
    std::string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        for(auto t: s)
        {
            if(t=='B')  city[i]|=(1<<0);
            else if(t=='G') city[i]|=(1<<1);
            else if(t=='R') city[i]|=(1<<2);
            else    city[i]|=(1<<3);
        }
    }
    std::vector<int> left(n,0);     //维护第i个城市的最左边可以直接到达的拥有不同颜色的城市
    std::vector<int> right(n,0);    //维护第i个城市的最右边可以直接到达的拥有不同颜色的城市
    right[n-1]=n;   //后面有妙用
    left[0]=-1;
    for(int i=n-2;i>=0;i--)
    {
        if(city[i]==city[i+1] || (city[i] & city[i+1])==0)
        {
            right[i]=right[i+1];
        }
        else    right[i]=i+1;
    }
    for(int i=1;i<n;i++)
    {
        if(city[i]==city[i-1] || (city[i] & city[i-1])==0)
        {
            left[i]=left[i-1];
        }
        else    left[i]=i-1;
    }
    while(q--)
    {
        int x,y;    cin>>x>>y;
        x-=1,y-=1;
        if(x==y)    cout<<"0\n";
        else
        {
            if(x>y) swap(x,y);
            int ans1=0;
            int tmp=x;
            while(x<n && (city[x] & city[y])==0)    //通过中间点跳跃
            {
                ans1+=right[x]-x;
                x=right[x];
            }
            if(x<n) ans1+=abs(x-y); //可以直接跳
            else    ans1=(1<<30);   //发现跳到n，说明无法到达
            x=tmp;

            int ans2=0;
            while(y>=0 && (city[x] & city[y])==0)   //通过中间点跳跃
            {
                ans2+=y-left[y];
                y=left[y];
            }
            if(y>=0)    ans2+=abs(x-y); //同上
            else    ans2=(1<<30);
            int ans=min(ans1,ans2); //选取min即可
            if(ans>=(1<<30))    cout<<-1<<"\n";
            else    cout<<ans<<"\n";
        }
    }
}
int main()
{
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

E

博弈论，本来自己觉得补不了，在大佬的督促下去补了。正好可以复习下\(SG\)函数，才发现自己以前对这个完全没有正确的认识，正好找这个机会补一补。（发现理解了\(SG\)函数也没有那么难）。

有时间的话看这篇文章：讲明白了\(SG\)函数到底是怎么来的：浅谈SG函数和博弈论 - 洛谷专栏 (luogu.com.cn)

先弄一些前置知识：策梅洛定理。

我们考虑对于一个游戏，他满足以下的特点

两人单挑，轮流操作
信息公开透明
没有随机因素
有限步内必然结束
不存在平局

策梅洛定理：对于这样的一个游戏，任何一个局面先手或者后手其中之一必然存在必胜策略

证明：

如果已经到了最终状态，按照游戏规则，必然有一方已经获胜
如果当前状态所有后继都导向先手必胜，那么本状态先手必败
如果当前状态可以导向先手必败，那么本状态先手必胜

所以每一个状态的胜负都可以被确定。

所以这些游戏可以使用记忆化搜索暴力解决。

回到题目：这种题还是得打表比较好（不会打表。。。）

简单总结就是，偶数的\(SG\)函数值都是0，质数的\(SG\)值就是他在质数表中的位置，合数的\(SG\)函数值就是它的最小质因子的\(SG\)函数值。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int MAXN=1e7+10;
std::vector<int> sg(MAXN,0);
void work(int n)
{
    std::vector<bool> isp(n,1);
    std::vector<ll> prime;
    std::vector<int> tmp(n,0);
    isp[0]=isp[1]=0;
    for(ll i=2;i<=n;i++)
    {
        if(isp[i])   
        {
            prime.push_back(i);
            tmp[i]=prime.size();
        }    
        for(auto t: prime)
        {
            if(i*t>n)    break;
            isp[i*t]=0;
            if(i%t==0)  break;
        }
    }

    sg[0]=0;
    sg[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(i%2==0)  sg[i]=0;
        else if(isp[i])   sg[i]=tmp[i];
        else
        {
            for(auto t: prime)
            {
                if(i%t==0)
                {
                    sg[i]=sg[t];
                    break;
                }
            }
        }
    }
}
void solve()
{
    int n;  cin>>n;
    int ans=0,x=0;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        ans^=sg[x];
    }
    if(ans) cout<<"Alice\n";
    else    cout<<"Bob\n";
}
int main()
{
    work(MAXN);
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

下面是打表的程序：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
const int MAXN=1e7+10;
int mex(auto v ,int x) // v可以是vector、set等容器 
{
    unordered_set<int> S;
    for(int i=0;i<v.size();i++)
    {
        if(__gcd(i,x)==1 && i!=0) S.insert(v[i]);
    }
    for (int i = 0;; ++i)
    {
        if(S.find(i) == S.end())
            return i;
    }    
}
void work()
{
    std::vector<int> sg(3,0);
    sg[0]=0;
    sg[1]=1;
    sg[2]=0;
    for(int i=3;i<=100;i++)
    {
        int val=mex(sg,i);
        sg.push_back(val);
        cout<<i<<": "<<val<<"\n";
    }
}
void solve()
{

}
int main()
{
    work();
    int t=1;
    cin>>t;
    while(t--)  solve();
    return 0;
}

对应的输出结果：