头像

cyuyu




在线 


最近来访(13)
用户头像
日川纲坂
用户头像
有的人八岁刷题八十岁才放弃
用户头像
逍遥生
用户头像
HiHello
用户头像
levelna
用户头像
眼泪终究是咸的
用户头像
Unique_80
用户头像
坠落的余晖
用户头像
RyanMoriarty
用户头像
子书寄南
用户头像
siyufeng
用户头像
等雨停
用户头像
少年与梦

分享 杨辉三角

cyuyu
1天前
思路在于:先将杨辉三角列成n行n列的矩阵,该矩阵满足的特点是
y[i][j]=y[i-1][j]+y[i][j-1];
在按照格式进行输出,格式输出这里需要列一下规律,单凭空想是绝对不行的!!!
#include<iostream>
using namespace std;
const int N=100;
int y[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        y[i][0]=1;
        y[0][i]=1;
    }

    for(int i=1;i<=n-2;i++){
        for(int j=1;j<=n-2;j++){
        y[i][j]=y[i-1][j]+y[i][j-1];
    }
    }
    for(int i=0;i<n;i++){
      for(int l=n-1-i;l>=0;l--){
            cout<<' ';
        }
        for(int j=0;j<=i;j++){
            cout<<y[i-j][j]<<' ';


        }
        cout<<endl;

    }

    return 0;
}



cyuyu
3天前

扩展欧几里得算法:

裴蜀定理:

对于a,b总是存在非零整数x,y使得 ax + by = (a , b)
证明:
因为a,b两者的最大公约数是(a,b)=d的,所以ax+by的最大公约数也是d,所以会存在x,y使得两者相等

代码:

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y){
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else{

        int d= exgcd(b,a%b,y,x);  //注意这里****
         y=y-a/b*x;              //*************,X,y这样的变换关系只进行一次,所以
                                 //不可以写为y=y-a/b*x; 
                                 //     return exgcd(b,a%b,y,x);
        return d;
    }
}
int main(){
    int n;
    cin>>n;
    int x,y,a,b;
    while(n--){
        cin>>a>>b;
        int c=exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }

    return 0;
}



cyuyu
3天前

筛法求欧拉函数

证明:

因为欧拉函数的求解只与质数的值有关而与质数的个数无关
所以1:当i%primes[j]!=0时,即primes[j]不是i的质数
所以oula[primes[j]*i]=oula[i]*(primes[j]-1)  //一个质数的欧拉函数是其数值减一
    2:当i%priems[j]==0时,即primes[j]是i的最小质数
即 1-1/priems[j]已经再oula[i]中出现过了,所以就不用再×了,所以
oula[primes[j]*i]=oula[i]*primes[j];

代码:

