2023.9.6 wzOI全场题解

· · 个人记录

A

说实话，这道题耗了我挺久的，很烦人。

原题:P7175 [COCI2014-2015#4] PŠENICA

如果你一个一个模拟的删，最后一个一个地都到中间去了，复杂度是 O(n^2) 的，我们发现这个过程肯定是有重复计算的。

注意到，Mirko 的操作是让最小的变第二小，Slavko 是让最大的变第二大，也就是在数量小于 3 之前他们的操作都是互不影响的，所以我们不妨考虑让他们每次进行相同次的操作，要么让最小的全部变成第二小，要么让最大的全部变成第二大，这样我们可以保证我们每次至少减少一个数，复杂度 O(n)，考虑到 h\le10^5，我们直接桶排就行了。

具体细节不妨看代码:

Code

int n,a[200005],cnt,trans[200005],b[200005];
int main(){
    n=read();
    for(int i=1;i<=n;i++)++a[read()];
    for(int i=0;i<=200000;i++){
        if(a[i])b[++cnt]=a[i],trans[cnt]=i;//记录
    }
    int l=1,r=cnt;
    while(r-l>=3){//如果个数大于4就一直进行减少操作
        if(b[l]>b[r])b[r-1]+=b[r],b[l+1]+=b[r],b[l]-=b[r],b[r]=0;//减去最小的
        else b[r-1]+=b[l],b[l+1]+=b[l],b[r]-=b[l],b[l]=0;
        if(!b[l])l++;//如果没了就移动指针
        if(!b[r])r--;
    }
    if(r-l<2)printf("Slavko\n%d %d",trans[l],trans[r]);//这里不仅是考虑了一开始长度就小于3的清况
    //还有因为长度等于四而两边相等然后减掉后只剩下两个的情况
    //所以答案显然是 Slavko 胜利
    else{//长度为 3 时
        if(b[l]<=b[r])puts("Mirko"),l++;//取等时因为Mirko是先手，所以胜利
        else puts("Slavko"),r--;
        printf("%d %d",trans[l],trans[r]);
    }
}

B

不会，但是之后听懂了，有时间我自己手推一遍，数学公式打起来很麻烦，所以直接复制 fjp 的源码了。

前言

这是前省一选手在看到数竞题之后有感而发，而出的一道题，他用心良苦，只为锻炼信竞选手的数学能力

题意

有 10 个石子，从左到右排成一列，编号 1 到 10，如果两个石子在某一时刻满足以下两个条件，则可以交换：

可以任意交换，问最终可以得到多少种不同的排列。

数竞原题是这样，然后我们把 10 推广到 n (n\le2\times 10^5)就变成了信竞题。

题目分析 by\ fjp

记数组 x_i 表示总石子个数为 i 的合法排列的数目,数组 A_i 表示第一个位置是 1 号石子的合法排列的数目，数组 B_i 表示第一个位置是 2 号石子的合法排列的数目，数组 C_i 表示第一个位置是 3 号石子的合法排列的数目，数组 D_i 表示第一个位置是 4 号石子的合法排列的数目。
首先，第一个位置只有可能是 1,2,3,4 号石子这四种可能，因为 1 号石子不可能和 5 号石子交换，所以 5 号石子不可能跑到 1 号石子的前面去，更别说在第一个位置了。而比 5 还要大的石子就更不可能跑到第一个位置去了。所以，

x_i=A_i + B_i+C_i+D_i

接下来考虑 A_i,B_i,C_i,D_i 怎么求。
首先，A_i 是最简单的。由于第一个位置是 1 号石子，所以这就相当于没有石子和 1 号石子交换过，所以 1 号石子不影响后续 2 \thicksim i 号石子的交换，所以

A_i=x_{i-1}

接着，考虑 B_i。这时，考虑到 5 不可能跑到 1 的前面去，所以所有可能的排列有

(2,1,\cdots)(2,3,1,\cdots)(2,4,1,\cdots)(2,3,4,1,\cdots)(2,4,3,1,\cdots) (2,1,\cdots)$ 的数目就是 $x_{i-2}$，因为 $1$ 和 $2$ 已经定好，所以不影响 $3\thicksim i$ 的交换。同样，$(2,3,1,\cdots)$ 的数目是 $x_{i-3}$，$(2,3,4,1,\cdots)$ 的数目是 $x_{i-4}$，$(2,4,3,1,\cdots)$ 的数目是 $x_{i-4}$。最后只剩下 $(2,4,1,\cdots)$ 这一种情况。看看剩下的石子，有 $3,5,6,7,\cdots,i$，由于石子能不能交换只和两个石子之间的差有关，所以 $3,5,6,7,\cdots,i$ 这些石子的能得到的排列数目就等于 $1,3,4,5,\cdots,i-2$ 能得到的排列数目。$1,3,4,5,\cdots,i-2$ 这里缺少 $2$，所以就相当于 $2$ 号石子已经排在最前面固定下来，剩下的石子能交换，所以这个排列数目就是 $B_{i-2}\textcolor{red}{(\ast)}

综上，

B_i=B_{i-2}+x_{i-2}+x_{i-3}+2\times x_{i-4}

然后，考虑 C_i。 所有可能的排列有

(3,1,\cdots)(3,2,1,\cdots)(3,4,1,\cdots)(3,2,4,1,\cdots)(3,4,2,1,\cdots)

先把简单的情况处理掉。 (3,2,1,\cdots) 数目是 x_{i-3}，(3,2,4,1,\cdots) 的数目是 x_{i-4}，(3,4,2,1,\cdots)的数目是 x_{i-4}。(3,1,\cdots) 用 \textcolor{red}{(\ast)} 的方法可知，排列数目是 B_{i-1}。 最后只剩下 (3,4,1,\cdots)的情况。考虑到 6 不可能跑到 2 的前面去,所以只可能有 (3,4,1,2,\cdots) 和 (3,4,1,5,2,\cdots) 这两种情形。(3,4,1,2,\cdots) 的数目是 x_{i-4}，(3,4,1,5,2,\cdots) 的数目是 x_{i-5}，所以总的情况就是 x_{i-4}+x_{i-5}\textcolor{red}{(\ast\ast)}综上

C_i=B_{i-1}+x_{i-3}+3\times x_{i-4}+ x_{i-5}

最后，我们考虑 D_i。 所有可能的排列有

(4,1,\cdots)(4,2,1,\cdots)(4,3,1,\cdots)(4,2,3,1,\cdots)(4,3,2,1,\cdots)

其中，(4,2,3,1,\cdots) 的数目是 x_{i-4}，(4,3,2,1,\cdots) 的数目是 x_{i-4}。(4,2,1,\cdots) 用 \textcolor{red}{(\ast)} 的方法可知，排列数目是 B_{i-2}。

最后只剩下 $(4,1,\cdots)$ 的情况。看看剩下的石子，有 $2,3,5,6,7,\cdots,i$，由于石子能不能交换只和两个石子之间的差有关，所以 $2,3,5,6,7，\cdots,i$ 这些石子的能得到的排列数目就等于 $1,2,4,5,6,7,\cdots,i-1$ 能得到的排列数目。$1,2,4,5,6,7,\cdots,i-1$ 这里缺少 $3$ ，所以就相当于 $3$ 号石子已经排在最前面固定下来，剩下的石子能交换，所以这个排列数目就是 $C_{i-1}$。综上 $$D_i=B_{i-2}+ C_{i-1}+ 3\times x_{i-4}+ x_{i-5}$$ 到现在，$x,A,B,C,D$ 的递推式我们都得到了。关于 $x,A,B,C,D$ 的初值，看 $std$ 就行了。 ### $std\ by\ fjp 
#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool read_(T &ready_get)
{
    T x=0,f=1;
    char ch=getchar();
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-') f=-1;
        ch=getchar();
        if(ch==-1) return false;
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+(ch-'0');
        ch=getchar();
    }
    ready_get=x*f;
    return true;
}
template <typename T>
void write_(T ready_put)
{
    if(ready_put<0) putchar('-'),ready_put*=-1;
    if(ready_put>9) write_(ready_put/10);
    putchar(ready_put%10+'0');
}
int T,n;
const long long mod=998244353,rn=2e5+10; 
long long x[rn],A[rn],B[rn],C[rn],D[rn];
void init()
{
    A[0]=0;B[0]=0;C[0]=0;D[0]=0;x[0]=1;
    A[1]=1;B[1]=0;C[1]=0;D[1]=0;x[1]=1;
    A[2]=1;B[2]=1;C[2]=0;D[2]=0;x[2]=2;
    A[3]=2;B[3]=2;C[3]=2;D[3]=0;x[3]=6;
    A[4]=6;B[4]=6;C[4]=6;D[4]=6;x[4]=24;
    for(int i=5;i<=rn;++i)
    {
        A[i]=x[i-1]%mod;
        B[i]=(B[i-2]+x[i-2]+x[i-3]+2*x[i-4])%mod;
        C[i]=(B[i-1]+x[i-3]+3*x[i-4]+x[i-5])%mod;
        D[i]=(B[i-2]+C[i-1]+3*x[i-4]+x[i-5])%mod;
        x[i]=(A[i]+B[i]+C[i]+D[i])%mod;
    }
}
int main()
{
    init();
    read_(T);
    while(T--)
    {
        read_(n);
        write_(x[n]),putchar('\n');
    }
    return 0;
}

