Coder-Strike 2014 - Finals (online edition, Div. 1) C:http://codeforces.com/problemset/problem/420/C
题意：每个人怀疑2个人。一个方案视为可能方案当且仅当有超过P个人支持这个方案。I支持方案J当且仅当J中至少有一个是I所怀疑的
题解：这一题简直是一一道模拟，真是虐心啊，调了很久，但是还是做出来了。统计每个数度数，然后找度数d[i]+d[j]>=p的对数，这里可以先把度数排个顺序，然后枚举i，然后用llower_bound（p-d[i]），找到第一个大于这个数的下标，然后用n+1减去就可以了。但是有重边的啊，这个是最麻烦的啊，假如说(3,5)出现了x次，那么实际上对于(3,5)这种方案支持的人数就是d[3]+d[5]-x,这么多，那么对于d[i]+d[j]>=p&&d[i]+d[j]-ct[edgenum]<p的话，说明这种方案被入选的原因是因为重边的存在，实际人数会少于p，所以是多算了。所以ans--。至于实现，看代码。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=3e5+10; 7 long long n,p; 8 long long deg[N],t1,t2; 9 long long deg1[N]; 10 long long ans; 11 long long ct[N]; 12 struct Node{ 13 long long x; 14 long long y; 15 }edge[N]; 16 int cmp(Node a,Node b){ 17 if(a.x<b.x)return true; 18 if(a.x==b.x&&a.y<b.y)return true; 19 return false; 20 } 21 int main(){ 22 while(~scanf("%I64d%I64d",&n,&p)){ 23 memset(deg,0,sizeof(deg)); 24 memset(deg1,0,sizeof(deg1)); 25 memset(ct,0,sizeof(ct)); 26 for(int i=1;i<=n;i++){ 27 scanf("%I64d%I64d",&t1,&t2); 28 deg[t1]++; 29 if(t1!=t2) 30 deg[t2]++; 31 deg1[t1]++; 32 if(t1!=t2) 33 deg1[t2]++; 34 if(t1>t2)swap(t1,t2); 35 edge[i].x=t1; 36 edge[i].y=t2; 37 } 38 sort(deg+1,deg+n+1); 39 ans=0; 40 for(int i=1;i<=n;i++){ 41 long long temp=lower_bound(deg+i+1,deg+n+1,p-deg[i])-deg; 42 if(temp<n+1) 43 ans+=(n-temp+1); 44 } 45 46 sort(edge+1,edge+n+1,cmp); 47 long long lastx=0,lasty=0,tp=1,pos=0; 48 for(int i=1;i<=n;i++){//去除重边，并且统计每条边出现的次数。 49 if(edge[i].x==lastx&&lasty==edge[i].y){ 50 tp++; 51 } 52 else{ 53 ct[pos]=tp; 54 tp=1; 55 edge[pos].x=lastx; 56 edge[pos++].y=lasty; 57 lastx=edge[i].x; 58 lasty=edge[i].y; 59 } 60 if(i==n&&edge[i].x==lastx&&lasty==edge[i].y){ 61 ct[pos]=tp; 62 tp=0; 63 edge[pos].x=lastx; 64 edge[pos++].y=lasty; 65 lastx=edge[i].x; 66 lasty=edge[i].y; 67 } 68 } 69 for(int i=1;i<pos;i++){//减去多算的部分 70 if((deg1[edge[i].x]+deg1[edge[i].y]>=p&°1[edge[i].x]+deg1[edge[i].y]-ct[i]<p)) 71 ans--; 72 } 73 printf("%I64d ",ans); 74 } 75 }