大佬思路: Tutorial for CF1641D – tommymio’s Notebook – 洛谷博客 (luogu.com.cn)
思路:
- 关键是转化这一步, 不要以序列为单位去看, 而是以序列的元素去看
- 这个容斥,可以想到bitset优化处理.
- 以元素为单位,建立n的bitset, 以w权值 排一个序,
- 枚举 i, 往前面找一个j 使得 i j, 最小, 这里就利用bitset的特性进行|处理, 然后在取反, 找到第一个 1 的位置 _Find_first(),
- 但是会爆空间, 于是对于出现次数小于 B 的数 进行暴力处理, 利用暴力平衡一下
题解代码:
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #include <ext/rope> using namespace std; #define fi first #define se second #define pb push_back #define eb emplace_back #define mp make_pair #define gcd __gcd #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define rep(i, n) for (int i=0; i<(n); i++) #define rep1(i, n) for (int i=1; i<=(n); i++) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define endl "\n" typedef long long ll; typedef unsigned long long ull; typedef unsigned uint; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ll> vll; typedef vector<vector<ll>> vvll; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; constexpr int N = 1e5 + 5; constexpr int M = 5; constexpr int T = 1000; #pragma GCC target("popcnt") int a[N][M]; int elem[N * M]; vi idx[N * M]; unique_ptr<bitset<N>> good[N * M]; bitset<N> state; int w[N]; int ord[N]; int conv[N]; int32_t main() { fastio; int n, m; cin >> n >> m; int sz = 0; rep(i, n) { rep(j, m) cin >> a[i][j], elem[sz++] = a[i][j]; cin >> w[i]; } sort(elem, elem + sz); sz = unique(elem, elem + sz) - elem; iota(ord, ord + n, 0); sort(ord, ord + n, [&](int i, int j) {return w[i] < w[j];}); rep(i, n) conv[ord[i]] = i; rep(i, n) { sort(a[i], a[i] + m); rep(j, m) { int v = lower_bound(elem, elem + sz, a[i][j]) - elem; a[i][j] = v; if(!j || a[i][j] != a[i][j - 1]) idx[v].pb(conv[i]); } } rep(i, sz) if(idx[i].size() >= T) { good[i] = make_unique<bitset<N>>(); good[i] -> set(); for(int v: idx[i]) good[i] -> reset(v); } int ans = INT_MAX; rep(i, n) { state.set(); state[conv[i]] = 0; rep(j, m) if(!j || a[i][j] != a[i][j - 1]) { int v = a[i][j]; if(idx[v].size() < T) for(int x: idx[v]) state[x] = 0; else state &= *good[v]; } int id = state._Find_first(); if(id >= n) continue; else { id = ord[id]; ans = min(ans, w[i] + w[id]); } } cout << (ans == INT_MAX ? -1 : ans) << endl; }
View Code
后记:
- bitset的每一次操作的复杂度为 其大小/w, w一般为32 ???
- bitset的相关函数很重要
原文地址:http://www.cnblogs.com/Lamboofhome/p/16911825.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性