首页 > 其他分享 >[61] (多校联训) A层冲刺NOIP2024模拟赛18

[61] (多校联训) A层冲刺NOIP2024模拟赛18

时间:2024-11-05 19:10:34浏览次数:4  
标签:x1 前缀 int 18 sum 多校 联训 y2 257

无论从什么意义上都能称得上挂 75 分的一场

A.选彩笔

好题

答案显然可以二分

突然发现我好像专长二分答案

钦定最大差值 \(dx\),将所有物品以 \((r,g,b)\) 看成三维空间坐标内的点,原问题可以转化成问空间里一个边长为 \(dx\) 的立方体内是否有至少 \(k\) 个点

考虑到值域不大,可以钦定立方体的一个顶点,以此来确定这个立方体,就变成了三维坐标下求给定坐标区间内点的个数问题

三维前缀和可以处理

然后说一下这个三维前缀和,之前模拟赛那个原题场考过一道 abc 的三维前缀和板子,和二维前缀和类似,简单容斥一下

\[s_{i,j,k}=s_{i-1,j,k}+s_{i,j-1,k}+s_{i,j,k-1}-s_{i-1,j-1,k}-s_{i-1,j,k-1}-s_{i,j-1,k-1}+s_{i-1,j-1,k-1}+a_{i,j,k} \]

要说咋记这玩意,其实最好的办法应该是找规律,你会发现 \(()-1\) 的个数的奇偶性是和符号相关的,然后根据首项(两项固定项)一定为正往下顺着推就行了

以防你像 CTH 一样求出前缀和不会用:

\((i',j',k')\) 到 \((i,j,k)\) 立方体内的前缀和为:

\[s_{i,j,k}-s_{i',j,k}-s_{i,j',k}-s_{i,j,k'}+s_{i',j',k}+s_{i',j,k'}+s_{i,j',k'}-s_{i',j',k'} \]

推法和上述还是一样的

int n,K;
int maxr,maxg,maxb;
int r[100001],g[100001],b[100001];
int cnt[257][257][257];
int sum[257][257][257];
int cal(int x1,int x2,int y1,int y2,int z1,int z2){
    return sum[x2][y2][z2]-sum[x1-1][y2][z2]-sum[x2][y1-1][z2]-sum[x2][y2][z1-1]+sum[x1-1][y1-1][z2]+sum[x1-1][y2][z1-1]+sum[x2][y1-1][z1-1]-sum[x1-1][y1-1][z1-1];
}
bool check(int maxdx){
    for(int i=1;i<=maxr;++i){
        for(int j=1;j<=maxg;++j){
            for(int k=1;k<=maxb;++k){
                if(cal(i,min(maxr,i+maxdx),j,min(maxg,j+maxdx),k,min(maxb,k+maxdx))>=K){
                    return true;
                }
            }
        }
    }
    return false;
}
int main(){
    scanf(n,K);
    for(int i=1;i<=n;++i){
        scanf(r[i],g[i],b[i]);
        cnt[r[i]+1][g[i]+1][b[i]+1]++;
        maxr=max(maxr,r[i]+1);
        maxg=max(maxg,g[i]+1);
        maxb=max(maxb,b[i]+1);
    }
    for(int i=1;i<=maxr;++i){
        for(int j=1;j<=maxg;++j){
            for(int k=1;k<=maxb;++k){
                sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]+sum[i][j][k-1]-sum[i-1][j-1][k]-sum[i-1][j][k-1]-sum[i][j-1][k-1]+sum[i-1][j-1][k-1]+cnt[i][j][k];
            }
        }
    }
    int l=0,r=max({maxr,maxg,maxb}),ans=r;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
}

B.兵蚁排序

也是成功挂上分了

注意到可交换次数高达 \(n^2\) 次,考虑冒泡排序,每次交换邻项元素

因为我们交换的方式是基于值排序,因此

  • 将一个值与其前面的值交换,当且仅当该值小于前方的值
  • 将一个值与其后面的值交换,当且仅当该值大于前方的值

按冒泡排序的思路暴力将 \(a\) 数组交换到 \(b\) 数组,若存在无法到达的目标位置则报告无解

跑出来和大样例一模一样,看来 std 也是这么写的

int n;
int a[1001],b[1001];
vector<pair<int,int>>op;
bool move(int pos,int to){
    for(int i=pos;i>to;--i){
        if(a[i-1]>=a[i]){
            swap(a[i],a[i-1]);
            op.push_back({i-1,i});
        }
        else{
            return false;
        }
    }
    return true;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    int cases;
    scanf(cases);
    while(cases--){
        op.clear();
        scanf(n);
        for(int i=1;i<=n;++i){
            scanf(a[i]);
        }
        for(int i=1;i<=n;++i){
            scanf(b[i]);
        }
        bool flag=false;
            for(int j=i;j<=n;++j){
                if(a[j]==b[i]){
                    if(move(j,i));
                    else{
                        flag=true;
                        break;
                    }
                }
            }
            if(flag) break;
        }
        if(flag) cout<<-1<<'\n';
        else{
            cout<<0<<'\n';
            cout<<op.size()<<'\n';
            for(pair<int,int>i:op){
                cout<<i.first<<" "<<i.second<<'\n';
            }
        }
    }
}
赛时 checker

这一份没法判无解

/**
 * 
 * ------ checker for T2 ------*/