#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int st[N];
int primes[N];
int oula[N];
ll ular(int n){
    int k=0;
    oula[1]=1;
    for(int i=2;i<=n;i++){

        if(st[i]==0){
            primes[k++]=i;
            oula[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0){
                oula[i*primes[j]]=oula[i]*primes[j];
                break;
            }
            oula[i*primes[j]]=oula[i]*(primes[j]-1);
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++){
        res+=oula[i];
    }
    return res;
}
int main(){
    int n;
    cin>>n;
    cout<<ular(n);

    return 0;
}

欧拉定理

欧拉.png



分享 约数

cyuyu
5天前

1.求解一个数的约数

试除法:
时间复杂度为O(sqrt(n))

//试除法求约数
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>get_yueshu(int x){
    vector<int>res;
    for(int i=1;i<=x/i;i++){
        if(x%i==0){           //只枚举小的那个约数
            res.push_back(i);
            if(i!=x/i){       //如果大的约数和小的约数不一样,就存入数组中,否则不存入
                res.push_back(x/i);
            }
        }
    }
    sort(res.begin(),res.end());
    return res;
}
int main(){
    int n;

    cin>>n;
    int x;
    while(n--){
        cin>>x;
        vector<int>T=get_yueshu(x);
        for(auto t:T){
            cout<<t<<' ';
        }
        cout<<endl;
    }
    return 0;
}

2.求解约数的个数
X=p1^a1p2^a2…………pk^ak;
对于每一个pi^ai都有:
pi^0、pi^1…………pi^ai个质因子,所以质因子的个数ans=(0+1+2……+ai)=ai+1
所以X的约数有(a1+1)
(a2+1)…………(ak+1)个
其实就是排列组合,看这些质因子有多少中排列情况
举例:
2
18=36,2=2^1, 18=2^13^2
所以36=2^2
3^2;
36的约数为 (2+1)*(2+1)=9,即 1 2 3 4 6 9 12 18 36

代码:

对于该题使用了没有使用过的map,详情: [map函数使用方法](https://blog.csdn.net/weixin_43828245/article/details/90214494) 
函数中不能有重复的键,但是可以有相同的键值,并且在该题目的插入中,因为质因子i不确定
所以选择primes[i]++的方式,每存入一个键为i,键值就++
#include<iostream>
#include<map>
using namespace std;
long long res=1;
const int N=1e9+7;
map<int,int>primes;

int main(){

    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            if(x%i==0){
                int k=0;
                while(x%i==0){
                    x=x/i;
                    primes[i]++;
                //primes.insert(pair<int,int>(i,++k));
                    }
            }
        }
        if(x>1)
        primes[x]++;
    }
    for(map<int,int>::iterator t=primes.begin();t!=primes.end();t++){
        res=res*(t->second+1)%N;
    }
    cout<<res;
    return 0;
}

3.求解一个数的约数和
在这里学到了用 auto去遍历map函数十分的简便
另外一个就是秦九韶算法,真的绝了
关于这个算法在22年寒假每一一题的笨拙的手指中听y总讲过,那会就感觉很精妙
但是没有深入去研究,今天在听约数和的时候再次惊讶秦九韶算法的精妙
这里:借用大佬的讲解
如果 N=p1^c1∗p2^c2∗…∗pk^ckN=p1^c1∗p2^c2∗…∗pk^ck
约数个数:(c1+1)∗(c2+1)∗…∗(ck+1)(c1+1)∗(c2+1)∗…∗(ck+1)
约数之和: (p1^0+p1^1+…+p1^c1)∗…∗(pk^0+pk^1+…+pk^ck)

算约数和的话需要求解出每一个质因子从其指数为0一直到他在x中出现的最大次数的和
然后各个相乘。
我的思路是利用pow()函数,代码如下:

 /*for(map<int,int>::iterator t=primes.begin();t!=primes.end();t++){
        int f=t->first;
        long long res=0;
        for(int i=0;i<=t->second;i++){
            res+=pow(f,i)%N;     //N=1e9+7

        }
        sum=sum*res%N;
    }
    cout<<sum;
    */

然后数小的时候结果正确,但是当数大的时候就会出现问题,原因在于
1.pow()函数的返回值是double类型而非int类型
2.他这个mod 1e9+10这里在式子中会出现问题所以不管怎样变化他就是有问题
通过看别的伙伴的思路,他们提出使用等比数列求和的方法也出现了问题
因为不知道是先mod 1e9+10还是先加再mod,这样精度啥的会出现问题,
然后看视频讲解时,y总用了秦九韶算法解决这个问题,简直目瞪口呆
t=t∗p+1
t=1
t=p+1
t=p2+p+1
……
t=pb+pb−1+…+1
太神奇了
秦.jpg
还有b进制转化为十进制的题目
代码:

int get(string s,int b){
//b进制函数转化为十进制
    int x=0;
    int i=0;
   /* for(auto c: s){
         x=x*b+c-'0';
    }*/
    while(i<s.size()){
        x=x*b+s[i]-'0';
        i++;

    }
    return x;
}

QQ图片20220112205757.jpg
就是一串式子进行化简成这个样子,找规律确定各个值
好了上代码吧!