C

原题：P4042 [AHOI2014/JSOI2014] 骑士游戏

前言

应该是第一次考场切紫（之前模拟赛没评级我也不知道有没有切过紫的），虽然 CE 了但是我还是觉得是考场切紫。说实话我感觉这题比最后两题都要简单，但是后两题都是蓝，就一个这个是紫的，洛谷评级这么合理？

\color{Red}{千万不要在考场上用一些没有用过常见英文单词做变量名或者函数名！！}

血的教训，因为有一个数组用了 kill[]，虽然本地可以编译并且所有样例都过了，但是在各大 OJ 上都是 CE。所以为什么不报错呢？真的服了。100->0。

思路

一开始觉得应该是跑个图什么的，比如用拓扑去更新之类的，发现有环，想到是不是要缩点，想到自己 tarjan 已经忘干净了，然后先去看了一下后面的题发现都不是什么善茬，又回来了。

然后就有了一个很关键的贪心思路，千万要注意，普通攻击是杀不死怪物的（R_i\ge 1，即一定会分裂），而所有攻击的代价都是正值，那么我们要用激光攻击杀死至少一只怪物。

那很显然的，激光攻击最小的那只就一定会被激光杀死，此时我们完全不需要考虑任何的环之类的，继续考虑一个类拓扑的东西。

