「CF1344C」Quantifier Question 解题报告

题面

解题思路

拓扑排序

一开始没看懂题目，感觉复杂的，后来就感觉还是可以的

分析

首先，我们要明确，如果有相关的若干个命题，一定要先出现 $\forall$，再出现 $\exist$，因此有了这个限制之后，我们想题目就会方便很多

显然，如果有环肯定是不成立的

我们先考虑对于一个点 $i$，如果 $i$ 点能到达的点 或者 能到达 $i$ 点的点的 $id < i$ ，显然 $i$ 点不能为 $\forall$，否则就能为 $\forall$，这样就做完了

Warning

1、注意是所有能到 $i$ 或者 $i$ 能到的点

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 200007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int HF[N],HL[N],n,m,t,d[N],S[N],ans;
int ver[N<<1],nxt[N<<1],P[N],vis[N],o[N];//别忘了N<<1
inline void Add(rint x,rint y) {
    ver[++t]=y,nxt[t]=HF[x],HF[x]=t;
    ver[++t]=x,nxt[t]=HL[y],HL[y]=t;
}
inline bool solve_P() {
    rint i,c,to,sum=0;queue<int>p;
    memset(P,inf,(n+1)<<2);
    for(i=1;i<=n;i++) if(!d[i]) p.push(i);
    while(!p.empty()) {
        c=p.front(),p.pop(),++sum;
        for(i=HF[c];i;i=nxt[i]) {
            --d[to=ver[i]],cmin(P[to],min(P[c],c));
            if(!d[to]) p.push(to);
        }
    }
    return sum<n;
}
inline void solve_S() {
    rint i,c,to;queue<int>p;
    memset(S,inf,(n+1)<<2);
    for(i=1;i<=n;i++) if(!o[i]) p.push(i);
    while(!p.empty()) {
        c=p.front(),p.pop();
        for(i=HL[c];i;i=nxt[i]) {
            --o[to=ver[i]],cmin(S[to],min(S[c],c));
            if(!o[to]) p.push(to);
        }
    }
}
int main() {
    rint i,x,y;
    n=read(),m=read();
    for(i=1;i<=m;i++) ++o[x=read()],++d[y=read()],Add(x,y);//要建正反图跑一跑
    if(solve_P()) {printf("-1");return 0;}solve_S();
    for(i=1;i<=n;i++) if(P[i]>i&&i<S[i]) vis[i]=1,++ans;
    printf("%d\n",ans);
    for(i=1;i<=n;i++) printf("%c",vis[i]?'A':'E');
    return 0;
}