发布时间：2025-04-27

题目链接

F. Tourist(签到)

题意：

初始分数1500，n个数，问到第几次总和至少4000分

void solve(){
    int n;
    cin>>n;
    int x=1500;
    int pos=-1;
    for(int i=1;i<=n;i++){
        int y;
        cin>>y;
        x+=y;
        if(pos==-1&&x>=4000)pos=i;
    }
    cout<<pos<<"\n";
}

I. Strange Binary(思维)

首先$n\%4=0$肯定不行，因为二进制末位必然会有两个$0$

其他情况都可以，最高位置1来完成

J. Stacking of Goods(思维)

重排列货物，使值最小

经典trick，我们看交换两个货物$i,j(j \lt i)$有什么变化

交换前：$v_j+v_i-c_iw_j$

交换后：$v_i+v_j-c_jw_i$

那么贡献不同的只有一部分，按$c_jw_i \lt c_iw_j$排序即可，如果不清楚大于和小于就两个都试一下

void solve(){
    int n;
    cin>>n;
    vector<array<int,3>> a(n);
    for(auto &[w,v,c]:a)cin>>w>>v>>c;
    sort(a.begin(),a.end(),[&](auto x,auto y){
        return x[2]*y[0]<y[2]*x[0];
    });
    int ans=0,W=0;
    for(auto &[w,v,c]:a)ans+=v-W*c,W+=w;
    cout<<ans<<"\n";
}

A. Gambling on Choosing Regionals(签到)

懒得补了

G. Game(数学)

• 两个人玩游戏，一个人获胜的概率为$p_0$,失败为$p_1$，剩下为平局
• 如果获胜的人分数本来就大于等于另一个人，直接赢得比赛
• 否则假设为$x,y(x \lt y),y=y-x$
• 求$A$获胜的概率

思路：

• 可以发现平局是没用的，一局比赛$A$赢的概率为$\frac{p_0}{p_0+p_1}$
• 如果$a=b$，那么赢的概率就是上面的数
• 考虑$a<b$的情况，那么他需要一直赢直到，$a>b$；那么交换位置，又变成了$a<b$的情况
• 一直递归下去即可
• 复杂度和欧几里得相同，$O(\log n)$

int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
int dfs(int a,int b,int pa,int pb){
    if(a==b)return pa;
    if(a>b)return (1-dfs(b,a,pb,pa)+mod)%mod;
    int x=b/a-(b%a==0);
    return qpow(pa,x)%mod*dfs(a,b-x*a,pa,pb)%mod;
}
void solve(){
    int x,y;
    cin>>x>>y;
    int a,b,c;
    cin>>a>>b>>c;
    cout<<dfs(x,y,a*qpow((a+b)%mod,mod-2)%mod,b*qpow((a+b)%mod,mod-2)%mod)<<"\n";
}

L. 502 Bad Gateway(数学)

• 设小于某个阈值$c$后就不再random，那么期望为$\frac{c-1}{2}+\frac{t}{c}$，对勾函数在，$\sqrt 2t$取等

E. Escape(BFS)

$n$个点$m$条边，每条边是双向的有向边，期望从点$1$到$n$，有$k$个机器人，每一秒会随机通过一条边前往下一个点，如果你在过程中被抓到了，就会逃离失败。(即在某一时刻在同一个点)；机器人只能走最多$d$的距离，超过距离会爆炸；设计一条线路，保证一定能逃离，或者说不可能

• 分奇偶考虑，先$BFS$预处理出在奇数还是偶数秒到达某个点的最小时刻
• 然后从$1$出发$BFS$，一个点能到达当他在相同奇偶性的秒数里面，比机器人先到达
• 复杂度$O(n+m)$
• 坑点：输出方案时，必须是没有前驱才停止，而不是到达点$1$就停止(因为$1$有可能会经过两次)

