2023-08-10 17:58:18

前言

这场打下来感觉没有很妙，感觉也是题目有一定的问题吧？比如 A 题看似不正常实则通过了的做法（nth_element 的滥用），B 题的数据范围不清晰，以及 C 题的卡空间导致不敢用二维线段树，不过也还好，订正之后还是有收获的。

这场基本上就是被莫名其妙送了很多分，但是努力打的分却没有多少（比如 B 的超长超复杂暴力），下次加油吧。

A

做法1（考场做法）

这题一开始各种什么速度，然后初始位置给我搞蒙了，我还以为要以 \(v\) 为斜率建一个李超线段树什么的来维护最大值啥的（显然我不会），后来发现 \(n,m\le 7000\)，算一下发现正解大概率是个 \(O(nm)\) 的。

先瞎打个暴力吧，每次 \(O(n)\) 更改答案，然后 \(O(n\log n)\) 排序，期望得分 \(30\) 分，实际得分 \(100\) 分？？？？？？？？离大谱，难道是重载运算符可以加速？而且每个点不超过 \(1000ms\)，给尤其韬都惊呆了，如果不是我之后打了正解他要因为自己拿同样的算法拿 \(30\) 分而悲伤窒息~

没想拿 \(k=1\) 的分，因为一开始没看见另外，还以为只有 \(10\) 分，但是我认为拿这几分也没那么麻烦（题解里什么半平面交），我觉得可以直接每次 \(O(n)\) 遍历找最大值即可。

然后发现它只是需要求一个位置的值，所以想到了仁蛟之前讲的 \(O(n)\) 求第 \(k\) 小的数，大概思路就是在快速排序的过程中排好一半之后直接抛掉不是答案的一半，然后继续递归求解，复杂度平摊 \(O(n)\)。

但是愚蠢的我连快速排序都不会，更不要说是快速排序的变种了，所以我就想起来之前第 \(k\) 小的数的题面和题解里面出现的神奇函数 nth_element，然后就查了一下用法就过了。

struct node{
    int v,s,id;ll ans;
    inline bool operator <(const node& w)const{
        if(ans==w.ans)return id<w.id;
        return ans>w.ans;
    }
}a[7003];
int n,m;
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int v=read(),s=read();
        a[i]={v,s,i,0};
    }
    m=read();
    for(int ttt=1;ttt<=m;ttt++){
        int t=read(),k=read();
        for(int i=1;i<=n;i++){
            a[i].ans=1ll*a[i].v*t+1ll*a[i].s;
        }
        nth_element(a+1,a+k,a+1+n);
        printf("%d\n",a[k].id);
    }
}

注：这份神奇的代码把 nth_element(a+1,a+k,a+1+n); 改成 sort(a+1,a+1+n) 也能过。

做法2（题解做法）

注意到，一旦一个赛车 \(x\) 超过了另一辆赛车 \(y\)，说明 \(v_x>v_y,s_x\le s_y\)，那么此后 \(y\) 都不会再次超过 \(x\)，也就是赛车两两之间交换的次数不超过 \(O(n^2)\)，而我们考虑到冒泡排序是可以通过优化，使得当序列的部分片段不出现交换时直接退出循环的，所以可以将询问按时间排序，然后离线每次跑优化了的冒泡排序即可。均摊复杂度 \(O(n^2+nm)\)。