如果 x 能变成 y，我们就给 y->x 连一条单向边并记录此时 x 的入度。每次我们弹出一个被杀死代价最小的怪兽，设代价为 k，然后用它去更新它连接的点，因为它死了，假设此时 x 花 v 的代价可以变成它，我们就让代价变成 v+k，并且此时 x 不再能变成它。这个思想的正确性很显然。那如果我们发现 x 不能变成任何怪兽了，那么此时杀死它的代价就可以是它的变身代价了吧？

然后这题又做完了，复杂度是一个非常优秀的 O(\sum R_i\log \sum R_i)。

Code

typedef long long ll;
const ll N=200005;
typedef pair<ll,ll> PII;
ll n,inn[N];//入度
vector<ll>f[N];
bool die[N];//这只怪物死了没
ll to[N],kil[N];//to 表示分裂代价，kil表示杀死代价
priority_queue<PII,vector<PII>,greater<PII> >Q;
int main(){
    n=read();
    for(ll i=1;i<=n;i++){
        to[i]=read();
        kil[i]=read();//被杀死的代价
        Q.push({kil[i],i});
        inn[i]=read();//入度其实就是可以变成的怪物数
        for(ll j=1;j<=inn[i];j++)
            f[read()].push_back(i);
    }
    while(!Q.empty()){
        ll w=Q.top().first,x=Q.top().second;
        Q.pop();
        if(die[x])continue;
        die[x]=1;
        kil[x]=min(kil[x],w);
        for(ll y:f[x]){
            if(die[y])continue;
            to[y]+=w;//因为这只怪物必死，所以分裂代价就要加
            if(!--inn[y])Q.push({to[y],y});//如果不能分裂，说明分裂可以直接死，加入答案
        }
    }
    cout<<kil[1];//输出杀死1的代价即可。
    return 0;
}