void solve(){
    int n,m,d;
    cin>>n>>m>>d;
    vector<int> adj[n+1];
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector have(n+1,vector<int>(2,INF)),dis(n+1,vector<int>(2,INF)),pre(n+1,vector<int>(2,0));
    int k;
    cin>>k;
    queue<PII> q;
    for(int i=0;i<k;i++){
        int x;
        cin>>x;
        have[x][0]=0;
        q.emplace(x,0);
    }
    while(!q.empty()){
        auto [u,o]=q.front();
        q.pop();
        for(auto v:adj[u]){
            if(have[v][o^1]==INF&&have[u][o]+1<=d){
                have[v][o^1]=have[u][o]+1;
                q.emplace(v,o^1);
            }
        }
    }
    dis[1][0]=0;
    q.emplace(1,0);
    int tt=-1;
    while(!q.empty()){
        auto [u,o]=q.front();
        q.pop();
        // if(u==n){
        //     tt=o;
        //     break;
        // }
        for(auto v:adj[u]){
            if(dis[v][o^1]==INF&&have[v][o^1]>dis[u][o]+1){
                pre[v][o^1]=u;
                dis[v][o^1]=dis[u][o]+1;
                q.emplace(v,o^1);
            }
        }
    }
    if(min(dis[n][0],dis[n][1])==INF)tt=-1;
    else if(dis[n][0]<dis[n][1])tt=0;
    else tt=1;
    if(tt==-1){
        cout<<"-1\n";
        return;
    }
    vector<int> st;
    int x=n;
    while(x){
        st.push_back(x);
        x=pre[x][tt];
        tt^=1;
    }
    cout<<st.size()-1<<"\n";
    while(st.size()){
        cout<<st.back()<<" ";
        st.pop_back();
    }
    cout<<"\n";
}

C. Prefix of Suffixes(kmp+结论)

对于$A_i$，满足的匹配的$j$满足$S[1...n-i]=S[i...n-1]$,我们需要维护这些对应的$i$下标的总和

实际上是z函数，但是需要动态维护

可以使用kmp求解,一开始的想法是在$j=ne[j]$失配的过程中，减去对应的值，但是这会漏掉一些情况

比如字符串aacaac，$ne[5]=2,ne[6]=3$，在下标$5$时的贡献是$B[4]+B[5]$，在下标$6$的贡献为$B[4]+B[6]$，但是下标$5$的贡献并不会减去，因此还是需要暴力跳，但是直接跳会超时

这里需要知道一些结论：

1. 对于一个下标$i$，它生成的$ne_i$会最多形成$\log n$个值域不相交的等差数列
2. 对于等差数列的一个数如果他能匹配$S[ne[j]+1]=S[i]$，那么整个等差数列都能匹配，此时可以直接跳到等差数列的头部

复杂度$O(n \log n)$

void solve(){
    int n;
    cin>>n;
    vector<int> S={0},A={0},B={0};
    int ans=0;
    int sum=0;
    vector<int> ne(n+1),top(n+1);
    for(int i=1;i<=n;i++){
        int s,a,b;
        cin>>s>>a>>b;
        s=(s+ans)%n;
        S.push_back(s);
        A.push_back(a);
        B.push_back(b);
        ans+=B[1]*A[i];
        if(i==1){
            cout<<ans<<"\n";
            continue;
        }
        int j=ne[i-1];
        while(j&&S[i]!=S[j+1]){
            sum-=B[i-j];
            j=ne[j];
        }
        if(S[i]==S[j+1])ne[i]=j+1;
        else ne[i]=j;
        if(i-ne[i]==ne[i]-ne[ne[i]])top[i]=top[ne[i]];
        else top[i]=ne[i];
        if(S[1]==S[i])sum+=B[i];
        while(j){
            if(S[j+1]==S[i]){
                if(S[ne[j]+1]==S[i]){
                    j=top[j];
                }
                else j=ne[j];
            }
            else{
                sum-=B[i-j];
                j=ne[j];
            }
        }
        ans+=sum*A[i];
        cout<<ans<<"\n";
    }
}

K. match(01trie分治+多项式乘法+组合数)

题意： 一个二分图

