头像

无味


访客:3360

离线:1天前


分享 枚举

无味
7天前

一般枚举问题的思路很明显就能看出来要用枚举,但是难点就在于要怎么缩小每个变量的范围,一般变量之间都是有某些关系的,通过缩小枚举的范围,设置枚举的顺序,来提高枚举顺序.否则就会超时。

1.完美立方 百炼2810

这个一看第一反应就是暴力

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int a=2;a<=n;++a)
        for(int b=a;b<=n;++b)
            for(int c=b;c<=n;++c)
                for(int d=c;d<=n;++d)
                    if(pow(a,3)==pow(b,3)+pow(c,3)+pow(d,3))
                        cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl; 

    return 0;
 } 

但是运行后是这样的:
QQ截图20200915204757.jpg
看了一圈没找出来毛病,又看了看题干,发现题干a,b,c,d大于1,那么b应该也从2开始;

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int a=2;a<=n;++a)
        for(int b=2;b<=n;++b)
            for(int c=b;c<=n;++c)
                for(int d=c;d<=n;++d)
                    if(pow(a,3)==pow(b,3)+pow(c,3)+pow(d,3))
                        cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl; 

    return 0;
 } 

这次输入24,输出的和样例一样,提交后显示超时.要想想怎么优化,能不能把a放在for循环的最内层呢

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int a=2;a<=n;++a)
        for(int b=a;b<=n;++b)
            for(int c=b;c<=n;++c)
                for(int d=c;d<=n;++d)
                    if(pow(a,3)==pow(b,3)+pow(c,3)+pow(d,3))
                        cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl; 

    return 0;
 } 

但是输出的和样例不一样
QQ截图20200915212450.jpg
发现这样输出并不是按照题干要求的,所以还是要把a放在第一重循环,那么就要想想怎么缩小范围了.
通过看样例,发现其实b,c,d的值没必要到n,每次到n-1结束就行,所以b[2,a-1];c[b,a-1];d[c,a-1];

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int a=2;a<=n;++a)
        for(int b=2;b<a;++b)
            for(int c=b+1;c<a;++c)
                for(int d=c+1;d<a;++d)
                    if(pow(a,3)==pow(b,3)+pow(c,3)+pow(d,3))
                        cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl; 

    return 0;
}

但是提交后还是显示超时,想了想爱还是不知道该怎么缩了,于是看了郭炜老师的讲解发现了问题,原来是死在了pow函数上:

#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int a=2;a<=n;++a)
        for(int b=2;b<a;++b)
            for(int c=b;c<a;++c)
                for(int d=c;d<a;++d)
                    if(a*a*a==b*b*b+c*c*c+d*d*d)
                        cout<<"Cube = "<<a<<", Triple = ("<<b<<","<<c<<","<<d<<")"<<endl; 

    return 0;
} 

pow的运行时间是3173ms,后边则是43ms,真是没想到哇!!!!amazing



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

无味
10天前
#include<iostream>
using namespace std;
const int N=10;
int n;
int num[N];
bool st[N];
void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;++i)
            cout<<num[i]<<" ";

        cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;++i)
            if(!st[i])
            {
                st[i]=true;
                num[u]=i;
                dfs(u+1);
                st[i]=false;
            }
    }
}

int main()
{
    cin>>n;

    dfs(1);
    return 0;
}


分享 排序

无味
11天前

1.快速排序:

算法描述:

  • 从待排序记录序列中选取一个记录(这个可以任意选取一个数字,通常选取第一个记录)为枢轴,其关键字设为K1;
  • 然后将其余关键字小于K1的记录移到前面,而将关键字大于或者等于K1的记录移到后面,结果将待排序记录序列分为两个子表,最后将关键字K1的值插入到分界线的位置。将这个过程称为一趟快速排序.
  • 通过一次划分后,就以关键字为K1的值为界,将待排序序列分成了两个子表,且前边子表中所有记录的值均小于K1,而后面子表中的所有的值均大于或等于K1。
  • 对分割后的子表继续按上述原则进行分割,直到所有子表的表长不超过1为止,此时待排序记录序列就变成了一个有序表.

其实快速排序是基于分治思想
QQ截图20200912093055.jpg

算法分析

QQ图片20200912093612.jpg

y总模板:

void quick_sort(int num[],int l,int r)
{
    if(l>=r) return;

    int i=l-1,j=r+1,mid=num[l];
    while(l<r)
    {
        do i++; while(num[i]<mid);
        do j--; while(num[i]>mid);
        if(i<j) swap(num[i],num[j]);
        else break;
    }
    quick_sort(num,l,j);qucik_sort(num,j+1,r);
}

y总这个代码的思路和学数据结构时老师讲的还不一样,老师当时是先从num[j]开始比较的,其实不管是从num[j]还是num[i]最后结果都是一样的.
QQ图片20200911205221.jpg

#include<iostream>
using namespace std;

int num[]={12,2,16,30,28,10,16,20,6,18};
void quick_sort(int num[],int l,int r)
{
    if(l>=r) return;

    int i=l-1,j=r+1,mid=num[l];
    while(i<j)
    {
        do i++; while(num[i]<mid);
        do j--; while(num[j]>mid);
        if(i<j) swap(num[i],num[j]);
        else break;
    }

    cout<<i<<" "<<j<<endl;
    quick_sort(num,l,j),quick_sort(num,j+1,r);
    //quick_sort(num, l, i-1), quick_sort(num, i, r);这样不行,会陷入死循环 .如果非要用i的话,那么就要更改mid=num[r];其实这个只需要背过一个就行
}