后记

我觉得 SPFA 的复杂度不一定正确，思路也很巧妙，但是显然可以用类似于网络图套菊花图之类的特殊图卡掉，这题数据水，不然看 D 题虽然在赛时过了但是却显然过不了 CF。

D

原题：CF1627E Not Escaping

考场上想不到什么很好的做法，只是觉得这个看上去很好建图，一看是单向边且只能向上，有想到 dp，但是觉得状态太难记录了，好像不是按照层数来的，比如如果去掉 x_i 就是一个很简单的 dp 水题了，所以就打算打个建图暴力了（感觉出题人的建图水平应该卡不掉我的 SPFA，然后发现连普通 dfs 都没卡掉）。

每个楼梯开个点，然后跑个 SPFA 即可。

赛时满分 Code

const int N=100050;
typedef pair<int,ll> PII;
struct FLOOR{int stx,sty,enx,eny;ll hp;};
struct loca{int x,y;}w[N];
int n,m,g,a[N],tot;
vector<FLOOR>fl[N];
vector<PII>f[N],id;
queue<int>Q;
ll dis[N];
bool vis[N];
int main(){
    for(int T=read();T--;){
        n=read(),m=read(),g=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
        }
        for(int i=1;i<=g;i++){
            int x1=read(),y1=read(),x2=read(),y2=read(),hp=read();
            fl[x1].push_back({x1,y1,x2,y2,hp});
        }
        w[(tot=1)]={1,1};
        for(int i=1;i<=tot;i++){
            int F=w[i].x;
            for(auto flo:fl[F]){
                w[++tot]={flo.enx,flo.eny};
                if(flo.enx==n)id.push_back({tot,flo.eny});
                f[i].push_back({tot,1ll*abs(flo.sty-w[i].y)*a[F]-flo.hp});
            }
        }
        for(int i=2;i<=tot;i++)dis[i]=1e18;
        dis[1]=0;
        Q.push(1);
        while(!Q.empty()){
            int x=Q.front();
            Q.pop();
            vis[x]=0;
            for(auto PI:f[x]){
                ll y=PI.first,w=PI.second;
                if(dis[y]>dis[x]+w){
                    dis[y]=dis[x]+w;
                    if(!vis[y]){
                        vis[y]=1;
                        Q.push(y);
                    }
                }
            }
        }
        ll ans=1e18;
        for(auto PI:id){
            int y=PI.first,eny=PI.second;
            if(dis[y]+1ll*abs(m-eny)*a[n]<ans)ans=dis[y]+1ll*abs(m-eny)*a[n];
        }
        if(ans>1e17)puts("NO ESCAPE");
        else printf("%lld\n",ans);
        for(int i=1;i<=tot;i++)f[i].clear(),vis[i]=0;
        for(int i=1;i<=n;i++)fl[i].clear();
        id.clear();
    }
    return 0;
}

然而不出我所料，在 Codeforces 上第四个点就 T 了，原因之一是其本身就是一个网络图，然后显然就噶了。

考虑正解。