#include<iostream>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e9+7;
map<int,int>primes;
int main(){

    int n;
    cin>>n;
    while(n--){
        int x;
        cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x=x/i;
                primes[i]++;
            }
        }
        if(x>1){
            primes[x]++;
        }
    }

    long long res=1;
    for(auto t:primes){        //用auto遍历,convenience
        int p=t.first;
        int d=t.second;
        long long sum=1;
        while(d--){
            sum=(sum*p+1)%N;

        }
        res=res*sum%N;
    }
    cout<<res;
    return 0;
}

4.欧几里得求最大公约数

直呼精辟啊!
证明如下:
有数字a,b;那么a、b的最大公约数等价于(b,a mod b),注意顺序,就是大的那一方在第一个数的位置
小的那一方在第二个数的位置,如此循环往复直至第二个数为0,此时结束,第一个数也就是两者的最大公约数
为什么上边两个式子是等价的呢,因为
假设d是a,b的最大公约数,d|a, d|b ,那么d|ax+by
a mod b=a-kb,k是a/b下取整,成立
从左往右推:因为d|a, d|b,所以d|a-k
b
从右往左推:因为d|a-kb ,d|b 现证明:d|a :
d|a-k
b +k*b = d|a 成立

代码

#include<iostream>
using namespace std;
int gcd(int a,int b){
    if(b!=0){
        return gcd(b,a%b);
    }
    else{
        return a;
    }
}
int main(){

    int n;
    cin>>n;
    int a,b;
    while(n--){
        cin>>b>>a;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}



cyuyu
6天前
  1. 试除法判断质数
 //首先,质数是大于等于2的数,1和小于1的数不是质数也不是合数
 #include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int flag;
    while(n--){
        int x;
        cin>>x;
        flag=0;
        if(x==1){
            cout<<"No"<<endl;
        }
        else{
            for(int i=2;i<=x/i;i++){   //注意一下这个地方:
                                    // 因为约数都是成双成对出现的比如12的约数:3和4,d 与 x/d 所以可以不用枚举到X,取一对中
                                    //较小的那个约数,即d<=x/d,所以 d=sqrt(x)
                                    //但是写的时候不要写成i<sqrt(x),这样每次判别会花费很多时间,也不要写成i*i<=x,这样可能
                                    //会出现i*i溢出的情况,最好是写成代码中的形式
                if(x%i==0){
                    cout<<"No"<<endl;
                    flag=1;
                    break;
                }
            }
            if(flag==0)
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}
  1. 试除法分解质因数
#include<iostream>
using namespace std;
void divide(int x){
    //为什么说i一定不可能时合数呢,证明如下:
    //假设i是一个合数,那么他一定能分解为质因子,质因子一定在2~i-1内但是这以内的数字在之前已经被除尽了,
    //比如12的质因数是2和3,那么就一定不可能找到6,因为6的质因数是2和3,在这之前已经被除尽了,也就是i一定被
    //x除过了所以i一定不是合数
    for(int i=2;i<=x/i;i++){ //小于sqrt(n)的质因子
    //n中只包含一个大于sqrt(n)的质因子,因为如果有两个大于sqrt(n)的质因子,那么两这相乘一定大于n这肯定是不成立的
        if(x%i==0){
             int c=0;
            while(x%i==0){
                x/=i;
                c++;
            }
            cout<<i <<' '<<c<<endl;
        }
    }
    if(x!=1){                //这里进行特判如果x有一个大于sqrt(n)的质因子,将他列出
        cout<<x<<' '<<1<<endl;  //这个地方我自己没想到
    }
    cout<<endl;
}
int main(){
    int n;
    cin>>n;
    int x;
    for(int i=0;i<n;i++){
        cin>>x;
        divide(x);
    }
    return 0;
}
  1. 朴素筛法
i从2开始升序遍历,去掉i的所有小于等于n的倍数,比如:
5以内:
2 3 4 5
2的倍数为4,去掉4,
3的倍数为6,忽略
4的倍数为8,忽略
5的倍数为10,忽略
所以n=5内的质数为2,3,5
所以时间复杂度为n(1/2+1/3+1/4+......+1/n)当n趋于无穷大时,是无穷级数,
时间复杂度为log(nlogn)
#include<iostream>
using namespace std;
const int N=1e6+10;
bool st[N];//没有被筛掉的数也就是质数集合
int primes[N];//存储质数
int main(){
    int n;
    cin>>n;
    int c=0;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[c++]=i;

        }
          for(int j=i+i;j<=n;j+=i){
            st[j]=true;
        }

    }
    cout<<c;

    return 0;
}
  1. 埃氏筛法
