头像

Wei.H.Y


访客:2842

离线:2天前



Wei.H.Y
2天前
//圆桌会议
//枚举顺序,为了避免造成旋转后两方案是同一种方案的情况,将第一个人固定在一号座位
//随后依次枚举每个位置坐那个人,放置时要符合规则,不能是朋友,最后判断最后放的一个人和1号是不是朋友就ok了

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=12;
const int M=50;
int n,m;
int st[N];
int g[N][N];//表示两个人是否是朋友
int res;


void dfs(int u, int last_id)
{
    //u 当前枚举到第几个朋友,last_id 上个位置放的是哪个朋友
    if(u==n)
    {
        if(!g[last_id][1])
        {
            res++;
            return;
        }
    }

    //枚举每个位置放哪个人
    for(int i=1;i<=n;i++)
    {
        if(!st[i]&&!g[i][last_id])
        {
            st[i]=1;
            dfs(u+1,i);
            st[i]=0;//恢复现场
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        g[a][b]=g[b][a]=1;
    }
    //将第一个位置置为1
    st[1]=true;

    dfs(1,1);//从第一个位置开始枚举;
    cout<<res<<endl;
    return 0;



}




Wei.H.Y
4天前
//迷宫

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int N=105;
char map[N][N];
int st[N][N],k,n,ha,la,hb,lb;
bool flag=false;

//定义方向向量
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool dfs(int x, int y)
{
    if(x==hb&&y==lb)
    {
        return true;
    }

    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<n&&b>=0&&b<n)
        {
            if(!st[a][b]&&map[a][b]=='.')
            {
                st[a][b]=1;
                if(dfs(a,b)) return true;

            }
        }
    }
    return false;
}

int main()
{
    cin>>k;
    while(k--)
    {
        cin>>n;
        for(int i=0;i<n;i++)
        cin>>map[i];

        cin>>ha>>la>>hb>>lb;
        if(map[ha][la]=='#'||map[hb][lb]=='#')
        {
            cout<<"NO"<<endl;
            continue;
        }
        memset(st,0,sizeof(st));
        if(dfs(ha,la))
        cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}



Wei.H.Y
4天前
//字母 
//求最多能经过几个不同的字母(我理解是这样的)
//设置一个字母数组来判断该字母是否被走过,设置一个判重数组来确定自己不走入已经走过的方格,
//枚举顺序:到一个点,就上下左右到新的点

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int MAX_Alphat=27;
const int R=22;
const int S=22;
//做一个字母映射: A-'A'=0 所以A->0;
int Alphat[MAX_Alphat];
int st[R][S];
int r,s;
char map[R][S];
int res=0;

//定义方向向量
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int x, int y,int step)
{

    // if(!st[x][y]&&!Alphat[map[x][y]-'A'])
    // {
    //     res++;

    // }
    if(step>res) res=step;
    //向四周扩散
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i];
        int b=y+dy[i];
        if(a>=0&&a<r&&b>=0&&b<s&&!st[a][b]&&!Alphat[map[a][b]-'A'])
        {
            st[a][b]=1;
            Alphat[map[a][b]-'A']=1;
            dfs(a,b,step+1);
            st[a][b]=0;
            Alphat[map[a][b]-'A']=0;

        }
    }


}


int main()
{
    scanf("%d%d",&r,&s);
    for(int i=0;i<r;i++)
    {
        cin>>map[i];
    }
    Alphat[map[0][0]-'A']=1;
    dfs(0,0,1);
    cout<<res<<endl;
    return 0;
}




Wei.H.Y
4天前
//急性中风
// BFs:每次扩展到危险区域周围的各个区域

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
const int M=1300,N=130,L=100;
int block[L][M][N],m,n,l,t;
int st[L][M][N];
//block存放脑部的情况,m,n,l,t 长、宽、高、以及危险阈值
struct node
{
    int x,y,z;
};



