头像

无味

AcWing University




离线:5天前


最近来访(2)
用户头像
Tkybk_dz

活动打卡代码 AcWing 78. 左旋转字符串

无味
2个月前

// class Solution {
// public:
// string leftRotateString(string str, int n) {
// string s;

// for(int i=n;i<str.size();i)
// s+=str[i];
// for(int i=0;i<n;
i)
// s+=str[i];
// return s;
// }
// };

class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.end() - n);
reverse(str.end() - n, str.end());
return str;
}
};




无味
3个月前
#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int num;
        cin>>num;
        if(num==1)
        {
            cout<<"No"<<endl;
            continue;
        }
        bool st=true;
        for(int i=2;i*i<=num;++i)
            if(num%i==0)
            {
                st=false;
                break;
            }
        if(st) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

TLE

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int num;
        cin>>num;
        if(num==1)
        {
            cout<<"No"<<endl;
            continue;
        }
        bool st=true;
        for(int i=2;i<=num/i;++i)
            if(num%i==0)
            {
                st=false;
                break;
            }
        if(st) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

只是将i*i<=num换成了i<=num/i就过了…



分享 年份问题

无味
3个月前

QQ截图20210415211426.jpg

AcWing 3391. 今年的第几天?

#include<iostream>
using namespace std;
bool year(int y)//闰年返回yes,平年返回no
{
    if(y%400==0||y%4==0&&y%100!=0)
        return true;
    else
        return false;
}
int main()
{
    int y,m,d;
    int r[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
    int p[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

    while(cin>>y>>m>>d)
    {
        int ans=0;
        ans+=d;
        if(year(y))//闰年
        {
            for(int i=m-1;i>=1;--i)
                ans+=r[i];
        }
        else//平年
        {
             for(int i=m-1;i>=1;--i)
                ans+=p[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

AcWing 3218. 日期计算

 #include<iostream>
using namespace std;
bool year(int y)
{
    if(y%400==0||y%4==0&&y%100!=0)
        return true;//闰年
    else
        return false;//平年
}
int main()
{
    int y,d;
    int r[]={0,31,29,31,30,31,30,31,31,30,31,30,31};
    int p[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

    while(cin>>y>>d)
    {
        int ans=1;
        if(year(y))
        {
            while(d>r[ans])//从一月份开始,先比较天数和当前月份的大小,天数<当前月份,说明答案就是当前月份
            {
                d-=r[ans];
                ans++;
            }
        }
        else
        {
             while(d>p[ans])
            {
                d-=p[ans];
                ans++;
            }
        }
        cout<<ans<<endl<<d<<endl;
    }

    return 0;
}

AcWing 3214. 节日

```

include[HTML_REMOVED]

using namespace std;
bool year(int y)//闰年返回yes,平年返回no
{
if(y%400==0||y%4==0&&y%100!=0)
return true;
else
return false;
}
int main()
{
int week[]={7,1,2,3,4,5,6};
int n,m;
cin>>n>>m;
int next=5;//2021-1-1是星期五
for(int i=n;i<=m;++i)
{
cout<<i<<”年:”<<next<<endl;
if(year(i))
{
next=week[(next+366)%7];
}
else
next=week[(next+365)%7];

} 
return 0;

}
```



分享 并查集

无味
3个月前

QQ截图20210411165315.jpg
QQ截图20210411165332.jpg
QQ截图20210411165356.jpg


HDU 1213.How Many Tables
题目不难,直接上代码:

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
    if(n==num[n]) return num[n];
    else find(num[n]);
}

void merge(int a,int b)//合并
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int t,n,m;
    cin>>t;

    while(t--)
    {
        cin>>n>>m;

        ini(n);//初始化

        while(m--)
        {
            int a,b;
            cin>>a>>b;

            if(find(a)!=find(b))
                merge(a,b);//合并                
        }

        int rec=0;
        for(int i=1;i<=n;++i)
            if(i!=find(i)) rec++;

        cout<<n-rec<<endl;//这个地方要注意

    }
    return 0;
}

算法进阶指南:

#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
void init()
{
    for(int i=1;i<=maxn;++i)//初始化 
        s[i]=i;
}
int find(int x)//查找 
{
    return x==s[x]?x:find(s[x]);
} 
void merge(int x,int y)//合并 
{
    x=find(x);
    y=find(y);
    if(x!=y) s[x]=s[y];
}

int main()
{
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;++i){
            cin>>x>>y;
            merge(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;++i)//统计有多少个集 
            if(s[i]==i)
                ans++;
        cout<<ans<<endl;
    }
}

复杂度:在上述程序中,查找find()、合并merge()的搜索深度是树的长度,复杂度都是O(n),性能较差。下面介绍合并和查询的优化方法,优化之后,查找和合并的复杂度都小于O(${log_2{n}}$).

  • 合并的优化:

在合并元素x和y时先搜到它们的根结点,然后再合并这两个根结点,即把一个根结点的集改成另一个根结点。这两个根结点的高度不同,如果把高度较小的集合并到较大的集上,能减少树的高度。下面是优化后的代码,在初始化时用height[i]定义元素i的高度,在合并时更改。

int height[maxn];
void init(){
    for(int i=1;i<=maxn;++i){
        s[i]=i;
        height[i]=0;//树的高度
    }
}
void merge(int x,int y){//优化合并操作
    x=find(x);
    y=find(y);
    if(height[x]==height[y]){
        height[x]=height[x]+1;//合并,树的高度加一
        s[y]=x;
    }
    else{
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}
  • 查询的优化—路径压缩:


    QQ截图20210411163026.jpg

程序如下:

int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);//路径压缩
    return s[x];
}
//这样其实还需要递归,但是只递归一次就好了,例如没有路径压缩时,要想求1的根结点,首先要到2-3-4,路径压缩之后,就是1-4.

QQ截图20210411164039.jpg

int find(int x){
    int r=x;
    while(s[r]!=r) r=s[r];//找到根结点
    int i=x,j;
    while(i!=r){
        j=s[i];//用临时变量j记录
        s[i]=r;//把路径上元素的集改为根结点
        i=j;
    }
    return r;
}

最终代码:

#include<iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
int height[maxn];
void init(){
    for(int i=1;i<=maxn;++i){
        s[i]=i;
        height[i]=0;//树的高度
    }
}
int find(int x){
    if(x!=s[x]) s[x]=find(s[x]);//路径压缩
    return s[x];
}
void merge(int x,int y){//优化合并操作
    x=find(x);
    y=find(y);
    if(height[x]=height[y]){
        height[x]=height[x]+1;//合并,树的高度加一
        s[y]=x;
    }
    else{
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}

int main()
{
    int t,n,m,x,y;
    cin>>t;
    while(t--){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;++i){
            cin>>x>>y;
            merge(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;++i)//统计有多少个集 
            if(s[i]==i)
                ans++;
        cout<<ans<<endl;
    }
}

POJ 2524.Ubiquitous Religions
刚开始的代码:

#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{

    if(x==s[x]) return s[x];
    else find(s[x]);
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int rec=1;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;

        init(n);

        int a,b,ans=0;
        while(m--)
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }

        for(int i=1;i<=n;++i)
            if(i==s[i]) ans++;

        cout<<"Case "<<rec<<": "<<ans<<endl;
        rec++;
    }
    return 0;
}

提交后显示WA.又看了一下没什么问题。看到n<50000后会不会是TLE了,于是加了个路径优化:

#include<iostream>
using namespace std;
const int maxn=50005;
int s[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(s[x]!=x) s[x]=find(s[x]);
    else return s[x];
//  if(x==s[x]) return s[x];
//  else find(s[x]);
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int rec=1;
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;

        init(n);

        int a,b,ans=0;
        while(m--)
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }

        for(int i=1;i<=n;++i)
            if(i==s[i]) ans++;

        cout<<"Case "<<rec<<": "<<ans<<endl;
        rec++;
    }
    return 0;
}

