CSP2022

Daidly · 2022-10-31 22:16:31 · 个人记录

疫情比较严重啊，现在 NOIp 看起来都玄。

CSP 取消了，只能 vp 一下。

T1

先枚举每个点，bfs 出中转次数不超过 k 次的点，并标记 f[i][j]=f[j][i]=1。

发现 1 与 A,B,C,D 构成的环可以拆成 1,A,B 与 1,D,C，这里想了好一会枚举 A,D 怎么做，结果发现自己弱智了。已经确定 1，在 n=2500 的背景下选择了枚举 B 和 C ，然后预处理 A,D。

考虑到可能会重复，例如通过 B 选出的 A 可能与 C,D 相同，所以我们最多只需要记录前三大即可。

预处理出对于 i 满足满足 f[i][j]=1,f[j][1]=1 的分数前三大的点 j，记为 \max_1[i],\max_2[i],\max_3[i]。

我们钦定 B<C，枚举 B,C，判断然后取最大值即可。

复杂度 O(n^2)，常数 \frac{9}{2}。

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}

const int N=2505,M=1e4+5,K=105;
int n,m,k,a[N],head[N],cnt;
struct node{
    int next,to;
}e[M<<1];

void add(int from,int to){
    e[++cnt]=(node){head[from],to};
    head[from]=cnt;
}

bool vis[N],f[N][N];
queue<int>q;
int dis[N];

void bfs(int x){
    while(!q.empty())q.pop();
    for(int i=1;i<=n;++i)vis[i]=0,dis[i]=1e18;
    q.push(x),dis[x]=-1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        if(dis[u]>=k)break;
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            f[x][v]=f[v][x]=1;
            dis[v]=min(dis[v],dis[u]+1);
            if(!vis[v])q.push(v);
        }
    }
}

int maxn[4][N];

signed main(){
    n=read(),m=read(),k=read();
    for(int i=2;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;++i){
        bfs(i);
    }
    for(int i=2;i<=n;++i){
        for(int j=2;j<=n;++j){
            if(i==j)continue;
            if(f[i][j]&&f[j][1]){
                if(a[j]>a[maxn[1][i]]){
                    maxn[3][i]=maxn[2][i];
                    maxn[2][i]=maxn[1][i];
                    maxn[1][i]=j;
                }else if(a[j]>a[maxn[2][i]]){
                    maxn[3][i]=maxn[2][i];
                    maxn[2][i]=j;
                }else if(a[j]>a[maxn[3][i]]){
                    maxn[3][i]=j;
                }
            }
        }
    }
    int ans=0;
    for(int i=2;i<=n;++i){
        for(int j=i+1;j<=n;++j){
            if(!f[i][j])continue;
            for(int k1=1;k1<=3;++k1){
                if(maxn[k1][i]==j)continue;
                for(int k2=1;k2<=3;++k2){
                    if(maxn[k1][i]!=maxn[k2][j]&&maxn[k2][j]!=i&&f[maxn[k1][i]][1]&&f[maxn[k2][j]][1]){
                        ans=max(ans,a[i]+a[j]+a[maxn[k1][i]]+a[maxn[k2][j]]);
                    }
                }
            }
        }
    }
    print(ans);
    return 0;
}

T2

考虑最优策略是什么，可以从暴力中发掘：

枚举小 L 选的每一个值，小 Q 选择乘积最小的值，而小 L 从这些值里面选取最大的。

根据暴力理解完题目之后，不能把目光只停留在列举每一个数中，要考虑数的形成过程，即两区间内选数相乘。

也就是说：对于小 L 的每种情况，小 Q 都有相应的对策，这个对策在形式上是固定的，而小 L 根据每一种情况反馈出的值选择对于他来说最优的。

先考虑 A_i,B_i>0 的情况，对于小 L 选的每一个正数 A_i，小 Q 形式上固定的对策是选择区间内最小的 B_i 与之相乘保证最小，对此，小 L 将会选区间内最大的 A_i 使乘积最大。

再考虑正负零的情况，稍微列举归纳可发现，我们将数分为非负数和负数：

对于小 L 选这两种情况，小 Q 也有固定的策略：

• 小 L 选非负数，小 Q 有负数选负数，没有负数选最小的非负数，总结一下可以得到小 Q 的策略是：选最小的。
• 小 L 选负数，小 Q 有非负数选最大的非负数，没有非负数选最大的负数，总结一下可以得到小 Q 的策略是：选最大的。

所以我们只需要预处理 6 组值：

