首页 > 代码库 > Coder-Strike 2014 - Finals (online edition, Div. 2)——Bug in Code
Coder-Strike 2014 - Finals (online edition, Div. 2)——Bug in Code
题目链接
- 题意:
给定n个数对(a, b),现在求有多少个数对(x, y)(1 <= x、y <= n)满足至少k个数对。x,y满足一个数对(a, b)当且仅当x、y出现在数对(a, b)中至少一次
3?≤?n?≤?3·105 - 分析:
不妨设选定两个数x、y,那么这对的值应该是cnt[x] + cnt[y] - cnt[(x, y)]。思考方向:
1.考虑(x, y):这样的复杂度是n*n的,且没办法降低,所以不可解
2.单独考虑一个x:现在一个明显的想法是二分找到所有满足cnt[x] + cnt[y] >= goal的个数,但是由于少减去了cnt[(x, y)],所以答案会包括一部分不正确的。但是(x, y)的对数是有限的,所以我们可以枚举所有的(x, y),看看它是否算在了答案中且是否合法
const int MAXN = 310000; struct Node { int n, num; int operator< (const Node& a) const { return num < a.num; } } ipt[MAXN]; int cnt[MAXN]; int cmp(Node& a, int b) { return a.num < b; } int main() { // freopen("in.txt", "r", stdin); int n, k, a, b; while (~RII(n, k)) { CLR(cnt, 0); map<pair<int, int>, int> mp; FE(i, 1, n) ipt[i].n = i; FE(i, 1, n) ipt[i].num = 0; REP(i, n) { RI(a); ipt[a].num++; cnt[a]++; RI(b); ipt[b].num++; cnt[b]++; if (a > b) swap(a, b); mp[MP(a, b)]++; } sort(ipt + 1, ipt + n + 1); LL ans = 0; FE(i, 1, n) { int ind = lower_bound(ipt + i + 1, ipt + n + 1, k - ipt[i].num, cmp) - ipt; ans += n - ind + 1; } FC(it, mp) { a = (it->first).first; b = (it->first).second; if (cnt[a] + cnt[b] >= k && cnt[a] + cnt[b] - it->second < k) ans--; } cout << ans << endl; } return 0; }
Coder-Strike 2014 - Finals (online edition, Div. 2)——Bug in Code
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。