过了…
这个题还是和hdu1213基本思路一样,难度属于简单题。


AcWing 836. 合并集合

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
    if(n==num[n]) return num[n];
    else find(num[n]);
}

void merge(int a,int b)
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;

    init(n);//初始化

    while(m--)
    {
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M')
        {
            if(find(a)!=find(b))
                merge(a,b);                
        }
        else
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }


    return 0;
}

查找操作时没加路径优化,TLE

#include<iostream>
using namespace std;
int num[100005];
void init(int n)//初始化
{
    for(int i=1;i<=n;++i)
        num[i]=i;
}

int find(int n)//查找
{
     if(n!=num[n])  num[n]=find(num[n]);
     else return num[n];
}

void merge(int a,int b)
{
    int x=find(a);
    int y=find(b);
    num[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;

    init(n);//初始化

    while(m--)
    {
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M')
        {
            if(find(a)!=find(b))
                merge(a,b);                
        }
        else
        {
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
    }


    return 0;
}

POJ 1611.The Suspects

#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
    for(int i=0;i<maxn;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    else return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}
int main()
{
    int n,m,k;
    int num[maxn];
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        while(m--)//挨个读入每个小组 
        {
            cin>>k;
            int num[maxn];
            for(int i=1;i<=k;++i)
                cin>>num[i];//将每一个小组成员的编号读入数组num中 
            int first=find(num[1]);//用变量first记录小组第一个人的根结点 
            for(int i=2;i<=k;++i)//将小组内成员进行合并 
                if(first!=find(num[i]))
                    merge(first,num[i]);                
        }
        int zero=find(0);//找到0号成员的根结点
        int ans=1;//记录可疑对象的数量 
        for(int i=1;i<n;++i)//遍历整个数组,寻找可疑对象 
            if(find(i)==zero) ans++;

        cout<<ans<<endl;
    }
    return 0;
}

妈的第一次写的时候就是不对,但看了很多次觉着没问题啊.
排查后发现是三个函数写错了,于是照着之前通过的题看了一下原来是find()函数里没有那个else…操

#include<iostream>
using namespace std;
const int maxn=30005;
int s[maxn];
void init(int n)
{
    for(int i=0;i<maxn;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}
int main()
{
    int n,m,k;
    int num[maxn];
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        init(n);
        while(m--)//挨个读入每个小组 
        {
            cin>>k;
            int num[maxn];
            for(int i=1;i<=k;++i)
                cin>>num[i];//将每一个小组成员的编号读入数组num中 
            int first=find(num[1]);//用变量first记录小组第一个人的根结点 
            for(int i=2;i<=k;++i)//将小组内成员进行合并 
                if(first!=find(num[i]))
                    merge(first,num[i]);                
        }
        int zero=find(0);//找到0号成员的根结点
        int ans=1;//记录可疑对象的数量 
        for(int i=1;i<n;++i)//遍历整个数组,寻找可疑对象 
            if(find(i)==zero) ans++;

        cout<<ans<<endl;
    }
    return 0;
}

AcWing 837. 连通块中点的数量

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    s[y]=x;
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            int ans=0;
            for(int i=1;i<=n;++i)
                if(find(a)==find(i)) ans++;

            cout<<ans<<endl;
        }
    }
    return 0;
}

TLE了,对合并进行优化:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(height[x]==height[y])
    {
        s[y]=x;
        height[x]++;
    }
    else
    {
        if(height[x]<height[y]) s[x]=y;
        else s[y]=x;
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            int ans=0;
            for(int i=1;i<=n;++i)
                if(find(a)==find(i)) ans++;

            cout<<ans<<endl;
        }
    }
    return 0;
}

还是TLE
看了一下这个题和上边的最大区别就是对了第三项询问点 a 所在连通块中点的数量
这一块不能简单的进行暴力,要进行优化:
设置一个数组sum[]来存储根结点下有多少个点,在进行合并的时候,顺便更新sum[]数组

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
        sum[i]=1;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    sum[x]=sum[x]+sum[y];
    sum[y]=0;
    s[y]=x;
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<sum[find(a)]<<endl;
        }
    }
    return 0;
}

AC了,再加上合并优化后看看快多少:

#include<iostream>
using namespace std;
const int maxn=100005;
int s[maxn],sum[maxn],height[maxn];
void init(int n)
{
    for(int i=1;i<=n;++i)
    {
        s[i]=i;
        height[i]=0;
        sum[i]=1;
    }

}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(height[x]==height[y])
    {
        s[y]=x;
        height[x]++;
        sum[x]+=sum[y];
        sum[y]=0;
    }
    else
    {
        if(height[x]<height[y]) 
        {
            s[x]=y;
            sum[y]+=sum[x];
            sum[x]=0;
        }
        else
        {
            s[y]=x;
            sum[x]+=sum[y];
            sum[y]=0;    
        }
    }
}

