C++博客-ArefaElvis

CSU校赛J题(Burnside)

ArefaElvis — Sun, 10 Oct 2010 15:17:00 GMT

这道题校赛时没人过，现在拿出来折腾了一番，着实经典，在此膜拜一下罗德安。

Problem J. Smallbox魔方

Description

n阶魔方是一个n×n×n的立方体，有6个面，每个面又分为n×n个小块，每个小块都可以涂上不同的颜色，如右边的图中分别是3阶和2阶魔方。

高阶魔方同时兼备了收藏，鉴赏及实用价值，而高阶的魔方内部构造极为复杂，设计困难。针对这个问题，smallbox公司推出了专门用于观赏的魔方，这种魔方不能拧动，为了能使魔方能展现不同的图案，smallbox魔方配有6种不同颜色的贴纸，用户可以根据自己的喜好在每个小色块上贴上不同的颜色，纸一旦贴上就不能更改了，当然你仍然可以把整个魔方拿起来再换一个角度来摆放。

一个smallbox魔方配有六种不同颜色的贴纸，共6×n×n张。每种颜色的贴纸数量已知。现在由你来把这些贴纸贴到这个魔方上，使魔方表面的每个小色块都恰好被贴上一张贴纸，那么你有多少种不同的贴纸方案呢？

如果一种贴纸方案能通过变换摆放方式得到另一种方案，那么这两种方案算同一种。

Input

第一行一个正整数T，表示测试数据的组数。每组数据有两行，第一行一个数n，1 ≤ n ≤ 50，表示这个smallbox魔方是n阶的。第二行6个数a₁,a₂.a₃,a₄,a₅,a₆，表示每种颜色的贴纸数量，0 ≤ a_i ≤ 6×n×n，这六个数的总和等于6×n×n。

Output

对应每组输入数据，输出一行，包含一个数，即贴纸方案总数，这个数很大，你只需要输出它除以1000,000,007的余数。

Sample Input

5 1 0 0 0 0

1 1 1 1 1 1

1 23 0 0 0 0

1 1 22 0 0 0

1 53 0 0 0 0

Sample output

正方体的空间24个置换如下：
1. 绕中心轴转动(共3*2个) （n分偶,奇讨论）
转动270度，90度两种情况

若为偶数有长度为4的循环节。
若为奇数有长度为4的循环节和两个长度为1的循环节。

转动180度

若 n为偶数每个循环节长度为2
若 n为奇数两个长度为1的循环节，其他长度为2

2. 绕某个中心轴转360度（虽然有3个轴但是是同一个置换，公1个）
每个循环节长度为1

3. 绕连接对边的中心的轴转动180度（共6个）
循环节长度为 2 (通过在魔方上标号，转动揣摩出来的)

4.绕体对角线轴转动120度,240度（共4*2个）
循环节长度为 3

所以总共有 1+3*3+6*1+4*2=24 个置换。

奇偶共有：
4*2个置换*循环节长度为3 + 6个置换*循环节长度为2 + 1个置换*循环节长度为1

