22/6/30

1，acwing 164.可达性统计；2， Decorating the Pastures；3， Perimeter

---

1，可达性统计； 

 思路：设f[x]表示x能到达的点的个数，

那么f[x]=(x)||f(y1)||f(y2)||....   （’||‘就是或运算，y1，y2是存在有向边的(x,y1)...）；

因此，要求f[x]就要知道后面的f[y1],f[y2]..所以就要按拓扑排序的逆序来做；

在表示x能否到i，可以用状态压缩，但是数据很长不是32位，就用到了bitset；

也就是将状态压缩不局限int来表示，而是可定长度的01数组来表示，并且 支持位运算；

一般来说是bitset<N>f[N]，f[i]代表一串01字符（一行），第i位是1就表示能到；

f[i][i]就是本身；

#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
using namespace std;
typedef pair<long long,long long>PLL;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef double dob; 
const int N=3e4+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++;
}
int n,m;
vector<int>xl;
bitset<N>f[N];
void 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];
            if(--d[j]==0)
            {
                q.push(j);
            }
        }
    }
    
}
signed main()
{
    quick_cin();
    cin>>n>>m;
    memset(h,-1,h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }
    topsort();
    per2(i,n-1,0)
    {
        int j=xl[i];
        f[j][j]=1;
        for(int k=h[j];~k;k=ne[k])
        {
            f[j]|=f[e[k]];
        }
    }
    rep2(i,1,n)cout<<f[i].count()<<endl;
    return 0;
}

2， Decorating the Pastures

题意：

n个牧场，m条双向道路连接，现给每个牧场插旗，有F和J两种，规定一条道路连接的两个牧场不能插同一种，求J最大的数，如果没有输出-1；

思路：不知道有没有孤立点，就遍历每个牧场，遍历过的标记，然后开始插旗，差的时候下一层和父亲不能一样，判断没有方案就是父亲和孩子插的旗一样；

#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=1e6+10;
int e[N],ne[N],h[N],idx;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int numj1,numj2;
int st[N];
bool ispf=0;
void bfs1(int x)
{
    queue<int>q;
    q.push(x);
    st[x]=1;
    numj1++;
    int f=1;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(!st[j])
            {
                q.push(j);
                if(st[t]==1)st[j]=2,numj2++;
                if(st[t]==2)st[j]=1,numj1++;
            } 
            else
            {
                if(st[j]==st[t])
                {
                    ispf=1;
                    return;
                }
            }
        }
    }
}
int ans;
signed main()
{
    quick_cin();
    memset(h,-1,h);
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }
    
    rep2(i,1,n)
    {
        if(!st[i])
        {
            numj1=0,numj2=0;
            bfs1(i);
            if(ispf)
            {
                cout<<-1;
                return 0;
            }
            ans+=max(numj1,numj2);
        }
    }
    cout<<ans;
    return 0;
}

3， Perimeter

dfs搜索最外边周长；

注意set的用法；

#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
using namespace std;
typedef pair<long long,long long>PLL;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
typedef double dob; 
set<PII>s,vis;
int n;
int ans;
bool ishole(int x,int y)
{
    rep2(i,-1,1)
    rep2(j,-1,1)
    {
        if(s.count(make_pair(x+i,y+j))==1)return 0;
    }
    return 1;
}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int x,int y)
{
    if(s.count(make_pair(x,y)))
    {
        ans++;
        return;
    }
    if(vis.count(make_pair(x,y)))return;
    vis.insert(make_pair(x,y));
    if(ishole(x,y))return;
    rep1(i,0,4)
    {
        dfs(x+dx[i],y+dy[i]);
    }
}
signed main()
{
    quick_cin();
    cin>>n;
    while (n--)
    {
        int x,y;
        cin>>x>>y;
        s.insert(make_pair(x,y));
    }
    auto st=*s.begin(); 
    dfs(st.first-1,st.second-1);
    cout<<ans;
 
    return 0;
}