本文主要是介绍Coder-Strike 2014 - Finals (online edition, Div. 1) C. Bug in Code，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
水题一道，但是卡了一个早上
我本着数据结构去做的，知道用树状数组就是没有想出来维护的方法....
用树状数组维护，提名 i 次的人有getsum个
注意一点的是，如果怀疑的人是 1 2，然后有一个人是同时提名这两个的，那么这个人就会被算两次
因此我每次用树状数组统计的时候，将同时和第i个人提名的各个人数减1，再统计，然后再恢复（这是一种很麻烦的做法，我是渣渣别介意
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define eps 1e-9
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62
#define pb(x) push_back(x)using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef vector<int> vi;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------#define lowbit(x) ((i)&(-i))const int MAXN = 300010;
int n, p;
int num[MAXN], c[MAXN];
vi e[MAXN];ll getsum(int i)
{ll res = 0;for(i++; i; i -= lowbit(i))res += c[i];return res;
}void update(int i, int x)
{for(i++; i < MAXN; i += lowbit(i))c[i] += x;
}int main()
{read(n),read(p);for(int i=0; i<n; i++){int a, b;read(a), read(b);e[a].pb(b);e[b].pb(a);}int cnt=0;ll ans=0;for(int i=1; i<=n; i++){num[i]=e[i].size();update(num[i], 1);}for(int i = 1; i <= n; i++){for(int j=0; j<e[i].size(); j++){update(num[e[i][j]], -1);update(--num[e[i][j]], 1);}if(num[i] >= p)ans+=n-1;elseans+=n-1-getsum(p-num[i]-1)+(num[i] <= p-num[i]-1);for(int j=0; j<e[i].size(); j++){update(num[e[i][j]], -1);update(++num[e[i][j]], 1);}}write(ans/2),putchar('\n');return 0;
}
下面的代码是S菊苣的解答
他说用的是容斥原理，思路和上面一样的
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> mp;
const int MAXN=300005;
int x[MAXN], y[MAXN];
int cnt[MAXN], cnt2[MAXN];
int main(){int n, p;cin>>n>>p;mp.clear();for(int i=0; i<n; i++){scanf("%d%d",&x[i],&y[i]);--x[i]; --y[i];cnt[x[i]]++; cnt[y[i]]++;cnt2[x[i]]++; cnt2[y[i]]++;if(x[i]>y[i]) swap(x[i],y[i]);mp[make_pair(x[i],y[i])]++;}sort(cnt,cnt+n);long long ans=0;for(int i=n-1; i>=0; i--){int c=lower_bound(cnt,cnt+i,p-cnt[i])-cnt;ans+=i-c;}for(map<pair<int,int>,int>::iterator it=mp.begin(); it!=mp.end(); it++){int f=it->first.first;int s=it->first.second;int d=it->second;if(cnt2[f]+cnt2[s]-d<p&&cnt2[f]+cnt2[s]>=p) ans--;}cout<<ans<<endl;return 0;
}这篇关于Coder-Strike 2014 - Finals (online edition, Div. 1) C. Bug in Code的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