int t;
struct node{
    int v,s,id;//对于 q,v 表示时间，s表示 排名，id表示第几个询问
    inline bool operator <(const node &w)const{
        return v<w.v;
    }
    inline bool operator >(const node &w)const{//若a>b，说明a比b优，要放在前面
        if(1ll*v*t+s==1ll*w.v*t+w.s)return id<w.id;
        return 1ll*v*t+s>1ll*w.v*t+w.s;
    }
}a[7003],q[7003];
int n,m,ans[7003];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        int v=read(),s=read();
        a[i]={v,s,i};
    }
    m=read();
    for(int i=1;i<=m;i++){
        int w=read(),k=read();
        q[i]={w,k,i};
    }
    sort(q+1,q+1+m);
    for(int o=1;o<=m;o++){
        t=q[o].v;
        int w=n-1,p=0;//p存最后一次交换的位置，因为如果之后不再交换，说明在当前时间下，后面部分已经有序，算是一个小优化吧
        for(int i=1;i<=n;i++){
            bool flag=1;//判断是否有发生交换
            for(int j=1;j<=w;j++){
                if(a[j+1]>a[j]){//更优就放前面
                    swap(a[j+1],a[j]);
                    flag=0;p=j;
                }
            }
            w=p;//记录当前时间状态下，还未有序的终点
            if(flag)break;//如果任意两两之间不交换，说明已经有序，直接退出
        }
        ans[q[o].id]=a[q[o].s].id;//记录答案
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
}

好家伙，说实话我冒泡排序都忘光了，打一个不同的方法算是复习一下冒泡排序吧。

B

原题

暴力

第一眼以为是网络流啥啥我不会的算法，然后仔细看观察到数据范围很小就想着随便搜索乱搞了。

把每一条路都处理出来，然后稍微去掉一些不优的路径（比自己的子集的答案要大），再搜索即可（一开始想当然以为选到一条路要一直走下去，没想到中途可以换线）。

\(30pts\ Code\)

struct DAY{int l,r;};
int n,m,K,e;
int f[25][25],cnt,s[300004];
ll F[300005],vis[300005];//2^18=262144
vector<DAY>No[25];
void dfs(int x,int zt,ll res){
    if(x==m){
        if(~F[zt^(1<<m-2)])F[zt^(1<<m-2)]=min(res,F[zt^(1<<m-2)]);
        else F[zt^(1<<m-2)]=res;
        return;
    }
    if(~vis[zt]&&vis[zt]<=res)return;
    vis[zt]=res;
    for(int i=2;i<=m;i++){
        if(i==x||f[x][i]==-1||(zt&(1<<i-2)))continue;
        dfs(i,(zt|(1<<i-2)),res+f[x][i]);
    }
}
ll ans=1e9;
void dfs2(int x,int st,ll res){//第 x 种状态路线，从 st 开始
    for(int i=1;i<m-1;i++){
        if(!(s[x]&(1<<i-1)))continue;
        for(DAY o:No[i]){
            int l=o.l,r=o.r;
            if(st>=l&&st<=r)return;
        }
    }
    ll now=res+F[s[x]];
    if(st==n){
        ans=min(ans,now);
        return;
    }
    for(int i=1;i<=cnt;i++){
        dfs2(i,st+1,now+(i==x?0:K));
    }
}
int main(){
    n=read(),m=read(),K=read(),e=read();
    memset(f,-1,sizeof(f));
    memset(vis,-1,sizeof(vis));
    memset(F,-1,sizeof(F));
    for(int i=1;i<=e;i++){
        int u=read(),v=read(),w=read();
        if(~f[u][v])f[u][v]=f[v][u]=min(f[u][v],w);
        else f[u][v]=f[v][u]=w;
    }
    dfs(1,0,0);
    for(int i=0;i<(1<<m-2);i++){
        if(F[i]==-1)continue;
        bool flag=0;
        for(int j=(i-1)&i;j;j=(j-1)&i){
            if(F[j]==-1)continue;
            if(F[i]>=F[j]){
                flag=1;
                break;
            }
        }
        if(!flag)s[++cnt]=i;
    }
    int d=read();
    for(int i=1;i<=d;i++){
        int id=read(),l=read(),r=read();
        No[id-1].push_back({l,r});//这里减1强行从1开始
    }
    for(int i=1;i<=cnt;i++){
        dfs2(i,1,0);
    }
    cout<<ans;
}

有一说一我感觉暴力比正解难打。

正解

考场上以及讲之前都一直以为是深搜乱搞，没想到居然是一个很奇怪的最短路 + dp。