i从2开始遍历到n的所有质数,然后去掉这些质数的倍数
比如:n=7
2 3 4 5 6 7
从2 开始,筛去4,6
3,筛取6
此时4筛取,跳过
5的倍数10,忽略
6筛掉
7的倍数为14,忽略,
所以质数为2,3,5,7
这种方法与朴素筛法的区别为,朴素筛法是是对每一个元素的倍数进行晒除,
埃氏筛法是将质数的倍数进行筛除,n内有n/lnn个质数,时间复杂度为nloglogn
  1. 线性筛法 借鉴的大佬的解答
若 n≈106n≈106,线性筛和埃氏筛的时间效率差不多,若 n≈107n≈107,线性筛会比埃氏筛快了大概一倍。

核心:1∼n1∼n 内的合数 pp 只会被其最小质因子筛掉。(算数基本定理)

原理:1∼n1∼n 之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,然后每一个数都只有一个最小质因子,因此每个数都只会被筛一次,因此线性筛法是线性的。

枚举到 ii 的最小质因子的时候就会停下来,即 if(i % primes[j] == 0) break;

当 i % primes[j] != 0 时,primes[j] 一定小于 ii 的最小质因子,primes[j] 一定是 primes[j]*i 的最小质因子。
当 i % primes[j] == 0 时,primes[j] 一定是 ii 的最小质因子,而 primes[j] 又是 primes[j] 的最小质因子,因此 primes[j] 是 primes[j]*i 的最小质因子。

void get_primes(){
    //外层从2~n迭代,因为这毕竟算的是1~n中质数的个数,而不是某个数是不是质数的判定
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就
        //没啥意义了
            st[primes[j]*i]=true;//用最小质因子去筛合数

            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子,那么只可能是此时的primes[j]<i的
            //最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
            //prime[j],之后接着用st[primes[j+1]*i]=true去筛合数时,就不是用最小质因子去更新了,因为i有最小
            //质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子,此时就应该
            //退出循环,避免之后重复进行筛选。
            if(i%primes[j]==0) break;
        }
    }

}





cyuyu
6天前
本题折磨了本菜鸡一中午,菜鸡思路是列出所有可能出现的情况,有以下几种:


1.  ————————————————             
       ——————————————————
       1 3
       2 4


2.        ——————————————         
    ——————————————————————
    1 3
    0 4


3.     —————————————————————         —————————   
     1 3
     4 5


4.   1 3
     3 6


5.           ——————————————————————            
                 ————————————
                 0  3
                 1  2

会有两区间的这五种关系,其中除了第三种情况不能合并外,其余均可以,
我的思路是将这么几种情况依据t[i].second与t[i+1].first等之间的关系
列出这么几种情况进行判别,这样当然很麻烦而且不停的出bug,这也许就是
菜鸡和大佬之间的区别,不懂得怎么样将这些情况进行简化!!!呜呜
继续努力吧!

以下是我遇到的问题:
对于c的处理很是头疼,原本我写的是
for(int i=0;i<n;){
    int q=t[i].second;
    while(q>t[i+1].first&&i+1>n){
        q=max(t[i+1].second,q);
        i++;
    }
    c++;



* int q=t[i].second;

    >>>>>
}
这样我遇到了很多问题,第一这样写会不会丢到某些区间,并且
如果一个集合只有一个区间时,这样c正确,但是如果两个区间,
并且不能合并就会出现问题当然当n>2时也存在各种各样的
问题,进行特判也不好整
另外就是while()循环的问题一直不能合并退出该循环,我下一个区间是
1 2   2 3    5 6
中的5 6的话跟c 间的关系也不好弄,问题在这里纠结了好久好久,我是个
废物。
并且我还惊奇的发现在*语句这里我再次int,q的值会出现问题,如果去掉
int 就没有问题,我不明白这里,?先打个小问号,等我成长这在思考

