题面：51nod1967 辣鸡出题人卡边表差评。。。 卡常数卡啊卡交了35发才过QAQ 当然底下还有，反正占了两页
本题的主题思路就是求一个欧拉回路，我们把有向图暂时先看作无向图 首先第一问其实就是度为偶数点的个数 第二问我们把其他度为奇数的点两两连起来，然后整张图跑欧拉回路定向就好了啊 没有卡常的能看的代码（加了I/O优化）：
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <iostream> #include <ctime> #include <map> #include <queue> #include <cstdlib> #include <string> #include <climits> #include <set> #include <vector> using namespace std; inline int read(){ int k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } int n,m,f[600001],d[600001],K[600001]; int nedge=0,p[600001],c[1000001],nex[600001],head[600001],e[600001]; inline void addedge(int x,int y,int z,int zz){ p[++nedge]=y;c[nedge]=z;nex[nedge]=head[x];head[x]=nedge;e[nedge]=zz; } inline void dfs(int x){ for(int k=head[x];k;k=nex[k])if(f[c[k]]==-1){ f[c[k]]=e[k];dfs(p[k]); } } int main() { n=read();m=read(); memset(f,-1,sizeof f); for(int i=1;i<=m;++i){ int x,y;x=read();y=read(); addedge(x,y,i,0);addedge(y,x,i,1); ++d[x];++d[y]; } int M=m; for(int i=1;i<=n;++i)if(d[i]&1)K[++K[0]]=i; for(int i=1;i<=K[0];i+=2){ m++;addedge(K[i],K[i+1],m,0);addedge(K[i+1],K[i],m,1); } printf("%d\n",n-K[0]); for(int i=1;i<=n;++i)dfs(i); for(int i=1;i<=M;++i)printf("%d",f[i]); return 0; }然后愉快地TLE了 整个卡常过程分为以下几步： 1. 把所有i++改成了++i（然并卵 2. 听了szb的建议把头文件给删了（这个时候我旁边的zcydalao用vector轻松AC本题 3. 疯狂地改数组大小+I/O优化 4. 然后总算找到一个合理的数组范围卡过了。。。
卡常过的不能看的代码：
#include <stdio.h> using namespace std; inline int read(){ int k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } inline void write(int x){if(x>=10)write(x/10);putchar(x%10+'0');} inline void writeln(int x){write(x);puts("");} bool e[730001];char f[400001]; int n,m,d[100001],K[400001]={0},cnt=-1; int nedge=0,p[730001],c[730001],nex[730001],head[730001]; inline void addedge(int x,int y,int z){ ++cnt;p[++nedge]=y;c[nedge]=z;nex[nedge]=head[x];head[x]=nedge;e[nedge]=cnt&1; } inline void dfs(int x){ for(int k=head[x];k;k=nex[k])if(f[c[k]]==-1){ f[c[k]]=e[k];dfs(p[k]); } } int main() { n=read();m=read(); for(int i=1;i<=n+m;++i)f[i]=-1; for(int i=1;i<=m;++i){ int x,y;x=read();y=read(); addedge(x,y,i);addedge(y,x,i); ++d[x];++d[y]; } int M=m; for(int i=1;i<=n;++i)if(d[i]&1)K[++K[0]]=i; for(int i=1;i<=K[0];i+=2){ addedge(K[i],K[i+1],++m);addedge(K[i+1],K[i],m); } writeln(n-K[0]); for(int i=1;i<=n;++i)dfs(i); for(int i=1;i<=M;++i)write(f[i]); return 0; }最慢一个点1156ms（卡过。。。），vector好像600ms就直接A掉了