• A$ 序列非负数 $\max_1,\min_1
• A$ 序列负数 $\max_2,\min_2
• B$ 序列 $\max_3,\min_3

用 ST 表实现即可，复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;

#define int long long 

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}

const int N=1e5+5;
int n,m,q,a[N],b[N],num[N],lgn,lgm;
int maxn1[N][21],minn1[N][21];
int maxn2[N][21],minn2[N][21];
int maxn3[N][21],minn3[N][21];

void init_maxn1(){
    for(int i=1;i<=n;++i)maxn1[i][0]=a[i];
    for(int j=1;j<=lgn;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            maxn1[i][j]=max(maxn1[i][j-1],maxn1[i+(1ll<<(j-1))][j-1]);
        }
    }
}

void init_minn1(){
    for(int i=1;i<=n;++i){
        if(a[i]>=0)minn1[i][0]=a[i];
        else minn1[i][0]=1e18;
    }
    for(int j=1;j<=lgn;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            minn1[i][j]=min(minn1[i][j-1],minn1[i+(1ll<<(j-1))][j-1]);
        }
    }
}

void init_maxn2(){
    for(int i=1;i<=n;++i){
        if(a[i]<0)maxn2[i][0]=a[i];
        else maxn2[i][0]=-1e18;
    }
    for(int j=1;j<=lgn;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            maxn2[i][j]=max(maxn2[i][j-1],maxn2[i+(1ll<<(j-1))][j-1]);
        }
    }
}

void init_minn2(){
    for(int i=1;i<=n;++i)minn2[i][0]=a[i];
    for(int j=1;j<=lgn;++j){
        for(int i=1;i+(1<<j)-1<=n;++i){
            minn2[i][j]=min(minn2[i][j-1],minn2[i+(1ll<<(j-1))][j-1]);
        }
    }
}

void init_maxn3(){
    for(int i=1;i<=m;++i)maxn3[i][0]=b[i];
    for(int j=1;j<=lgm;++j){
        for(int i=1;i+(1<<j)-1<=m;++i){
            maxn3[i][j]=max(maxn3[i][j-1],maxn3[i+(1ll<<(j-1))][j-1]);
        }
    }
}

void init_minn3(){
    for(int i=1;i<=m;++i)minn3[i][0]=b[i];
    for(int j=1;j<=lgm;++j){
        for(int i=1;i+(1<<j)-1<=m;++i){
            minn3[i][j]=min(minn3[i][j-1],minn3[i+(1ll<<(j-1))][j-1]);
        }
    }
}

signed main(){
    n=read(),m=read(),q=read();
    lgn=(int)log2(n),lgm=(int)log2(m);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)b[i]=read();
    for(int i=1;i<=n;++i){
        if(a[i]>=0)num[i]=num[i-1]+1;
        else num[i]=num[i-1];
    }
    init_maxn1(),init_minn1();
    init_maxn2(),init_minn2();
    init_maxn3(),init_minn3();
    int l1,r1,l2,r2,ans,lga,lgb,tmpa,tmpb;
    while(q--){
        l1=read(),r1=read(),l2=read(),r2=read();
        ans=-1e18;
        lga=(int)log2(r1-l1+1);
        lgb=(int)log2(r2-l2+1);
        if(num[r1]-num[l1-1]>0){
            tmpb=min(minn3[l2][lgb],minn3[r2-(1<<lgb)+1][lgb]);
            if(tmpb>=0){
                tmpa=max(maxn1[l1][lga],maxn1[r1-(1<<lga)+1][lga]);
                ans=max(ans,tmpa*tmpb);
            }else{
                tmpa=min(minn1[l1][lga],minn1[r1-(1<<lga)+1][lga]);
                ans=max(ans,tmpa*tmpb);
            }
        }
        if(num[r1]-num[l1-1]<r1-l1+1){
            tmpb=max(maxn3[l2][lgb],maxn3[r2-(1<<lgb)+1][lgb]);
            if(tmpb>=0){
                tmpa=max(maxn2[l1][lga],maxn2[r1-(1<<lga)+1][lga]);
                ans=max(ans,tmpa*tmpb);
            }else{
                tmpa=min(minn2[l1][lga],minn2[r1-(1<<lga)+1][lga]);
                ans=max(ans,tmpa*tmpb);
            }
        }
        print(ans),puts("");
    }
    return 0;
}

T3

题目比较难读，用了快半个小时才读懂题......

人话翻译：

• 删去所有以 u 为终点的点
• 加边 (u,v)
• 加上所有以 u 为终点的点