感悟:
_**先进行排序!!!!!**_

这道题应该把while循环改为if语句,将各个区间联系起来,其实两者的时间复杂度是一样的,
能用if就别用while 了,可以少考虑一些问题

这里c的起始值是1,而我原先设的c=0,如果c=0,会出现一些问题,需要特判,
如果c=1,会很有逻辑性,反正现在的这个代码有许多地方我都不能正确的进行思考
思维逻辑不能连贯,缜密,在谁和谁比较,什么情况下c++上几乎没有思考,还是
思维逻辑的问题!!!

方法一: 贪心处理,对左端点进行排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct P{
    int l,r;
    bool operator<(const P&T){
        return r<T.r;
    }
}t[N];
int n;
int select(){

    sort(t,t+n);
    //对第二个元素进行升序
    int q=t[n-1].l;
    /*
    1   2    _____
    2   4         __________
    3   4             ______
    4   5                   ______*
    */
    int c=1;
    vector<pii> y;
    for(int i=1;i<n;i++){
        if(t[i].first<=d){
            d=max(d,t[i].second);

        }
        else{
            c++;
            y.push_back({q,d});
            d=t[i].second;
            q=t[i].first;

        }
    }
    if(d==t[0].second){                      //如果只有一个区间
        y.push_back({q,d});

    }                                         //这部分内容是将合并后区间的值赋给y数组,输出
    if(d!=t[0].second){
        y.push_back({q,d});                   //最后一个区间
    }
    for(auto seg:y){
        cout<<seg.first<<' '<<seg.second<<endl;
    }
    return c;
}
int main(){

    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t[i].l>>t[i].r;
    }
    cout<<select();
    return 0;
}

方法二: 贪心处理,对右端点进行排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
pair<int,int>t[N];
int n;
int select(){
    sort(t,t+n);//对第一个元素进行升序排序
    int q=t[0].first;
    int d=t[0].second;
    int c=1;
    //假设t[0]为一个独立不能合并的区间
    for(int i=1;i<n;i++){
        if(t[i].first<=d){
            d=max(d,t[i].second);
        }
        else{
            c++;
            //没有区间进行合并第二个区间开始做一个不能进行合并的独立区间
            d=t[i].second;
        }
    }
    return c;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>t[i].first>>t[i].second;
    }
    cout<<select();
    return 0;
}

方法三: y总的合并区间模板

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int N=1e5+10;
int n;
typedef pair<int ,int>pii;
vector <pii>segs;
void merge(vector<pii>&segs){
    vector<pii>res;
    sort(segs.begin(),segs.end());
    //先将所有区间进行排序
    //优先以左端点排序在以右端点进行排序
    int st=-2e9,ed=-2e9;
    //设置边界
    for(auto seg:segs){
        if(ed<seg.first){            //如果当前维护区间和枚举区间没有交集

            if(st!=-2e9)
            res.push_back({st,ed});//如果当前维护的区间不是初始区间
                                  // 将维护的区间存入到res中

                st=seg.first;     //更新st,ed;
                ed=seg.second;

        }
         else{
                //                  如果当前维护区间和枚举区间有交集
                ed=max(ed,seg.second);

            }

    }
     if(st!=-2e9){                   //如果区间不为空,将最后一个区间存入到res中
                res.push_back({st,ed});
            }
            segs=res;

}
int main(){

    cin>>n;
    int l,r;
    for(int i=0;i<n;i++){
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout<<segs.size();
    for(auto t:segs){
       //对排序的结果进行输出
       //对于vector数组进行这样遍历!!!!!!
       cout<<t.first<<' '<<t.second<<endl;
   }
    return 0;
}
自己的错误代码:
 for(int i=1;i<n;){
        flag=0;
        while(d>=t[i].first&&i<n){
           d=max(d,t[i].second);
          flag=1;
          i++;
        }
        if(flag==0){
            c++;
        }


         d=t[i].second;
        i++;



    }
    return c;
}



