传送门 https://codeforces.com/problemset/problem/1243/E
题意:
现有 \(k,k\leq 15\) 个盒子, 每个盒子里面有 \(n_i,n_i\leq 5000\) 个数, 所有数两两不相同.
现在要从每个盒子里面取出一个数, 之后再将取出来的数放入每个盒子 (不一定放回原来的盒子).
问经过一次操作后, 是否每个盒子中加起来的总和相等, 如果是, 就给出一种方案数.
思路:
设所有数总和为 \(sum\), 那么若 \(sum\% k\not ={0}\), 那么必然不存在一种合法方案数.
现在知道最终每个盒子里面终态的总和为 \(t=\frac{sum}{k}\).
因为盒子个数很少, 我们枚举每个数出发去找环, 这部分的时间复杂度为 \(O(15^2\cdot 5000)\).
最后 \(check\) 一下能否将 \(k\) 个盒子划分为若干个合法的环, 这里我们用状压 \(dp\) 很好解得.
注意记录一下每个状态下环的方案数.
一开始我是枚举所有的状态, 然后找是否存在一个环满足该状态. 这一的话枚举状态的时间复杂度为 \(O(2^k)\), 找这样一个环的复杂度为 \(O(k\cdot n_i)\). 显然时间复杂度直接炸了. 因为可能一个点会被遍历多次, 会多出许多无用的计算.
细节见代码:
- /*
- * Author: heyuhhh
- * Created Time: 2020/3/5 19:57:13
- */
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #include <cmath>
- #include <set>
- #include <map>
- #include <queue>
- #include <iomanip>
- #include <assert.h>
- #define MP make_pair
- #define fi first
- #define se second
- #define pb push_back
- #define sz(x) (int)(x).size()
- #define all(x) (x).begin(), (x).end()
- #define INF 0x3f3f3f3f
- #define Local
- #ifdef Local
- #define dbg(args...) do { cout <<#args << "->"; err(args); } while (0)
- void err() { std::cout <<'\n'; }
- template<typename T, typename...Args>
- void err(T a, Args...args) { std::cout <<a << ' '; err(args...); }
- template <template<typename...> class T, typename t, typename... A>
- void err(const T <t> &arg, const A&... args) {
- for (auto &v : arg) std::cout <<v << ' '; err(args...); }
- #else
- #define dbg(...)
- #endif
- using namespace std;
- typedef long long ll;
- typedef pair<int, int> pii;
- //head
- const int N = 5005, M = 16;
- int k;
- int n[M], a[M][N];
- map <ll, pair<int, int>> mp;
- ll S[M];
- ll t;
- bool f[1 <<M], g[1 << M];
- int pre[1 << M];
- pii to[M], where[M][N];
- vector <pii> way[1 <<M];
- void run() {
- scanf("%d", &k);
- ll sum = 0;
- for(int i = 1; i <= k; i++) {
- scanf("%d", &n[i]);
- for(int j = 1; j <= n[i]; j++) {
- scanf("%d", &a[i][j]);
- sum += a[i][j];
- mp[a[i][j]] = MP(i, j);
- S[i] += a[i][j];
- }
- }
- if(sum % k != 0) {
- cout << "NO" << '\n';
- return;
- }
- t = sum / k;
- for(int i = 1; i <= k; i++) {
- for(int j = 1; j <= n[i]; j++) {
- ll need = t - (S[i] - a[i][j]);
- where[i][j] = mp.count(need) ? mp[need] : MP(-1, -1);
- }
- }
- for(int i = 1; i <= k; i++) {
- for(int j = 1; j <= n[i]; j++) {
- pii now = MP(i, j);
- vector <pii> cyc;
- int s = 0, flag = 1;
- while(1) {
- s ^= (1 << (now.fi - 1));
- cyc.push_back(now);
- pii to = where[now.fi][now.se];
- if(to == MP(-1, -1)) {
- flag = 0;
- break;
- }
- now = to;
- if(s & (1 << (now.fi - 1))) {
- if(now != MP(i, j)) flag = 0;
- break;
- }
- }
- if(flag == 0) continue;
- way[s] = cyc;
- f[s] = 1;
- }
- }
- g[0] = true;
- for(int sta = 0; sta < 1 << k; sta++) {
- for(int s = sta; s; s = (s - 1) & sta) {
- if(g[sta ^ s] & f[s]) {
- g[sta] = true;
- pre[sta] = s;
- break;
- }
- }
- }
- if(g[(1 << k) - 1] == false) cout << "NO" << '\n';
- else {
- cout << "YES" << '\n';
- int now = (1 << k) - 1;
- while(now) {
- int p = pre[now];
- for(auto it : way[p]) {
- pii go = where[it.fi][it.se];
- to[go.fi] = MP(a[go.fi][go.se], it.fi);
- }
- now -= p;
- }
- for(int i = 1; i <= k; i++) {
- cout << to[i].fi << '' << to[i].se <<'\n';
- }
- }
- }
- int main() {
- run();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3456461.html