project euler 106(阅读理解)

發表於 更新於 分類於 Disqus： 文章字數： 1k 所需閱讀時間 ≈ 3 分鐘

题目

https://projecteuler.net/problem=106

题目说，S(集合)表示集合元素的和

集合A如果它任何不相交的两个子集B和C，同时满足

  1. S(B) != S(C)
  2. 如果 B的元素个数比 C多，那么 S(B)>S(C)

那么A是满足题意的

问 现在 给了一个集合，元素个数是n且满足第二条，要测试多少对 子集， 才能判定它是满足题意的

然后举例

n=4 是25中的 1对

n=7 是 966中的70对

求 n=12 时 需要判断的是261625中的多少对

理解

我是没想到，还能在ProjectEuler练习语文

注意到 一对不相交子集 如果元素个数不同，那么满足2一定不满足1,所以，如果“可能”满足1,那么元素个数相等

那么首先说 n=4时25怎么来的

假设四个元素 且排序了的 {A,B,C,D}

一个元素的比对就是 3+2+1=6,

两个元素的比对 3 种

因为不相交 所以 3个以上元素的不比对

所以哪里来的 25呢？？？？？？？？？？？？

换个思路

假设比对是有序的也就是 x和y比，y和x比 算两种，那么方案数一定是2的倍数？也不会25？

再说先放弃不相交的性质，只要不相等就计数？

1
2
3
1个元素 3+2+1=6
2个元素 5+4+3+2+1 = 15
3个元素 3+2+1=6

就是出不来25啊

一个办法是结束吧，放弃吧，只去关心1是怎么来的

然后我甚至想到了勾股定理4x4+3x3=25 然而也不是

难道是没考虑2的时候，之考虑了不相交

1
2
3
4
1对比1 3+2+1=6
1对比2 4x3 = 12
1对比3 4x1 = 4
2对比2 3

还真的是25

按照这个思路，尝试一下n=7,是不是966

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1v1:6+5+4+3+2+1 = 21
1v2:7x15=105
1v3:7x20=140
1v4:7x15=105
1v5:7x6=42
1v6:7x1=7
2v2:6x(5x4/2)+5x(4x3/2)+4x(3x2/2)+3x(2x1/2) = 105
2v3:21x10=210
2v4:21x5=105
2v5:21x1=21
3v3:15x4+10*1=70
3v4:35x1=35

21+105+140+105+42+7+105+210+105+21+70+35=966

那么这样说真的就是这个值了，不过n=12时这个值并不需要我们求

解

然后我们来看看 什么是可能

n=4, {A,B,C,D}

个数不相等的两个子集 一定不等

1v1 一定不等

2v2有 AB vs CD , AC vs BD, AD vs BC, 而只有AD vs BC是“可能”的，前面两组根据大小偏序关系一定不等

没有3v3以及以上

那么对于任意n呢

先看看n=7，{ABCDEFG}

1v1老样子一定不等

还剩下2v2和3v3

对于 2v2，一定是 一个的最小到最大构成的区间，包含另一个，

1
2
3
4
5
6
7
8
9
10
11
12
BC为中间:1x4=4
BD为中间:1x3=3
BE为中间:1x2=2
BF为中间:1x1=1
CD为中间:2x3=6
CE为中间:2x2=4
CF为中间:2x1=2
DE为中间:3x2=6
DF为中间:3x1=3
EF为中间:4x1=4

4+3+2+1+6+4+2+6+3+4=35

对于3v3,

X1<Y1<X2<Y2<X3<Y3一定不行， 7个

X1<X2<X3<Y1<Y2<Y3一定不行， 7个

X1<X2<Y1<X3<Y2<Y3一定不行， 7个

X1<X2<Y1<Y2<X3<Y3一定不行， 7个

X1<Y1<X2<X3<Y2<Y3一定不行， 7个

所以可行的3v3是 70-5x7=35 个

总共 35+35是70个

那么根据上面看到 实际上，不可能就是

两个子集排序后，对应下标位置偏序一致

代码

还需要代码吗，这题核心是语文的阅读理解，猜作者的意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)

int ia = 0;
int a[20];
int ib = 0;
int b[20];

int possible = 0;

int N = 12;

bool test_possible(){
  if(ia != ib)return false;
  int gcnt=0;
  int lcnt=0;
  rep(i,0,ia){
    if(a[i]< b[i]){
      lcnt++;
    }else{
      gcnt++;
    }
  }
  return lcnt != 0 && gcnt != 0;
}

void tryidx(int index){
  if(index == N){
    possible += test_possible();
    return;
  }
  a[ia++] = index;
  tryidx(index+1);
  ia--;
  if(ia != 0){
    b[ib++] = index;
    tryidx(index+1);
    ib--;
  }

  tryidx(index+1);
}


int main(){
  cin>>N;
  tryidx(0);
  printf("%d\n",possible);
  return 0;
}