Logo

菜单

2025.7.15模拟赛赛后

wjyppm
发布于 2025-07-15 / 9 阅读
0
0
#题解#笔记

0.前言

省流：\text{Rk } 1 \to \text{Rk 3},305 \to 255。

T1 虎爷ywk

判断是否存在正整数 n，使得 k|n^2，但 k 不能整除 n，若存在输出最小的 n，否则输出 -1。
1\le k \le 10^{12}

这个数据范围一眼就让我想到 O(\sqrt{k})，但是怎么个根号？有一个显然的想法就是 \sqrt{k} \to k 试除，但是这样显然是不行的。

考虑将 k 质因数分解为 p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}}\dots，那么题目构造过程就是当 a_{1} 为偶数时直接除 2 即可，若为奇数则加 1 除 2 即可。这样构造保证最小，最坏情况就是 k|n 直接输出 -1 即可，时间复杂度 O(\sqrt{k})。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
int K,fk,ret;
vector<pir> op;

int ksm(int a,int b){
    int ret=1;
    while(b){
        if(b&1) ret=ret*a;
        a=a*a;
        b>>=1;
    }
    return ret;
}

signed main(){
    freopen("SH.in","r",stdin);
    freopen("SH.out","w",stdout);
    cin>>K;
    fk=K;
    for(int i=2;i<=sqrt(fk);i++){
        if(K%i==0){
            int s=0;
            while(K%i==0){
                K/=i;
                s++;
            }
            op.push_back(pir(i,s));
        }
    }
    if(K>1) op.push_back(pir(K,1));
    ret=1;
    for(auto p:op){
        if(p.second%2==0) ret*=ksm(p.first,p.second/2);
        else ret*=ksm(p.first,(p.second+1)/2);
    }
    if(ret%fk==0) cout<<-1;
    else cout<<ret;
    return 0;
}

T2 Johnsonloy的比赛

image.png

博弈论，但是 SG 不好做，考虑 DP，最优决策下一定时从大到小拿取，证明考虑反证法与调整法证明即可，所以先排序，让后设 f(i,0/1) 表示到第 i 个题，当前是 Crimson000 学长先手还是 \text{YC乌龙} 学长先手，Crimson000 的最大得分。显然转移：

\begin{aligned} f(i,0)&=\max\limits_{j=1}^{i-1} f(j,1)+sum_{i}-sum_{j} \\ f(i,1)&=f(i-1,0) \end{aligned}

可以单调队列优化或线段树优化，时间复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2e6+15;
int n,a[MN],q[MN],sum[MN],f[MN][2],ql,qr;

struct Segment{
#define ls p<<1
#define rs p<<1|1

    struct Node{
        int l,r,val;
    }t[MN<<2];

    void pushup(int p){
        t[p].val=max(t[ls].val,t[rs].val);
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            t[p].val=-1e9;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int pos,int k){
        if(t[p].l==t[p].r){
            t[p].val=k;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=pos) modify(ls,pos,k);
        else  modify(rs,pos,k);
        pushup(p);
    }

    int query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val;
        }
        int mid=(t[p].l+t[p].r)>>1;
        int ret=-1e9;
        if(mid>=fl) ret=max(ret,query(ls,fl,fr));
        if(mid<fr) ret=max(ret,query(rs,fl,fr));
        return ret;
    }

}sg;

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

bool cmp(int x,int y){
    return x>y;
}

signed main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    read(n);
    sg.build(1,1,n);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    f[1][0]=a[1],f[1][1]=0;
    sg.modify(1,1,0);
    for(int i=2;i<=n;i++){
        f[i][0]=sg.query(1,1,i-1)+sum[i];
        f[i][1]=f[i-1][0];
        sg.modify(1,i,f[i][1]-sum[i]);
    }
    put(max(f[n][0],f[n][1]));
    return 0;
}

T3 会后空翻的YC乌龙

image.png

操作可逆。考虑贪心，每一次遇到 c_{i}\neq s_{i} 的时候我们就开始以 i 为左端点开始枚举右端点，考虑右端点什么取到，当 cnt_{1} \bmod 2 =0 并且 c_{j}=s_{i} 的时候我们可以考虑翻转。

由于翻转操作是可逆的，任何操作序列都可以重新排列为从左到右的贪心操作序列。所以不会漏解，每次操作至少修正一个不匹配的位置，最多 O(n) 次。

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e5+15;
int cntc,cnts,n;
string c,s;
vector<pir> op;