int bfs(node v)
{
    int dx[] = { 1, -1, 0, 0, 0, 0 };
    int dy[] = { 0, 0, 1, -1, 0, 0 };
    int dz[] = { 0, 0, 0, 0, 1, -1 };
    queue<node> q;
    q.push(v);//将第一个结点压进队列
    st[v.x][v.y][v.z]=1;//判重数组记录为1,标记为访问过
    int cnt=1;//cnt记录危险区域的个数

    //接下来就可以四周扩散Bfs了
    while(!q.empty())
    {
        int a,b,c;
        //获取第一个结点
        node w=q.front();
        q.pop();
        for(int i=0;i<6;i++)
        {
            a=w.x+dx[i];
            b=w.y+dy[i];
            c=w.z+dz[i];
            if(a>=0&&a<l&&b>=0&&b<m&&c>=0&&c<n)
            {
                if(block[a][b][c]&&!st[a][b][c])
                    {
                        node temp;
                        temp.x=a;
                        temp.y=b;
                        temp.z=c;
                        st[a][b][c]=1;
                        q.push(temp);
                        cnt++;
                    }
            }


        }


    }
    return cnt;//返回危险区域数
}

int main()
{
    scanf("%d%d%d%d",&m,&n,&l,&t);
    for(int i=0;i<l;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<n;k++)
            {
                scanf("%d",&block[i][j][k]);
            }
        }
    }
    //memset(st,0,sizeof(st));
    int res=0;
    for(int i=0;i<l;i++)
    {
        for(int j=0;j<m;j++)
        {
            for(int k=0;k<n;k++)
            {
                if(!st[i][j][k]&&block[i][j][k])
                {
                    node in;
                    in.x=i;
                    in.y=j;
                    in.z=k;
                    int vol=bfs(in);
                    if(vol>=t) res+=vol;
                }
            }
        }
    }

    cout<<res<<endl;
    return 0;



}




Wei.H.Y
7天前
//单词接龙 
// 1.单词接龙游戏中,想要使得龙的长度最长,那么两单词的重合部分就要取最小值
// 枚举顺序大致为,选择一个字符串拼接到后面,然后更新长度,再枚举下一个字符串,直到全部连接完成

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int N=21;
int st[N],n;//st为判重数组,每个字符串最多用两次
int new_dragon,max_dragon;//表示单词龙的长度
string str[N];


int matching(string &s1, string &s2)
{
    //用来得到接龙时两单词的重合长度,s2是被拼接的
    if(s1.length()==1)
    {
        if(s1[0]==s2[0])
        {
            //s1长度为1,且s1 s2第一个字符相等的话,那龙增加的长度就是s2-1
            return s2.length();
        } 
        else return 0;//拼接失败~
    }

    else
    {
        //说明两字符串长度都大于一,那么就少最短的重合长度
        for(int i=1;i<s1.length();i++)
        {
            if(s1.substr(s1.length()-i,s1.length())==s2.substr(0,i))
            {
                return s2.length()-i;
            }
        }
    }

}

void dfs(string &s)
{
    //s为每次接龙完单词末尾的这一个单词
    for(int i=0;i<n;i++)
    {
        //matching返回0的话说明匹配不成功
        int t=matching(s,str[i]);
        if(st[i]<2&&t)
        {
            new_dragon+=t;
            if(new_dragon>max_dragon)
            {
                max_dragon=new_dragon;
            }
            st[i]++;
            dfs(str[i]);
            st[i]--;
            new_dragon-=t;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        cin>>str[i];
    }
    string cr;
    cin>>cr;
    dfs(cr);
    cout<<max_dragon<<endl;
    return 0;


}




Wei.H.Y
7天前
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=9;
int map[1<<N],ones[1<<N];//map 用来表示二进制的1对应第几位,例如100对应2 ones用来存储某一个二进制有几个1,
int row[N],col[N],block[3][3];//row 存放某一个的二进制表示,用来显示可用数字的情况,col\block同理

int cnt;//统计空白格子数
char str[10][10];
inline int lowbit(int x)
{
    return x&-x;
}
inline int get(int x,int y)
{
    //返回i行j列可用哪几个数字
    return row[x]&col[y]&block[x/3][y/3];
}

void init()
{
    //init 初始化,用于将row\col\block数组的每个数字都全置为1 
    for(int i=0;i<N;i++)
    {
        row[i]=(1<<N)-1;

    col[i]=(1<<N)-1;

    }


    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            block[i][j]=(1<<N)-1;
        }
    }

}