奇数还有:
(3*2)个置换*(两个长度为1的循环节其他长度为4）+ 3个置换*（两个长度为1的循环节其他长度为4）
偶数还有:
(3*2)个置换*(循环节长度为4)+ 3个置换*（循环节长度为2）

  1 #include
  2 #include
  3 #include
  4
  5 using namespace std;
  6
  7 typedef long long LL;
  8
  9 const int max_n=15000+5;
10 const int MOD=1000000007;
11
12 LL fac[max_n],inv[max_n],facv[max_n];    //fac[n]=n!%MOD (facv[n]*fac[n])=1;    (inv[n]*n)%MOD=1
13
14 LL mypow(LL a,int b){
15     LL res=1;
16     for(;b;b>>=1){
17         if(b&1)    res=(res*a)%MOD;
18         a*=a;    a%=MOD;
19     }
20     return res;
21 }
22 LL cal_inv(int t){
23     return mypow((LL)t,MOD-2);
24 }
25
26 void ini(){
27     fac[0]=1;    facv[0]=1;
28     for(int i=1;i 29         inv[i]=cal_inv(i);
30         facv[i]=(facv[i-1]*inv[i])%MOD;
31         fac[i]=(fac[i-1]*i)%MOD;
32     }
33 }
34
35 int col[6],N;
36
37 int gcd(int a,int b){
38     if(b==0)    return a;
39     return gcd(b,a%b);
40 }
41
42 LL solve(int t){
43     int b[6],tot=0;
44     for(int i=0;i<6;i++){
45         b[i]=col[i]/t;
46         tot+=b[i];
47     }
48     LL res=1;
49     res=(res*fac[tot])%MOD;
50     for(int i=0;i<6;i++){
51         res=(res*facv[b[i]])%MOD;
52     }
53     return res;
54 }
55 int main()
56 {
57     int T;
58     ini();
59     scanf("%d",&T);
60
61     for(int ncas=1;ncas<=T;ncas++){
62
63         scanf("%d",&N);
64         int e=0;
65         for(int i=0;i<6;i++){
66             scanf("%d",&col[i]);
67             e=gcd(e,col[i]);
68         }
69
70         LL ans=0;
71         ans = (ans+solve(1))%MOD;
72         if(e%2==0){
73             ans = (ans+6*solve(2) )%MOD;
74         }
75         if(e%3==0){
76             ans = (ans+8*solve(3) )%MOD;
77         }
78
79         if(N&1){    //N为奇数
80             for(int i=0;i<6;i++){
81                 for(int j=0;j<6;j++){
82                     if((i==j&&col[i]>=2)||(i!=j&&col[i]&&col[j])){
83                         col[i]--;    col[j]--;
84                         int t=0;
85                         for(int k=0;k<6;k++){
86                             t=gcd(t,col[k]);
87                         }
88                         if(t%2==0){
89                             ans=(ans+3*solve(2))%MOD;
90                         }
91                         if(t%4==0){
92                             ans = (ans+6*solve(4))%MOD;
93                         }
94                         col[i]++;    col[j]++;
95                     }
96                 }
97             }
98         }else{
99             if(e%2==0){
100                 ans = (ans+3*solve(2))%MOD;
101             }
102             if(e%4==0){
103                 ans = ( ans+6*solve(4) )%MOD;
104             }
105         }
106         ans=(ans*inv[24])%MOD;
107         printf("%lld\n",ans,N);
108     }
109     return 0;
110 }
111

ArefaElvis 2010-10-10 23:17 发表评论

UVA 11255 Necklace (Burnside)

ArefaElvis — Sun, 10 Oct 2010 11:52:00 GMT

题意：有三种不同颜色的珍珠(pearls)白（W颗），灰（G颗），黑（B颗），其中3<=W+G+B<=40，问用这些珍珠可以串成多少种(W+G+B)长的不同的项链（项链可在平面内转动，也可翻转）。
令W+G+B=N;

先考虑转动，项链可转动(2PI)*K/N (1<=K<=N)共N个不同角度，而K置换(转动 (2PI)*K/N 度)可表示为 gcd(K,N)个长度为 N/gcd(K,N)的循环节，很容易发现如果gcd(W,G,B)%gcd(K,N)!=0,那么K置换的固定构型为0个，如果 gcd(W,G,B)%gcd(K,N)==0 那么 K置换的固定构型为 W/gcd(K,N), G/gcd(K,N),B/gcd(K,N)三类型的序列排列个数，即K置换的固定构型数为：C[F[W+G+B],F[W]] * C[F[G+B],B]（另F[X]=X/gcd(K,N),X={W,G,B,X+X} , C[X,Y]为组合数）。

现在考虑翻转。

如果N为奇数，那么翻转的 N个置换都是{一个长度为1的循环节+(N-1)/2个长度为2的循环节}，这样如果 W,G,B三个都为奇数，那么固定构型数为0，如果只有一个为奇数（假设W为奇数）那么固定构型数为 (W-1)/2, G/2,B/2的三类型序列排列个数。

如果N为偶数，那么有 N/2个置换为{N/2个长度为2的循环节}，这种情况必须W,G,B都为偶数，而且很好处理。
还有N/2个置换为{（N-2）/2个长度为2的循环节，2个长度为1的循环节}，如果W,G,B都是偶数，那么固定构型数为 {(W>=2)*{(W-2)/2,G/2,B/2 的三类型排列数} + （B>=2)*{W/2,G/2,(B-2)/2的三类型排列数} + (G>=2)*{W/2,(G-2)/2,G/2的三类型排列数}}，如果W,G,B有两个是奇数（假设为W,G),那么固定构型数为2*{(W-1)/2,(G-1)/2,B的三类型排列数}。

由于其中涉及到的三类型排列数最大为 40!/14!/13!/13! = 2.4～* 10^17, 而max(unsigned long long )=2^64-1=1.8～*10^19 ,所以用unsigned long long 即可解决。

  1 #include
  2 #include
  3 #include
  4
  5 using namespace std;
  6
  7 const int max_n=41;
  8 typedef unsigned long long ULL;
  9
10 ULL c[max_n][max_n];
11
12 void ini(){
13     c[0][0]=1;
14     for(int i=1;i 15         for(int j=0;j<=i;j++){
16             if(j==0||j==i)    c[i][j]=1;
17             else{
18                 c[i][j]=c[i-1][j-1]+c[i-1][j];
19             }
20         }
21     }
22 }
23
24 int W,B,G,N;
25 int phi[max_n];
26
27 void gen_phi(int N){
28     int i,j;
29     phi[1]=1;
30     for(i=2;i<=N;i++)    phi[i]=i;
31     for(i=2;i<=N;i+=2)    phi[i]/=2;
32     for(i=3;i<=N;i+=2){
33         if(phi[i]==i){
34             for(j=i;j<=N;j+=i){
35                 phi[j]=phi[j]/i*(i-1);
36             }
37         }
38     }
39 }
40 int gcd(int a,int b){
41     if(b==0)    return a;
42     return gcd(b,a%b);
43 }
44
45 int main()
46 {
47     int T;
48     ini();
49     gen_phi(max_n-1);
50
51     scanf("%d",&T);
52     for(int ncas=1;ncas<=T;ncas++){
53         scanf("%d%d%d",&W,&B,&G);
54         N=W+B+G;
55
56         ULL ans=0;
57
58         int e=gcd(W,B);    e=gcd(e,G);    //e为最小单元
59
60         for(int i=1;i*i<=N;i++){
61             if(N%i==0){
62                 if(i*i==N && (e%i==0) ){
63                     ans += phi[i]*c[N/i][W/i]*c[(B+G)/i][B/i];
64                 }else{
65                     if(e%(i)==0){
66                         ans += phi[i]*c[N/i][W/i]*c[(B+G)/i][B/i];
67                     }
68                     if(e%(N/i)==0){
69                         int t=N/i;
70                         ans += phi[t]*c[N/t][W/t]*c[(B+G)/t][B/t];
71                     }
72                 }
73             }
74         }
75
76         ULL part1=ans/N;    ans=0;
77
78         int odd_cnt=(W&1)+(B&1)+(G&1);
79         if(N&1){  // 奇数个可分成一个长度为1的循环节和(N-1)/2个长度为2的循环节。
80             if(odd_cnt==1){
81                 int T=N-1;
82                 if(W&1){
83                     ans += c[T/2][(W-1)/2]*c[(B+G)/2][B/2]*N;
84                 }else if(B&1){
85                     ans += c[T/2][(B-1)/2]*c[(W+G)/2][W/2]*N;
86                 }else if(G&1){
87                     ans += c[T/2][(G-1)/2]*c[(W+B)/2][W/2]*N;
88                 }
89             }
90         }else{
91
92             if(odd_cnt==0){
93                 ans += N/2*c[N/2][W/2]*c[(B+G)/2][B/2];
94                 int T=N-2;
95                 if(W>=2){
96                     ans += N/2*c[T/2][(W-2)/2]*c[(B+G)/2][B/2];
97                 }
98                 if(B>=2){
99                     ans += N/2*c[T/2][(B-2)/2]*c[(W+G)/2][W/2];
100                 }
101                 if(G>=2){
102                     ans += N/2*c[T/2][(G-2)/2]*c[(W+B)/2][W/2];
103                     //因为这个地方笔误，又再找各种莫须有的错误，让无聊的WA很嚣张的绽放了3次
104                     //另又改成JAVA，提交Runtime Error 才发现。
105                 }
106             }
107             if(odd_cnt==2){
108                 int T=N-2;
109                 if(!(W&1)){
110                     ans += N*c[T/2][W/2]*c[(B+G-2)/2][(B-1)/2];
111                 }else if(!(B&1)){
112                     ans += N*c[T/2][B/2]*c[(W+G-2)/2][(G-1)/2];
113                 }else if(!(G&1)){
114                     ans += N*c[T/2][G/2]*c[(W+B-2)/2][(W-1)/2];
115                 }
116             }
117         }
118         ans/=N;
119         ans=(ans+part1)/2;
120         printf("%llu\n",ans);
121     }
122     return 0;
123 }
124

