头像

冷月无声re


访客:564

在线 



求问一个二维的方格怎么对应到一维数组中,y总说要是坐标x,y都从0开始,则对应x*n+y中去,要是坐标都从1开始对应关系应该是什么啊?
希望各位大佬分享一下好的办法qwq


活动打卡代码 AcWing 164. 可达性统计

#include<bits/stdc++.h>
using namespace std;
const int N=30010;
int din[N],q[N];
int h[N],e[N],ne[N],idx;
int n,m;
bitset<N> f[N];//用来记录编号为i的点能够走到哪些点
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(!din[i])
        q[++tt]=i;
    }
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            din[j]--;
            if(!din[j]) q[++tt]=j;
        }
    }
}
int main()
{
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        din[b]++;
    }
    topsort();
    for(int i=n-1;i>=0;i--)
    {
        int j=q[i];
        f[j][j]=1;//表示编号第j个节点能够到达j自己
        for(int i=h[j];i!=-1;i=ne[i])
        {
            int k=e[i];
            f[j]|=f[k];
        }
    }

    for(int i=1;i<=n;i++)
    cout<<f[i].count()<<endl;
    return 0;
}


活动打卡代码 AcWing 1192. 奖金

#include<bits/stdc++.h>
using namespace std;
const int N=10010,M=30010;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dist[N];
int path[N],din[N];
int cnt=0;
void init()
{
    memset(h,-1,sizeof(h));
    idx=0;
}
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
    {
        if(!din[i])
        {
            path[++tt]=i;
            cnt++;
        }
    }
    while(hh<=tt)
    {
        int t=path[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            din[j]--;
            if(!din[j])
            {
                path[++tt]=j;
                cnt++;
            }
        }
    }
    return cnt==n;
}

int main()
{
    cin>>n>>m;
    init();
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(b,a,1);
        din[a]++;
    }
    if(!topsort()) puts("Poor Xed");
    else 
    {
        int res=0;
        memset(dist,0x3f,sizeof(dist));
        for(int i=1;i<=n;i++) dist[i]=100;
        for(int i=0;i<cnt;i++)
        {
            int j=path[i];
            for(int k=h[j];k!=-1;k=ne[k])
            {
                int h=e[k];
                if(dist[h]<dist[j]+1)
                {
                    dist[h]=dist[j]+1;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            res+=dist[i];
        }
        cout<<res<<endl;
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N;
bool st[M];
typedef long long LL;
LL f[N][M];
int n,m;
int main()
{
    while(cin>>n>>m,(n||m))
    {
        for(int i=0;i<1<<n;i++)
        {
            st[i]=true;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        st[i]=false;
                        break;
                    }
                    cnt=0;
                }
                else cnt++;
            }
            if(cnt&1) st[i]=false;
        }
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=0;j<1<<n;j++)
            for(int k=0;k<1<<n;k++)
            {
                if((j&k)==0&&st[j|k])
                f[i][j]+=f[i-1][k];
            }
        }
        cout<<f[m][0]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1191. 家谱树

#include<bits/stdc++.h>
using namespace std;
const int N=110;
vector<int> Edge[N];
int n;
int din[N];
int path[N];
int cnt=0;
void topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(!din[i])
        q.push(i);
    }
    while(q.size())
    {
        int t=q.front();
        path[cnt++]=t;
        q.pop();
        for(int i=0;i<Edge[t].size();i++)
        {
            int j=Edge[t][i];
            din[j]--;
            if(!din[j])
            {
                q.push(j);
            }
        }
    }
    for(int i=0;i<cnt;i++)
    cout<<path[i]<<" ";
    cout<<endl;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int son;
        while(cin>>son,son)
        {
            Edge[i].push_back(son);
            din[son]++;
        }
    }
    topsort();
    return 0;
}