cyuyu
7天前
折磨了本菜鸡一下午,本来思路是用pair<char,char>t,t[i].first,t[i].second分别表示一个
字符串的最小和最大的字符,想让他们按照升序进行排序,但是没有把pair的性质搞清楚,
这两个元素是在一起的不能分开,所以不可能实现两个元素均按升序排列,原先的思路就是
利用二分将最小/大字符按照升序得出其最小/最大位置。
第二次以为利用字符串进行升序,然后将全部字符串进行排序,二分后得出每个字符的最小和最大位置
这肯定不对。
正确思路是用正序字符串同逆序字符串进行比较二分后得出其最小和利用逆序和正序字符串进行二分,
得出最大位置,并且第二个二分是mid=(l+r+1)/2的模板,不是mid=(l+r)/2,如果用后者第二个位置
出现问题,这两个二分模板的异同点需要搞明白!!!!
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
const int N=1e5+10;
string u[N];
string d[N];
string o[N];
string q[N];
int main(){

    int n;
    cin>>n;
string  s;
int k=0,p=0;
for(int i=0;i<n;i++){
    cin>>s;
    sort(s.begin(),s.end());

     u[i]=s;//abcd
     o[i]=s;
    reverse(s.begin(),s.end());
    d[i]=s;//dcba
    q[i]=s;
}
sort(u,u+n);
sort(d,d+n);

 int l,r;
 for(int i=0;i<n;i++){
     l=0;
     r=n-1;
     while(l<r){
         int mid=(l+r)/2;
         if(o[i]<=u[mid]){
             r=mid;
         }
         else{
             l=mid+1;
         }
     }
     cout<<l+1<<' ';
      l=0;
     r=n-1;
     while(l<r){
         int mid=(l+r)/2;
         if(q[i]<=d[mid]){
             r=mid;
         }
         else{
             l=mid+1;
         }
     }
     cout<<l+1<<endl;
 }
 return 0;
}



cyuyu
8天前
方法一:采用模拟队列的方式
其中p[N][N]数组的值是该点由来的点的坐标
memset() 函数可以说是初始化内存的“万能函数”
http://c.biancheng.net/view/231.html
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110;
int n,m;
int q[N][N];//记录地图
int d[N][N];//记录离起点的距离
typedef pair<int,int>pii;
pii p[N][N];//用于记录某点是由{p[i].first,p[i].second}跳转而来
int bfs(){
    pii t[N*N];//注意这里的数组的值要开到N*N,不是N
    memset(d,-1,sizeof d);//初始化d数组,设数组中所有点均未被访问过
    d[0][0]=0;            //在原点距离为0
    //t[0]={0,0};
    int hh=0,tt=0;       //模拟队列
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};//按照上下左右的原则,x,y两坐标的变化
    t[++tt]={0,0};
    while(hh!=tt){//队列不为空
        pii temp=t[++hh];
        for(int i=0;i<4;i++){
            int x=temp.first+dx[i];
            int y=temp.second+dy[i];

            if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&q[x][y]==0){//d[x][y]==-1是为了筛选该点是第一次被遍历到,如果不是第一次被遍历即不是最短路径上的点
                p[x][y]=temp;
                d[x][y]=d[temp.first][temp.second]+1;
                t[++tt]={x,y};
            }
        }
    }
  int k=n-1;
  int l=m-1;

    while(k||l){//如果判断条件是k>=0&&l<=0就超时了

        cout<<k<<' '<<l<<endl;
        k=p[k][l].first;
        l=p[k][l].second;


    }
    return d[n-1][m-1];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>q[i][j];
        }
    }

    cout<<bfs();
    return 0;
}

