menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[容斥+三元环]BZOJ5407【girls】题解
apps BZOJ
local_offer 查看标签
comment 6 条评论

题目概述

JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪,但是三个妹子之间不能有冲突,一种方案 $(i,j,k),i<j<k$ 的贡献为:$Ai+Bj+Ck$ ,求所有合法方案的总贡献。

解题报告

很明显可以容斥:至少 $0$ 个冲突 $-$ 至少 $1$ 个冲突 $+$ 至少 $2$ 个冲突 $-$ 至少 $3$ 个冲突。

前面三个都很好算(就是比较烦QAQ),问题是怎么求 $3$ 个冲突的贡献,我们发现 $3$ 个冲突就是个三元环,所以只需要找三元环就行了,可以参考这篇Blog

示例程序

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
#define fr first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned long long ULL;
const int maxn=200000,maxm=200000;

int n,m,D[maxn+5];ULL A,B,C,ans;pair<int,int> e[maxm+5];
vector<int> pre[maxn+5],suf[maxn+5];vector<ULL> sum[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5],ti,vis[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline ULL C2(ULL n) {return n*(n-1)>>1;}
inline ULL Sum(ULL L,ULL R) {return (L+R)*(R-L+1)>>1;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);readi(m);readi(A);readi(B);readi(C);
    for (int i=1;i<=m;i++) {readi(e[i].fr);readi(e[i].sc);if (e[i].fr>e[i].sc) swap(e[i].fr,e[i].sc);}
    sort(e+1,e+1+m);m=unique(e+1,e+1+m)-e-1;
    for (int i=1;i<=m;i++) suf[e[i].fr].pb(e[i].sc);
    for (int i=1;i<=m;i++) swap(e[i].fr,e[i].sc);sort(e+1,e+1+m);
    for (int i=1;i<=m;i++) pre[e[i].fr].pb(e[i].sc);
    for (int i=1;i<=m;i++) D[e[i].fr]++,D[e[i].sc]++;
    for (int i=1;i<=m;i++) D[e[i].fr]<D[e[i].sc]?Add(e[i].fr,e[i].sc):Add(e[i].sc,e[i].fr);
    for (int i=0;i<n-2;i++) ans+=A*i*C2(n-i-1);
    for (int i=1;i<n-1;i++) ans+=B*i*i*(n-i-1);
    for (int i=2;i<n;i++) ans+=C*i*C2(i);
    for (int i=0;i<n;i++)
        for (int j=0,si=suf[i].size();j<si;j++){
            int u=suf[i][j];
            ans-=(A*i+B*u)*(n-1-u)+C*Sum(u+1,n-1);
            ans-=(A*i+C*u)*(u-i-1)+B*Sum(i+1,u-1);
            ans-=(B*i+C*u)*i+A*Sum(0,i-1);
        }
    for (int i=0;i<n;i++){
        int si=suf[i].size();sum[i].resize(si);if (si) sum[i][0]=suf[i][0];
        for (int j=1;j<si;j++) sum[i][j]=sum[i][j-1]+suf[i][j];
    }
    for (int i=0;i<n;i++)
        for (int j=0,si=suf[i].size();j<si;j++){
            int u=suf[i][j];
            ans+=(A*i+B*u)*(si-j-1)+C*(sum[i][si-1]-sum[i][j]);
            if (suf[u].size()) ans+=(A*i+B*u)*suf[u].size()+C*sum[u][suf[u].size()-1];
        }
    for (ULL i=0,sum=0;i<n;i++,sum=0)
        for (int j=0,si=pre[i].size();j<si;j++)
            {int u=pre[i][j];ans+=(B*u+C*i)*j+A*sum;sum+=pre[i][j];}
    for (int i=1;i<=m;i++){
        int x=e[i].fr,y=e[i].sc;ti++;
        for (int j=lnk[x];j;j=nxt[j]) vis[son[j]]=ti;
        for (int j=lnk[y];j;j=nxt[j])
            if (vis[son[j]]==ti){
                int a=x,b=y,c=son[j];if (a>b) swap(a,b);if (a>c) swap(a,c);if (b>c) swap(b,c);
                ans-=A*a+B*b+C*c;
            }
    }printf("%llu\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
    2019-03-22 22:11:32Minamoto
    keyboard_arrow_down
    2019-03-22 22:11:32

    jzTQL,各种意义上的TQL

    remove_red_eye访客
      2019-03-24 18:51:45CHNJZ
      keyboard_arrow_down
      2019-03-24 18:51:45
      @Minamoto 

      太fake了吧

      remove_red_eye
      访客
      2019-03-23 10:13:40ZigZagK
      keyboard_arrow_down
      2019-03-23 10:13:40
      @Minamoto 

      JZ可是人生赢家

      account_circle
      博主
        2019-03-23 14:19:14Minamoto
        keyboard_arrow_down
        2019-03-23 14:19:14
        @ZigZagK 

        您一定非常羡慕吧

        remove_red_eye
        访客
    2019-03-20 21:14:47chnjz
    keyboard_arrow_down
    2019-03-20 21:14:47

    我是这种人嘛 ⌇●﹏●⌇

    remove_red_eye访客
      2019-03-21 07:54:21ZigZagK
      keyboard_arrow_down
      2019-03-21 07:54:21
      @chnjz 

      你应该全部带走

      account_circle
      博主
keyboard_arrow_up