Heim  >  Artikel  >  Web-Frontend  >  Coder-Strike 2014

Coder-Strike 2014

WBOY
WBOYOriginal
2016-06-24 12:05:291072Durchsuche

codeforces.com/contest/421/problem/D

  • 题意:
    给定n个数对(a, b),现在求有多少个数对(x, y)(1 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, 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   <br>  <br>  <p></p> 
    Stellungnahme:
    Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn