CSP-S2022 游“寄”

Songnj_office · 2022-11-07 22:17:55 · 个人记录

死于第一题死磕k层图，（最后也没想到k层图正解，倒是想到了枚举中间的点的做法）

真正寄在了第二题奇妙的RE，我调了半天也没想到为什么会RE

赛场思路

第一题想了一下，然后跳到第二题去做，第二题结论比较显然，我们会这么想，其实选c_{i,j}等价于a_i*b_j 那么选取一段矩阵 c_{l1-r1,l2-r2}中的一个数，就相当于从a_{l1-r1}中选一个数X，从b_{l2-r2}中选取一个数Y,使X*Y这个数满足条件就等价于要求。

我们这么想，如果小L可以选的的数里面有正整数

1、小Q可以选的数里面有负数，那么如果小L选取正整数，小Q就能把他变成负数，则小L最优只能选 0 或 最小的正整数 。小Q则选取最大的负数

2、小Q可以选的数里面没有负数，但有0，那么小Q选0

3、小Q可以选的数里面只有正整数，那么小Q最优只能选最小的正整数 。小L则选取最大的正整数

同理我们可以处理如果小Q可以选的数里面有负数最优的情况

然后我们思考一下要处理的信息，分别要处理区间最大正整数，区间最小负数，区间最小正整数，区间最大负数 (a,b都要分别求)，显然用RMQ、线段树这些区间算法做。

但是赛场上写的代码只有本地能过，交评测机就RE，什么问题我也不知道。

回到第一题，我想到了建立k层图，但是很有趣，由于k层图不能保证不重复经过一个点，所以k层图显然是假做法，如果有大佬会k层图正确的建图做法，当我没说。

然后想到了枚举中点，因为枚举这一段是n^2复杂度的，但是没写（赛后冷静了一下就想到这做法其实就是正解）

赛后

第二题不知道为啥不能过，反正重新写了一遍，还是用的线段树，过了，但是这次把线段树封装成了结构体，把调试难度降下来了，感觉这些小妙招还是要多用

第一题想到了正解，首先我们容易想到，转乘不超过k次就是指点u与点v可以互相到达的条件当且仅当u与v的最短距离不超过k，那么我们就跑深搜，把能互相到达的点暴力求出来，然后重新连边即可完成建图。随后我们暴力拼接一条路径
开始点->A->B这条路径，我们发现暴力求取这些路径对是O(n^2)的，但是拼接可能还会达到O(n^4)仔细思考后，我们发现 以B为终点的路径实际只有最大的3条可能对结果产生影响，所以只存储前3大的路径，然后再暴力的拼接两条路径，判断一下合不合法就行了，复杂度O(3*n*3*n+n*n)=O(10*n^2)不快，但的确够用，贴一下赛后用半小时就写出来的两题代码(这份代码没用结构体封装，但是query部分只写了两个，其他的全部用查找和替换解决)

第三题比较蒙，第四题k=1与k=2的部分分还行，然后k=3的部分直接暴力，最后56分收场

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Maxn=1e5+5;
ll a[Maxn],b[Maxn];
int la[Maxn],lb[Maxn],za[Maxn],zb[Maxn],fa[Maxn],fb[Maxn];
ll taz[4*Maxn],taf[4*Maxn],tazm[4*Maxn],tafm[4*Maxn],tbz[4*Maxn],tbf[4*Maxn],tbzm[4*Maxn],tbfm[4*Maxn];
void build(int id,int l,int r){
    if(l==r) {
        if(a[l]>0){
            taz[id]=a[l];
            tazm[id]=a[l];
            taf[id]=-1;
            tafm[id]=1e18;
        }else if(a[l]<0){
            a[l]=a[l]*-1;
            taf[id]=a[l];
            tafm[id]=a[l];
            taz[id]=-1;
            tazm[id]=1e18;
            a[l]=a[l]*-1;
        }else {
            taz[id]=-1;
            tazm[id]=1e18;
            taf[id]=-1;
            tafm[id]=1e18;
        }
        return ;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    taz[id]=max(taz[id*2],taz[id*2+1]);
    tazm[id]=min(tazm[id*2],tazm[id*2+1]);
    taf[id]=max(taf[id*2],taf[id*2+1]);
    tafm[id]=min(tafm[id*2],tafm[id*2+1]); 
}
void build2(int id,int l,int r){
    if(l==r) {
        if(b[l]>0){
            tbz[id]=b[l];
            tbzm[id]=b[l];
            tbf[id]=-1;
            tbfm[id]=1e18;
        }else if(b[l]<0){
            b[l]=b[l]*-1;
            tbf[id]=b[l];
            tbfm[id]=b[l];
            tbz[id]=-1;
            tbzm[id]=1e18;
            b[l]=b[l]*-1;
        }else {
            tbz[id]=-1;
            tbzm[id]=1e18;
            tbf[id]=-1;
            tbfm[id]=1e18;
        }
        return ;
    }
    int mid=(l+r)/2;
    build2(id*2,l,mid);
    build2(id*2+1,mid+1,r);
    tbz[id]=max(tbz[id*2],tbz[id*2+1]);
    tbzm[id]=min(tbzm[id*2],tbzm[id*2+1]);
    tbf[id]=max(tbf[id*2],tbf[id*2+1]);
    tbfm[id]=min(tbfm[id*2],tbfm[id*2+1]); 
}
ll qtaz(int id,int l,int r,int x,int y){
    if(r<x||l>y) return -1;
    if(x<=l&&r<=y){
        return taz[id];
    }
    int mid=(l+r)/2;
    return max(qtaz(id*2,l,mid,x,y),qtaz(id*2+1,mid+1,r,x,y));
}
ll qtazm(int id,int l,int r,int x,int y){
    if(r<x||l>y) return 1e18;
    if(x<=l&&r<=y){
        return tazm[id];
    }
    int mid=(l+r)/2;
    return min(qtazm(id*2,l,mid,x,y),qtazm(id*2+1,mid+1,r,x,y));
}
ll qtaf(int id,int l,int r,int x,int y){
    if(r<x||l>y) return -1;
    if(x<=l&&r<=y){
        return taf[id];
    }
    int mid=(l+r)/2;
    return max(qtaf(id*2,l,mid,x,y),qtaf(id*2+1,mid+1,r,x,y));
}
ll qtafm(int id,int l,int r,int x,int y){
    if(r<x||l>y) return 1e18;
    if(x<=l&&r<=y){
        return tafm[id];
    }
    int mid=(l+r)/2;
    return min(qtafm(id*2,l,mid,x,y),qtafm(id*2+1,mid+1,r,x,y));
}
ll qtbf(int id,int l,int r,int x,int y){
    if(r<x||l>y) return -1;
    if(x<=l&&r<=y){
        return tbf[id];
    }
    int mid=(l+r)/2;
    return max(qtbf(id*2,l,mid,x,y),qtbf(id*2+1,mid+1,r,x,y));
}
ll qtbfm(int id,int l,int r,int x,int y){
    if(r<x||l>y) return 1e18;
    if(x<=l&&r<=y){
        return tbfm[id];
    }
    int mid=(l+r)/2;
    return min(qtbfm(id*2,l,mid,x,y),qtbfm(id*2+1,mid+1,r,x,y));
}

ll qtbz(int id,int l,int r,int x,int y){
    if(r<x||l>y) return -1;
    if(x<=l&&r<=y){
        return tbz[id];
    }
    int mid=(l+r)/2;
    return max(qtbz(id*2,l,mid,x,y),qtbz(id*2+1,mid+1,r,x,y));
}
ll qtbzm(int id,int l,int r,int x,int y){
    if(r<x||l>y) return 1e18;
    if(x<=l&&r<=y){
        return tbzm[id];
    }
    int mid=(l+r)/2;
    return min(qtbzm(id*2,l,mid,x,y),qtbzm(id*2+1,mid+1,r,x,y));
}

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        la[i]=la[i-1],za[i]=za[i-1],fa[i]=fa[i-1];
        if(a[i]<0) fa[i]++;
        if(a[i]>0) za[i]++;
        if(a[i]==0) la[i]++;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
        lb[i]=lb[i-1],zb[i]=zb[i-1],fb[i]=fb[i-1];
        if(b[i]<0) fb[i]++;
        if(b[i]>0) zb[i]++;
        if(b[i]==0) lb[i]++;
    }
    build(1,1,n);
    build2(1,1,m);
    for(int i=1;i<=q;i++){
        int l1,r1,l2,r2;
        ll ans=-1e18;
        cin>>l1>>r1>>l2>>r2;
    //  cout<<qtafm(1,1,n,l1,r1)<<" "<<qtaf(1,1,n,l1,r1)<<" "<<qtazm(1,1,n,l1,r1)<<" "<<qtaz(1,1,n,l1,r1)<<" "<<qtbfm(1,1,m,l2,r2)<<" "<<qtbf(1,1,m,l2,r2)<<" "<<qtbzm(1,1,m,l2,r2)<<" "<<qtbz(1,1,m,l2,r2)<<" ";
        if(fa[r1]-fa[l1-1]>0){
            if(zb[r2]-zb[l2-1]>0) ans=max(ans,-1*qtafm(1,1,n,l1,r1)*qtbz(1,1,m,l2,r2));
            else if(fb[r2]-fb[l2-1]>0) ans=max(ans,qtaf(1,1,n,l1,r1)*qtbfm(1,1,m,l2,r2));
        //  cout<<"sd";
        }
        if(za[r1]-za[l1-1]>0){
            if(fb[r2]-fb[l2-1]>0) ans=max(ans,-1*qtazm(1,1,n,l1,r1)*qtbf(1,1,m,l2,r2));
            else if(zb[r2]-zb[l2-1]>0) ans=max(ans,qtaz(1,1,n,l1,r1)*qtbzm(1,1,m,l2,r2));
        //  cout<<"sb"; 
        }
        if(ans<0&&la[r1]-la[l1-1]>0) ans=0;
        if(ans>0&&lb[r2]-lb[l2-1]>0) ans=0;

        cout<<ans<<endl; 
    }
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dd[2505][2505];
int vis[2505];
ll dq[2505];
int head[2505],cnt;
struct node{
    int v,next;
}s[100005];
void add(int u,int v){
    s[cnt].v=v,s[cnt].next=head[u],head[u]=cnt;
    cnt++;
}
queue<int> pq;
void bfs(int S){
    memset(vis,-1,sizeof(vis));
    pq.push(S);
    dd[S][S]=0;
    vis[S]=1;
    while(!pq.empty()){
        int u=pq.front();
        pq.pop();
    //  cout<<"fus";
        for(int i=head[u];i!=-1;i=s[i].next){
            int v=s[i].v;
            //cout<<"fusd";
            if(vis[v]==-1) {
                dd[S][v]=dd[S][u]+1;
                pq.push(v);
                vis[v]=1;
            }
        }
    }
}
ll ma[3000][4][2];
void merge(int u,int v){
    if(dq[u]+dq[v]>ma[u][1][1]) {ma[u][1][1]=dq[u]+dq[v];ma[u][1][0]=v;return ;}
    if(dq[u]+dq[v]>ma[u][2][1]) {ma[u][2][1]=dq[u]+dq[v];ma[u][2][0]=v;return ;}
    if(dq[u]+dq[v]>ma[u][3][1]) {ma[u][3][1]=dq[u]+dq[v];ma[u][3][0]=v;return ;}
}
ll ans=0;
int main(){
    memset(head,-1,sizeof(head));
    memset(dd,0x3f,sizeof(dd));
    memset(ma,-0x3f,sizeof(ma));
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++){
        cin>>dq[i];     
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v),add(v,u); 
    }
    k++;
    for(int i=1;i<=n;i++) bfs(i);
    for(int i=2;i<=n;i++)
        for(int j=2;j<=n;j++) if(dd[i][j]<=k&&i!=j&&dd[1][j]<=k) merge(i,j);
    /*for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<dd[i][j]<<" ";
        }
        cout<<endl;
    }*/
    for(int i=1;i<=n;i++){
        //枚举i
        for(int e1=1;e1<=3;e1++){
            if(ma[i][e1][1]<0) continue;
            for(int j=1;j<=n;j++){
                if(i==j||dd[i][j]>k||ma[i][e1][0]==j) continue;
                for(int e2=1;e2<=3;e2++){
                    if(ma[j][e2][1]<0) continue;
                    if(i==ma[j][e2][0]||ma[i][e1][0]==ma[j][e2][0]) continue;
                    ans=max(ma[i][e1][1]+ma[j][e2][1],ans);
                //  if(ma[i][e1][1]+ma[j][e2][1]==8) cout<<i<<" "<<j<<" ";
                }
            }
        } 
    }
    cout<<ans<<endl;
    return 0;
} 

总结

感觉自己写的代码可读性比较高，但是自己也不好调试，尤其在码量较大的时候，没有选取更合理的封装结构体，致使可能某一颗线段树会越界访问节点，感觉还是在一些技巧性的方面比较欠缺，后面也要适应这些缩短代码量的方法，对于T1这种题，多从几个方面想想问题，不要死磕k层图这种显然，但是入手发现很难切入的点，有好写的想法就去写，而且要加快码速，否则第四题实际上是可以骗到分的。

其次应该注意开数组对数组边界条件的限制，注意对时间、空间、以及打的部分分的选取，更好的拿分

之后可能会加强在压行这方面的训练，然后在判断解法上面要下点功夫，预估后面会找几道 大模拟/FFT 这种比较难调试的题目来练练手。