bool dfs(int cnt)
{
    if(!cnt) return true;//将所有空白格子填写完成的话,则true

    int minv=10;
    int x,y;//存放最少方案数的格子的横纵坐标

    //先找到一个可放数字最少的格子
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(str[i][j]=='.')
            {
                int s=ones[get(i,j)];
                if(s<minv) 
                {
                    minv=s;
                    x=i,y=j;
                }

            }
        }
    }
    //先给出可选方案的二进制表示


    //找到目标格子之后开始模拟填数独
    for(int i=get(x,y);i;i-=lowbit(i))
    {
        int t=map[lowbit(i)];//t为最后一位1对应的是第几位
        row[x]-=1<<t;
        col[y]-=1<<t;
        block[x/3][y/3]-=1<<t;
        str[x][y]='1'+t;
        if(dfs(cnt-1)) return true;
        row[x]+=1<<t;
        col[y]+=1<<t;
        block[x/3][y/3]+=1<<t;
        str[x][y]='.';
    }
    return false;

}


int main()
{
    //预处理一下map、ones数组
    for(int i=0;i<1<<N;i++)
    {
        int s=0;
        for(int j=i;j;j-=lowbit(j)) s++;
        ones[i]=s;//统计i的二进制有多少个1 
    }
    for(int i=0;i<N;i++)
    {
        map[1<<i]=i;
    }


        init();
        int cnt=0; //!!!! 每次要置为1 因为有多组测试数据
        for(int i=0;i<9;i++)
        {
            cin>>str[i];
        }
        for(int i=0,k=0;i<N;i++)
        {
            for(int j=0;j<N;j++,k++)
            {
                if(str[i][j]!='.')
                {
                    int t=str[i][j]-'1';//把1~9 映射成0~8
                    row[i]-=1<<t;//i行  t位 不能取  置为0
                    col[j]-=1<<t;//j列 同理
                    block[i/3][j/3]-=1<<t;

                }
                else cnt++; 
            }
        }
        dfs(cnt);

        for(int i=0;i<9;i++)
        {
            cout<<str[i]<<endl;
        }

    return 0;

}



Wei.H.Y
7天前
//糖果
//大致顺序:先枚举可选择数最少的一列,然后再在这一列中枚举选择哪一行
//这样的时间复杂度应该是最低的,


#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>

using namespace std;

const int N=110, M=1<<20;
vector<int > col[N];//用来记录col中每一列可选择的行数有哪些
int n,m,k;
int log2[M];//预处理,方便计算 log2(2的n次方)
int lowbit(int x)
{
    return x& -x;
}

int h(int state)
{
    //编写估价函数,看这时的state最少需要用几行来完成
    int res=0;
    //求最小方案数时,假设选择了某一列,则等价于选择了这一列的全部方案数
    for(int i=(1<<m)-1-state;i;i-=lowbit(i))
    {
        int c=log2[lowbit(i)];//i返回最后一位1,通过log2直接映射为最后一位1的位置
        res++;
        for(auto row:col[c])
        {
            i=i&~row; //row表示哪一列有1,每次选择一种方案,等价于将这种方案对应的位变为0,通过&操作实现
        }


    }
    return res;
}
bool dfs(int depth,int state)// depth表示层数,state用于维护选择糖果过程中已经选择了哪些口味
{
    if(!depth||h(state)>depth)
    {
        //若可选择的方案为0或者最小需要选择的方案数都小于当前可选的方案数的话,则判断是否合法
        //判断方法:看state是否全为1
        return state==(1<<m)-1;// (1<<m)-1表示m位全是一, 即2^m-1
    }

    //接下来找可选择数最少的一列

    int t=-1;//t是指向选择数最少的那一列的指针

    //*****
    for (int i = (1 << m) - 1 - state; i; i -= lowbit(i))
    {
        int c = log2[lowbit(i)];
        if (t == -1 || col[t].size() > col[c].size())
            t = c;
    }
    //接下来枚举选择哪一行
    for(auto row: col[t])
    {
        if(dfs(depth-1,state|row)) return true;
    }
    return false;

}


