22/6/29

1，cf Solve The Maze；2，acwing 1191.家谱树；3，acwing 1192.奖金；

---

1，cf solve the maze

题意：给出n*m 的矩阵，'.'代表空地，'#'代表墙，'B'代表坏人，'G'代表好人，你现在可以在任意空地上加墙，来使得好人可以到的第(n,m)块地，坏人无法到达；如果可以这样，输出yes，否则输出no；

思路：直接给坏人围墙，然后从（n，m）bfs，如果能遍历到所有好人，就是yes；

注意特判：没有好人就是yes；好人和坏人挨着，no；终点是墙，no；

细节：注意bfs标记st为1的时机，放入队列的时候就标记，而不是出队在标记；后者会导致tle；

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define mset(a,i,b) memset((a),(i),sizeof (b))
#define mcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long>PLL;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
const int N=110;
int n,m;
char a[N][N];
vector<PII>g,b;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int st[N][N];
void bfs()
{
    queue<PII>q;
    q.push({n,m});
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int x=t.yi,y=t.er;
        rep1(i,0,4)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx<1||yy<1||xx>n||yy>m||a[xx][yy]=='#'||st[xx][yy])continue;
            q.push({xx,yy});
            st[xx][yy]=1;
        }
    }
}
void solve()
{
    cin>>n>>m;
    mset(a,0,a);
    mset(st,0,st);
    g.clear();
    b.clear();
    rep2(i,1,n)
        rep2(j,1,m)
        {
            cin>>a[i][j];
            if(a[i][j]=='B')b.pb({i,j});
            if(a[i][j]=='G')g.pb({i,j});
        }
    if(!g.size())
    {
        YES;
        return;
    }
    int bsiz=b.size();
    rep1(i,0,bsiz)
    {
        rep1(j,0,4)
        {
            int x=b[i].yi+dx[j];
            int y=b[i].er+dy[j];
            if(a[x][y]=='G')
            {
                NO;
                return;
            }
            if(a[x][y]=='.')a[x][y]='#';
        }
    }
    if(a[n][m]=='#')
    {
        NO;
        return;
    }
    bfs();
    int gsiz=g.size();
    rep1(i,0,gsiz)
    {
        if(!st[g[i].yi][g[i].er])
        {
            NO;
            return;
        }
    }
    YES;
}
signed main()
{
    quick_cin();
    int T;
    cin>>T;
    while(T--)solve();
 
    return 0;
}

浅记一下memset中，sizeof 和数字的区别

sizeof 跟一个数字，然后得到数组的长度，所以不能sizeof（40），这是错误的；

而单独数字，则代表40个字节长度，int 单位字节长度是4，所以10*4=40；

2，家谱树；

 思路：简单拓扑排序，注意add(a,b)和d[b]++;

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long>PLL;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
int n;
const int N=1e5+10;
int e[N],ne[N],h[N],idx;
int d[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
vector<int>ans;
void topsort()
{
    queue<int>q;
    rep2(i,1,n)if(!d[i])q.push(i);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        
        ans.pb(t);
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q.push(j);
            }
        }
    }
}
signed main()
{
    quick_cin();
    memset(h,-1,h);
    cin>>n;
    rep2(i,1,n)
    {
        int x;
        while(cin>>x,x)
        {
            add(i,x);
            d[x]++;
        }
    }
    //rep2(i,1,n)cout<<d[i]<<endl;
    topsort();
    int siz=ans.size();
    rep1(i,0,siz)cout<<ans[i]<<" ";
    return 0;
}

3，奖金；

递推关系，拓扑序列； 

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rep1(i,a,n) for( int i=a;i<n;++i) 
#define rep2(i,a,n) for( int i=a;i<=n;++i) 
#define per1(i,n,a) for( int i=n;i>a;i--) 
#define per2(i,n,a) for( int i=n;i>=a;i--)
#define quick_cin() cin.tie(0),cout.tie(0),ios::sync_with_stdio(false)
#define memset(a,i,b) memset((a),(i),sizeof (b))
#define memcpy(a,i,b) memcpy((a),(i),sizeof (b))
#define pro_q priority_queue
#define pb push_back
#define pf push_front
#define endl "\n"
#define lowbit(m) ((-m)&(m))
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define yes cout<<"yes\n"
#define no cout<<"no\n"
#define yi first
#define er second
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long>PLL;
typedef pair<int,PII> PIII;
typedef long long LL;
typedef double dob;
int n,m;
const int N=1e5+10;
int e[N],ne[N],h[N],idx;
int d[N],dist[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
vector<int>xl;
bool topsort()
{
    queue<int>q;
    rep2(i,1,n)if(!d[i])q.push(i);
    while(q.size())
    {
        int t=q.front();
        q.pop();
        
        xl.pb(t);
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            d[j]--;
            if(d[j]==0)
            {
                q.push(j);
            }
        }
    }
    return xl.size()==n;
}
signed main()
{
    quick_cin();
    memset(h,-1,h);
    cin>>n>>m;
    while (m--)
    {
        int a,b;
        cin>>a>>b;
        add(b,a);
        d[a]++;
    }
    if(!topsort())cout<<"Poor Xed";
    else
    {
        rep2(i,1,n)dist[i]=100;
        int siz=xl.size();
        rep1(i,0,siz)
        {
            int j=xl[i];
            for(int k=h[j];~k;k=ne[k])
            {
                int jj=e[k];
                dist[jj]=max(dist[jj],dist[j]+1);
            }
        }
        int ans=0;
        rep2(i,1,n)ans+=dist[i];
        cout<<ans;
    }
    return 0;
}