ArefaElvis 2010-10-10 19:52 发表评论

POJ_2888 Magic Bracelet (有限制的Burnside , 矩阵幂 )

ArefaElvis — Sat, 09 Oct 2010 16:33:00 GMT

给一串有n(1<=10^9 && gcd(n,9973))颗珠子的项链染色，已知某些{ci,cj}（i可能等于j）颜色不能出现在相连的珠子中。项链在平面内转动（不能翻转）得到的为等价方案，求不同的染色方案数mod 9973。

由于项链只能绕中心转动，而不能翻转，所以有一个很好的性质：项链转 2*PI*k/n个角度的置换共有 gcd(k,n)个长度均为len=n/gcd(k,n)的循环节，而且可以发现，若gcd(k,n)>1,则从某一个编号的项链开始顺时针（或逆时针）相邻的len个珠子两两处于不同的循环节中。这样k置换（1<=k<=n）的固定构型数等价于：
给长度为gcd(k,n)的序列染色（没写错，确实是序列），其中所有相邻编号（beg和end为相邻的）为合法对（若color i 和 color j 能够分别出现在相邻的两珠子上，那么说(i,j)是合法对）的染色方案。

假设一个长度为 L 的序列的合法表示为 a1,a2,……,aL 那么(a1,a2)(a2,a3),……，(a(L-1),aL),(aL,a1)必定都为1 ，所以令 g[ai,aj]=1表示（ai,aj）为合法对，g[ai,aj]=0表示(ai,aj)为非法对。那么以a1开头的合法序列为k个那么必定存在且仅存在k个不同的序列{b1,b2,b3,b4,……，b(L-1)}满足 g[a1,b1]*g[b1,b2]*……g[b(L-2),b(L-1)]*g[b(L-1),a1]=1; 这样很显然就是矩阵g[ai,aj]的L次幂中g[a1,a1]的的值。

很显然，这题可以用矩阵快速幂取模。

  1 #include
  2 #include
  3 #include
  4 using namespace std;
  5
  6 const int max_n=15;
  7 const int MOD=9973;
  8 int N;
  9
