个人空间 - AcWing

Will_15

关注数

粉丝数

阅读量

2253

+关注发消息

离线：10小时前

最近来访(28)

急先锋

谈笑起_2

不吃萝卜的Henry

junbinliang

和平...qs

雲流

ZHUYIJIAO

雷霆尬拔

yxc的小迷妹

StarLi9ht

落秋

sunchenxi

清清小苏打

坤坤教你如何AC

KoNan

种花家的市长

jzwong

giraffe

krio

No.3_3

活动打卡代码 AcWing 116. 飞行员兄弟

Will_15
21小时前

                //输入数据，遍历所有方案，是1就改变并保存，遍历所有位置是否有关闭，无关闭更新最小值，
//turn_all:该行该列全部改变
//turn_one:变反
//get：二维转一维
//开关问题的共性：只能按一次，且顺序无所谓
//开关问题或者只有两种状态都可以用二进制枚举所有方案
//二维二进制枚举写法，要把二维映射为一维
//这里用二进制枚举所有方案，所以不用dfs
//一般PII都用vector来存，还可以知道存的个数，也就是操作的个数
//vector可以直接赋值
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
typedef pair<int,int>PII;

const int N=5;

char g[N][N],backup[N][N];

int get(int x,int y)//将二维转一维
{
    return x*4+y;
}

void turn_one(int x,int y)//转换一个开关
{
    if(g[x][y]=='+')g[x][y]='-';
    else g[x][y]='+';
}

void turn_all(int x,int y)//转换十字开关
{
    for(int i=0;i<4;i++)
    {
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);//中间的开关，重复，需要重新改过来
}

int main()
{
    for(int i=0;i<4;i++)cin>>g[i];
    memcpy(backup,g,sizeof g);//枚举所有方案记得要将原数据拷贝，再拷贝回去
    vector<PII>res;

    for(int op=0;op<1<<16;op++)//遍历所有位置，用op，1<<16就是2^16
    {
        vector<PII>ans;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(op>>get(i,j)&1)//将所有位置作为二进制写法遍历所有情况，将二维转一维后再右移
                //枚举二进制的每一位就用：op>>i&1
                {//二进制判断中记得&1  &1   &1
                    turn_all(i,j);
                    ans.push_back({i,j});
                }
            }
        }

        bool close=false;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(g[i][j]=='+')//+是关闭状态
                {
                    close=true;break;
                }
            }
        }

        if(!close)
        {
            if(res.empty()||res.size()>ans.size())
            res=ans;//vector可以直接赋值
        }

        memcpy(g,backup,sizeof backup);//记得拷贝过去进入下一个枚举
    }

    cout<<res.size()<<endl;//vector知道他的大小，知道操作多少次

    for(PII node:res)
    {
        cout<<node.first+1<<" "<<node.second+1<<endl;//结果从1开始
    }
    return 0;
}

            

题解 AcWing 116. 飞行员兄弟

Will_15
21小时前

                //输入数据，遍历所有方案，是1就改变并保存，遍历所有位置是否有关闭，无关闭更新最小值，
//turn_all:该行该列全部改变
//turn_one:变反
//get：二维转一维
//开关问题的共性：只能按一次，且顺序无所谓
//开关问题或者只有两种状态都可以用二进制枚举所有方案
//二维二进制枚举写法，要把二维映射为一维
//这里用二进制枚举所有方案，所以不用dfs
//一般PII都用vector来存，还可以知道存的个数，也就是操作的个数
//vector可以直接赋值
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;
typedef pair<int,int>PII;

const int N=5;

char g[N][N],backup[N][N];

int get(int x,int y)//将二维转一维
{
    return x*4+y;
}

void turn_one(int x,int y)//转换一个开关
{
    if(g[x][y]=='+')g[x][y]='-';
    else g[x][y]='+';
}

void turn_all(int x,int y)//转换十字开关
{
    for(int i=0;i<4;i++)
    {
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);//中间的开关，重复，需要重新改过来
}

int main()
{
    for(int i=0;i<4;i++)cin>>g[i];
    memcpy(backup,g,sizeof g);//枚举所有方案记得要将原数据拷贝，再拷贝回去
    vector<PII>res;

    for(int op=0;op<1<<16;op++)//遍历所有位置，用op，1<<16就是2^16
    {
        vector<PII>ans;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(op>>get(i,j)&1)//将所有位置作为二进制写法遍历所有情况，将二维转一维后再右移
                //枚举二进制的每一位就用：op>>i&1
                {//二进制判断中记得&1  &1   &1
                    turn_all(i,j);
                    ans.push_back({i,j});
                }
            }
        }

        bool close=false;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<4;j++)
            {
                if(g[i][j]=='+')//+是关闭状态
                {
                    close=true;break;
                }
            }
        }

        if(!close)
        {
            if(res.empty()||res.size()>ans.size())
            res=ans;//vector可以直接赋值
        }

        memcpy(g,backup,sizeof backup);//记得拷贝过去进入下一个枚举
    }

    cout<<res.size()<<endl;//vector知道他的大小，知道操作多少次

    for(PII node:res)
    {
        cout<<node.first+1<<" "<<node.second+1<<endl;//结果从1开始
    }
    return 0;
}

            

