模版题ac

acwing

  • 787第k 个数
  • 787归并排序
  • 788逆序对的数量
  • 795前缀和
  • 796子矩阵的和
  • 789数的范围
  • 790数的三次方根
  • 797差分
  • 799最长相同子序列
  • 800数组的目标和
  • 801二进制中1的个数
  • 802区间和(有点难)
  • 803区间合并
  • 830单调栈
  • 154滑动窗口
  • 842排列数字

787第k 个数

快速排序

#include<bits/stdc++.h>
using namespace std;
void quick_sort(int n[], int l, int r){
    if(l>=r) return ;
    int i=l-1,j=r+1,x=n[l+r>>1];
    while(i<j){
        do i++; while(n[i]<x);
        do j--; while(n[j]>x);
        if(i<j) swap(n[i],n[j]);
    }
    quick_sort(n,l,j); quick_sort(n,j+1,r);
}
int main(){
    int n[1000001];
    int k,num;
    cin>>num>>k;
    for(int i=0;i<num;i++){
        scanf("%d",&n[i]);
    }
    quick_sort(n,0,num-1);
    cout<<n[k-1];
    return 0;
}

787归并排序

#include<bits/stdc++.h>
using namespace std;
void merge_sort(int num[],int l,int r){
    if(l>=r) return ;
    int mid=l+r>>1;
    merge_sort(num,l,mid);
    merge_sort(num,mid+1,r);
    int k=0;i=l;j=mid+1;
    int tmp[10001];
    while(i<=mid&&j<=r){
        if(num[i]<=num[j]) tmp[k++]=num[i++];
        else tmp[k++]=num[j++];
    }
    while(i<=mid) tmp[k++]=num[i++];
    while(j<=r) tmp[k++]=num[j++];
    for(i=l,j=0;i<=r;i++,j++){
        q[i]=tmp[j];
    }  
}
int mian(){
    int n,num[100001];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    merge_sort(num,0,n-1);
    for(int i=0;i<n;i++){
        cout<<num[i]<<" ";
    }
    return 0;
}

788逆序对的数量

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

int tmp[100010];
long long int merge_sort(int q[],int l, int r){
    if(l>=r) return 0;
    int mid=l+r>>1;
    long long int res=0;
    res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);//左边和右边的和加起来

    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else{
            tmp[k++]=q[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];//只有两边都是有序的才能排序
    return res;
}
int main(){
    int n;
    cin>>n;
    int q[100010];
    for(int i=0;i<n;i++){
        cin>>q[i];
    }
    cout<<merge_sort(q,0,n-1);
}

795前缀和

#include<bits/stdc++.h>
using namespace std;
int s[100100];
void create(int num[],int n){
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+num[i];
    }
}
int main(){
    int n,m;
    
    int b,e;
    cin>>n>>m;
    int num[100010];
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    create(num,n);
    while(m--){
        cin>>b>>e;
        cout<<s[e]-s[b-1]<<endl;
        
    }
}

796子矩阵的和

#include<iostream>
using namespace std;
int main(){
    int m,n,q;
     int num[1001][1001];
     int s[1001][1001];
    cin>>m>>n>>q    ;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>num[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+num[i][j];
        }
    }
    int x1,x2,y1,y2;
    while(q--){
        cin>>x1>>y1>>x2>>y2;
        cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
    }
    return 0;
}

789数的范围

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,q,m;
    int num[100010];
    cin>>n>>q;
    for(int i=0;i<n;i++) cin>>num[i];
    while(q--){
        cin>>m;
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;//r=l-1
            if(num[mid]>=m ) r = mid;//找右边界。如果中间值大于该值,那么说明边界应该在mid的左边。让右边界等于mid。这个地方不用加一。r=l+r=l,变了,还是可以的
            else l=mid+1;
        }
        if(num[l]!=m) cout<<"-1 -1"<<endl;
        else {
            cout<<l<<" ";
            l=0,r=n-1;
            while(l<r){
                int mid=l+r+1>>1;//但这里l=l+r/2=l,l=l.死循环了
                if(num[mid]<=m) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}

790数的三次方根

#include<iostream>
using namespace std;
int main(){
    double l=-10000,r=10000;
    
    double n;
    cin>>n;
    while(r-l>1e-8){
        double m=(l+r)/2;
        if(m*m*m>=n) r=m;
        else l=m;
    }
    printf("%.6lf",l);
}

797差分

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],s[100010];//原数组和差分数组

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;//后面的可以理解,前面的自己模拟一下就行了
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) insert(i,i,a[i]);
    int left,right,val;
    while(m--){
        cin>>left>>right>>val;
        insert(left,right,val);
    }
    
    for(int i=1;i<=n;i++) b[i]+=b[i-1];
    
    for(int i=1;i<=n;i++) cout<<b[i]<<" ";
    
    return 0;
}