10 struct Mat{
11     int mat[max_n][max_n];
12 };
13
14 Mat operator*(Mat a,Mat b){
15     Mat c;
16     memset(c.mat,0,sizeof(c.mat));
17     for(int i=0;i 18         for(int j=0;j 19             for(int k=0;k 20                 if(a.mat[i][k] && b.mat[k][j]){
21                     c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
22                 }
23             }
24         }
25     }
26     return c;
27 }
28
29 Mat operator^(Mat A,int x){
30     Mat c;
31     memset(c.mat,0,sizeof(c.mat));
32     for(int i=0;i 33     for(;x;x>>=1){
34         if(x&1){
35             c=c*A;
36         }
37         A=A*A;
38     }
39     return c;
40 }
41
42 int mypow(int a,int b){
43     int res=1;
44     for(;b;b>>=1){
45         if(b&1){
46             res*=a;    res%=MOD;
47         }
48         a*=a;    a%=MOD;
49     }
50     return res;
51 }
52
53 int M,K;
54
55 int PHI(int n){
56     int i,res=n;    long long j;
57     for(i=2,j=4LL;j<=(long long)n;i++,j+=i+i-1){
58         if(!(n%i)){
59             res=res/i*(i-1);
60             while(!(n%i))    n/=i;
61         }
62     }
63     if(n>1)    res=res/n*(n-1);
64     return res%MOD;
65 }
66
67 Mat A;
68 int solve(int p){
69     int res=0;
70     Mat C=A^p;
71     for(int i=0;i 72         res+=C.mat[i][i];    res%=MOD;
73     }
74     return res;
75 }
76 int main()
77 {
78     int T;
79
80     scanf("%d",&T);
81
82     for(int ncas=1;ncas<=T;ncas++){
83         scanf("%d%d%d",&M,&N,&K);
84         int u,v;
85         for(int i=0;i 86             for(int j=0;j 87                 A.mat[i][j]=1;
88             }
89         }
90         for(int i=0;i 91             scanf("%d%d",&u,&v);
92             A.mat[u-1][v-1]=A.mat[v-1][u-1]=0;
93         }
94
95         int ans=0;
96
97         for(int p=1;p*p<=M;p++){
98             if(M%p==0){
99                 if(p*p==M){
100                     ans = (ans+ PHI(p)*solve(p) )%MOD;
101                 }else{
102                     ans = (ans+ PHI(p)*solve(M/p)+ PHI(M/p)*solve(p) )%MOD;
103                 }
104             }
105         }
106
107         int inv=mypow((M%MOD),MOD-2);    //晕，这里没取模导致超出整形，WA了三次
108         ans*=inv; ans%=MOD; //逆元。
109         printf("%d\n",ans);
110     }
111     return 0;
112 }
113

ArefaElvis 2010-10-10 00:33 发表评论

SGU 282 Isomorphism (Burnside)

ArefaElvis — Sat, 09 Oct 2010 11:07:00 GMT

求：用C种颜色染N阶完全图的不同染色方案(mod P),P为素数（两个染色方案是相同的当且仅当顶点编号重排后各边的颜色相同），
其中1<=N<=53,1<=C<=1000;

很明显这个群有N!个置换（顶点的排列）,一个置换可表示为 (a1,a2,……,am)(b1,b2,……,bn)(c1,c2,……,ck) ……循环节的形式，其中m+n+k=N。以下证明：

1：在一个置换下，关联的顶点都在某个L长的循环节的边，可分成一共floor(L/2)个等价类。
2：在一个置换下，关联的顶点分别在两个长度为L1,L2的循环节内的边，可分成一共gcd(L1,L2)个等价类。

证明1：在下面的证明中[x] 表示 (x mod L)

由于边{a[i],a([i]+[k])},{a[j],a([j]+[k])} ([k]>=1 && k<=L-1)在同一个等价类，而且 {a[i],a([i]+[k])} 与 {a[i],a([i]+[L-k])}在同一个等价类，所以
[k]={1,2,3,……,floor(L/2)} 和 [k]={L-1,L-2,……,ceil(L/2)}分别对应同一个等价类。所以1得证。

证明2：

若v1属于{a1,a2,……,am},v2属于{b1,b2,……,bn},则{v1,v2}的等价边为 {v1+[t],v2+[t]},其中,在t从 1开始增加的过程中，首次出现v1==v1+[t] && v2==v2+[t] 是在 t=lcm(m,n)的时候，所以每一条边共有lcm(m,n)条等价边，所以共有 m*n/lcm(m,n)个等价类即为 gcd(m,n);

如果一个置换可以表示为长度分别为 L1,L2,……,Lk(非降序排列)的k个循环节，那么在这个置换下边共有 n=Sum(floor(Li/2) ) + Sum(gcd(Li,Lj))个置换群;
而 k1*L1+k2*L2+k3*L3+……km*Lm=N(其中 Li != Lj for i != j) 的置换共有
(N! *( (L1-1)! )^k1 *( (L2-1)!)^k2 *……* ((Lm-1)!)^km ) / ( ( (L1!)^k1 * (L2!)^k2 * (L3!)^k3*……(Lm!)^km )* (k1! * k2! * k3!*……*km!) )
即为 tot = N!/( (L1^k1)*(L2^k2)*(L3^k3)*……(Lm^km) * (k1! * k2! * k3! * …… *km!));
所以可以表示成这个形式(k1*L1+k2*L2+k3*L3+……+km*Lm)的固定构型个数为 ans= n* pow (C,tot) 个。

1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int max_n=60;
7 typedef long long LL;
8
9 int N,C,P;
10
11 LL facv[max_n],inv[max_n];
12
13 LL mypow(LL a,LL b){
14     LL res=1,radix=a%P;
15     while(b){
16         if(b&1){
17             res*=radix;    res%=P;
18         }
19         radix*=radix;    radix%=P;
20         b>>=1;
21     }
22     return res;
23 }
24
25 LL cal_inv(int i){
26     return mypow(i,P-2);
27 }
28
29 int gcd(int i,int j){
30     if(j==0)    return i;
31     return gcd(j,i%j);
32 }
33 void ini(){
34     facv[1]=1;
35     inv[1]=1;
36     for(int i=2;i<=N;i++){
37         inv[i]=cal_inv(i);
38         facv[i]=facv[i-1]*inv[i];    facv[i]%=P;
39     }
40 }
41
42 int factor[max_n][2];    LL ans;
43
44 void search(int sum,int top){
45     if(sum==N){
46         LL n=1;
47         for(int i=1;i<=top;i++){
48             int len=factor[i][0],cnt=factor[i][1];
49             n*=mypow(inv[len],cnt); n%=P;
50             n*=facv[cnt];    n%=P;
51         }
52         LL tot=0;
53         for(int i=1;i<=top;i++){
54
55             int len=factor[i][0],cnt=factor[i][1];
56             tot+=cnt*(len/2);            //the same circle
57             tot+=cnt*(cnt-1)/2*len;        //two different circle
58
59             for(int j=i+1;j<=top;j++){
60                 int len_j=factor[j][0],    cnt_j=factor[j][1];
61                 tot+=(cnt*cnt_j*gcd(len_j,len));
62             }
63         }
64         ans+=(n*mypow(C,tot))%P;    ans%=P;
65         return;
66     }
67     if(sum+factor[top][0]>=N){
68         return;
69     }
70     for(int i=factor[top][0]+1;i<=N-sum;i++){
71         for(int j=1;sum+i*j<=N;j++){
72             factor[top+1][0]=i;    factor[top+1][1]=j;
73             search(sum+i*j,top+1);
74         }
75     }
76 }
77 int main()
78 {
79     while(scanf("%d%d%d",&N,&C,&P)!=EOF){
80         ini();
81         factor[0][0]=0;
82         ans=0;
83         search(0,0);
84         printf("%lld\n",ans);
85     }
86     return 0;
87 }
88

ArefaElvis 2010-10-09 19:07 发表评论

HDU_3577 (退化的线段树TLE到想呐喊了)

ArefaElvis — Fri, 24 Sep 2010 09:46:00 GMT

http://acm.hdu.edu.cn/showproblem.php?pid=3577

题意：某路火车共有 N(N<=1000000：这个数字对于站点来说着实惊人)个站点,有Q个人先后去买[bi,ei) {for 1<=i<=Q}的票，问在保证火车上总人数总不超过K的情况下哪些人可以买到票。

TLE的实现：用full[i]标记此段是否被覆盖，在插入的时候，如果目标线段覆盖了子线段并且子线段的full是false，还不能插入，只有当full[i]==true，并且目标线段覆盖了子线段才插入此子线段。细想一下，如果插入的线段都是比较短的时候，这个线段树可能退化成插入节点，而不再是插入线段了。

TLE的代码(免得忘了这个，下次再写一个)

1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 const int max_n=1000005;
7 int tree[max_n*4+1],full[max_n*4+1];
8 int k,Q;
9 void query(int i,int lt,int rt,int beg,int end,bool &legal){
10         if(full[i]){
11                 if(tree[i]>=k){
12                         legal=false;
13                 }
14                 return;
15         }
16         int mid=(lt+rt)/2;
17         if(beg<=mid){
18             query(i<<1,lt,mid,beg,end,legal);
19         }
20         if(end>=mid+1){
21                 query((i<<1)+1,mid+1,rt,beg,end,legal);
22         }
23 }
24
25 void insert(int i,int lt,int rt,int beg,int end){
26         if(beg<=lt&&end>=rt&&full[i]){
27                 tree[i]++;    full[i]=true;
28                 return;
29         }
30         if(full[i]){
31                 full[i]=false;    full[(i<<1)]=full[(i<<1)+1]=true;
32                 tree[i<<1]=tree[(i<<1)+1]=tree[i];
33         }
34         int mid=(lt+rt)/2;
35         if(beg<=mid){
36                 insert(i<<1,lt,mid,beg,end);
37         }
38         if(end>=mid+1){
39                 insert((i<<1)+1,mid+1,rt,beg,end);
40         }
41 }
42 int main()
43 {
44
45         int T;
46         scanf("%d",&T);
47         for(int ncas=1;ncas<=T;ncas++){
48                 scanf("%d%d",&k,&Q);
49
50                 tree[1]=0,full[1]=true;
51                 printf("Case %d:\n",ncas);
52                 int beg,end;
53                 for(int i=0;i<Q;i++){
54                         scanf("%d%d",&beg,&end);
55                         bool legal=true;
56                         query(1,1,max_n-1,beg,end-1,legal);
57                         if(legal){
58                                 insert(1,1,max_n-1,beg,end-1);
59                                 printf("%d ",i+1);
60                         }
61                 }
62                 printf("\n\n");
63         }
64 }
65

改进：设两个属性： cover[i]记录完全覆盖次数， max_subcover[i] ：子段覆盖最大次数。

ArefaElvis 2010-09-24 17:46 发表评论

2-SAT问题总结

ArefaElvis — Wed, 22 Sep 2010 09:44:00 GMT

摘要: 1. http://acm.pku.edu.cn/JudgeOnline/problem?id=3207题意：在一个圆圈上顺时针或逆时针排好N个点(0-->N-1)，现在要以给定的M组端点画M条曲线段，曲线段可在圆内或圆外，判断是否存在一种画法使得这M条曲线段不相交。分析：每一条曲线段可置于圆内或圆外。这样可用两个顶点分别表示曲线段的摆放情况，例如（顶点2*i表示第i条曲线段置于... 阅读全文

ArefaElvis 2010-09-22 17:44 发表评论