#include<bits/stdc++.h>
using namespace std;
int cases;
int n;
int a[100001],b[100001];
int main(){
    ifstream in("sort.in"),out("sort.out");
    in>>cases;for(int p=1;p<=cases;++p){
        in>>n;
        for(int i=1;i<=n;++i){
            in>>a[i];
        }
        for(int i=1;i<=n;++i){
            in>>b[i];
        }
        int opt;
        out>>opt;
        if(opt==-1){
            cout<<"Testcase "<<p<<" : no solution exist"<<endl;
        }
        else{
            int m,x,y;out>>m;
            if(m>n*n){
                cout<<"Testcase "<<p<<" : TOO MUCH OPERATIONS"<<endl;
                continue;
            }
            while(m--){
                out>>x>>y;
                swap(a[x],a[y]);
            }
            int flag=0;
            for(int i=1;i<=n;++i){
                if(a[i]!=b[i]){
                    flag=i;
                    break;
                }
            }
            if(flag){
                cout<<"Testcase "<<p<<" : FIND WRONG ANSWER ON PLACE "<<flag<<endl;
                for(int i=1;i<=n;++i){
                    cout<<a[i]<<" ";
                }
                cout<<endl;
                for(int i=1;i<=n;++i){
                    cout<<b[i]<<" ";
                }
                cout<<endl;
            }
            else cout<<"Testcase "<<p<<" : answer is correct"<<endl;
        }
    }
}

C.人口局 DBA

在做了


这是什么

标签:x1,前缀,int,18,sum,多校,联训,y2,257
From: https://www.cnblogs.com/HaneDaCafe/p/18528485

相关文章

  • [BUUCTF 2018]Online Tool
    典型的PHP代码审计开始审计^()[]{}$\,\x0A和\xFF以及不配对的单/双引号转义$sandbox=md5("glzjin".$_SERVER['REMOTE_ADDR']);echo'youareinsandbox'.$sandbox;@mkdir($sandbox);//新建目录,默认权限,最大可能的访问权chdir($sandbox);//改......
  • 洛谷题单指南-二叉堆与树状数组-P1801 黑匣子
    原题链接:https://www.luogu.com.cn/problem/P1801题意解读:动态维护一组序列,并随时可以求第k小的值,每次求第k小的顺序是递增的,比如第一次取第1小,然后是第2小,以此类推。解题思路:对于求第k小的问题,已经介绍过几种方案:1、快选算法,每次查询时间复杂度logn,传送门:https://www.cnblogs......
  • P5308 [COCI2018-2019#4] Akvizna
    原题链接奶龙题,主要是凸性的证明,然后wqs二分求解即可。轮数的选择是\(1\)~\(n\),假如是\(1\)轮,答案显然为\(1\),为\(n\)轮,答案就是\(\sum_{i=1}^{n}i^{-1}\),从这里就可以直接猜出凸性了。然后是不考虑轮数限制的求法,直接dp即可:\(f_{i}=\max\{f_j+\frac{i-j}{i}\}\),......
  • 国标GB28181-2016平台LiteGBS国标GB28181设备端接入SDK国标级联共享功能的优势体现在
    在现代安防监控领域,视频监控管理平台的国标级联共享功能是实现跨区域、跨系统资源整合与共享的关键技术。LiteGBS平台以其卓越的性能和广泛的兼容性,为用户提供了一个高效、可靠的解决方案。本文将详细介绍国标GB28181-2016平台LiteGBS在国标级联共享方面的五大优势,展示其如何帮助......
  • P4383 [八省联考 2018] 林克卡特树
    简化题意,给一棵树,找出恰好\(k+1\)条链,是这些链之和最大。有恰好选出的字眼,并且原问题显然具有凸性,直接考虑wqs二分。然后每条链会减去二分的\(mid\),然后没有限制,求最大链和及链的数量,考虑树形dp。设\(f_{x,0/1/2}\)表示以\(x\)为根的子树,\(x\)点入度为\(0/1/2\)所......
  • Google Play 三季度应用下架报告:下架约 180万款应用,同比增长 80%
    大家好,我是牢鹅!聊到GooglePlay封号下架,相信大伙应该不陌生了吧!由于前些年各种捞偏门的App以及大量马甲包的出现,让谷歌不停的更新它们的审核机制,特别是近年谷歌开始大规模使用大模型对开发者的账号、应用扫描,导致很多做绿色合规应用的开发者被误封与下架,这也大大提高了普通开......
  • Python学习18天
    打印金字塔'''1*1层14个总层数-当前层数***2层33个*****3层52个*******4层71个*********......
  • “握拳宝宝”18岁了,现在他长这样!而那张表情包也拯救了他的家庭
    只要你网上冲浪,就不可能没看到过这张表情包一个小宝宝握紧拳头,表情坚定,仿佛刚刚取得了某种胜利。这张照片被广泛传播,成为了经典的表情包。表情包的主角萨米·格里纳(SammyGriner)被称为“成功宝宝”,还被外媒评价“可能是互联网上最著名的婴儿”。NodoubtinyourIntern......
  • python+flask框架的智慧停车平台 小程序18(开题+程序+论文) 计算机毕业设计
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容选题背景随着城市化进程的加速,车辆数量急剧增加,停车难问题已成为各大城市面临的普遍难题。智慧停车平台作为解决停车难问题的有效手段,近年来在国内......
  • 谈一谈React18的服务端组件
    最近笔者腾出了大把的时间,学习了一下React18。什么是服务器组件React18带来了一个实验性的特性:ReactServerComponents,简称RSC,即服务器组件。服务器组件可能会在React19版本作为稳定特性推出。如果目前就用于生产的话,可能需要注意API在未来的变化情况。什么是服务器......