SPFA 被卡的原因大概也有我对于每一个终点都通过起点跟起点所在层的所有终点连了边，而如果同一层有 10^4 个起点，然后上面有 10^4 个终点，那光连边的复杂度就得爆炸。

首先还是用一个很显然的结论，我只可能往 (n,m) 和楼梯走，所以有效点只有起点终点和楼梯的起点和终点。考虑每个有效点的答案 dp_i 表示到 i 点减小的最小生命值，那么显然如果它是楼梯终点，它的答案可以从楼梯起点转移过来，也可以从同层的点转移过来，因为同层左右都有，所以得做两次转移。有人可能会觉得做两次转移不会使其错误吗，答案是显然的不会，如果之前转移来的没有被更新，显然也不会加入答案，复杂度 O(k)。

Code

const int N=100050;
typedef pair<int,ll> PII;
struct FLOOR{
    int i,x,to=-1,hp;
    inline bool operator <(const FLOOR &w)const{return x<w.x;}
};
int n,m,g,a[N],tot;
vector<FLOOR>f[N];
ll dp[200005];
int main(){
    for(int T=read();T--;tot=0){
        n=read(),m=read(),g=read();
        for(int i=1;i<=n;i++)
            a[i]=read(),f[i].clear();
        for(int i=1;i<=g;i++){
            int x1=read(),y1=read(),x2=read(),y2=read(),hp=read();
            f[x1].push_back({++tot,y1,tot+1,hp});
            f[x2].push_back({++tot,y2,-1,0});
        }
        f[1].push_back({++tot,1,-1,0});
        f[n].push_back({++tot,m,-1,0});
        for(int i=1;i<=tot;i++)dp[i]=1e18+0.3;
        dp[tot-1]=0;
        for(int t=1;t<=n;t++){
            sort(f[t].begin(),f[t].end());
            for(int i=1;i<f[t].size();i++)
                dp[f[t][i].i]=min(dp[f[t][i].i],dp[f[t][i-1].i]+1ll*(f[t][i].x-f[t][i-1].x)*a[t]);
            for(int i=f[t].size()-2;i>=0;--i)
                dp[f[t][i].i]=min(dp[f[t][i].i],dp[f[t][i+1].i]+1ll*(f[t][i+1].x-f[t][i].x)*a[t]);
            for(int i=0;i<f[t].size();i++)
                if(dp[f[t][i].i]<1e18)
                dp[f[t][i].to]=min(dp[f[t][i].to],dp[f[t][i].i]-f[t][i].hp);
        }
        if(dp[tot]<1e18)printf("%lld\n",dp[tot]);
        else puts("NO ESCAPE");
    }
    return 0;
}

E

原题:P7497 四方喝彩

第五的题唉！咳咳。赛时没啥思路，打了个暴力跑了。