int main(){
    freopen("YC.in","r",stdin);
    freopen("YC.out","w",stdout);
    cin>>c>>s;
    for(int i=0;i<c.length();i++){
        if(c[i]=='0') cntc++;
        if(s[i]=='0') cnts++;
    }
    if(cntc!=cnts){
        cout<<"NO";
        return 0;
    }
    for(int i=0;i<c.length();i++){
        if(c[i]!=s[i]){
            int cnt1=0;
            bool flag=0;
            for(int j=i;j<c.length();j++){
                if(c[j]=='1') cnt1++;
                if(!(cnt1&1)&&c[j]==s[i]){
                    op.push_back(pir(i+1,j+1));
                    int x=i,y=j;
                    while(x<y){
                        swap(c[x],c[y]);
                        x++,y--;
                    }
                    flag=1;
                    break;
                }
            }
            if(!flag){
                cout<<"NO";
                return 0;
            }
        }
    }
    cout<<"YES\n"<<op.size()<<'\n';
    for(auto p:op) cout<<p.first<<" "<<p.second<<'\n';
    
    return 0;
}

T4 博弈论

原：CF1076G

不是我真的服了，pos 开 11 就 RE 敏感肌是吧。

先考虑 [1,n] 怎么做，根据 T2 原则提高组博弈论不考 SG 函数显然考虑 DP，设 f_{i} 表示到第 i 座山，先手能否必赢还是必败。正着 DP 及其难做，考虑倒过来 DP。有两个转移：

  • 当 a_{i} 是奇数时，f_{i}=1，先手必胜。
  • 当 a_{i} 是偶数时，若 f \in [i+1,i+m] 中没有必败状态则先手必败，否则先手必胜。

奇偶在于看谁跳出去。

时间复杂度 O(nmq) 无法通过。

考虑优化，考虑线段树维护，注意到 m\le 10，考虑从这里下手。根据 f 的性质时 01 序列，考虑把区间有用的 dp 值状压下来。

对于线段树的区间我们记录如果 [r+1,r+m] 的 dp 状态值为 S，那么区间 [l,l+m-1] 的 dp 值是什么，合并很好合并。

考虑区间修改，区间修改其实就是在修改奇偶性，注意到加偶数没有任何卵用，加奇数其实就是区间反转奇偶性，直接打反转 tag 和维护两个状压集合就可以。

进一步优化，许多的 S 是没有用的，我们只需要知道 S 中第一个 0 在哪里就可以了，时间 O(qm \log n)。

恭喜 PPM，成功挂分 100->50！

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
int n,m,q,a[MN];

struct Segment{
#define ls p<<1
#define rs p<<1|1

    struct QWQ{
        int pos[16];
        //敏感肌pos开小就炸杠
        QWQ operator +(const QWQ &x)const{
            QWQ ret;
            for(int i=1;i<=m+1;i++){
                ret.pos[i]=pos[x.pos[i]];
            }
            return ret;
        }
    };

    struct Node{
        int l,r;
        int isrev;
        QWQ val[2];
    }t[MN<<2];

    void dorev(int p){
        swap(t[p].val[1],t[p].val[0]);
        t[p].isrev^=1;
    }

    void pushdown(int p){
        if(t[p].isrev){
            dorev(ls);
            dorev(rs);
            t[p].isrev=0;
        }
    }

    void pushup(int p){
        t[p].val[0]=t[ls].val[0]+t[rs].val[0];
        t[p].val[1]=t[ls].val[1]+t[rs].val[1];
    }

    void build(int p,int l,int r){
        t[p].l=l;
        t[p].r=r;
        if(l==r){
            if(a[l]==1){
                t[p].val[0].pos[m+1]=m+1;
                t[p].val[1].pos[m+1]=1;
            }else{
                t[p].val[0].pos[m+1]=1;
                t[p].val[1].pos[m+1]=m+1;
            }
            for(int i=1;i<=m;i++){
                t[p].val[0].pos[i]=t[p].val[1].pos[i]=i+1;
            }
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(p);
    }

    void modify(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            dorev(p);
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid>=fl) modify(ls,fl,fr);
        if(mid<fr) modify(rs,fl,fr);
        pushup(p);
    }

    QWQ query(int p,int fl,int fr){
        if(t[p].l>=fl&&t[p].r<=fr){
            return t[p].val[0];
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(mid<fl) return query(rs,fl,fr);
        if(mid>=fr) return query(ls,fl,fr);
        return query(ls,fl,fr)+query(rs,fl,fr);
    }
}sg;

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

signed main(){
    freopen("boyi.in","r",stdin);
    freopen("boyi.out","w",stdout);
    read(n,m,q);
    for(int i=1;i<=n;i++){
        read(a[i]);
        a[i]=(a[i]&1)^1;
    }
    sg.build(1,1,n);
    while(q--){
        int op,l,r,x;
        read(op,l,r);
        if(op==1){
            read(x);
            if(x&1) sg.modify(1,l,r);
        }else{
            auto ret=sg.query(1,l,r);
            if(ret.pos[m+1]==1){
                put("Bob");
            }else put("Alice");
        }
    }
    return 0;
}

后言

构造太烂了，要加紧学习构造了。

写完题后不要傻坐，赶紧对拍或者检查代码越界，用 fsanitize 越界报错。

成绩不太满意，主要原因还是经验太少和大意，以后一定要更正这些错误。

整体二分
图论优化建图

评论