我们要先预处理出 \(co_{i,j}\)，表示第 \(i\) 填到第 \(j\) 天都走同一条可走的最短路的花费。

令 \(f_{i}\) 表示前 \(i\) 天的最小花费，那么转移方程很好想：

表示在第 \(j+1\) 天换路线，一直到第 \(i\) 天的花费。

因为点数很小，所以随便怎么求最短路，求多少次，时间复杂度都够的，注意一些细节：

• 在赋值 \(co[][]\) 数组的时候最好不要直接用 memset(co,0x3f,sizeof(co)) ，因为这样只能保证在相加极大值的时候不会爆，而 \(co[][]\) 在转移是乘上一个数，会导致爆 long long 或者 int 。
• 注意怎么判断一个时间区间内一个点可不可用，例如 \(k\) 点在 \([l,r]\) 时间段不能用，那么我们现在时间区间为 \([i,j]\)，判断为 \((i\le l\le j)||(i\le r\le j)||(l\le i,j\le r)\)，不要像我一样少写一个调半个小时。想必不会有人跟我一样蠢
• 因为这个变量名的命名很乱，所以要注意使用的变量名与其意义对应。某人又因为写错了一个变量，而样例里两个变量的值是一样的，结果上交直接爆 0。

\(Code\)

typedef pair<ll,ll> PII;
struct Ban{
    int id,l,r;
}a[502];
int n,m,d,K;//与题目不一样，分别表示码头数，边数，天数，换线成本
vector<PII>f[25];
bool ban[25],vis[25];
ll co[102][102],dp[102],dis[22];
priority_queue<PII>Q;
ll Dijkstra(){
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)dis[i]=1e9;//细节1
    Q.push({(dis[1]=0),1});
    while(!Q.empty()){
        int x=Q.top().second;
        Q.pop();
        if(vis[x]||ban[x])continue;
        vis[x]=1;
        for(PII PI:f[x]){
            int y=PI.first,w=PI.second;
            if(dis[y]>dis[x]+w)Q.push({-(dis[y]=dis[x]+w),y});
        }
    }
    return dis[n];
}
int main(){
    d=read(),n=read(),K=read(),m=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        f[u].push_back({v,w});
        f[v].push_back({u,w});
    }
    int baned=read();
    for(int i=1;i<=baned;i++){
        a[i].id=read(),a[i].l=read(),a[i].r=read();
    }
    for(int i=1;i<=d;i++)//细节3
        for(int j=i;j<=d;j++){
            memset(ban,0,sizeof(ban));
            for(int o=1;o<=baned;o++){
                int l=a[o].l,r=a[o].r;
                if((i<=l&&j>=l)||(i<=r&&j>=r)||(l<=i&&j<=r))//细节2
                    ban[a[o].id]=1;
            }
            co[i][j]=Dijkstra();
        }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=-K;
    for(int i=1;i<=d;i++){//细节3
        for(int j=0;j<i;j++){
            dp[i]=min(dp[i],dp[j]+co[j+1][i]*(i-j)+K);
        }
    }
    printf("%lld",dp[d]);//细节3
}

C

考场上因为写爆了只写了一个 \(80\) 分暴力。

第一眼就知道是二维数据结构，然后想到之前看别人写的线段树套线段树（二维线段树），发现似乎这个连 \(n\le 3000\) 都过不了，现在赛后发现似乎是可以过的，因为模数很小，开 short 的空间是 \(12000\times 12000\times 2 B\) 的空间，大约为 \(270 MB\)，反正是可以通过的，但是我当时一直想的是开 long long 或者 int，就没有想到可以写二维线段树拿个 \(95pts\)。

那么这个空间只能写二维树状数组了，前置知识看我博客二维树状数组吧。

然后就是写的过程中发现：