发现没有 3 操作就是个线段树2模板，有的话怎么思考呢？
我一开始有想比如对每个区间记一个封印时长，然而这样在对应时间的时候可能因为上面标记没有下来导致没有被解封，如果强行下传解封可能导致复杂度退化到 O(nm\log n)。所以我们不如直接对于每一个封印操作追加一个解封操作。具体的，每次封印都增加印记，解封减少封印，只有当封印为 0 时才彻底解封。
封印的问题解决了，答案怎么计算？我们每次乘法和加分肯定是依据没被封印的长度来的，不如我们记三个值：没封印的值，封印的值，没封印的个数。然后具体细节看代码吧。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid (l+r>>1)
#define ls (root<<1)
#define rs (root<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int mod=1e9+7;
int read(){
    int x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
struct tree{
    ll zv,fv,len,mu=1,plus,ban;
}tr[800005];
int n,m;
inline void pushup(int root){
    tr[root].fv=(tr[ls].fv+tr[rs].fv)%mod;
    tr[root].zv=(tr[ls].zv+tr[rs].zv)%mod;
    tr[root].len=tr[ls].len+tr[rs].len;
}
inline void pushdown(int root){
    if(!tr[root].plus&&tr[root].mu==1)return;
    if(!tr[ls].ban){
        (tr[ls].zv*=tr[root].mu)%=mod;
        (tr[ls].zv+=tr[root].plus*tr[ls].len%mod)%=mod;
        tr[ls].plus=(tr[ls].plus*tr[root].mu%mod+tr[root].plus)%mod;
        (tr[ls].mu*=tr[root].mu)%=mod;
    }
    if(!tr[rs].ban){
        (tr[rs].zv*=tr[root].mu)%=mod;
        (tr[rs].zv+=tr[root].plus*tr[rs].len%mod)%=mod;
        tr[rs].plus=(tr[rs].plus*tr[root].mu+tr[root].plus)%mod;
        (tr[rs].mu*=tr[root].mu)%=mod;
    }
    tr[root].plus=0;
    tr[root].mu=1;
    return;
}
void build(int root,int l,int r){
    if(l==r)return tr[root].len=1,tr[root].zv=read(),void();
    build(lson),build(rson);
    pushup(root);
}
void Mu(int root,int l,int r,int x,int y,ll v){
    if(tr[root].ban)return;
    if(x<=l&&r<=y){
        (tr[root].zv*=v)%=mod;
        (tr[root].mu*=v)%=mod;
        (tr[root].plus*=v)%=mod;
        return;
    }
    pushdown(root);
    if(mid>=x)Mu(lson,x,y,v);
    if(mid<y)Mu(rson,x,y,v);
    pushup(root);
}
void add(int root,int l,int r,int x,int y,ll v){
    if(tr[root].ban)return;
    if(x<=l&&r<=y){
        (tr[root].zv+=v*tr[root].len%mod)%=mod;
        (tr[root].plus+=v)%=mod;
        return;
    }
    pushdown(root);
    if(mid>=x)add(lson,x,y,v);
    if(mid<y)add(rson,x,y,v);
    pushup(root);
}
void locked(int root,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        if(!tr[root].ban){
            tr[root].len=0;
            (tr[root].fv+=tr[root].zv)%=mod;
            tr[root].zv=0;
        }
        tr[root].ban++;
        return;
    }
    pushdown(root);
    if(mid>=x)locked(lson,x,y);
    if(mid<y)locked(rson,x,y);
    if(!tr[root].ban)pushup(root);
}
void unlocked(int root,int l,int r,int x,int y){
    if(x<=l&&r<=y){
        if(!--tr[root].ban){
            if(l==r)
                (tr[root].zv+=tr[root].fv)%=mod,tr[root].fv=0,tr[root].len=1;
            else pushdown(root),pushup(root);
        }
        return;
    }
    pushdown(root);
    if(mid>=x)unlocked(lson,x,y);
    if(mid<y)unlocked(rson,x,y);
    if(!tr[root].ban)pushup(root);
}
ll query(int root,int l,int r,int x,int y){
    if(x<=l&&r<=y)return (tr[root].zv+tr[root].fv)%mod;
    pushdown(root);
    ll ans=0;
    if(mid>=x)ans+=query(lson,x,y);
    if(mid<y)ans+=query(rson,x,y);
    if(!tr[root].ban)pushup(root);
    return ans%mod;
}
vector<pair<int,int> >unlocq[200005];
int main(){
    n=read(),m=read();
    build(1,1,n);
    for(int t=1;t<=m;t++){
        int opt=read(),l=read(),r=read();
        if(opt==4){
            printf("%lld\n",query(1,1,n,l,r));
        }else{
            ll v=read();
            if(opt==1)add(1,1,n,l,r,v);
            else if(opt==2)Mu(1,1,n,l,r,v);
            else{
                locked(1,1,n,l,r);
                unlocq[t+v].push_back({l,r});
            }
        }
        for(auto PI:unlocq[t])
            unlocked(1,1,n,PI.first,PI.second);
    }
    return 0;
}

后记

注意了！！