当前位置: 代码迷 >> 综合 >> 牛客网多校第七场 E Counting 4-Cliques
  详细解决方案

牛客网多校第七场 E Counting 4-Cliques

热度:74   发布时间:2023-11-23 07:21:16.0
/*
题意:输入k(<=1e6),构造一个图使得图中大小为4的团恰好有k个。首先考虑构造完全图,那么t个点的完全图一共能有C(t, 4)个大小为4的团。但是在C(t, 4)和C(t+1, 4)之间会有空缺,因此在完全图外放若干个点,每个点与这个完全图中的若干个点连边,最后会形成类似于C(t, 4)+C(x1, 3)+C(x2, 3)+…这样的式子,并且要能补满中间的空隙。至于为什么是另外找五个点,没办法证明出来,但四个点的话 额外的17个大小为4的团就出不来
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;ll C4(ll n) { // C(n, 4)ll ans = n * (n - 1) * (n - 2) * (n - 3) / (1 * 2 * 3 * 4);return ans;
}ll C3(ll n) { // C(n, 3)ll ans = n * (n - 1) * (n - 2) / (1 * 2 * 3);return ans;
}ll mp[200000 + 5];
int k;int main() {memset(mp, -1, sizeof(mp));for (ll i = 1; i <= 100; i++) {mp[C3(i)] = i;}scanf("%d", &k);ll C = 70;ll t = 4;while ((t + 1) <= C && C4(t + 1) <= k) {t++;}C = min(C, t);ll a, b, c, d, e = -1;for (a = 2; a <= C; a++) {for (b = a; b <= C; b++) {for (c = b; c <= C; c++) {for (d = c; d <= C; d++) {ll cnt = C3(a) + C3(b) + C3(c) + C3(d);if (cnt <= k - C4(t)&& mp[k - C4(t) - cnt] >= 0&& mp[k - C4(t) - cnt] <= C) {e = mp[k - C4(t) - cnt];break;}}if (e != -1)    break;}if (e != -1)    break;}if (e != -1)    break;}printf("%lld %lld\n", t + 5, t * (t - 1) / 2 + a + b + c + d + e);for (int i = 1; i <= t; i++) {for (int j = i + 1; j <= t; j++) {printf("%d %d\n", i, j);}}for (int j = 1; j <= a; j++)    printf("%lld %d\n", t + 1, j);for (int j = 1; j <= b; j++)    printf("%lld %d\n", t + 2, j);for (int j = 1; j <= c; j++)    printf("%lld %d\n", t + 3, j);for (int j = 1; j <= d; j++)    printf("%lld %d\n", t + 4, j);for (int j = 1; j <= e; j++)    printf("%lld %d\n", t + 5, j);
}