活动打卡代码 AcWing 95. 费解的开关

Will_15
22小时前

                //main：输入多组测试数据，输入数据，拷贝，遍历所有第一行的方案，是1就转动开关，遍历1到4行，关就按下
//下一行开关，最后判断第一行是否有关的，得到最小值，拷贝，输出
//得到一些性质，确定一些东西，找出一点规律，递推嘛
//难题就是难在组合拳，所以如果你发现时间允许那就是可以先用暴力枚举算出来，多种算法组合在一起
//只有0,1就可以转化为二进制遍历所有方案
//字符'1'变成字符'0'字符’0‘变成字符’1‘可以直接异或1
#include<iostream>
#include<cstring>
using namespace std;
const int N=6;
char g[N][N],backup[N][N];

int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};

void turn(int x,int y)
{
    for(int i=0;i<5;i++)//遍历所有方向
    {
        int a,b;
        a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<5&&b>=0&&b<5)//判断不越界
        {
            g[a][b]^=1;//字符'1'变成字符'0'字符’0‘变成字符’1‘可以直接异或1
        }
    }
}

int main()
{
    int T;cin>>T;
    while(T--)
    {
        int res=20;//求最小初始化为最大
        for(int i=0;i<5;i++)cin>>g[i];
        memcpy(backup,g,sizeof g);


        for(int op=0;op<=31;op++)//二进制枚举第一行
        {
            int cnt=0;
            for(int i=0;i<5;i++)
            {
                if(op>>i&1)//二进制是1就改变
                {
                    turn(0,i);
                    cnt++;
                }
            }

            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {
                    if(g[i][j]=='0')//第0层确定，后面的除最后层都随上一层唯一确定，要改变的，一定通过
            //后一层改变，核心思路：只能通过特定的几个位置改变我当前这个位置达到一一确定，递推效果
                    {
                        turn(i+1,j);
                        cnt++;
                    }
                }
            }

            bool close=false;
            for(int i=0;i<5;i++)//判断是否有暗灯
            {
                if(g[4][i]=='0')
                {
                    close=true;
                    break;
                }
            }

            if(!close)res=min(res,cnt);//没有暗灯满足条件，更新最小值
            memcpy(g,backup,sizeof g);
        }
        if(res>6)res=-1;
        cout<<res<<endl;

    }
    return 0;
}

            

题解 AcWing 95. 费解的开关

Will_15
22小时前

                //main：输入多组测试数据，输入数据，拷贝，遍历所有第一行的方案，是1就转动开关，遍历1到4行，关就按下
//下一行开关，最后判断第一行是否有关的，得到最小值，拷贝，输出
//得到一些性质，确定一些东西，找出一点规律，递推嘛
//难题就是难在组合拳，所以如果你发现时间允许那就是可以先用暴力枚举算出来，多种算法组合在一起
//只有0,1就可以转化为二进制遍历所有方案
//字符'1'变成字符'0'字符’0‘变成字符’1‘可以直接异或1
#include<iostream>
#include<cstring>
using namespace std;
const int N=6;
char g[N][N],backup[N][N];

int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};

void turn(int x,int y)
{
    for(int i=0;i<5;i++)//遍历所有方向
    {
        int a,b;
        a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<5&&b>=0&&b<5)//判断不越界
        {
            g[a][b]^=1;//字符'1'变成字符'0'字符’0‘变成字符’1‘可以直接异或1
        }
    }
}

int main()
{
    int T;cin>>T;
    while(T--)
    {
        int res=20;//求最小初始化为最大
        for(int i=0;i<5;i++)cin>>g[i];
        memcpy(backup,g,sizeof g);


        for(int op=0;op<=31;op++)//二进制枚举第一行
        {
            int cnt=0;
            for(int i=0;i<5;i++)
            {
                if(op>>i&1)//二进制是1就改变
                {
                    turn(0,i);
                    cnt++;
                }
            }

            for(int i=0;i<4;i++)
            {
                for(int j=0;j<5;j++)
                {
                    if(g[i][j]=='0')//第0层确定，后面的除最后层都随上一层唯一确定，要改变的，一定通过
            //后一层改变，核心思路：只能通过特定的几个位置改变我当前这个位置达到一一确定，递推效果
                    {
                        turn(i+1,j);
                        cnt++;
                    }
                }
            }

            bool close=false;
            for(int i=0;i<5;i++)//判断是否有暗灯
            {
                if(g[4][i]=='0')
                {
                    close=true;
                    break;
                }
            }

            if(!close)res=min(res,cnt);//没有暗灯满足条件，更新最小值
            memcpy(g,backup,sizeof g);
        }
        if(res>6)res=-1;
        cout<<res<<endl;

    }
    return 0;
}

            

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

