P2565 [SCOI2009] 骰子的学问 题解

· · 题解

P2565 题解

题目分析：

首先我们把一个骰子的一个元素的权值定义为这个元素比多少个在它需要战胜的骰子中的元素要大，所以判断能否战胜的条件就是这个骰子中所有元素的权值和大于 \lfloor\frac{m^2}{2} \rfloor。

接下来我们从一组样例入手（第三组样例）：

注意到这组样例中将一和二交换会让第一个骰子的权值和更大，而其他不变。基于此，我们又可以注意到填数的路径其实是由被战胜的骰子至战胜的骰子的。

更进一步的：

所以我们考虑假设已经填了前一部分数，考虑下一个数怎么填。可以贪心地考虑下一个数必然要填在需要战胜这一个骰子的骰子上，并且这是对的。

于是考虑搜索，深搜地去填数，定义能填表示填数时为剩余的数的权值均为 m 时是否能继续（就是剩余都是最优时的答案）。

有无解的判定和证明是简单的，其他题解里也有。

于是我们就很简单地解决了这道题。

代码如下：

#include <bits/stdc++.h>
#define int long long

using namespace std;
using Pii = pair<int, int>;

const int N = 205;

int n, m, a[N], t, c[N], v[N];
vector<int> e[N], r[N];

void D(int x) {
  if (++v[x] > 1e5) {
    cout << 0;
    exit(0);
  }
  if (r[x].size() == m) {
    return;
  }
  for (; c[x] - (int)(r[a[x]].size()) <= m * (m - (int)(r[x].size()) - 1) && r[x].size() < m; c[x] -= r[a[x]].size()) {
    r[x].push_back(++t);
  }
  for (int i : e[x]) {
    D(i);
  }
}

signed main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    e[a[i]].push_back(i);
    c[i] = m * m / 2 + 1;
    if (a[i] == i) {
      cout << 0;
      return 0;
    }
  }
  for (int i = 1; i <= n; i++) {
    D(i);
  }
  if (*max_element(c + 1, c + n + 1) > 0) {
    cout << 0;
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j : r[i]) {
      cout << j << ' ';
    }
    cout << '\n';
  }
  return 0;
}