int main()
{
    int n,m;
    cin>>n>>m;
    init(n);

    while(m--)
    {
        string s;
        int a,b;
        cin>>s;
        if(s=="C")
        {
            cin>>a>>b;
            if(find(a)!=find(b))
                merge(a,b);
        }
        else if(s=="Q1")
        {
            cin>>a>>b;
            if(find(a)==find(b)) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        else
        {
            cin>>a;
            cout<<sum[find(a)]<<endl;
        }
    }
    return 0;
}

第一个1122ms,第二个1058ms,还是快一点的


AcWing 2069. 网络分析

#include<iostream>
using namespace std;
const int maxn=10005;
int s[maxn];
long long sum[maxn];
bool initi(int n)
{
    for(int i=1;i<=n;++i)
        s[i]=i;
}
int find(int x)
{
    if(x!=s[x]) s[x]=find(s[x]);
    return s[x];
}
void merge(int x,int y)
{
    x=find(s[x]);
    y=find(s[y]);
    s[y]=x;
}
int main()
{
    int n,m;
    cin>>n>>m;
    initi(n);

    int c,a,b;
    while(m--)
    {
        cin>>c>>a>>b;
        if(c==1)//连接
            merge(a,b);
        else//发送消息
            for(int i=1;i<=n;++i)
                if(find(i)==find(a)) sum[i]+=b;
    }
    for(int i=1;i<=n;++i)
        cout<<sum[i]<<" ";
    return 0;
}

不出意外,TLE
下面就要优化将所有和结点p相同根结点的点+t这一操作




分享 高精度

无味
4个月前

一般来说:
A + B: A和B的位数小于等于$10^6$;
A - B: A和B的位数小于等于$10^6$;
A x a: A的位数小于等于$10^6$,a的小于等于$10^9$.
高精度除法不常见


#include<iostream>
#include<vector>
using namespace std;
int main()
{
    string s1,s2;
    vector<int> a,b,c;

    cin>>s1>>s2;

    for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');
    //当把string中的数字转换成整数时就是这样:-'0'!!!

    int d=0;//d表示进位
    for(int i=0;i<a.size()&&i<b.size();++i)
    {
        c.push_back((a[i]+b[i]+d)%10);
        d=(a[i]+b[i]+d)/10;
    }

    if(a.size()>c.size())
    {
        for(int i=c.size();i<a.size();++i)
        {
            c.push_back((a[i]+d)%10);
            d=(a[i]+d)/10;
        }
    }

    if(b.size()>c.size())
    {
        for(int i=c.size();i<b.size();++i)
        {
            c.push_back((b[i]+d)%10);
            d=(b[i]+d)/10;
        }
    }    


    if(d) c.push_back(d);//最后还有进位时

    for(int i=c.size()-1;i>=0;--i)//倒序输出
        cout<<c[i];

    return 0;
}

y总的:

#include<iostream>
#include<vector>
using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);//这个地方牛逼!!!

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];//这个地方也牛逼!!!
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(1);
    return C;
}

int main()
{
    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');

    //vector<int> C=add(A,B);
    auto C=add(A,B);//等价于vector<int> C=add(A,B).这个auto就是会自动匹配类型,因为add()函数的返回值是vector<int>类型的,所以就自动给C匹配成vector<int>类型的 

    for(int i=C.size()-1;i>=0;i--) cout<<C[i]; 

    return 0;
}

  • 高精度减法:

AcWing 792. 高精度减法
减法和加法略有不同,当len(s1)>len(s2)的时候,一定有s1>s2,这时进行正常的s1-s2竖式运算模拟就行;当len(s1)<len(s2),此时一定有s1<s2,这时需要swap(s1,s2),此时一定有s1>s2,再进行s1-s2竖式运算模拟,然后对最后结果加上-负号就好了.还有一种情况就是len(s1)=len(s2),但s1<s2,此时需要进行swap(s1,s2),再进行s1-s2竖式运算模拟.但是这种通过判断len(s1)和len(s2)不能确定s1,s2的大小了,而且也想不到别的方法来判断,给挡在这了.
看了y总代码后发现其实很简单,只需要判断s1<s2就好了,是自己忘了两个字符串比较的含义了,下面来回顾一下:
两个字符串比较大小,当第一次出现在相同位置两个字符不相等时,两个字符中ASCII大的所在字符串就大

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &a,vector<int> &b)
{
    vector<int> c;

    int d=0;
    for(int i=0;i<a.size();++i)
    {
        if(i<b.size())
        {
            if(a[i]-b[i]-d<0)
            {
                c.push_back(10+a[i]-b[i]-d);
                d=1;
            }
            else
            {
                c.push_back(a[i]-b[i]-d);
                d=0;
            }
        }
        else
        {
            if(a[i]-d<0)
            {
                c.push_back(10+a[i]-d);
                d=1;
            }
            else
            {
                c.push_back(a[i]-d);
                d=0;
            }
        }
    }
    return c;

}
int main()
{
  bool st;
  string s1,s2;
  cin>>s1>>s2;


  vector<int>a,b;

  if(s1.size()<s2.size()||(s1.size()==s2.size()&&s1<s2))
  {
      swap(s1,s2);
      st=true;
  }//这一块很有必要,可以写几个样例试试看:8888 99999;8888 9999等

  for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
  for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');

  vector<int> c=add(a,b);

  while(true)
  {
    if(c.size()==1) break;

    if(c[c.size()-1]==0) c.pop_back();
    else break;
  }

  if(st) cout<<"-";

  for(int i=c.size()-1;i>=0;--i)
    cout<<c[i];

  return 0;  
}

刚开始的时候没有写while(true){…}这个语句,当输入111 111时输出000,这肯定不对,而且输入11 12时输出-01,所以要将后边的0给清一清

QQ截图20210329202600.jpg
y总代码:

#include<iostream>
#include<vector>
using namespace std;

//判断是否有A>=B
bool cmp(vector<int> &A, vector<int> &B)
{
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;--i)
        if(A[i]!=B[i])
            return A[i]>B[i];
    return true;
}

//C=A-B
vector<int> sub(vector<int> &A,vector<int> &B)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size();++i)
    {
        t=A[i]-t;
        if(i<B.size()) t-=B[i];
        C.push_back((t+10)%10);
        if(t<0) t=1;
        else t=0;
    }
    while(C.size()>1&&C.back()==0) C.pop_back();

    return C;
}
int main()
{
    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');

    if(cmp(A,B))
    {
        vector<int> C=sub(A,B);
        for(int i=C.size()-1;i>=0;--i) cout<<C[i];
    }
    else
    {
        vector<int> C=sub(B,A);
        cout<<"-";
        for(int i=C.size()-1;i>=0;--i) cout<<C[i];
    }
    return 0;
}


  • 高精度乘法:
    高精度乘法还是模拟我们列竖式的过程:
    QQ截图20210329142253.jpg

AcWing 793. 高精度乘法

#include<iostream>
#include<vector>
using namespace std;

vector<int> mul(vector<int> &a,vector<int> &b)
{
    vector<int> d[5];
    vector<int> c;
    for(int i=0;i<b.size();++i)
    {
        for(int k=0;k<i;++k)
            d[i].push_back(0);//将尾部进行加零处理

        int t=0;
        for(int j=0;j<a.size();++j)
        {
            d[i].push_back((b[i]*a[j]+t)%10);
            t=(b[i]*a[j]+t)/10;
        }
        if(t) d[i].push_back(t);
    }//将b的每一位与a的每一位相乘

    for(int i=0;i<b.size()-1;++i)
    {
       for(int j=d[i].size();j<d[b.size()-1].size();++j)
            d[i].push_back(0);
    }//将每行尾部进行加零

    int t=0;
    for(int i=0;i<d[b.size()-1].size();++i)
    {
        int sum=0;
        for(int j=0;j<b.size();++j)
        {
            sum+=d[j][i];
        }
        c.push_back((sum+t)%10);
        t=(sum+t)/10;
    }//执行的是相加处理

    if(t) c.push_back(t);

    return c;
}
int main()
{
    string s1,s2;
    vector<int> a,b,c;
    cin>>s1>>s2;

    if(s1=="0"||s2=="0") 
    {
        cout<<0;
        return 0;
    }

    for(int i=s1.size()-1;i>=0;--i) a.push_back(s1[i]-'0');
    for(int i=s2.size()-1;i>=0;--i) b.push_back(s2[i]-'0');


    if(a.size()<b.size()) c=mul(b,a);
    else c=mul(a,b);//习惯上len(a)>len(b)

    for(int i=c.size()-1;i>=0;--i)
        cout<<c[i];


    return 0;
}