活动打卡代码 AcWing 165. 小猫爬山

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int sum[N];
int w[N];
int n,m;
int res=N;
void dfs(int u,int cnt)
{
    if(cnt>=res) return;

    if(u==n)
    {
        res=cnt;
        return;
    }
    for(int i=0;i<cnt;i++)
    {
        if(sum[i]+w[u]<=m)
        {
            sum[i]+=w[u];
            dfs(u+1,cnt);
            sum[i]-=w[u];
        }
    }
    sum[cnt]=w[u];
    dfs(u+1,cnt+1);
    sum[cnt]=0;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>w[i];
    sort(w,w+n);
    reverse(w,w+n);
    dfs(0,0);
    cout<<res<<endl;
    return 0;
}



题目描述

翰翰和达达饲养了N只小猫,这天,小猫们要去爬山。

经历了千辛万苦,小猫们终于爬上了山顶,但是疲倦的它们再也不想徒步走下山了(呜咕>_<)。

翰翰和达达只好花钱让它们坐索道下山。

索道上的缆车最大承重量为W,而N只小猫的重量分别是C1、C2……CN。

当然,每辆缆车上的小猫的重量之和不能超过W。

每租用一辆缆车,翰翰和达达就要付1美元,所以他们想知道,最少需要付多少美元才能把这N只小猫都运送下山?

输入格式
第1行:包含两个用空格隔开的整数,N和W。

第2..N+1行:每行一个整数,其中第i+1行的整数表示第i只小猫的重量Ci。

输出格式
输出一个整数,表示最少需要多少美元,也就是最少需要多少辆缆车。

数据范围
1≤N≤18 ,
1≤Ci≤W≤108

样例

输入样例:

5 1996
1
2
1994
12
29

输出:

2

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20;
int n,m;
int sum[N];//每辆车装的重量
int w[N];
int res=N;//最多N辆车,每人一辆
bool cmp(const int& a,const int& b) 
{
    return a>b;
}
void dfs(int u,int cnt)//当前正在安排的猫的编号为u,已经使用的车辆数量为cnt,当前这只猫的两种安排方案:插到现有的或新开一辆
{
    //最优性剪枝
    if(cnt>=res) return;//当前方案不是最优的,不用再搜了

    //边界条件,正在安排第n+1只猫,结束
    if(u==n)
    {
        res=cnt;//cnt一定小于res,因为cnt过了第一个判断条件
        return;
    }
    //方案一:插入已有的cnt车辆,编号0-cnt-1
    for(int i=0;i<cnt;i++)
    {   
        //可行性剪枝,如果坐的下的话才能坐
        if(sum[i]+w[u]<=m)
        {
            sum[i]+=w[u];
            dfs(u+1,cnt);
            sum[i]-=w[u];//恢复现场
        }
    }
    //方案二:开一辆新车,编号cnt
    sum[cnt]=w[u];
    dfs(u+1,cnt+1);
    sum[cnt]=0;//恢复现场

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    cin>>w[i];
    //优化搜索顺序
    sort(w,w+n,cmp);//从大到小排序
    //y总写法,nb
    //sort(w,w+n);
    //reverse(w,w+n);
    dfs(0,0);//从编号为0的小猫开始安排,刚开始一辆车也没有
    cout<<res<<endl;
    return 0;
}



我碰见的不同的dfs写法,便于记忆:

🤦‍♀️>不知道为什么就TLE的写法!!!
#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m;
const int N=11;
bool st[N][N];
int ans=0;
void dfs(int a,int b,int cnt)
{
    if(a<0||b<0||a>=n||b>=m) return;
    if(st[a][b]) return;
    if(cnt==n*m)
    {   ans++;
        return;
    }
    st[a][b]=true;
    for(int i=0;i<8;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        dfs(nx,ny,cnt+1);
    }
    st[a][b]=false;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {   ans=0;
        int sx,sy;
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
    }
    return 0;
}
🤷‍♂️>不知道为什么改变判断条件就莫名其妙Ac的玄学写法

