构造字符串 50pts
错解50pts；
考虑正解，对于题目中的要求，我们可以转换成若干个相等与不等的操作，若相等则用并查集合并一下，不等则连边，若同块连边则无解，否则从前往后遍历赋值，每次找所连边其它块值的 $ \operatorname{mex} $ 即可；
时间复杂度：$ \Theta(nm \alpha(n)) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
int fa[5005];
int find(int x) {
if (x != fa[x]) fa[x] = find(fa[x]);
return fa[x];
}
struct sss{
int x, y, z;
}e[5005];
int cnt;
vector<int> v[5005];
int ans[5005];
bool vis[5005];
int main() {
freopen("str.in", "r", stdin);
freopen("str.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
int cnt = m;
memset(ans, -1, sizeof(ans));
for (int i = 1; i <= m; i++) {
cin >> e[i].x >> e[i].y >> e[i].z;
if (e[i].x > e[i].y) swap(e[i].x, e[i].y);
if (e[i].z != 0) {
int l = e[i].x;
int r = e[i].y;
int o = e[i].z;
while(o) {
fa[find(l)] = find(r);
l++;
r++;
o--;
}
if (r <= n) {
e[++cnt] = {l, r, 0};
}
} else {
e[++cnt] = e[i];
}
}
for (int i = m + 1; i <= cnt; i++) {
int l = e[i].x;
int r = e[i].y;
if (find(l) == find(r)) {
cout << -1;
return 0;
}
v[find(l)].push_back(find(r));
v[find(r)].push_back(find(l));
}
for (int i = 1; i <= n; i++) {
int x = find(i);
if (ans[x] != -1) continue;
for (int j = 0; j <= n; j++) vis[j] = false;
for (int j = 0; j < v[x].size(); j++) {
if (ans[v[x][j]] != -1) vis[ans[v[x][j]]] = true;
}
for (int j = 0; j <= n; j++) {
if (!vis[j]) {
ans[x] = j;
break;
}
}
}
for (int i = 1; i <= n; i++) {
cout << ans[find(i)] << ' ';
}
return 0;
}