其实上边思路自己想复杂了,对于b其实不用挨个拆开运算,完全可以把b看成一个整体
y总

#include<iostream>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &a,int num)
{
    vector<int> c;

    int t=0;
    for(int i=0;i<a.size();++i)
    {
        c.push_back((a[i]*num+t)%10);
        t=(a[i]*num+t)/10;
    }
    if(t) c.push_back(t);

    return c;
}
int main()
{
    string s;
    int num;
    cin>>s>>num;
    vector<int> a;
    if(num==0) 
    {
        cout<<0;
        return 0;
    }
    for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

    vector<int> b;
    b=mul(a,num);

    for(int i=b.size()-1;i>=0;--i) cout<<b[i];
    return 0;
}

习题:

  1. HDU.1047 Integer Inquiry

归根结底还是用到最上边高精度加法的核心代码,只不过是涉及到多组输入

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &a,vector<int> &b)
{
    vector<int> c;
    if(a.size()<b.size())
        swap(a,b);

    int t=0;    
    for(int i=0;i<a.size();++i)
    {
        t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(1);
    return c;
}
int main()
{
    int n; 
    string s;
    vector<int>a,b;
    cin>>n;
    getchar();
    while(n--)
    {
        a.clear();b.clear();//每组都要清空 

        while(cin>>s&&s!="0")
        {
            if(s=="") continue;

            if(a.empty())
                for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

            else
            {
                for(int i=s.size()-1;i>=0;--i) b.push_back(s[i]-'0');
                a=add(a,b);
            }

            b.clear();//输入一组后必须要清空 
        }


        for(int i=a.size()-1;i>=0;--i)
            cout<<a[i];

        cout<<endl;

        if(n) cout<<endl;
    }

    return 0;
}

刚开始思路这样,输入数据测试都对,但提交就是WA
看了看其他通过代码后发现了问题,原来是漏了一组情况,当输入的数是0 0时应该输出0,但我上边的思路是什么也不输出.所以就要特判这种情况

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &a,vector<int> &b)
{
    vector<int> c;
    if(a.size()<b.size())
        swap(a,b);

    int t=0;    
    for(int i=0;i<a.size();++i)
    {
        t+=a[i];
        if(i<b.size()) t+=b[i];
        c.push_back(t%10);
        t/=10;
    }
    if(t) c.push_back(1);
    return c;
}
int main()
{
    int n; 
    string s;
    vector<int>a,b;
    cin>>n;
    getchar();
    while(n--)
    {
        a.clear();b.clear();//每组都要清空 

        int num=0;
        while(cin>>s&&s!="0")
        {
            num++;

            if(s=="") continue;

            if(a.empty())
                for(int i=s.size()-1;i>=0;--i) a.push_back(s[i]-'0');

            else
            {
                for(int i=s.size()-1;i>=0;--i) b.push_back(s[i]-'0');
                a=add(a,b);
            }

            b.clear();//输入一组后必须要清空 
        }

        if(s=="0"&&num==0) cout<<"0";
        else
        {
            for(int i=a.size()-1;i>=0;--i)
                cout<<a[i];
        }

        cout<<endl;

        if(n) cout<<endl;
    }

    return 0;
}

这样就可以了,hdu上的题真有点恶心…

  1. HDU.1042 N!
    百度可知10000!是有 35660 位数




无味
4个月前

POJ 1602.Text Reverse
//直接暴力:

#include<iostream>
using namespace std;
#include<cmath>
int main()
{
    int n;
    cin>>n;
    getchar();

    while(n--)
    {
        string s;

        getline(cin,s);
        for(int first=0,last=0;last<s.size();++last)
        {
            while(s[last]!=' '&&last<s.size())
                last++;


            for(int i=first,j=last-1;i<j;++i,j--)   
                swap(s[i],s[j]);

            first=last+1;
        }       

        cout<<s<<endl;
    }
    return 0; 
 } 

//使用stack:

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n;
    char ch;
    cin>>n;
    getchar();
    while(n--)
    {
        stack<char> s;
        while(true)
        {
            ch=getchar(); //一次读入一个字符
            if(ch==' '||ch=='\n'||ch==EOF)
            {
                while(!s.empty())
                {
                    cout<<s.top(); //输出栈顶
                    s.pop(); //清除栈顶 
                }
                if(ch=='\n'||ch==EOF) break;
                cout<<" ";
            }
            else s.push(ch); // 入栈 
        }
        cout<<endl; 
    }
    return 0;
 } 

POJ 1020.Encoding

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    getchar(); //当先输入一个证书,然后再输入字符串的时候,在输入整数后要用getchar()吸收掉后边的回车 
    while(n--)
    {
        string s;
        getline(cin,s);

        for(int i=0,j=0;j<s.size();++i,++j)
        {
            while(s[j+1]==s[i]&&j<s.size())
                j++;

            if(i==j) cout<<s[i];
            else cout<<j-i+1<<s[i];

            i=j;
        }
        cout<<endl;
    }
    return 0;
 } 


分享 STL

无味
4个月前

动态数组:

基础知识:

习题:

POJ 4841.圆桌问题
刚开始看到这个问题没想到用动态数组怎么去做,于是就直接模拟暴力的:

#include<iostream>
using namespace std;
int main()
{
    string s;
    int n,m;
    while(cin>>n>>m)
    {
        for(int i=1;i<=2*n;++i) 
            s[i]='G'; //先将数组初始化全为好人


        int run=1;//相当于一个指针,一直在围着桌子转    
        for(int i=1;i<=n;++i)
        {
            int sum=0; 
            while(1)
            {
                if(s[run%(2*n+1)]=='G') sum++;//赶走以后位置还在那,sum计数时要跳过已经赶走的 
                if(sum==m) break;//当又跳过m个人以后,这时需要跳出来赶人了 
                run++;
            }
            s[run%(2*n+1)]='B';
        }
        for(int i=1;i<=2*n;++i) 
        {
            cout<<s[i];
            if(i%50==0) cout<<endl;
        }

        cout<<endl<<endl;
    }
    return 0;
}

提交后WA了,但是没发现有什么错误.

下面是用vector通过代码:

#include<iostream>
using namespace std;
#include<vector>
int main()
{
    vector<int> table; //模拟圆桌
    int n, m;
    while (cin >> n >> m)
    {
        for (int i = 0; i < 2 * n; ++i)
            table.push_back(i); //初始化

        int pos = 0; //记录当前位置
        for (int i = 1; i <= n; ++i) //赶走n个人
        {
            pos = (pos + m - 1) % table.size(); //圆桌是个环,取余处理
            table.erase(table.begin() + pos); //赶走坏人,table人数减1
        }
        int j = 0;
        for (int i = 0; i < 2 * n; ++i) //打印预先安排座位
        {
            if (!(i % 50) && i) cout << endl; //50个字母一行
            if (j < table.size() && i == table[j]) //table留下的都是好人
            {
                j++;
                cout << "G";
            }
            else
                cout << "B";
        }
        cout << endl << endl; //留一个空行
    }
    return 0;
}

