头像

持剑人


访客:986

在线 


新鲜事 原文

新鲜事这个功能怕不是直接灌水。。。



排列数字(全排列问题)


PS:dfs最重要的一点就是用什么顺序去遍历所有的方案

分析:

给定3个空格

往里面填数,使这里的那个数不等于前面那个数字

1


Ac Code:

//全排列问题
#include <iostream>
using  namespace std;

int n,p[10];
bool is[10];//看看这个点有没有被用过

void dfs(int x)
{
    if(x==n) //如果有方案了,就输出
    {
        for(int i=0;i<n;i++) cout<<p[i]<<' ';
        cout<<endl;
        return ;
    }
    //
    for(int i=1;i<=n;i++)
    {
        if(!is[i])//如果i没有被填过
        {
            p[x]=i;//把i填进去
            is[i]=true;//把第i个数标记为用过
            //处理

            dfs(x+1);//用x++的话,一会还要x--,所以就用x+1省事
            //搜索下一层

            is[i]=false;
            //回溯(回复原来递归下一层前的现场)
        }
    }
}

int main()
{
    cin>>n;

    dfs(0);//从0开始

    return 0;
}


活动打卡代码 AcWing 842. 排列数字

//全排列问题
#include <iostream>
using  namespace std;

int n,p[10];
bool is[10];//看看这个点有没有被用过

void dfs(int x)
{
    if(x==n) //如果有方案了,就输出
    {
        for(int i=0;i<n;i++) cout<<p[i]<<' ';
        cout<<endl;
        return ;
    }
    //
    for(int i=1;i<=n;i++)
    {
        if(!is[i])//如果i没有被填过
        {
            p[x]=i;//把i填进去
            is[i]=true;//把第i个数标记为用过
            //处理

            dfs(x+1);//用x++的话,一会还要x--,所以就用x+1省事
            //搜索下一层

            is[i]=false;
            //回溯(回复原来递归下一层前的现场)
        }
    }
}

int main()
{
    cin>>n;

    dfs(0);//从0开始

    return 0;
}


活动打卡代码 AcWing 795. 前缀和

#include <iostream>
using namespace std;

const int N=100010;

int sum[N],a[N],ans[N];

int main()
{
    int n,m;

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];

    sum[0]=0;
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];

    for(int i=1;i<=m;i++) 
    {
        int l,r;
        cin>>l>>r;
        ans[i]=sum[r]-sum[l-1];
    }

    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;

    return 0;
}


活动打卡代码 AcWing 791. 高精度加法

持剑人
16天前
#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
string al,bl;
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    int la,lb,lc,x=0;           //x=进位
    cin>>al;
    cin>>bl;                    //读入al,bl
    la=al.length();
    lb=bl.length();             //计算长度
    if(al=="0\0"&&bl=="0\0")
    {
        cout<<"0";              //特判 
        return 0;
    }
    for(int i=0;i<=la-1;i++)
    {
        a[la-i]=al[i]-48;        //转为数字
    }    
    for(int i=0;i<=lb-1;i++)
    {
        b[lb-i]=bl[i]-48;       //转为数字
    }
    lc=1;
    while(lc<=la||lc<=lb)
    {
        c[lc]=a[lc]+b[lc]+x;
        x=c[lc]/10;             //进位    
        c[lc]%=10;              //求相加之后的个位
        lc++;                   //计算下一个数 
    } 
    c[lc]=x;
    while(c[lc]==0)
    {
        lc--;                   //去掉前导0 
    } 
    for(int i=lc;i>=1;i--)
    {
        cout<<c[i];              
    } 
    return 0;
}



持剑人
18天前

高精加

原理:电脑模拟人工加法

1

这里采用倒着进行运算,因为这样的话方便进位


vector实现

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;

    int t=0;//进位
    for(int i=0;i < A.size() || i < B.size();i++)
    {
        if(i<A.size()) t+=A[i];//如果i小于A的总长度的话,那么就将sum加上A的这一位的数
        if(i<B.size()) t+=B[i];//如果i小于B的总长度的话,那么就将sum加上B的这一位的数
        C.push_back(t%10);//保证sum不大于10
        t/=10;//把各位去掉
    }
    if(t) C.push_back(1);//如果最后还有数的话,那么它就一定是1

    return C ;
}

int main()
{gao
    string a,b;
    vector<int> A,B;

    cin>>a>>b;

    for( int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//倒着存有助于进位
    for( int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');//倒着存有助于进位


    auto C=add(A,B);//auto就是自动匹配类型变量

    for(int i=C.size()-1;i>=0;i--)
    {
        printf("%d",C[i]);
    }

    return 0;
}

普通实现

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
string al,bl;
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    int la,lb,lc,x=0;           //x=进位
    cin>>al;
    cin>>bl;                    //读入al,bl
    la=al.length();
    lb=bl.length();             //计算长度
    if(al=="0\0"&&bl=="0\0")
    {
        cout<<"0";              //特判 
        return 0;
    }
    for(int i=0;i<=la-1;i++)
    {
        a[la-i]=al[i]-48;        //转为数字
    }    
    for(int i=0;i<=lb-1;i++)
    {
        b[lb-i]=bl[i]-48;       //转为数字
    }
    lc=1;
    while(lc<=la||lc<=lb)
    {
        c[lc]=a[lc]+b[lc]+x;
        x=c[lc]/10;             //进位    
        c[lc]%=10;              //求相加之后的个位
        lc++;                   //计算下一个数 
    } 
    c[lc]=x;
    while(c[lc]==0)
    {
        lc--;                   //去掉前导0 
    } 
    for(int i=lc;i>=1;i--)
    {
        cout<<c[i];              
    } 
    return 0;
}



持剑人
18天前

高精加

原理:电脑模拟人工加法

1

这里采用倒着进行运算,因为这样的话方便进位


vector实现

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int> C;

    int t=0;//进位
    for(int i=0;i < A.size() || i < B.size();i++)
    {
        if(i<A.size()) t+=A[i];//如果i小于A的总长度的话,那么就将sum加上A的这一位的数
        if(i<B.size()) t+=B[i];//如果i小于B的总长度的话,那么就将sum加上B的这一位的数
        C.push_back(t%10);//保证sum不大于10
        t/=10;//把各位去掉
    }
    if(t) C.push_back(1);//如果最后还有数的话,那么它就一定是1

    return C ;
}

