头像

well188




在线 


活动打卡代码 AcWing 843. n-皇后问题

well188
9小时前

第1遍

按行枚举,因为每行只能放1个

#include <cstdio>
using namespace std;
const int N=20;
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) printf("%s\n",g[i]);
        printf("\n");
        return;
    }
    for(int i=0;i<n;i++){
        if(!col[i] && !dg[u+i] && !udg[i-u+n]){
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[i-u+n]=true;
            dfs(u+1);
            g[u][i]='.';
            col[i]=dg[u+i]=udg[i-u+n]=false;
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}

第2遍

一个格子一个格子的枚举

#include <cstdio>
using namespace std;
const int N=20;
char g[N][N];
bool row[N],col[N],dg[2*N],udg[2*N];
int n;
void dfs(int x,int y,int s){
    if(s>n) return;
    if(y==n) y=0,x++;
    if(x==n){
        if(s==n){
            for(int i=0;i<n;i++) printf("%s\n",g[i]);
            printf("\n");
        }
        return;
    }
    g[x][y]='.';
    dfs(x,y+1,s);

    if(!row[x] && !col[y] && !dg[y-x+n] && !udg[y+x]){
        g[x][y]='Q';
        row[x]=col[y]=dg[y-x+n]=udg[y+x]=true;
        dfs(x,y+1,s+1);
        g[x][y]='.';
        row[x]=col[y]=dg[y-x+n]=udg[y+x]=false;
    }
}
int main(){
    scanf("%d",&n);
    dfs(0,0,0);
    return 0;
}


活动打卡代码 AcWing 744. 数组中的列

well188
11小时前
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    char op;
    double matrix[12][12];
    cin>>n>>op;
    for (int i = 0;i<12; i ++ )
        for (int j=0;j<12;j++)cin>>matrix[i][j];
    double s=0;
    for (int i=0;i<12;i++) s+=matrix[i][n];
    if (op == 'M') s /= 12;
    printf("%.1lf\n", s);
    return 0;
}



活动打卡代码 AcWing 744. 数组中的列

well188
12小时前
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    char op;

    double matrix[12][12];

    cin >> n >> op;
    for (int i = 0; i < 12; i ++ )
        for (int j = 0; j < 12; j ++ )
            cin >> matrix[i][j];

    double s = 0;
    for (int i = 0; i < 12; i ++ ) s += matrix[i][n];

    if (op == 'M') s /= 12;

    printf("%.1lf\n", s);

    return 0;
}



well188
12小时前
#include <cstdio>
using namespace std;
double m[12][12];
int main(){
    char ch;
    double s=0.0;
    scanf("%c",&ch);
    for(int i=0;i<12;i++){
        for(int j=0;j<12;j++){
            scanf("%lf",&m[i][j]);
        }
    }
    int cnt=0;
    for(int i=1;i<12;i++){
        for(int j=0;j<i;j++){
            s+=m[i][j];
            cnt++;
        }
    }
    if(ch=='S') printf("%.1lf\n",s);
    else printf("%.1lf",s/cnt);

    return 0;
}



well188
12小时前
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int a[1000];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int p = 0;
    for(int i=1;i<n;i++)
        if(a[i]<a[p])
            p=i;

    printf("Minimum value: %d\nPosition: %d\n", a[p], p);
    return 0;
}


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

well188
13小时前

PP yxc

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    long long f[61];
    f[0]=0,f[1]=1;
    for(int i=2;i<=60;i++) f[i]=f[i-1]+f[i-2];
    int n;
    cin>>n;
    while(n--)
    {
        int t;
        cin>>t;
        printf("Fib(%d) = %lld\n",t,f[t]);
    }
    return 0;
}


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

well188
13小时前
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    long long f[61];
    f[0]=0,f[1]=1;
    for(int i=2;i<=60;i++) f[i]=f[i-1]+f[i-2];
    int n;
    cin>>n;
    while(n--)
    {
        int t;
        cin>>t;
        printf("Fib(%d) = %lld\n",t,f[t]);
    }
    return 0;
}


活动打卡代码 AcWing 740. 数组变换

well188
13小时前

PP yxc

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int i,a[20];
    for(i=0;i<=19;i++) cin>>a[i];
    for(i=0;i<=9;i++) swap(a[i],a[19-i]);
    for(i=0;i<=19;i++) printf("N[%d] = %d\n",i,a[i]);
    return 0;

}


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

well188
1天前

第3遍

注意:递归函数每层局部变量根据环境会不同,但全局变量不受影响。本题局部变量u,i。全局变量n
要清楚每层中局部变量的值是什么,这里很容易弄混,然后就不明白递归咋运行的了。
dfs.png

#include <cstdio>
using namespace std;
const int N=10;
int n,path[N];
bool f[N];
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        printf("\n");
    }
    else{
        for(int i=0;i<n;i++){
            if(!f[i]){
                path[u]=i+1;
                f[i]=true;
                dfs(u+1);
                f[i]=false;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}

第2遍

使用变量state作为判断是否使用的因素。
问:为什么state不用在回退时还原?
答:state是一个局部变量,在递归的每一层都有一个正确的值,比如在根节点分配的第1层,每个循环获得的state都是0,故不用还原。但state在递进是仍然需要检查和设置。

#include <cstdio>
using namespace std;
const int N=10;
int n,path[N];
void dfs(int u,int state){
    if(u==n){
        for(int i=0;i<n;i++) printf("%d ",path[i]);
        printf("\n");
    }
    else{
        for(int i=0;i<n;i++){
            if(!(state>>i&1)){
                path[u]=i+1;
                dfs(u+1,state+(1<<i));
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(0,0);
    return 0;
}

第1遍

dfs就是循环+剪枝+递归
循环:每个节点都循环3次,1,2,3
剪枝:每个用过的节点都标记
递归:递进到头,再回归撤销标记

#include <cstdio>
using namespace std;
const int N=10;
int q[N],n;
bool f[N];
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++){
            printf("%d ",q[i]);
        }
        printf("\n");
    }
    else{
        for(int i=1;i<=n;i++){
            if(!f[i]){
                q[u]=i;
                f[i]=true;
                dfs(u+1);
                f[i]=false;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}



well188
1天前

PP

#include <cstdio>
#include <cstring>
using namespace std;
int main(){
    double m[15][15];
    char ch[10];
    scanf("%s",ch);
    for(int i=0;i<12;i++){
        for(int j=0;j<12;j++){
            scanf("%lf",&m[i][j]);
        }
    }
    double s=0;
    int c=0;
    for(int i=1;i<=11;i++){
        for(int j=12-i;j<=11;j++){
            c++;
            s+=m[i][j];
        }
    }
    if(strcmp(ch,"S")==0) printf("%.1lf\n",s);
    else printf("%.1lf\n",1.0*s/c);
    return 0;
}