QQ截图20210318165917.jpg

用list

#include<iostream>
#include<list>
using namespace std;
int main()
{
    list<int>table;
    int n,m;
    while(cin>>n>>m)
    {
        table.clear(); // 清空list容器
        for(int i=0;i<2*n;++i) //将所有人的编号放入list
            table.push_back(i);
        list<int>::iterator it=table.begin();
        while(table.size()>n){ //只要还有不止n个人,就要找一个坏人让其出列
            for(int i=1;i<m;++i){ //报数 
                ++it;
                if(it==table.end())
                    it=table.begin(); 
            } 
            it=table.erase(it); //删除元素后,迭代器失效,要重新让迭代器指向被删元素的后面 

            if(it==table.end())
                it=table.begin(); 
        } 

        it=table.begin();

        for(int i=0;i<2*n;++i)
        {
            if(!(i%50)&&i) cout<<endl;
            if(it!=table.end()&&i==*it){
                it++;
                cout<<"G";
            }   
            else
                cout<<"B";
        } 
        cout<<endl<<endl;
    }
    return 0;
}

QQ截图20210319171554.jpg

AcWing 82. 圆圈中最后剩下的数字
上面那个题和上边圆桌问题是一个问题,本质都是约瑟夫环问题.
所以先用上边直接暴力的思路改一下:

class Solution {
public:
    int lastRemaining(int n, int m){
       bool st[100000];
       for(int i=0;i<n;++i) st[i]=false;

       int run=0;
       for(int i=1;i<n;++i)//n个数,要求最后留下的1个数,所以要循环删除n-1次
       {
           int sum=0;
           while(1)
           {
               if(st[run%n]==false) sum++;
               if(sum==m) break;
               run++;
           }
           st[run%n]=true;//表示被删除
       }
       for(int i=0;i<n;++i)
           if(st[i]==false)
               return i; //将剩下的最后一个元素返回
    }
};

提交后通过了,那上边那个题是因为什么呢!!!!!?

下面用vector来做

class Solution {
public:
    int lastRemaining(int n, int m){
        vector<int> a;

        for(int i=0;i<n;++i) a.push_back(i);

        int pos=0;

        for(int i=1;i<n;++i)
        {
            pos=(pos+m-1)%a.size();
            a.erase(a.begin()+pos);
        }

       return *a.begin(); 

    }
};

直接暴力用时195ms,vector用时26ms

当然这个题还可以用递归来做:

class Solution {
public:
    int lastRemaining(int n, int m){
       if(n==1) return 0;
       return (lastRemaining(n -1,m)+m)%n;
    }
};

这个用时22ms.


AcWing 1455.招聘
这个题的本质也是约瑟夫环问题,第一反应是用vector做:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> table;

    int t;
    cin>>t;

    while(t--)
    {
        table.clear();
        int n,m,a[1010];
        cin>>n>>m;

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

        for(int i=0;i<n;++i) table.push_back(i); //初始化


        int pos=0;

        for(int i=1;i<=n;++i)
        {
            pos=(pos+a[(i-1)%m]-1)%table.size();

            table.erase(table.begin()+pos);
        }

        cout<<*table.begin()<<endl;
    }
    return 0;
}

由于0<T<10,0<n<$10^7$,所以此题时间复杂度为$10^8$,但这个还是没有算上erase.感觉应该就是这个地方有问题此题还是要用递归来做

后来看到list删减的复杂度是常数,就想着用list会不会就可以,一试还是TLE:

#include<iostream>
#include<list>
using namespace std;
int main()
{
        list<int> table;
        int t;
        cin>>t;
        while(t--)
        {
            table.clear(); // 清空list容器
            int n,m,a[1010];
            cin>>n>>m;
            for(int i=0;i<m;++i)
                cin>>a[i];

            for(int i=0;i<n;++i) table.push_back(i); //将编号放入list

            list<int>::iterator it=table.begin();

            for(int j=1;j<n;++j){ //只要还有不止一个人,就要找一个人将其淘汰
                for(int i=1;i<a[(j-1)%m];++i){ //报数 
                    ++it;
                    if(it==table.end())
                        it=table.begin(); 
                } 
                it=table.erase(it); //删除元素后,迭代器失效,要重新让迭代器指向被删元素的后面 

                if(it==table.end())
                    it=table.begin(); 
            } 
            cout<<table.front()<<endl; //front返回第一个元素的引用 
        }
    return 0;   
}

栈:

基础知识:

习题:

POJ 1602.Text Reverse
//直接暴力:

#include<iostream>
using namespace std;
#include<cmath>
int main()
{
    int n;
    cin>>n;
    getchar();

    while(n--)
    {
        string s;

        getline(cin,s);
        for(int first=0,last=0;last<s.size();++last)
        {
            while(s[last]!=' '&&last<s.size())
                last++;


            for(int i=first,j=last-1;i<j;++i,j--)   
                swap(s[i],s[j]);

            first=last+1;
        }       

        cout<<s<<endl;
    }
    return 0; 
 } 

//使用stack:

#include<iostream>
#include<stack>
using namespace std;
int main()
{
    int n;
    char ch;
    cin>>n;
    getchar();
    while(n--)
    {
        stack<char> s;
        while(true)
        {
            ch=getchar(); //一次读入一个字符
            if(ch==' '||ch=='\n'||ch==EOF)
            {
                while(!s.empty())
                {
                    cout<<s.top(); //输出栈顶
                    s.pop(); //清除栈顶 
                }
                if(ch=='\n'||ch==EOF) break;
                cout<<" ";
            }
            else s.push(ch); // 入栈 
        }
        cout<<endl; 
    }
    return 0;
 } 

QQ截图20210318185757.jpg


队列:

基础知识:

习题

POJ 1702.ACboy needs your help again!

#include<iostream>
#include<queue>
#include<stack>
using namespace std;
queue<int> q;
stack<int> st;
void fifo()
{
    if (q.empty()) cout << "None" << endl;
    else
    {
        cout << q.front() << endl;
        q.pop();
    }

}
void filo()
{
    if (st.empty()) cout << "Nosane" << endl;
    else
    {
        cout << st.top() << endl;
        st.pop();
    }
}
int main()
{
    int n, m;
    cin >> m;
    while (m--)
    {
        string s, io;
        int num;
        cin >> n >> s;

        if (s == "FIFO")
        {
            q = queue<int>();
            while (n--)
            {
                cin >> io;
                if (io == "IN")
                {
                    cin >> num;
                    q.push(num);
                }
                else fifo();
            }
        }
        else
        {
            st = stack<int>();
            while (n--)
            {
                cin >> io;
                if (io == "IN")
                {
                    cin >> num;
                    st.push(num);
                }
                else filo();
            }
        }
    }
    return 0;
}

