阿里技术笔试-染色问题讨论

好奇第一题怎么做。。第一次做国内公司的面试，感觉是简单的数学但就是没想出来。

感觉是回溯，没写完

两题都是没做出来 好难

我第一题也是用的中位数，但是只对了80%的测试😂

第二题回溯只有给的用例能通过，，应该是超时了，忘了剪枝。

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long LL; const int maxn = 5010; int t, n, m, c, flag = 0; int l[maxn], cnt[maxn], mp[8][8]; void dfs(int x, int y) {   //printf("%d %d\n", x, y);   if (x == n && y == m + 1) {     flag = 1;     return;   }   for (int i = 0; i < c; i++) {     if (flag == 1) break;     if (i != mp[x - 1][y] && i != mp[x][y - 1] && cnt[i] < l[i]) {       mp[x][y] = i;       cnt[i]++;       if (x != n && y == m) dfs(x + 1, 1);       else dfs(x, y + 1);       cnt[i]--;       mp[x][y] = -1;     }   } } int main() {   scanf("%d", &t);   while (t--) {     memset(mp, -1, sizeof mp);     flag = 0;     scanf("%d %d %d", &n, &m, &c);     for (int i = 0; i < c; i++) {       scanf("%d", &l[i]);     }     dfs(1, 1);     printf("%s\n", flag == 1?"YES":"NO");   }   return 0; }