int main()
{
    quick_sort(num,0,9);
    for(int i=0;i<=9;++i)
        cout<<num[i]<<" ";
}

QQ截图20200911205359.jpg

所以还是按照y总的模板走!!!

下面回忆一下do…while:
QQ截图20200912073900.jpg


2.归并排序:

算法描述:

算法分析

QQ图片20200912111719.jpg

y总模板:

void merge_sort(int num[],int l,int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;//等价于mid = (l + r)/2;
    merge_sort(num, l, mid);
    merge_sort(num, mid + 1, r);

    int k=0,i = l, j = mid + 1;
    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) num[i] = tmp[j];
 }



活动打卡代码 AcWing 717. 简单斐波那契

无味
13天前
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1,a=0,b=1;i<=n;++i){
        cout<<a<<" ";
        int c=a+b;
        a=b;b=c;
    }
    return 0;
}

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int nums[46]={0,0,1};
    for(int i=3;i<=n;++i)
        nums[i]=nums[i-1]+nums[i-2];

    for(int i=1;i<=n;++i)
        cout<<nums[i]<<" ";
    return 0;
}



无味
14天前
#include<iostream>
using namespace std;
int n;
const int N=10;
void dfs(int u,int nums[],bool st[])
{
    if(u>n){
        for(int i=1;i<=n;++i)//注意这个地方是i从1开始!!!
            cout<<nums[i]<<" ";
    cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;++i)
            if(!st[i])
            {
                st[i]=true;
                nums[u]=i;
                dfs(u+1,nums,st);
                st[i]=false;
            }
    }
}
int main()
{
    cin>>n;
    int nums[N];
    bool st[n]={0};

    dfs(1,nums,st);

    return 0;
}


活动打卡代码 AcWing 823. 排列

无味
16天前

刚开始思路:

#include<iostream>
using namespace std;

int n;
bool b[10]={0};

void f(int cnt){
    if(cnt==n) cout<<endl;
    else if(cnt<n){
        for(int i=1;i<=n;++i){
            if(!b[i])
                cout<<i<<" ";
                b[i]=true;
                //cnt++;
                f(cnt+1);
                b[i]=false;
        }
    }

}
int main()
{
    cin>>n;
    f(0);
    return 0;
}

但就是运行不出来,调试了一会也出不来,于是看了y总的代码:

#include<iostream>
using namespace std;

const int N=10;
int n;
void dfs(int u,int nums[],bool st[])
{
    if(u>n){
        for(int i=1;i<=n;++i)
            cout<<nums[i]<<" ";
    cout<<endl;
    }
    else
    {
        for(int i=1;i<=n;++i)
            if(!st[i]){
                nums[u]=i;
                st[i]=true;
                dfs(u+1,nums,st);
                st[i]=false;
            }
    }
}
int main()
{
    cin>>n;
    int nums[N];
    bool st[n]={0};

    dfs(1,nums,st);
    return 0;
}

y总是先把每个数存到nums数组中,然后等存满了就输出,我是想着用i来输出,但没找到错在哪,于是照着y总的改了改,但还是不行,后边再回来看吧

#include<iostream>
using namespace std;
const int N=10;
int n;
void dfs(int u,bool st[])
{
    if(u>n)
        cout<<endl;
    else
    {
        for(int i=1;i<=n;++i)
            if(!st[i])
            {
                st[i]=true;
                cout<<i<<" ";
                dfs(u+1,st);
                st[i]=false;
            }
    }
}
int main()
{
    cin>>n;

    int nums[N];
    bool st[n]={0};

    dfs(1,st);
    return 0;
}


活动打卡代码 AcWing 815. 打印字符串

无味
16天前
#include<iostream>
using namespace std;
void print(char str[])
{
    puts(str);//cout<<str;也可以
}
int main()
{
    char str[100];
    cin.getline(str,105);
    print(str);
    return 0;
}



无味
19天前
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int num=0;

        for(vector<int>::iterator i=nums.begin();i!=nums.end();++i)
            if(*i==k)
                num++;

        return num;
    }
};

y总:
class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        int cnt=0;

        for(int x : nums)
            if(x==k)
                cnt++;

        return cnt;
    }
};



无味
28天前
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s;
    while(cin>>s)
        cout<<s<<" ";
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s;
    getline(cin,s);

    for(int i=0;i<s.size();++i)
    {
        int j=i;
        string str;
        while(j<s.size()&&s[j]!=' ') str+=s[j++];

        cout<<str<<" ";

        while(s[j]==' ') j++;

        i=j-1;//注意:因为上边还要++i.
    }
    return 0;
}



活动打卡代码 AcWing 770. 单词替换

无味
28天前
#include<iostream>
#include<sstream>
using namespace std;
int main()
{
    string s,a,b;
    getline(cin,s);
    cin>>a>>b;

    stringstream ssin(s);
    string str;
    while(ssin>>str)
        if(str==a) cout<<b<<" ";
        else cout<<str<<" ";

    return 0;
}




#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    string s,a,b;
    getline(cin,s);
    cin>>a>>b;

    for(int i=0,d=0;i<s.size();++i)
    {
        string word;
        while(j<s.size()&&s[j])!=' ')
            word+=line[j++];

        if(word==a) cout<<b<<' ';
        else cout<<word<<' ';
    }

    return 0;
}