#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m;
const int N=11;
bool st[N][N];
int ans=0;
void dfs(int a,int b,int cnt)
{
    if(cnt==n*m)
    {   ans++;
        return;
    }
    st[a][b]=true;
    for(int i=0;i<8;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        if(nx<0||ny<0||nx>=n||ny>=m) continue;
        if(st[nx][ny])continue;
        dfs(nx,ny,cnt+1);
    }
    st[a][b]=false;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {   ans=0;
        int sx,sy;
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
    }
    return 0;
}

最后这种写法才是我这种弱鸡才会准确写对的一种写法,回溯与标记在一起,美滋滋😊😊

#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m;
const int N=11;
bool st[N][N];
int ans=0;
void dfs(int a,int b,int cnt)
{
    if(cnt==n*m)
    {   ans++;
        return;
    }
    st[a][b]=true;
    for(int i=0;i<8;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        if(nx>=0&&nx<n&&ny>=0&&ny<m&&!st[nx][ny])
        {
           st[nx][ny]=true;
           dfs(nx,ny,cnt+1);
           st[nx][ny]=false;

        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {   ans=0;
        int sx,sy;
        cin>>n>>m>>sx>>sy;
        memset(st,0,sizeof(st));
        st[sx][sy]=1;
        dfs(sx,sy,1);
        cout<<ans<<endl;
    }
    return 0;
}



题目:马走日

#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m;
const int N=11;
bool st[N][N];
int ans=0;
void dfs(int a,int b,int cnt)
{
    if(cnt==n*m)
    {   ans++;
        return;
    }
    st[a][b]=true;
    for(int i=0;i<8;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        if(nx<0||ny<0||nx>=n||ny>=m) continue;
        if(st[nx][ny])continue;
        dfs(nx,ny,cnt+1);
     // st[a][b]=false;
    }
    st[a][b]=false;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {   ans=0;
        int sx,sy;
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
    }
    return 0;
}

下面的代码为什么会TLE啊!!!!

#include<bits/stdc++.h>
using namespace std;
int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};
int n,m;
const int N=11;
bool st[N][N];
int ans=0;
void dfs(int a,int b,int cnt)
{
    if(a<0||b<0||a>=n||b>=m) return;
    if(st[a][b]) return;
    if(cnt==n*m)
    {   ans++;
        return;
    }
    st[a][b]=true;
    for(int i=0;i<8;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        dfs(nx,ny,cnt+1);
    }
    st[a][b]=false;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {   ans=0;
        int sx,sy;
        cin>>n>>m>>sx>>sy;
        dfs(sx,sy,1);
        cout<<ans<<endl;
    }
    return 0;
}

样例都能过,但后一个代码为什么TLE了啊,请教大佬



活动打卡代码 AcWing 1113. 红与黑

#include<bits/stdc++.h>
using namespace std;
const int N=30;
int n,m;
char g[N][N];
bool st[N][N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int dfs(int a,int b)
{
    int cnt=1;
    if(g[a][b]=='#') return 0;
    if(a<0||a>=n||b<0||b>=m) return 0;
    if(st[a][b]) return 0;
    st[a][b]=true;
    for(int i=0;i<4;i++)
    {
        int nx=a+dx[i];
        int ny=b+dy[i];
        //if(nx<0||ny<0||nx>=n||ny>=m) continue;
        // if(st[nx][ny]) continue;
        //if(g[nx][ny]!='.') continue;
        cnt+=dfs(nx,ny);
    }
    return cnt;
}
int main()
{
    while(cin>>m>>n,n||m)
    {
    for(int i=0;i<n;i++) cin>>g[i];
    int sx,sy;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        if(g[i][j]=='@')
        {
            sx=i;
            sy=j;
        }
    }
    memset(st,0,sizeof(st));
    cout<<dfs(sx,sy)<<endl;
    }
    return 0;
}