朋友 (HGOI 2019.2.16 T2)

2019-02-16 16:09:14


题目大意

数据范围

n<=100000,a[i][j]<=50

解法

这道题竟然花了我好一段时间去想。。

我一开始还在琢磨Hash之类的orz

然后,想到正解后:tmd怎么这么简单,wc怎么这么暴力,这么无脑(╯°Д°)╯︵┻━┻

其实就是一个四个圈的容斥,开一个一维数组,一个二维数组,一个三维数组,一个四位数组,分别记一下,有多少个人有这些一个或者两个或者三个或者四个数字。。减一下加一下balabala就好了

具体看代码,看不懂的就智障了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int SD,k[5];
int a[60];
int b[60][60];
int c[60][60][60];
int d[60][60][60][60];
int Clac(int x,int y,int p,int q)
{
    int res=a[x]+a[y]+a[p]+a[q]-b[x][y]-b[x][p]-b[x][q]-b[y][p]-b[y][q]-b[p][q]+c[x][y][p]+c[x][y][q]+c[x][p][q]+c[y][p][q]-d[x][y][p][q];
    a[x]++,a[y]++,a[p]++,a[q]++;
    b[x][y]++,b[x][p]++,b[x][q]++,b[y][p]++,b[y][q]++,b[p][q]++;
    c[x][y][p]++,c[x][y][q]++,c[x][p][q]++,c[y][p][q]++;
    d[x][y][p][q]++;
    return res;
}
int main()
{
    freopen("friend.in","r",stdin);
    freopen("friend.out","w",stdout);
    scanf("%d",&SD);
    while(SD--)
    {
        scanf("%d%d%d%d",&k[1],&k[2],&k[3],&k[4]);
        sort(k+1,k+5);
        printf("%d\n",Clac(k[1],k[2],k[3],k[4]));
    }
    return 0;
}