上边还可以优化,再简练些,后边再写吧
下边书上的代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,temp;
    cin>>t;
    while(t--){
        string str,str1;
        queue<int>Q;
        stack<int>S;
        cin>>n>>str;
        for(int i=0;i<n;++i){
            if(str=="FIFO"){ //队列 
                cin>>str1;
                if(str1=="IN"){
                    cin>>temp; Q.push(temp);
                }
                if(str1=="OUT"){
                    if(Q.empty()) cout<<"None"<<endl;
                    else{
                        cout<<Q.front()<<endl;
                        Q.pop(); 
                    }

                }
            }
            else{ //栈 
                cin>>str1;
                if(str1=="IN"){
                    cin>>temp; S.push(temp);
                } 
                if(str1=="OUT"){
                    if(S.empty()) cout<<"None"<<endl;
                    else{
                        cout<<S.top()<<endl;
                        S.pop();
                    }
                }
            }
        }
    }
    return 0;
}



无味
4个月前
  • 一、图的深度优先遍历
  • 二、图的广度优先遍历
  • 三、城市地——图的深度优先遍历(练习)
  • 四、最少转机——图的广度优先遍历(练习)
  • 五、最短路径
    • 只有五行的算法———Floyd-Warshall
    • Dijkstra算法————通过边实现松弛
    • Bellman-Ford————解决负权边
    • Bellman-Ford的队列优化
    • 最短路径算法对比分析

一、图的深度优先遍历

问题引入:

QQ截图20210314112824.jpg
QQ截图20210314112858.jpg
QQ截图20210314141511.jpg
QQ截图20210314141951.jpg

void dfs(int cur) //cur是当前所在的顶点编号
{
    cout << cur << " ";
    sum++; //每访问一个顶点sum就加1
    if (sum == n) return; //所有的顶点都已经访问过则直接退出
    for (i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连
    {
        //判断当前节点cur到顶点i是否有边,并判断顶点i是否访问过
        if (e[cur][i] = 1 && book[i] == 0)
        {
            book[i] = 1; //标记顶点i已经访问过
            dfs(i); //从顶点i再出发继续遍历
        }
    }
    return;
}

上边代码变量中:
cur—存储的是当前正在遍历的顶点;
二维数组e—存储的就是图的边(邻接矩阵);
数组book—用来记录哪些顶点已经访问过;
变量sum—用来记录已经访问过多少个顶点;
变量n—存储的是图的顶点的总个数

完整代码如下:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];
void dfs(int cur) //cur是当前所在的顶点编号
{
    cout << cur << " ";
    sum++; //每访问一个顶点sum就加1
    if (sum == n) return; //所有的顶点都已经访问过则直接退出
    for (int i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连
    {
        //判断当前节点cur到顶点i是否有边,并判断顶点i是否访问过
        if (e[cur][i] == 1 && book[i] == 0)
        {
            book[i] = 1; //标记顶点i已经访问过
            dfs(i); //从顶点i再出发继续遍历
        }
    }
    return;
}
int main()
{
    int m, a, b;
    cin >> n >> m;
    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

    //读入顶点之间的边
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1; //这里是无向图,所以需要将e[b][a]也赋为1
    }

    //从1号城市出发
    book[1] = 1; //标记1号顶点已访问
    dfs(1); //从1号顶点开始遍历

    return 0;
}

QQ截图20210314150815.jpg


二、图的广度优先遍历

问题引入:

QQ截图20210314151011.jpg
QQ截图20210314151248.jpg

完整代码如下:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];

int main()
{
    int n, m, a, b, cur, book[101] = { 0 }, e[101][101];
    int que[1001], head, tail;
    cin >> n >> m;
    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

    //读入顶点之间的边
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1; //这里是无向图,所以需要将e[b][a]也赋为1
    }

    //队列初始化
    head = 1;
    tail = 1;

    //从1号顶点出发,将1号顶点加入队列
    que[tail] = 1;
    tail++;
    book[1] = 1; //标记1号顶点已访问

    //当队列不为空的时候循环
    while (head < tail)
    {
        cur = que[head]; //当前正在访问的顶点编号
        for (int i = 1; i <= n; ++i) //从1~n依次尝试
        {
            //判断从顶点cur到顶点i是否有边,并判断顶点i是否已经访问过
            if (e[cur][i] == 1 && book[i] == 0)
            {
                //如果从顶点cur到顶点i有边,并且顶点i没有被访问过,则将顶点i入队
                que[tail] = i;
                tail++;
                book[i] = 1; //标记顶点i已访问
            }
            //如果tail大于n,则表明所有顶点都已经被访问过
            if (tail > n)
                break;
        }
        head++; // 注意这个地方,千万不要忘记当一个顶点扩展结束后,head++,然后才能继续往下扩展

    }

    for (int i = 1; i < tail; ++i)
        cout << que[i]<<" ";

    return 0;
}

QQ截图20210314192128.jpg


使用深度优先搜索和广度优先搜索来遍历图都将会得到这个图的生成树。那么什么叫做生成树,生成树又有哪些作用呢?
这个后边再讨论,下面我们先来看看图有什么作用,它究竞能解决什么实际问题。


三、城市地——图的深度优先遍历(练习)

问题引入:

QQ截图20210314154226.jpg
QQ截图20210314154411.jpg
QQ截图20210314154451.jpg

思路:

QQ截图20210314163159.jpg
QQ截图20210314163626.jpg

代码如下:

自己根据上边思路改的:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];
int dmin = 999999999;//表示最短长度
int num = 0; //当前走了多少米了
void dfs(int cur) //cur是当前所在的顶点编号
{

    sum++; //每访问一个顶点sum就加1

    if (cur == 5)
        if (num < dmin)
        {
            dmin = num;
            return;
        }


    if (sum == n) return; //所有的顶点都已经访问过则直接退出
    for (int i = 1; i <= n; ++i) //从1号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连
    {
        //判断当前节点cur到顶点i是否有边,并判断顶点i是否访问过
        if (e[cur][i] > 0 && e[cur][i] < 999999999 && book[i] == 0)
        {
            book[i] = 1; //标记顶点i已经访问过
            num += e[cur][i];
            dfs(i); //从顶点i再出发继续遍历
            num -= e[cur][i];
            book[i] = 0; //上边这两行一定不能少
        }
    }
    return;
}
int main()
{
    int m, a, b;
    cin >> n >> m;
    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

    //读入顶点之间的边
    for (int i = 1; i <= m; ++i)
    {
        int dis;
        cin >> a >> b >> dis;
        e[a][b] = dis;

    }

    //从1号城市出发
    book[1] = 1; //标记1号顶点已访问
    dfs(1); //从1号顶点开始遍历

    cout << dmin;

    return 0;
}

答案给出的代码:

#include<iostream>
using namespace std;
int dmin = 999999999, book[101], n, e[101][101];

