头像

Will_15




离线: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;
}



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;
}



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;
}



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;
}



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;
}



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;
}



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;
}