两个点可以匹配当$a_ i\oplus b_j \geq k$

问对于所有的$x \in[1,n]$，有多少种方案匹配数为$x$

• 因为是异或，所以从高到低按位考虑，然后自底向上合并答案
• 设$f(A,B,i)$表示考虑到第$i$位，集合内满足的方案数，返回一个多项式
• 假设$A_0$为第$i$位为$0$的$A$集合的数，同理$A_1,B_0,B_1$
• 如果$k$的第$i$位为$0$，那么当前位不同的都可以任选，因此先算出来$f(A_0,B_0,i-1),f(A_1,B_1,i-1)$的多项式，然后枚举$0,1$匹配分别用了多少个数，那么剩余的$A_1$和$B_0$,$A_0$和$B_1$可以任意匹配，统计答案
• 如果为$1$，则当前位只能选不一样的，合并$f(A_0,B_1,i-1),f(A_1,B_0,i-1)$
• 多项式合并就是做多项式乘法，这很好理解
• 考虑大小为$n$和$m$的集合任意匹配，有多少种方案
• 对于匹配数$i$，显然有$\binom{n}{i} \binom{m}{i}$种选取，然后这$i$个数可以任意组合方案为$i!$，因此总方案为$\binom{n}{i} \binom{m}{i} i!$
• 复杂度$O(n^4)$，不太会分析，对于dfs的次数为字典树节点的个数$2n$，每个节点最坏为$n^4$，理论上为$O(n^5)$(因此如果每次设数组大小为$n$就会超时)，但是实际上远达不到

int fac[210],ifac[210],n,k;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n-1;i>=0;i--){
        ifac[i]=ifac[i+1]*(i+1)%mod;
    }
}
int C(int n,int m){
    if(n<m||m<0)return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
vector<int> mul(const vector<int> &a,const vector<int> &b){
    vector<int> ans(a.size()+b.size()-1);
    for(int i=0;i<a.size();i++){
        for(int j=0;j<b.size();j++){
            ans[i+j]=(ans[i+j]+a[i]*b[j])%mod;
        }
    }
    return ans;
}
vector<int> get(int n,int m){
    vector<int> ans(min(n,m)+1);
    for(int i=0;i<ans.size();i++)ans[i]=C(n,i)*C(m,i)%mod*fac[i]%mod;
    return ans;
}
vector<int> dfs(vector<int> &a,vector<int> &b,int bit){
    if(a.empty()||b.empty())return {1};
    if(bit==-1)return get(a.size(),b.size());
    vector<vector<int>> A(2),B(2);
    for(auto &x:a){
        A[x>>bit&1].push_back(x);
    }
    for(auto &x:b){
        B[x>>bit&1].push_back(x);
    }
    if(k>>bit&1)return mul(dfs(A[0],B[1],bit-1),dfs(A[1],B[0],bit-1));
    auto ans=dfs(A[0],B[0],bit-1),res=dfs(A[1],B[1],bit-1);
    vector<int> Ans(min(a.size(),b.size())+1);
    for(int i=0;i<ans.size();i++){
        for(int j=0;j<res.size();j++){
            array<int,2> cnta,cntb;
            cnta[0]=A[0].size()-i;
            cntb[0]=B[0].size()-i;
            cnta[1]=A[1].size()-j;
            cntb[1]=B[1].size()-j;
            int val=ans[i]*res[j]%mod;
            vector<int> tmp=mul(get(cnta[0],cntb[1]),get(cnta[1],cntb[0]));
            for(int x=0;x<tmp.size();x++){
                Ans[i+j+x]=(Ans[i+j+x]+tmp[x]*val%mod)%mod;
            }
        }
    }
    return Ans;
}
void solve(){
    cin>>n>>k;
    init(n);
    vector<int> a(n),b(n);
    for(auto &x:a)cin>>x;
    for(auto &x:b)cin>>x;
    auto ans=dfs(a,b,59);
    while(ans.size()<n+1)ans.push_back(0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<"\n";
}