//cure是当前所在城市的编号,dis是当前已经走过的路程
void dfs(int cur, int dis)
{
    //如果当前走过的路程已经大于当之前找到的最短路,则没有必要再往下尝试了,立即返回
    if (dis > dmin) return;
    if (cur == n) //判断是否到达了目标城市
    {
        if (dis < dmin) dmin = dis; //更新最小值
        return;
    }

    for (int j = 1; j <= n; ++j) //从1号城市到n号城市依次尝试
    {
        ////判断当前城市cur到城市j是否有路,并判断城市j是否在已走过的路径中
        if (e[cur][j] != 99999999 && book[j] == 0)
        {
            book[j] = 1; //标记城市j已经在路径中
            dfs(j, dis + e[cur][j]); //从城市j再出发,继续寻找目标城市
            book[j] = 0; //之前一步探索完毕后,取消对城市j的标记
        }
    }
    return;
}
int main()
{
    int m, a, b, c;
    cin >> n >> m;
    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

    //读入顶点之间的边
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b >> c;
        e[a][b] = c;

    }

    //从1号城市出发
    book[1] = 1; //标记1号顶点已访问
    dfs(1, 0); //从1号顶点开始遍历

    cout << dmin;

    return 0;
}

两个代码最大的一个不同就是它把表示走到cur的距离的变量放到函数参数的地方了,这样回溯时就不用再进行减掉了,这点以后要学会!!!!

QQ截图20210314182314.jpg

注意:

QQ截图20210314182756.jpg
QQ截图20210314182929.jpg
QQ截图20210314182938.jpg

我们使用了二维数组来存储这个图(顶点和边的关系),这种存储方法叫做图的邻接矩阵表示法。
本节的解法中存储图的方法还有很多种,比如邻接表等,我们后面再做详细讲解。
此外求图上两点之间的最短路径,除了使用深度优先搜索以外,还可以使用广度优先搜索、Floyd、Bellman-Ford、Dijkstra等

四、最少转机——图的广度优先遍历(练习)

问题引入:

QQ截图20210314184149.jpg
QQ截图20210314184210.jpg

思路:

QQ截图20210314202421.jpg

代码如下:

自己思路代码:

#include<iostream>
using namespace std;
int book[101], sum, n, e[101][101];

int main()
{
    int n, m, a, x, y, b, cur, book[101] = { 0 }, e[101][101];
    int que[1001], head, tail;
    cin >> n >> m >> x >> y;
    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999; //我们在这里假设999999999为正无穷

    //读入顶点之间的边
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        e[a][b] = 1;
        e[b][a] = 1; //这里是无向图,所以需要将e[b][a]也赋为1
    }

    //队列初始化
    head = 1;
    tail = 1;

    //从x号顶点出发,将x号顶点加入队列
    que[tail] = x;
    tail++;
    book[x] = 1; //标记x号顶点已访问


    int min=0;//表示最少转机次数 
    //当队列不为空的时候循环
    while (head < tail)
    {

        if(book[y]==1) break;//当y城市进入队列时,这时结束就行了

        min++;

        cur = que[head]; //当前正在访问的顶点编号
        for (int i = 1; i <= n; ++i) //从1~n依次尝试
        {
            //判断从顶点cur到顶点i是否有边,并判断顶点i是否已经访问过
            if (e[cur][i] == 1 && book[i] == 0)
            {
                //如果从顶点cur到顶点i有边,并且顶点i没有被访问过,则将顶点i入队
                que[tail] = i;
                tail++;
                book[i] = 1; //标记顶点i已访问
            }
            //如果tail大于n,则表明所有顶点都已经被访问过
            if(book[y]) break;//当y城市进入队列时,这时结束就行了 

            if (tail > n)
                break;
        }
        head++; // 注意这个地方,千万不要忘记当一个顶点扩展结束后,head++,然后才能继续往下扩展

    }

    cout<<min<<endl;

    return 0;
}

QQ截图20210314195441.jpg
但是运行后答案一直是3
原因是什么呢?

当while运行第一次的时候,cur=1,min=1,将2,3,两个入队列;
当while运行第二次的时候,cur=2,min=2,将4入队列;
当while运行第三次的时候,cur=3,min=3,将5入队列;
循环结束,输出min=3.

想了一会没想出要怎么解决

答案给出的代码:

#include<iostream>
using namespace std;
struct note
{
    int x; //城市编号
    int s; //转机次数
};

int main()
{
    struct note que[2501];
    int e[51][51] = { 0 }, book[51] = { 0 };
    int head, tail;
    int n, m, a, b, cur, start, end, flag = 0;
    cin >> n >> m >> start >> end;

    //初始化二维矩阵
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999;

    //读入城市之间的航班
    for (int i = 1; i <= m; ++i)
    {
        cin >> a >> b;
        //注意这里是无向图
        e[a][b] = 1;
        e[a][b] = 1;
    }

    //队列初始化
    head = 1;
    tail = 1;

    //从start号城市出发,将start号城市加入队列
    que[tail].x = start;
    que[tail].s = 0;
    tail++;
    book[1] = start; //标记start号城市已在队列中

    //当队列不为空的时候循环
    while (head < tail)
    {
        cur = que[head].x; //当前队列中首城市的编号
        for (int j = 1; j <= n; ++j) //从1~n依次尝试
        {
            if (e[cur][j] != 99999999 && book[j] == 0)
            {
                //如果从城市cur到城市j有航班并且城市j不在队列中,则将j号城市入队
                que[tail].x = j;
                que[tail].s = que[head].s + 1; //转机次数+1
                tail++;
                //标记城市j己经在队列中
                book[j]=1;
            }
            //如果到达目标城市,停止扩展,任务结束,退出循环
            if (que[tail].x == end)
            {
                //注意下面两句话的位置千万不要写颠倒了
                flag = 1;
                break;
            }
        }
        if (flag)
            break;
        head++; //注意这地方,千万不要忘记当一个点扩展结束后,head++才能继续扩展
    }

    //打印队列中末尾最后一个(目标城市)的转机次数
    //注意tai1是指向队列队尾(即最后一位)的下一个位置,所以这需要 - 1
    cout << que[tail-1].s;

    return 0;
}

当然也可以使用深度优先搜索解决,但是这里用广度优先搜索会更快

**广度优先搜索更加适用于所有边的权值相同的情况**


五、最短路径

5.1 只有五行的算法———Floyd-Warshall

问题引入:

QQ截图20210314203842.jpg

QQ截图20210314203929.jpg

思路:

QQ截图20210314204059.jpg
QQ截图20210314205919.jpg
QQ截图20210315141408.jpg
QQ截图20210315141423.jpg
QQ截图20210315141444.jpg
QQ截图20210315141505.jpg
QQ截图20210315141551.jpg

这段代码的基本思想就是:最开始只允许经过1号顶点进行中转,接下来只允许经过1和2号顶点进行中转……允许经过1~n号所有顶点进行中转,求任意两点之间的最短路程;
用一句话概括就是:从i号顶点到j号顶点只经过前k号点的最短路程。其实这是一种“动态规划”的思想;

代码:

#include<iostream>
using namespace std;
int main()
{
    int e[10][10], n, m, t1, t2, t3;
    int inf = 99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m,n表示顶点个数,m表示边的条数
    cin >> n >> m;

    //初始化
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = inf;

    //读入边
    for (int i = 1; i <= m; ++i)
    {
        cin >> t1 >> t2 >> t3;
        e[t1][t2] = t3;
    }

    //Floyd-Warshall算法核心语句
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (e[i][j] > e[i][k] + e[k][j])
                    e[i][j] = e[i][k] + e[k][j];

    //输出最终结果
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            cout << e[i][j]<<" ";
        cout << endl;
    }

    return 0;
}