在每一次操作之后判断：

• 是否每个点的出度为 1
• 是否每个点都能走到一个环

很显然第一个判断是包括了第二个的，所以我们只用判断：是否每个点的出度为 1。

赛时：O(mq) 模拟做法显然好做，然后没有 t=2 和 t=4 的情况只需要我们支持每次加删一条边和判断，用一个 multiset 维护出度判断首尾是否相同即可。对于有 t=2 的，我们用一个集合维护未被摧毁的边，由于每次加边只能加一条，复杂度是有保证的。这是 60，然后还写了一个用集合维护删边的，复杂度没有保证想骗点分，结果好像没骗到。码了整整两百行。

正解是 hash，看到判断每个点的出度全为 1，我们考虑给每个点随机赋一个权值 val_i，设出来一个与出度有关的 h(u)，用 \sum h(u) 来判断。

然后考虑如何应对上述操作。发现以 u 为终点很逆天，于是我们建反图把它干掉。

将图转化为反图，需要支持的操作变为：

• 删边 (u,v)
• 删去所有以 u 为起点的点
• 加边 (u,v)
• 加上所有以 u 为起点的点

此时我们需要判断：

• 每个点的入度为 1

对于删去所有和恢复所有边，需要我们记录所有点的初始出度和当前出度。

但是判断的是入度，应该怎么办呢？

考虑把当前点的贡献转移到起点，即对于边 u\to v，我们不记录 v 的入度，而记录 u 的出度，把 val_v 记录到 h(u) 上，这样既不会改变最终答案，又能解决出入度冲突问题。

所以我们设 h(u) 为以 u 为起点的边的终点权值和，这满足对于每个点入度都为 1 的图他们的 \sum h(u) 相同，即一个点的权值只会被统计一次。

为了保证正确率，可以多随机几个点的权值。

#include<bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}

void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}

const int N=5e5+5;
const int MAX=1e9+7;
int n,m,q;
int d[N],nd[N],val[N][5],ans[5];
int nsum[N][5],nSum[5],sum[N][5];

signed main(){
    n=read(),m=read();
    srand(time(0));
    for(int i=1;i<=n;++i){
        for(int j=0;j<5;++j){
            val[i][j]=rand()*rand()%MAX;
            ans[j]+=val[i][j];
        }
    }
    for(int i=1;i<=m;++i){
        int u=read(),v=read();
        d[v]++,nd[v]++;
        for(int j=0;j<5;++j){
            sum[v][j]+=val[u][j];
            nsum[v][j]+=val[u][j];
            nSum[j]+=val[u][j];
        }
    }
    q=read();
    int t,u,v;
    while(q--){
        t=read();
        if(t==1){
            u=read(),v=read();
            nd[u]--;
            for(int i=0;i<5;++i)nsum[v][i]-=val[u][i],nSum[i]-=val[u][i];
        }else if(t==2){
            u=read();
            nd[u]=0;
            for(int i=0;i<5;++i)nSum[i]-=nsum[u][i],nsum[u][i]=0;
        }else if(t==3){
            u=read(),v=read();
            nd[u]++;
            for(int i=0;i<5;++i)nsum[v][i]+=val[u][i],nSum[i]+=val[u][i];
        }else{
            u=read();
            nd[u]=d[u];
            for(int i=0;i<5;++i)nSum[i]+=(sum[u][i]-nsum[u][i]),nsum[u][i]=sum[u][i];
        }
        bool flag=1;
        for(int i=0;i<5;++i)if(ans[i]!=nSum[i])flag=0;
        if(flag)puts("YES");
        else puts("NO");
    } 
    return 0;
}

T4

开 T4 的时候时间已经不多了，然后就写挂了 8 分。

看完这题我直接就写了个把 s 到 t 之间的链扯下来 dp，然后就挂在了样例 2。

可以发现当 k=3 时是能跳出链外的。

于是我在写的 dfs 上加了对于 x 向外枚举 3 层转移，然后加上 k=1 就交了......

赛后发现挂分了，写了个拍可以发现存在这样一种情况：x 是 s 到 t 最优的中转点，而如果只从 s 开始 dfs 可能先到 t 再到 x。

对于这种情况，我们只需要跑 n 遍 dfs 就行了（

这样就有 44 分，其实把 k=2 单拎出来写的话分更多。

正解是倍增维护矩阵，鉴定为是我考场上写不出来的。

先扔这了，有时间再补。

总结

没参加有点遗憾，题目偏向思维与基础。

还需要加强码力与思维。