int main()
{gao
    string a,b;
    vector<int> A,B;

    cin>>a>>b;

    for( int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');//倒着存有助于进位
    for( int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');//倒着存有助于进位


    auto C=add(A,B);//auto就是自动匹配类型变量

    for(int i=C.size()-1;i>=0;i--)
    {
        printf("%d",C[i]);
    }

    return 0;
}

普通实现

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005],c[100005];
string al,bl;
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    int la,lb,lc,x=0;           //x=进位
    cin>>al;
    cin>>bl;                    //读入al,bl
    la=al.length();
    lb=bl.length();             //计算长度
    if(al=="0\0"&&bl=="0\0")
    {
        cout<<"0";              //特判 
        return 0;
    }
    for(int i=0;i<=la-1;i++)
    {
        a[la-i]=al[i]-48;        //转为数字
    }    
    for(int i=0;i<=lb-1;i++)
    {
        b[lb-i]=bl[i]-48;       //转为数字
    }
    lc=1;
    while(lc<=la||lc<=lb)
    {
        c[lc]=a[lc]+b[lc]+x;
        x=c[lc]/10;             //进位    
        c[lc]%=10;              //求相加之后的个位
        lc++;                   //计算下一个数 
    } 
    c[lc]=x;
    while(c[lc]==0)
    {
        lc--;                   //去掉前导0 
    } 
    for(int i=lc;i>=1;i--)
    {
        cout<<c[i];              
    } 
    return 0;
}


活动打卡代码 AcWing 790. 数的三次方根

持剑人
20天前
#include <iostream>
using namespace std;

int main()
{
    double x;
    scanf("%lf",&x);

    double l=-10000,r=10000;
    //这样可以防止 0 < x < 1时的问题
    //不然l=0,r=x的话,输入0.001时,答案找不到0.1
    while(r-l>1e-8)//精度是1的负八次方
    {
        double mid=(l+r)/2;//中间数

        if(mid*mid*mid>=x)//当mid^3大于
        {
            r=mid;
        }
        else
        {
            l=mid;
        }
    }

    printf("%lf",l);//l和r其实都一样

    return 0;
}


活动打卡代码 AcWing 788. 逆序对的数量

持剑人
21天前
#include <iostream>
using namespace std;

typedef long long LL;//重定义后比较好看
const LL  N=100010;

LL n,q[N],tmp[N];

LL msort(int l,int r)//左指针和右指针
{
    if(l>=r) return 0;//重合就退出

    int mid=(l+r)>>1;//求中间值
    LL res=msort(l,mid) + msort(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++];//那么tmp就等于右半边的
        }
        else //若左半边>右半边
        {
            tmp[k++]=q[j++];//那么tmp就等于左半边的
            res+=mid-i+1;//但q[i]<=q[j]的时候,那么它后面的符合逆序对
        }
    }
    //把没有放完的再进去
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r)   tmp[k++]=q[j++];

    i=l,k=0;
    while(i<=r)//物归原主
    {
        q[i]=tmp[k];
        i++;
        k++;
    }    

    return res;//返回res
}

int main()
{
    cin>>n;
    for(int i=0;i<=n;i++) cin>>q[i];

    cout<<msort(0,n-1)<<endl;

    return 0;
}


活动打卡代码 AcWing 789. 数的范围

持剑人
23天前
#include <iostream>
using namespace std;

const int N=100010;

int n,m,q[N];

int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++) cin>>q[i];
    //输入

    while(m--)//一共有m个询问
    {
        int x;
        cin>>x;//这里求的边界就是要查询的数

        int l=0,r=n-1;//下标从0~n-1
        //先二分左半边
        while(l<r)
        {
            //mid可能是答案,所以要用模板2
            int mid=(l+r)>>1;
            //相当于/2,但是/2是向下取整,>>是四舍五入
            if(q[mid]>=x) r=mid;
            else l=mid+1;
        }

        if(q[l]!=x) cout<<"-1 -1"<<endl;
        //当序列中不存在x时,返回的是最前面的那个>=x的数
        //所以如果x不存在的话,返回的数就一定>=x
        //所以就输出-1,-1
        else
        {
            cout<<l<<" ";
            //其实输出l和r都没所谓,因为跳出循环时l是等于r的

            //再二分右半边
            int l=0,r=n-1;
            while(l<r)
            {
                //模板1
                int mid=(l+r+1)>>1;
                if(q[mid]<=x) l=mid;
                else r=mid-1;
            }
            cout<<l<<endl;
        }
    }
    return 0;
}