QQ截图20210315143253.jpg

总结:

  • 通过这种方法我们可以求出任意两个点之间的最短路径。它的时间复杂度是O($N^3$);
  • 如果时间复杂度要求不高,使用Floyd-Warshall来求指定两点之间的最短路径或者指定一个点到其余各个顶点的最短路径也是可行的。当然也有更快的算法(例如:Dijkstra算法);
  • Floyd-Warshall算法不能解决带有“负权回路”(或者叫“负权环”)的图;
    QQ截图20210315144224.jpg

5.2 Dijkstra算法—通过边实现松弛

问题引入:

QQ截图20210315144456.jpg

思路:

QQ截图20210315144559.jpg
QQ截图20210315145213.jpg
QQ截图20210315150527.jpg
QQ截图20210315150659.jpg

总结一下刚才的算法,算法的基本思想是:每次找到离源点(上面例子的源点就是1号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。
基本步骤如下:

  • 将所有的顶点分为两部分:已知最短路程的顶点集合Р和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book数组来记录哪些点在集合P中。例如对于某个顶点i,如果book[i]为1则表示这个顶点在集合P中,如果book[i]为0则表示这个顶点在集合Q中。
  • 设置源点s到自己的最短路径为О即dis[s]=0。若存在有源点能直接到达的顶点i,则把dis[]设为e[s][i]。同时把所有其他(源点不能直接到达的)顶点的最短路径设为正无穷。
  • 在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边,对每一条边进行松弛操作。例如存在一条从u到v的边,那么可以通过将边u→v添加到尾部来拓展一条从s到v的路径,这条路径的长度是 dis[u]+e[u][v]。如果这个值比目前已知的 dis[v]的值要小,我们可以用新值来替代当前dis[v]中的值。
  • 重复第3步,如果集合Q为空,算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

完整的Dijkstra算法代码如下:

#include<iostream>
using namespace std;
int main()
{
    int e[10][10], dis[10], book[10], u, n, m, t1, t2, t3, min;
    int inf = 99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
    //读入n和m,n表示顶点个数,m表示边的条数
    cin >> n >> m;

    //初始化
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i == j) e[i][j] = 0;
            else e[i][j] = inf;

    //读入边
    for (int i = 1; i <= m; ++i)
    {
        cin >> t1 >> t2 >> t3;
        e[t1][t2] = t3;
    }

    //初始化dis数组,这里是1号顶点到其余各个顶点的初始路程
    for (int i = 1; i <= n; ++i)
        dis[i] = e[1][i];

    //book数组初始化
    for (int i = 1; i <= n; ++i)
        book[i] = 0;
    book[1] = 1;

    //Dijkstra算法核心语句
    for (int i = 1; i <= n - 1; ++i)
    {
        //找到离1号顶点最近的顶点
        min = inf;
        for (int j = 1; j <= n; ++j)
            if (book[j] == 0 && dis[j] < min)
            {
                min = dis[j];
                u = j;
            }
        book[u] = 1;
        for (int v = 1; v <= n; ++v)
            if (e[u][v] < inf)
                if (dis[v] > dis[u] + e[u][v])
                    dis[v] = dis[u] + e[u][v];

    }

    //输出最终结果
    for (int i = 1; i <= n; ++i)
        cout << dis[i] << " ";
    return 0;
}

QQ截图20210316103827.jpg

通过上面的代码我们可以看出,这个算法的时间复杂度是O($N^2$)。其中每次找到离1号顶点最近的顶点的时间复杂度是O(N),这里我们可以用“堆”来优化,使得这一部分的时间复杂度降低到O(logN)。

优化:

另外对于边数M少于$N^2$的稀疏图来说(我们把M远小于$N^2$的图称为稀疏图,而M相对较大的图称为稠密图),我们可以用邻接表(这是个神马东西?不要着急,待会再仔细讲解)来代替邻接矩阵,使得整个时间复杂度优化到O(M+N)logN。请注意!在最坏的情况下M就是$N^2$,这样的话(M+N)logN要比$N^2$还要大。但是大多数情况下并不会有那么多边,因此(M+N)logN要比$N^2$小很多。

下面来讲一下邻接表:

如何用邻接表来存储一个图呢?先上数据:

4 5
1 4 9
2 4 6
1 2 5
4 3 8
1 3 7

QQ截图20210316104759.jpg

现在用邻接表来存储这个图,先给出代码如下:

int n, m, i;
//u、v和w的数组大小要根据实际情况来设置,要比m的最大值要大1
int u[6], v[6], w[6];
//first和next的数组大小要根据实际情况来设置,要比n的最大值要大1
int first[5], next[5];
cin >> n >> m;
//初始化first数组下标1~n的值为-1,表示1~n顶点暂时都没有边
for (int i = 1; i <= n; ++i)
    first[i] = 1;
for (int i = 1; i <= m; ++i)
{
    cin >> u[i] >> v[i] >> w[i]; // 读入每一条边
    //下面两句是关键了
    next[i] = first[u[i]];
    first[u[i]] = i;
}
  • 这里为大家介绍的是使用数组来实现邻接表,而没有使用真正的指针链表,这是一种在实际应用中非常容易实现的方法.
  • 这种方法为每个顶点i (i从1~n)都设置了一个链表,里面保存了从顶点i出发的所有的边(这里用first和next数组来实现)
  • 首先我们需要为每一条边进行1~m的编号。用u、v和w三个数组来记录每条边的信息,即u[i]、v[i]和w[i]表示第i条边是从第u[i]号顶点到v[i]号顶点(u[i]→v[i]),且权值为w[i]。
  • first数组的1~n号单元格分别用来存储1~n号顶点的第一条边的编号,初始的时候因为没有边加入所以都是-1。即first[u[i]保存顶点u[i]的第一条边的编号,next[i]存储“编号为i的边”的“下一条边”的编号。

QQ截图20210316110138.jpg

总结:



活动打卡代码 AcWing 16. 替换空格

无味
4个月前
class Solution {
public:
    string replaceSpaces(string &str) {
        string s;
        for(int i=0;i<str.size();++i)
            if(str[i]!=' ') s+=str[i];
            else s+="%20";

        return s;
    }
};


活动打卡代码 AcWing 21. 斐波那契数列

无味
4个月前
class Solution {
public:
    int Fibonacci(int n) {
        int num[40]={0,1};

        for(int i=2;i<=n;++i)
            num[i]=num[i-1]+num[i-2];

        return num[n];
    }
};

class Solution {
public:
    int Fibonacci(int n) {
      int a=0,b=1;
      while(n--)
      {
          int c=a+b;
          a=b,b=c;
      }
    return a;
    }
};

//递归:
class Solution {
public:
    int Fibonacci(int n) {
      if(n<=1) return n;
      return Fibonacci(n-1)+Fibonacci(n-2);

    }
};