P3087 题解

· · 题解

题意

有 L 类属性，给定 N 只奶牛在每类属性的取值，令每类属性出现过的值就是该类属性的取值集合。求每类属性所 有可能的取值组合中，按字典序排序后，没有出现在这 N 只奶牛列表里的第 K 个取值组合是什么。

思路

每类属性实际上就是进制中的一位，所有属性构成一个混合进制。

首先我们要求出每一位的进率，和每只奶牛在每一位上对应的值，可以对每⼀类属性的值排序，然后去重，按顺序 从 0 开始编号。也可以更加粗暴的先判断每个值是否第一次出现，然后对每个值统计比它小的第一次出现的值的个数，就得到了每个值对应的编号，最大的编号 +1 就是该位的进率。

然后就可以将每只奶牛对应的混合进制数转换成最小单位数量，排序后这些数将数轴分成 N + 1 个区间，我们按顺序处理每个区间，就能找到第 K 个数对应的数值。 最后我们再将数值转换回混合进制，输出每位上的数对应的属性，就是答案。

复杂度

令属性类的数量为 L。

时间

属性值总数 \mathcal O(NL)。

奶牛对应的十进制数排序 \mathcal O(n \log n)。

寻找第 K 个数 \mathcal O(N)。

转换回混合进制 \mathcal O(L)。

总时间复杂度为 \mathcal O(N^2L)。

空间

记录属性 \mathcal O(NL)，注意常数为属性长度 10。

代码

#include <algorithm>
#include <iostream>

using namespace std;

const int kMaxN = 102, kMaxL = 31;

struct P {          // 属性种类
  int r, w;         // 位权、进率
  string s[kMaxN];  // 位上的数对应的属性值
} p[kMaxL];
string s[kMaxN][kMaxL], str;
int b[kMaxN][kMaxL], v[kMaxN], n, k, l, x;

int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> str >> str >> str >> str;
    for (l = 0;; l++) {  // 读入属性
      cin >> str;
      if (str == "cow.") {  // 属性结束
        break;
      }
      s[i][l] = str, b[i][l] = 1;       // 记录属性、初始化首次出现标记
      for (int j = 1; j < i; j++) {     // 枚举之前的同类属性
        b[i][l] &= s[j][l] != s[i][l];  // 判重标记是否首次出现
      }
    }
  }
  for (int k = l - 1; k >= 0; k--) {                    // 权重由低到高枚举属性类型
    p[k].w = k == l - 1 ? 1 : p[k + 1].w * p[k + 1].r;  // 计算当前属性的位权
    for (int i = 1; i <= n; i++) {                      // 枚举每只奶牛
      int c = 0;                                        // 初始化位上的值
      for (int j = 1; j <= n; j++) {                    // 枚举其他奶牛
        c += b[j][k] && s[j][k] < s[i][k];              // 计算较小同类属性数量
      }
      p[k].r = max(p[k].r, c + 1);  // 更新进率
      p[k].s[c] = s[i][k];          // 记录值对应的属性
      v[i] += c * p[k].w;           // 累加位对应的值
    }
  }
  sort(v + 1, v + 1 + n);             // 将拥有的奶牛按值排序
  v[0] = -1, v[n + 1] = 1e9 + 1;      // 初始化边界
  for (int i = 1; i <= n + 1; i++) {  // 枚举缝隙寻找第k只
    if (k <= v[i] - v[i - 1] - 1) {   // 在当前缝隙中
      x = v[i - 1] + k;
      break;
    } else {
      k -= v[i] - v[i - 1] - 1;  // 减去当前缝隙长度
    }
  }
  for (int i = 0; i < l; i++) {   // 值转混合进制
    int y = x / p[i].w % p[i].r;  // 计算位上的值
    cout << (i ? " " : "") << p[i].s[y];
  }
  return 0;
}