没写过题解那就水一发
题目：
长时间的干旱使得Farmer John的N块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。在Farm
er John的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶
农，Farmer John想要确保他的每头奶牛都能得到丰富的食谱。他的M头奶牛每一头都有两块喜爱的草地，他想要确
保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John知道没有一块草地受到多
于3头奶牛的喜爱。
请帮助Farmer John选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
Input
输入的第一行包含N（2≤N≤100）和M（1≤M≤150）。
以下M行，每行包含两个范围为1…N的整数，为Farmer John的一头奶牛喜欢的两块草地。
Output
输出一个N位数，每一位均为1…4之一，表示每一块草地上所种的草的种类。
第一位对应草地1的草的种类，第二位对应草地2，以此类推。如果有多种可行的解，只需输出所有解中最小的N位数。
Sample Input
5 6
4 1
4 2
4 3
2 5
1 2
1 5
Sample Output
12133
题目大意：给出n和m，表示n位和m个限制，限制包含x和y，表示x位和y位上的数字不一样
每一位只能放1，2，3，4中的一个数，求字典序最小的序列
第一眼看上去：不会
想了三分钟：好简单的题
我是不会告诉你我打挂了一次的
人为规定x<y，按x顺序从小到大快排一遍，从第一位开始枚举，考虑每一位对后面跟他有关系的点的限制
因为是按照字典序排列，所以排当前位数不需要考虑后面的，直接取用能取用的最小数即可
最后说下复杂度，O(max(m,4))轻松跑1s
代码写挂过一次
/*菜鸡xyh在线被暴打*/ #include<bits/stdc++.h> #define ll long long #define fill(a,b) memset(a,b,sizeof(a)) using namespace std; bool flag[2100][5]; int n,m,tot[2100]; struct kk{int x,y;}node[2100]; int cmp(kk A,kk B){return A.x<B.x;} void dfs(int k,int side){ int u,ans; if (k>n) exit(0); for (int i=1;i<=4;i++) if (flag[k][i]){ans=i;break;} printf("%d",ans); for (u=side;node[u].x==ans;u++) flag[node[u].y][ans]=false; /*这里之前手贱写了个u++，后来发现这样有些边会漏掉枚举*/ dfs(ans+1,u); }int main(){ scanf("%d%d",&n,&m);fill(flag,true); for (int i=1;i<=m;i++){ scanf("%d%d",&node[i].x,&node[i].y); if (node[i].x>node[i].y) swap(node[i].x,node[i].y); }sort(node+1,node+m+1,cmp); for (int i=1;i<=n;i++) ++tot[i]; dfs(1,1); return 0; }
做这道题的感受
划水真舒服注意思路，考虑限制