HGOI 20181028（复赛备考）

/*真是暴力的一天，最后一题MLE？由于数组开得太大了！！！270滚粗考场上好像智商高了很多？！(假的)*/

sol：暴力求解，然后没有数据范围吐槽一下（我开了10000000）

code：（100pts）

# include 
     
      using namespace std;const int MAXN=1e7+10;char s[MAXN];int fun(char c){    if (c=='W') return 64;if (c=='H') return 32;if (c=='Q') return 16;    if (c=='E') return 8; if (c=='S') return 4; if (c=='T') return 2;    if (c=='X') return 1;}bool check(int l,int r){    int ret=0;    for (int i=l;i<=r;i++) ret+=fun(s[i]);    if (ret==64) return true;    else return false;}int main(){    freopen("jingle.in","r",stdin);    freopen("jingle.out","w",stdout);    cin>>s; int len=strlen(s);    int cnt=0; for (int i=0;i
     

 

 

其实看一下就可以发现奇环显然是不行的。偶环一定可以通过0和1求解，然后就想到二分图

显然，如果这是张二分图那么就Yes采取01染色法求解（dfs暴力O(n)），如果不能做到01染色那么就输出No

但是注意图并不一定是连通图所以要多遍dfs

code(100pts)——第一次在考场上写read和write很激动然后封装了Input Output Base System的struct！码风很奇怪。。。

# include 
     
      # define Rint register intusing namespace std;const int MAXN=10005,MAXM=2*100005;int head[MAXN],col[MAXN],tot=0,n,m;bool vis[MAXN],ff;struct rec{ int pre,to;}a[MAXM];struct IOBS{    inline int read()    {        int X=0,w=0; char c=0;        while (!(c>='0'&&c<='9')) { w|=c=='-';c=getchar();}        while (c>='0'&&c<='9') { X=(X<<3)+(X<<1)+(c^48); c=getchar();}        return w?-X:X;    }    inline void write(Rint x)    {        if (x<0) { x=-x; putchar('-');}        if (x>9) write(x/10);        putchar(x%10+'0');    }    inline void write_files(Rint x,char cc){ write(x); putchar(cc);}    inline void Files()    { freopen("perfect.in","r",stdin); freopen("perfect.out","w",stdout);}}IO;inline void adde(Rint u,Rint v){    a[++tot].pre=head[u];    a[tot].to=v;    head[u]=tot;}inline void dfs(Rint u,Rint c){    vis[u]=true; col[u]=c;    for (Rint i=head[u];i;i=a[i].pre){        int v=a[i].to;         if (vis[v]&&col[v]!=(!c)) { ff=false; return;}        if (vis[v]&&col[v]==(!c)) continue;        dfs(v,!c);    }}int main(){    IO.Files(); n=IO.read(); m=IO.read();    int u,v;     for (Rint i=1;i<=m;i++) {        u=IO.read();v=IO.read();        adde(u,v); adde(v,u);    }    memset(vis,false,sizeof(vis));    for (Rint i=1;i<=n;i++) {        if (vis[i]) continue;        ff=true; dfs(i,0);        if (ff==false) { printf("NO\n"); return 0;}    }    putchar('Y');putchar('E');putchar('S');putchar('\n');    for (Rint i=1;i<=n;i++)     if (i!=n) IO.write_files(col[i],' ');    else IO.write(col[i]);    putchar('\n');    return 0;}
     

 

 

 

sol： 通过n,m<=5发现是暴力题然后算了下裸bfs暴力会TLE但是还是打了23333！

我可是码过斗地主、德州扑克的人！其实这点码量差不多就是100行左右吧

不大不大 bfs套bfs！ （注意Mle！）

# include 
     
      # define Rint register intusing namespace std;const int MAXN=7;const int dx[]={
   0,-1,0,1,0};const int dy[]={
   0,0,1,0,-1};struct node{ int M[MAXN][MAXN],L,scr;};struct rec{ int x,y,step;};char s[MAXN];int mp[MAXN][MAXN],start[MAXN][MAXN],n,m;bool inq[MAXN][MAXN];queue
      
       Q;  inline bool check(Rint X1,Rint Y1,Rint X2,Rint Y2,int &d){    while(!Q.empty()) Q.pop();     memset(inq,false,sizeof(inq));    inq[X1][Y1]=true; rec st; st.step=0; st.x=X1; st.y=Y1;    Q.push(st);    while (!Q.empty()) {        rec u=Q.front();Q.pop();         for (int i=1;i<=4;i++) {            rec v;            v.x=u.x+dx[i]; v.y=u.y+dy[i]; v.step=u.step+1;            if (v.x==X2&&v.y==Y2) { d=v.step-1;  return true;}            if (v.x>n||v.x<1|v.y>m||v.y<1||inq[v.x][v.y]||mp[v.x][v.y]!=10) continue;            if (v.x==X2&&v.y==Y2) { d=v.step-1;  return true;}            Q.push(v); inq[v.x][v.y]=true;        }    }    return false;}queue
       
        q;inline void bfs(){    node st; memcpy(st.M,start,sizeof(start));    st.L=0; st.scr=0;    int ans_scr=0,ans_L=0x7f7f7f7f;    q.push(st);    while (!q.empty()) {        node u=q.front();q.pop();        for (Rint X1=1;X1<=n;X1++)        for (Rint Y1=1;Y1<=m;Y1++) {          if (u.M[X1][Y1]==-1||u.M[X1][Y1]==10) continue;             for (Rint X2=1;X2<=n;X2++)             for (Rint Y2=1;Y2<=m;Y2++) {                  if (X1==X2&&Y1==Y2) continue;                  if (u.M[X2][Y2]==-1||u.M[X2][Y2]==10) continue;                  if (u.M[X1][Y1]!=u.M[X2][Y2]) continue;                  int delt_L; memcpy(mp,u.M,sizeof(u.M));                  if (check(X1,Y1,X2,Y2,delt_L)) {                      node v=u; memcpy(v.M,u.M,sizeof(u.M));                      v.L=u.L+delt_L; v.scr=u.scr+1;                      v.M[X1][Y1]=v.M[X2][Y2]=10;                      if (v.scr>ans_scr) { ans_scr=v.scr; ans_L=v.L; }                      else if (v.scr==ans_scr&&v.L
        
         >s;        for (Rint j=0;j
         
          ='0'&&s[j]<='9') start[i][j+1]=s[j]-'0';        else if (s[j]=='X') start[i][j+1]=-1;    }    bfs();    return 0;}