Will_15
22小时前

                #include<iostream>
using namespace std;
const int N=47;
int f[N];
int main()
{
    int n;cin>>n;
    f[1]=0;
    f[2]=1;
    for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];
    for(int i=1;i<=n;i++)cout<<f[i]<<" ";
    return 0;
}

            

题解 AcWing 717. 简单斐波那契

Will_15
22小时前

                #include<iostream>
using namespace std;
const int N=47;
int f[N];
int main()
{
    int n;cin>>n;
    f[1]=0;
    f[2]=1;
    for(int i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];
    for(int i=1;i<=n;i++)cout<<f[i]<<" ";
    return 0;
}

            

活动打卡代码 AcWing 93. 递归实现组合型枚举

Will_15
1天前

                //dfs:结束输出，遍历，遍历下一层，恢复现场
//画一颗递归搜索树做递归题，然后在这颗树上分析参数，恢复现场其实就是恢复path状态，回溯的过程
//遍历所有情况就是for循环在递归内，n<10,时间复杂度：m*m!
#include<iostream>
using namespace std;
const int N=30;
int path[N];
int n,m;
void dfs(int u,int start)
{
    if(u>m)
    {
        for(int i=1;i<=m;i++)cout<<path[i]<<" ";
        puts("");
        return;
    }
    for(int i=start;i<=n;i++)
    {
        path[u]=i;
        dfs(u+1,i+1);
        path[u]=0;
    }
}
int main()
{
    cin>>n>>m;
    dfs(1,1);
    return 0;
}


            

活动打卡代码 AcWing 1209. 带分数

Will_15
1天前

                //遍历所有情况的题就是在最后分配
//main:输入目标，dfs，输出
//dfs：若u>9，最后分配所有情况输出，遍历所有要排列的数排列好
//cal：从左到右依次分配
#include<iostream>
using namespace std;
const int N=10;
int num[N];
int st[N];
int n,cnt;
int cal(int l,int r)
{
    int res=0;
    for(int i=l;i<=r;i++)
    {
        res=res*10+num[i];//将散开的数计算为一个数
    }
    return res;
}

void dfs(int u)
{
    if(u>9)//排列完之后合并判断是否满足结果
    {
        for(int i=1;i<=7;i++)
        {
            for(int j=i+1;j<=8;j++)//两刀分为三份，遍历所有分法找到符合条件的
            {
                int a,b,c;
                a=cal(1,i);
                b=cal(i+1,j);
                c=cal(j+1,9);
                if(n*c==a*c+b)cnt++;
            }
        }
    }


    for(int i=1;i<=9;i++)//得到全排列
    {
        if(!st[i])
        {
            st[i]=1;
            num[u]=i;
            dfs(u+1);
            st[i]=0;
            num[u]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<cnt<<endl;
    return 0;
}

            

题解 AcWing 1209. 带分数

Will_15
1天前

                //遍历所有情况的题就是在最后分配
//main:输入目标，dfs，输出
//dfs：若u>9，最后分配所有情况输出，遍历所有要排列的数排列好
//cal：从左到右依次分配
#include<iostream>
using namespace std;
const int N=10;
int num[N];
int st[N];
int n,cnt;
int cal(int l,int r)
{
    int res=0;
    for(int i=l;i<=r;i++)
    {
        res=res*10+num[i];//将散开的数计算为一个数
    }
    return res;
}

void dfs(int u)
{
    if(u>9)//排列完之后合并判断是否满足结果
    {
        for(int i=1;i<=7;i++)
        {
            for(int j=i+1;j<=8;j++)//两刀分为三份，遍历所有分法找到符合条件的
            {
                int a,b,c;
                a=cal(1,i);
                b=cal(i+1,j);
                c=cal(j+1,9);
                if(n*c==a*c+b)cnt++;
            }
        }
    }


    for(int i=1;i<=9;i++)//得到全排列
    {
        if(!st[i])
        {
            st[i]=1;
            num[u]=i;
            dfs(u+1);
            st[i]=0;
            num[u]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);
    cout<<cnt<<endl;
    return 0;
}

            

活动打卡代码 AcWing 94. 递归实现排列型枚举

Will_15
1天前

                //main：输入数据，dfs
//dfs:>n+1输出，遍历所有要选的数，没选就选，下一层
//2^n小于n!
//n<10,时间复杂度对应：n*n！：dfs中套一个for循环
#include<iostream>
using namespace std;
const int N=10;
int n;
int st[N];
int res[N];
void dfs(int u)
{
    if(u==n+1)//遍历完每层输出
    {
        for(int i=1;i<=n;i++)cout<<res[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)//把循环写在里头更加能遍历所有情况，用于遍历所有情况
    {
        if(!st[i])
        {
            st[i]=1;
            res[u]=i;
            dfs(u+1);
            st[i]=0;//恢复现场
            res[u]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);//循环写在外头一般是判断是否
    return 0;
}

            

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论