SGU 476

这两天我在拼命刷SGU。。本来想弄哥country hero爽一下的。。结果没成功

这道题是说一个教练,有3*N个学生,要把他们3个3个分成N组,同时有k个3元组的学生不能成为一组,有多少种方法。

由于N<=1000,k<=20。。我的办法是利用冗斥原理来做,枚举每移一种k个3元组的子集,然后分别计算各种方法数。。就可以了。。

但是这样是要TLE的。。我发现不用每一个算出来都加一下。。由于实际上+的值只有k+1种,弄一个add数组表示每种情况被+的次数。。到最后乘一下就可以了。。

Code:因为是高精度,所有我用了Java

import java.math.*;import java.util.*;import static java.math.BigInteger.*;public class Solution { static Scanner in=new Scanner(System.in); static BigInteger[] P; static int[] Add; static int[][] L; static int n,k; static void CalP() { BigInteger now=ONE; if(n<=k) P[n]=ONE; for(int i=1;i<=n;i++) { now=now.multiply(valueOf(i*3-2)); now=now.multiply(valueOf(i*3-1)); now=now.multiply(valueOf(i*3)); now=now.divide(valueOf(6)); now=now.divide(valueOf(i)); if(n-i<=k) P[n-i]=now; } } static boolean[] In; static void dfs(int pos,int ch) { if(pos==k) { if(ch%2==0) Add[ch]++; else Add[ch]–; return; } boolean check=true; for(int i=0;i<3;i++) if(In[L[pos][i]]) { check=false; break; } if(check) { for(int i=0;i<3;i++) In[L[pos][i]]=true; dfs(pos+1,ch+1); for(int i=0;i<3;i++) In[L[pos][i]]=false; } dfs(pos+1,ch); } public static void main(String[] args) { n=in.nextInt();k=in.nextInt(); L=new int[k][3]; for(int i=0;i<k;++i) { for(int j=0;j<3;j++) L[i][j]=in.nextInt()-1; } P=new BigInteger[k+1]; Add=new int[k+1]; In=new boolean[n*3]; CalP(); dfs(0,0); BigInteger Ans=ZERO; for(int i=0;i<=k;i++) if(P[i]!=null) Ans=Ans.add(P[i].multiply(valueOf(Add[i]))); System.out.println(Ans); }}

本高亮代码使用codeHl生成,查看详情

3 thoughts on “SGU 476

  1. of course like your web-site but you need to test the spelling on several of your posts. Several of them are rife with spelling problems and I find it very bothersome to inform the reality nevertheless Ill certainly come again again.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>