方法二:stl,队列
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=110;
int n,m;
int q[N][N];//记录地图
int d[N][N];//记录离起点的距离
typedef pair<int,int>pii;
pii p[N][N];//用于记录某点是由{p[i].first,p[i].second}跳转而来
int bfs(){
   // pii t[N*N];//注意这里的数组的值要开到N*N,不是N
    memset(d,-1,sizeof d);//初始化d数组,设数组中所有点均未被访问过
    d[0][0]=0;            //在原点距离为0
    //t[0]={0,0};
    queue<pii>t;   //queue<pair<int,int>>t;
    int hh=0,tt=0;       //模拟队列
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};//按照上下左右的原则,x,y两坐标的变化
    t.push({0,0});
    while(!t.empty()){//队列不为空
        pii temp=t.front();
        t.pop();
        for(int i=0;i<4;i++){
            int x=temp.first+dx[i];
            int y=temp.second+dy[i];

            if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&q[x][y]==0){//d[x][y]==-1是为了筛选该点是第一次被遍历到,如果不是第一次被遍历即不是最短路径上的点
                p[x][y]=temp;
                d[x][y]=d[temp.first][temp.second]+1;
                t.push({x,y});
            }
        }
    }
  int k=n-1;
  int l=m-1;

    while(k||l){//如果判断条件是k>=0&&l<=0就超时了

        cout<<k<<' '<<l<<endl;
        k=p[k][l].first;
        l=p[k][l].second;


    }
    return d[n-1][m-1];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>q[i][j];
        }
    }

    cout<<bfs();
    return 0;
}



分享 数组去重

cyuyu
8天前
先进行排序,在进行去重会简单很多,之所以会想到这个知识点,在 [51. 数字排列](https://) 中遇到问题,
还未解决
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a[10] = { 0,1,1,0,2,3,2,4,2,4 };
    sort(a, a + 10);
    cout << a[0];
    for (int i = 0; i<10; i++)
    {
      if (a[i] != a[i - 1])
   cout << " " << a[i];
    }
    cout << endl;
    return 0;
}



cyuyu
8天前
  • 解法一:这种解法和排列数字的解法类似,自我感觉这种解法比第二种解法要好理解
#include<iostream>
using namespace std;
const  int N=20;
int n;
char g[N][N];
int l[N],ug[N],ng[N];
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<g[i]<<endl;
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<n;i++){
        if(!l[i]&&!ug[i+u]&&!ng[i-u+n]){
            g[u][i]='Q';
            l[i]=ug[i+u]=ng[i-u+n]=1;
            dfs(u+1);
            l[i]=ug[i+u]=ng[i-u+n]=0;
            g[u][i]='.';
        }
    }

}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

* 
  • 解法二:对于该种解法需要注意几个问题:
  • 1.开头的两个if语句不能互换位置,否则不能ac ,呜呜,但是这个回溯啥的太复杂了,我还不明白为什么:
  • 现在知道了,如果互换位置,在进入下边if判断语句进行剪枝时,会出现i=n,还会出现j=n的情况出现
  • 数组越界的情况,所以如果要是互换位置在下边语句中加入i<n,j<n,就可以了
  • 2.dfs(i,j+1,c);这个语句前边不能加上Else,在一次循环中该语句必执行

  • 解法一和解法二的异同点:解法一一个皇后就在一行,所以只需要找列,比较简单,

  • 解法二一个一个的空格进行筛选,如果符合进入dfs(i,j+1,c+1),但是不能保证这之后的
  • 所有皇后都能满足要求,所以回溯后可能会进入dfs(i,j+1,c)。
#include<iostream>
using namespace std;
int n;
const int N=20;
char g[N][N];
int row[N],l[N],ug[N],ng[N];
void dfs(int i,int j,int c){
     if(j==n){
       j=0;
       i++;
    }
    if(i==n){
        if(c==n){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<g[i][j];
                }
                cout<<endl;
            }
            cout<<endl;
        }
        return ;
    }


        if(!row[i]&&!l[j]&&!ug[i+j]&&!ng[j-i+n]){   //&&i<n&&j<n
            g[i][j]='Q';
            row[i]=l[j]=ug[i+j]=ng[j-i+n]=1;
            dfs(i,j+1,c+1);
            row[i]=l[j]=ug[i+j]=ng[j-i+n]=0;
            g[i][j]='.';
        }

            dfs(i,j+1,c);



}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0,0,0);
    return 0;
}