int main()
{
    scanf("%d%d%d",&n,&m,&k);
    //预处理log2
    for(int i=0;i<m;i++)
    {
        log2[1<<i]=i;
    }

    for(int i=0;i<n;i++)
    {
        int state=0;
        //将该包糖果所包含的糖果对应的位数置为1
        for(int j=0;j<k;j++)
        {
            int c;
            cin>>c;
            state=state|1<<c-1;

        }

        //找出这包糖果 哪个位置可以填成1,将该列对应的col+1
        for(int j=0;j<m;j++)
        {
            if(state>>j&1)//若第j位有1
            {
                col[j].push_back(state);
            }
        }


    }

    int depth=0;
    while(!dfs(depth,0)&&depth<=m) depth++;
    if(depth>m) depth=-1;
    cout<<depth<<endl;

    return 0;


}



Wei.H.Y
8天前
//欧拉路径

//欧拉图:连通图&&所有顶点度数为偶数
//半欧拉图:连通图&&两个顶点的度数为奇数
//非欧拉图:不是连通图 ||连通图 &&奇数度数的点数不是0也不是2

//大致思路:统计每个点的度数,再得出奇数度数的点的个数,并且同时判断图的连通性。
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;
const int N=505;
int n,m;
int graph[N][N],st[N],digree[N];//graph来标记边之间是否连通,st用于遍历图的连通性
int t,cnt;//digree记录各结点 度数,t记录奇数度数的个数, cnt 标记连通结点的个数


void dfs(int u)//从第u个结点开始遍历图
{
    st[u]=true;
    cnt++;

    for(int i=1;i<=n;i++)
    {
        if(graph[u][i]&&!st[i])
        {
            dfs(i);
        }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    int a,b;

    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&a,&b);
        graph[a][b]=graph[b][a]=1;
        digree[a]++,digree[b]++;

    }

    //统计奇数度数点的个数
    for(int i=1;i<=n;i++)
    {
        cout<<digree[i]<<' ';
        if(digree[i]%2!=0)
        {
            t++;
        }
    }
    cout<<endl;

    //判断连通性
    dfs(1);
    //若为连通图
    if(cnt==n)
    {
        if(t==0)
        {
            cout<<"Eulerian"<<endl;
        }
        else if(t==2)
        {
            cout<<"Semi-Eulerian"<<endl;
        }
        else cout<<"Non-Eulerian"<<endl;
    }
    else 
    cout<<"Non-Eulerian"<<endl;

    return 0;



}



Wei.H.Y
8天前
//火车进栈

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>


using namespace std;
int cnt=20;
vector<int> state1;//答案
stack<int> state2;//栈
int state3=1;//表示从state3往后的数字还没有进栈
int n;


void dfs()
{
    if(!cnt) return ;
    if(state1.size()==n)
    {
        cnt--;
        for(int i=0;i<state1.size();i++)
        {
            cout<<state1[i];
        }
        cout<<endl;
    }

    //枚举出栈
    if(!state2.empty())
    {
        state1.push_back(state2.top());
        state2.pop();
        dfs();
        state2.push(state1.back());
        state1.pop_back();

    }

    if(state3<=n)
    {
        state2.push(state3);
        state3++;
        dfs();
        state3--;
        state2.pop();
    }

}
int main()
{
    cin>>n;
    dfs();
}



Wei.H.Y
8天前
//矩阵路径



class Solution {
public:



    bool dfs(vector<vector<char>>& matrix, string &str ,int u,int x, int y )
    {
        if(str[u]!=matrix[x][y]) return false;
        if(u==str.size()-1)
        {
            return true;
        }
        int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
        char m=matrix[x][y];
        matrix[x][y]='*';
        //爆搜四条路径
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a>=0&&a<matrix.size()&&b>=0&&b<matrix[a].size()&&matrix[a][b]!='*')
            {
                if(dfs(matrix,str,u+1,a,b)) return true;
            }
        }
        matrix[x][y]=m;
        return false;


    }
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[i].size();j++)
                if(dfs(matrix,str,0,i,j)) return true;

    }


};