799最长相同子序列

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m[100010],n;
    int res=0;
    cin>>n;
        map<int,int> s;
    for(int i=0;i<n;i++) {
        cin>>m[i];
    }
    for(int i=0,j=0;i<n;i++){
        s[m[i]]++;//
        while(s[m[i]]>1){
            s[m[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    cout<<res;
} 

800数组的目标和

#include<bits/stdc++.h>
using namespace std;
int main(){
    int l1,l2,x;
    int a[100010],b[100010];
    cin>>l1>>l2>>x;
    for(int i=0;i<l1;i++) cin>>a[i];
    for(int i=0;i<l2;i++) cin>>b[i];
    for(int i=0,j=l2-1;i<l1;i++){//按照单调性,j从第二个数组的最右端开始往左找,找到最左的能够满足加和大于目标的
        
      
        while(j>0&&a[i]+b[j]>x){
            j--;
        }
        if(a[i]+b[j]==x) {
            cout<<i<<" "<<j;
            break;
        }
    }
    return 0;
}

801二进制中1的个数

#include<bits/stdc++.h>
using namespace std;
int main(){
    int res=0;
    int n,m;
    cin>>n;
    while(n--){
        cin>>m;
        res=0;
        while(m>0){
            if(m%2==1) res++;
            m/=2;
        }
        cout<<res<<" ";
    }
    return 0;
}

802区间和(有点难)

挺复杂的感觉,需要自己模拟一下看好理解一些

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


typedef pair<int,int> PII;//pair类型保存两个操作
vector<int> alls;	//所有的插入操作和查询操作
vector<PII> add,query;	//定义这两个操作集
int a[300010],s[300010]={0};//len add+2*query定义这两个用来离散化。a的值对应的是alls中的值,对应上
int find(int x){	//二分查找到该点的下标位置作为all数组的索引,就是把alls里面的很多数投射到a里面,再通过alls去索引查找
    int l=0,r=alls.size()-1;
    
    while(l<r){
        int mid=l+r >>1;
        
        if(x<=alls[mid]) r=mid;
        else l=mid+1;
    }
    return r+1;//从1开始
}

int main(){
    int m,n;
    cin>>m>>n;
    int x,c;
    for(int i=0;i<m;i++){
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    int l,r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        query.push_back({l,r});
        alls.push_back(l);alls.push_back(r);//把待查询的和add的都加进去。重点还是查询部分的。因为去重就可以把
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重操作,先排序。
    for(auto item : add){
        int x=find(item.first);
        a[x]+=item.second;
    }
    for(int i=1;i<=alls.size();i++){
        s[i]=s[i-1]+a[i];//计算离散后的前缀和
    }
    for(auto item : query){
        int l=find(item.first);
        int r=find(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    
    return 0;
}

803区间合并

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
void merge(vector<PII> &segs){

    vector<PII> res;
    int st=-2e9,ed=-2e9;//有点坑,这里要设置成最小否则后面判断会出问题。最小是-2e9
    sort(segs.begin(),segs.end());//容易拉下,先对所有的线段排序再从里面往外取。
   
    for(auto seg : segs)
        if(ed<seg.first)//没交集
        {
            if(st!=-2e9) res.push_back({st,ed});//防止是第一个
            st=seg.first;ed=seg.second; //加进去之后,开始往下看别的线段
        }
        else ed=max(ed,seg.second); //否则就让ed等于ed和seg里面最大的一个
    
    if(st!=-2e9) res.push_back({st,ed});//最后一个的处理。最后一个假如没合并的话不会进循环了。所以要单独判断
    
    segs=res;
    
}
int main(){
    
    int n;
    cin>>n;
    vector<PII> segs;
    int l,r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        segs.push_back({l,r});
    }

    merge(segs);
    
    cout<<segs.size();
    return 0;
    
}

830单调栈

#include<bits/stdc++.h>
using namespace std;
//找出每个数左边离他最近的比他大/小的数
int n;
int stk[100010];
int tt;
int main(){
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        while(tt&&stk[tt]>=x) tt--;//找比当前数小最近的数。栈里面的值比当前的数要大,说明之后就可以不用考虑了,直接把小数放进去其他的弹出来就可以了
        if(tt) cout<<stk[tt]<<" ";
        else cout<<-1<<" ";
        stk[++tt]=x;
    }
    return 0;
}

154滑动窗口

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


int a[1000010],q[1000010];
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++) cin>>a[i];
    int hh=0,tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++; //保证队列始终在窗口内部,队头不能太小了,出来就把队头的删掉。
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;   //如果队尾元素大于当前元素,那就不用要了没啥用了
        q[++tt]=i;//把这个数加进队列里面去
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
     hh=0;tt=-1;
    for(int i=0;i<n;i++){
        if(hh<=tt&&q[hh]<i-k+1) hh++; //保证队列始终在窗口内部,队头不能太小了,出来就把队头的删掉。
        while(hh<=tt&&a[q[tt]]<=a[i]) tt--;   //如果队尾元素小于当前元素,说明窗口里面这个数肯定不会用到了,直接删掉
        q[++tt]=i;//把这个数加进队列里面去
        if(i>=k-1) cout<<a[q[hh]]<<" ";
    }
    cout<<endl;
    return 0;
}

842排列数字

DFS方法

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

bool st[10];
int path[10];

void dfs(int u){
    if(u==n) {  //1-n的排列应该有n个数。每一层就会多一个数,因此到n层就该停止了
        for(int i=0;i<n;i++){
            cout<<path[i]<<" ";//path只保留当前数量等于n的路径上的数组内的元素
        }
        cout<<endl;
        return;
    }
    
    else{
        for(int i=1;i<=n;i++){//开始从1遍历
            if(!st[i]){//首先判断待加入的这个是不是遍历过了。1一开始没有,加进去
            path[u]=i;  
            st[i]=true;//更新维护这个状态,然后去下一层dfs1。在第二层时1用过了,还剩2和3,到第三层dfs2,仅剩3,因此123
                        //出来,dfs3输出,返回到dfs2,去看3,3被占用,解除,退回dfs1,dfs1支持3,因此132,重复后,回到dfs
                        //1,结束,在看st全部解锁,放2上去,锁2看13这样类推
            dfs(u+1);
            st[i]=false;
            }
        }
        
        
    }
}

int main(){
    cin>>n;
    dfs(0);
    
    
}

热门文章

暂无图片
编程学习 ·

那些年让我们目瞪口呆的bug

程序员一生与bug奋战&#xff0c;可谓是杀敌无数&#xff0c;见怪不怪了&#xff01;在某知识社交平台中&#xff0c;一个“有哪些让程序员目瞪口呆的bug”的话题引来了6700多万的阅读&#xff0c;可见程序员们对一个话题的敏感度有多高。 1、麻省理工“只能发500英里的邮件” …
暂无图片
编程学习 ·

redis的下载与安装

下载redis wget http://download.redis.io/releases/redis-5.0.0.tar.gz解压redis tar -zxvf redis-5.0.0.tar.gz编译 make安装 make install快链方便进入redis ln -s redis-5.0.0 redis
暂无图片
编程学习 ·

《大话数据结构》第三章学习笔记--线性表(一)

线性表的定义 线性表&#xff1a;零个或多个数据元素的有限序列。 线性表元素的个数n定义为线性表的长度。n为0时&#xff0c;为空表。 在比较复杂的线性表中&#xff0c;一个数据元素可以由若干个数据项组成。 线性表的存储结构 顺序存储结构 可以用C语言中的一维数组来…
暂无图片
编程学习 ·

对象的扩展

文章目录对象的扩展属性的简洁表示法属性名表达式方法的name属性属性的可枚举性和遍历可枚举性属性的遍历super关键字对象的扩展运算符解构赋值扩展运算符AggregateError错误对象对象的扩展 属性的简洁表示法 const foo bar; const baz {foo}; baz // {foo: "bar"…
暂无图片
编程学习 ·

让程序员最头疼的5种编程语言

世界上的编程语言&#xff0c;按照其应用领域&#xff0c;可以粗略地分成三类。 有的语言是多面手&#xff0c;在很多不同的领域都能派上用场。大家学过的编程语言很多都属于这一类&#xff0c;比如说 C&#xff0c;Java&#xff0c; Python。 有的语言专注于某一特定的领域&…
暂无图片
编程学习 ·

写论文注意事项

参考链接 给研究生修改了一篇论文后&#xff0c;该985博导几近崩溃…… 重点分析 摘要与结论几乎重合 这一条是我见过研究生论文中最常出现的事情&#xff0c;很多情况下&#xff0c;他们论文中摘要部分与结论部分重复率超过70%。对于摘要而言&#xff0c;首先要用一小句话引…
暂无图片
编程学习 ·

安卓 串口开发

上图&#xff1a; 上码&#xff1a; 在APP grable添加 // 串口 需要配合在项目build.gradle中的repositories添加 maven {url "https://jitpack.io" }implementation com.github.licheedev.Android-SerialPort-API:serialport:1.0.1implementation com.jakewhart…
暂无图片
编程学习 ·

2021-2027年中国铪市场调研与发展趋势分析报告

2021-2027年中国铪市场调研与发展趋势分析报告 本报告研究中国市场铪的生产、消费及进出口情况&#xff0c;重点关注在中国市场扮演重要角色的全球及本土铪生产商&#xff0c;呈现这些厂商在中国市场的铪销量、收入、价格、毛利率、市场份额等关键指标。此外&#xff0c;针对…
暂无图片
编程学习 ·

Aggressive cows题目翻译

描述&#xff1a; Farmer John has built a new long barn, with N (2 < N < 100,000) stalls.&#xff08;John农民已经新建了一个长畜棚带有N&#xff08;2<N<100000&#xff09;个牛棚&#xff09; The stalls are located along a straight line at positions…
暂无图片
编程学习 ·

剖析组建PMO的6个大坑︱PMO深度实践

随着事业环境因素的不断纷繁演进&#xff0c;项目时代正在悄悄来临。设立项目经理转岗、要求PMP等项目管理证书已是基操&#xff0c;越来越多的组织开始组建PMO团队&#xff0c;大有曾经公司纷纷建造中台的气质&#xff08;当然两者的本质并不相同&#xff0c;只是说明这个趋势…
暂无图片
编程学习 ·

Flowable入门系列文章118 - 进程实例 07

1、获取流程实例的变量 GET运行时/进程实例/ {processInstanceId} /变量/ {变量名} 表1.获取流程实例的变量 - URL参数 参数需要值描述processInstanceId是串将流程实例的id添加到变量中。变量名是串要获取的变量的名称。 表2.获取流程实例的变量 - 响应代码 响应码描述200指…
暂无图片
编程学习 ·

微信每天自动给女[男]朋友发早安和土味情话

微信通知&#xff0c;每天给女朋友发早安、情话、诗句、天气信息等~ 前言 之前逛GitHub的时候发现了一个自动签到的小工具&#xff0c;b站、掘金等都可以&#xff0c;我看了下源码发现也是很简洁&#xff0c;也尝试用了一下&#xff0c;配置也都很简单&#xff0c;主要是他有一…
暂无图片
编程学习 ·

C语言二分查找详解

二分查找是一种知名度很高的查找算法&#xff0c;在对有序数列进行查找时效率远高于传统的顺序查找。 下面这张动图对比了二者的效率差距。 二分查找的基本思想就是通过把目标数和当前数列的中间数进行比较&#xff0c;从而确定目标数是在中间数的左边还是右边&#xff0c;将查…
暂无图片
编程学习 ·

项目经理,你有什么优势吗?

大侠被一个问题问住了&#xff1a;你和别人比&#xff0c;你的优势是什么呢? 大侠听到这个问题后&#xff0c;脱口而出道&#xff1a;“项目管理能力和经验啊。” 听者抬头看了一下大侠&#xff0c;显然听者对大侠的这个回答不是很满意&#xff0c;但也没有继续追问。 大侠回家…
暂无图片
编程学习 ·

nginx的负载均衡和故障转移

#注&#xff1a;proxy_temp_path和proxy_cache_path指定的路径必须在同一分区 proxy_temp_path /data0/proxy_temp_dir; #设置Web缓存区名称为cache_one&#xff0c;内存缓存空间大小为200MB&#xff0c;1天没有被访问的内容自动清除&#xff0c;硬盘缓存空间大小为30GB。 pro…
暂无图片
编程学习 ·

业务逻辑漏洞

身份认证安全 绕过身份认证的几种方法 暴力破解 测试方法∶在没有验证码限制或者一次验证码可以多次使用的地方&#xff0c;可以分为以下几种情况︰ (1)爆破用户名。当输入的用户名不存在时&#xff0c;会显示请输入正确用户名&#xff0c;或者用户名不存在 (2)已知用户名。…