• char 爆完了，因为 char 的取值范围是 [-128,127] 的。
• short 的内存爆了，只能拿 \(95pts\)（当然如果是 NOIP 估计直接爆炸），算了一下有 \(512MB\)。
• 只能用 unsigned char，但是一定要及其小心赋值的问题，其他方法见代码。
• 一定要看清题目的输入顺序啊，我调这个又调了半个小时，还有变量不要打错了啊啊啊。

\(Code\)

const int N=8002;
#define lb(x) (x&-x)
int n,mod,q,lasans;
unsigned char d[N][N],xd[N][N],yd[N][N],xyd[N][N];
void add(int x,int y,int v){
    for(int i=x;i<=n;i+=lb(i))
        for(int j=y;j<=n;j+=lb(j)){
            int p1=d[i][j],p2=xd[i][j],p3=yd[i][j],p4=xyd[i][j];
            p1=((p1+v)%mod+mod)%mod;
            p2=((p2+v*x%mod)%mod+mod)%mod;
            p3=((p3+v*y%mod)%mod+mod)%mod;
            p4=((p4+v*x%mod*y%mod)%mod+mod)%mod;
            //先转成int运算完了再赋值，还有小心负数
            d[i][j]=p1,xd[i][j]=p2,yd[i][j]=p3,xyd[i][j]=p4;
        }
}
int query(int x,int y){
    int res=0;
    for(int i=x;i;i-=lb(i))
        for(int j=y;j;j-=lb(j)){
            int p1=d[i][j],p2=xd[i][j],p3=yd[i][j],p4=xyd[i][j];
            res+=((x+1)%mod)*((y+1)%mod)%mod*p1%mod-((x+1)%mod)*p3%mod-((y+1)%mod)*p2%mod+p4;
            res=(res%mod+mod)%mod;
            //小心负数
        }
    return res;
}
void update(int x1,int y1,int x2,int y2,int v){
    add(x1,y1,v);
    add(x1,y2+1,-v);
    add(x2+1,y1,-v);
    add(x2+1,y2+1,v);
    return;
}
int query(int x1,int y1,int x2,int y2){
    return ((query(x2,y2)+query(x1-1,y1-1)-query(x1-1,y2)-query(x2,y1-1))%mod+mod)%mod;
}
int main(){
    n=read(),q=read(),mod=read();
    while(q--){
        int opt=read(),x1=read(),x2=read(),y1=read(),y2=read();
        x1=(x1%n+lasans%n)%n,x2=(x2%n+lasans%n)%n,y1=(y1%n+lasans%n)%n,y2=(y2%n+lasans%n)%n;
        x1++,x2++,y1++,y2++;
        if(x1>x2)x1^=x2^=x1^=x2;
        if(y1>y2)y1^=y2^=y1^=y2;
        if(opt&1){
            update(x1,y1,x2,y2,1);
        }else{
            int ans=query(x1,y1,x2,y2);
            lasans=(lasans%n+ans%n)%n;
            printf("%d\n",ans);
        }
    }
}

后记

好家伙打个比赛 3 小时，订正了我 5~6 个小时，不过还是学到了很多东西的，比如二维树状数组，一维树状数组的区间操作，冒泡排序的巧妙用法，写 dp 的新思路。

本栏目推荐文章
• Ubuntu下运行LVGL模拟器
• 初中信息奥赛模拟测试
• NES 模拟器中音画同步问题
• HBuilder X 连接MuMu模拟器
• 遗传算法、模拟退火算法等优化问题算法
• Flutter 项目运行到ios模拟器报错 : Error (Xcode): SDK does not contain 'libarclite'
• mac M2 arm 架构模拟器运行 x86 apk
• AD采集卡设计方案：130-基于PCIe的中速模拟AD采集卡
• 模拟(1)
• TiDB 在单机上模拟部署生产环境集群

模拟赛 8.8模拟赛8.8 模拟赛 小结8.8 8.8 周记8.8 个人赛 个人8.8 anolis centos 8.6 8.8 centos maven3 maven 8.8 pyyz 8.8 oracle linux rhel 8.8 观后 观后感 天道8.8