USACO 6.4 章节

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

The Primes

题目大意

5*5矩阵,给定左上角

要所有行，列，从左向右看对角线为质数，没有前导零，且这些质数数位和相等(题目给和)

按字典序输出所有方案。。。

题解

看上去就是个 无脑暴搜

题目条件翻译成处理或剪枝

  1. 按照 字典序顺序搜，
  2. 末位是奇数
  3. 和确定了，那么前4位的和的奇偶性确定了
  4. 数值是5位数，可以先生成质数表
  5. 和-前n位和 小于 9乘剩余位数

也许先把第一行和第一列定下，然后按照数位和 再分组质数，搜索量会超级小?

17 7的这组数据 超过5s (i7-7700HQ)

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <bits/stdc++.h>
#define rep(i,a,n) for (long long i=a;i<n;i++)
#define per(i,a,n) for (long long i=n-1;i>=a;i--)

using namespace std;

const string filename = "prime3";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int A[10][10];
int p[100010];
int s;

bool check(int idxi,int idxj){
  {
    int sum = 0;
    rep(i,0,idxi+1){
      sum+=A[i][idxj];
    }
    if(sum > s){
      return false;
    }
    if( (s-sum) > (4-idxi)*9 ){
      return false;
    }
    if(idxi == 0 && sum == 0){
      return false;
    }
    if(idxi == 4){
      if(sum != s){
        return false;
      }
      int v = 0;
      rep(i,0,5){
        v*=10;
        v+=A[i][idxj];
      }
      if(p[v]){
        return false;
      }
    }
    if(idxi == 3 && (s-sum)%2 == 0){
      return false;
    }
  }
  {

    int sum = 0;
    rep(j,0,idxj+1){
      sum+=A[idxi][j];
    }
    if(sum > s){
      return false;
    }
    if( (s-sum) > (4-idxj)*9 ){
      return false;
    }
    if(idxj == 0 && sum == 0){
      return false;
    }
    if(idxj == 4){
      if(sum != s){
        return false;
      }
      int v = 0;
      rep(j,0,5){
        v*=10;
        v+=A[idxi][j];
      }
      if(p[v]){
        return false;
      }
    }
    if(idxj == 3 && (s-sum)%2 == 0){
      return false;
    }
  }
  {
    // 左下到右上
    if(idxi+idxj == 4){
      int sum = 0;
      rep(i,0,idxi+1){
        sum+=A[i][4-i];
      }
      if(sum > s){
        return false;
      }
      if( (s-sum) > (4-idxi)*9 ){
        return false;
      }
      if(idxi == 4){
        if(sum != s){
          return false;
        }
        int v = 0;
        per(i,0,5){
          v*=10;
          v+=A[i][4-i];
        }
        if(p[v]){
          return false;
        }
      }
    }
  }
  {
    // 左上到右下
    if(idxi-idxj == 0){
      int sum = 0;
      rep(i,0,idxi+1){
        sum+=A[i][i];
      }
      if(sum > s){
        return false;
      }
      if( (s-sum) > (4-idxi)*9 ){
        return false;
      }
      if(idxi == 4){
        if(sum != s){
          return false;
        }
        int v = 0;
        rep(i,0,5){
          v*=10;
          v+=A[i][i];
        }
        if(p[v]){
          return false;
        }
      }
      if(idxj == 3 && (s-sum)%2 == 0){
        return false;
      }
    }
  }
  return true;
}

void print(){
  static bool pre_n = false;
  if(pre_n){
    printf("\n");
  }else{
    pre_n = true;
  }
  rep(i,0,5){
    rep(j,0,5){
      printf("%d",A[i][j]);
    }
    printf("\n");
  }
}

void dfs(int pos){
  if(pos == 25){
    print();
    return ;
  }
  int idxi = pos/5;
  int idxj = pos%5;
  rep(i,0,10){
    A[idxi][idxj] = i;
    if(check(idxi,idxj)){
      dfs(pos+1);
    }
  }
}

void init(){
  rep(i,2,100000){
    if(!p[i]){
      for(long long j = i*i;j<100000;j+=i){
        p[j] = 1;
      }
    }
  }
}

int main(){
  usefile();
  init();
  cin>>s>>A[0][0];
  dfs(1);

  return 0;
}

根据和来看看个数得到 和:个数

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
4:4
5:12
7:28
8:45
10:95
11:143
13:236
14:272
16:411
17:479
19:630
20:664
22:742
23:757
25:741
26:706
28:580
29:528
31:379
32:341
34:205
35:166
37:84
38:62
40:34
41:13
43:4
44:2

相对于原来 的搜索空间 小了很多

改完以后 第6个点超时: 17 1

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <bits/stdc++.h>
#define rep(i,a,n) for (long long i=a;i<n;i++)
#define per(i,a,n) for (long long i=n-1;i>=a;i--)

using namespace std;

const string filename = "prime3";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int A[10][10];
int p[100010];
map<int,vector<int>>sum2v;
set<string>ss;
int s;

void print(){
  string news = "";
  rep(i,0,5){
    rep(j,0,5){
      news += ('0'+A[i][j]);
    }
    news += '\n';
  }
  ss.insert(news);
  return ;
  static bool pre_n = false;
  if(pre_n){
    printf("\n");
  }else{
    pre_n = true;
  }
  rep(i,0,5){
    rep(j,0,5){
      printf("%d",A[i][j]);
    }
    printf("\n");
  }
}

void check(){
  int ncnt = 0;
  int sum = 0;
  per(i,0,5){
    sum*=10;
    sum+=A[i][4-i];
    ncnt+=A[i][4-i];
  }
  if(ncnt != s)return;
  if(p[sum])return;
  int sum0=0;
  int ncnt0=0;
  rep(i,0,4){
    sum0+=A[i][i];
    sum0*=10;
    ncnt0+=A[i][i];
  }
  int sum1=0;
  int ncnt1=0;
  rep(j,0,4){
    sum1+=A[4][j];
    sum1*=10;
    ncnt1+=A[4][j];
  }
  int sum2=0;
  int ncnt2=0;
  rep(i,0,4){
    sum2+=A[i][4];
    sum2*=10;
    ncnt2+=A[i][4];
  }
  if(ncnt0 != ncnt1 || ncnt0 != ncnt2)return;
  int i = s - ncnt0;
  if(i < 0 || i > 10 || i%2 == 0)return ;
  if((!p[sum0+i]) && (!p[sum1+i]) && (!p[sum2+i])){
    // printf("sum:%d\n",sum);
    A[4][4] = i;
    print();
  }
}

void dfs(int ij){
  if(ij == 4){
    check();
    return ;
  }
  int prerow = 0;
  int precol = 0;
  rep(j,0,ij){
    prerow *=10;
    prerow += A[ij][j];
  }
  if(ij == 0){
    prerow = A[0][0];
  }

  rep(i,0,ij){
    precol += A[i][ij];
    precol *=10;
  }

  for(auto vrow:sum2v[prerow]){
    int pre0 = false;
    per(j,0,5){
      // printf("[%d]%d ==> vrow[%05d]A0[%d][%lld]=%d\n",ij,prerow,vrow,ij,j,vrow%10);
      A[ij][j]=vrow%10;
      vrow/=10;
      if(ij == 0 && A[ij][j] == 0){
        pre0 = true;
        break;
      }
    }
    if(pre0)continue;
    int pcol = precol+A[ij][ij];
    for(auto vcol:sum2v[pcol]){
      pre0 = false;
      per(i,0,5){
        // printf("\t[%d] %d ==> vcol[%05d]A1[%lld][%d]=%d\n",ij,pcol,vcol,i,ij,vcol%10);
        A[i][ij]=vcol%10;
        vcol/=10;
        if(ij == 0 && A[i][ij] == 0){
          pre0 = true;
          break;
        }
      }
      if(pre0)continue;
      dfs(ij+1);
    }
  }
}

void init(){
  rep(i,2,100000){
    if(!p[i]){
      if(i>=10000){
        int sum = 0;
        int ii = i;
        rep(idx,0,5){
          sum+=ii%10;
          ii/=10;
        }
        if(sum == s){
          int ii = i;
          rep(idx,0,5){
            sum2v[ii].push_back(i);
            ii/=10;
          }
        }
      }
      for(long long j = i*i;j<100000;j+=i){
        p[j] = 1;
      }
    }
  }
}

int main(){
  usefile();
  cin>>s>>A[0][0];
  init();
  dfs(0);
  for(auto item:ss){
    static bool pn = false;
    if(pn){
      printf("\n");
    }else{
      pn = true;
    }
    printf("%s",item.c_str());
  }
  return 0;
}

再增加一个预先剪枝 依然没过 第6个点，在我的电脑上1.893s

然后我对 中间的点，进行了预处理(预先判断 左下角到右上角)，tle 9,数据是23 1,虽然我的电脑上1.099s

然后 把map换成 数组 就本地0.227s，USACO就过了…

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <bits/stdc++.h>
#define rep(i,a,n) for (long long i=a;i<n;i++)
#define per(i,a,n) for (long long i=n-1;i>=a;i--)

using namespace std;

const string filename = "prime3";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int A[10][10];
int p[100010];
vector<int>sum2v[100010];
set<string>ss;
int s;

void print(){
  string news = "";
  rep(i,0,5){
    rep(j,0,5){
      news += ('0'+A[i][j]);
    }
    news += '\n';
  }
  ss.insert(news);
  return ;
  static bool pre_n = false;
  if(pre_n){
    printf("\n");
  }else{
    pre_n = true;
  }
  rep(i,0,5){
    rep(j,0,5){
      printf("%d",A[i][j]);
    }
    printf("\n");
  }
}

void check(){
  int ncnt = 0;
  int sum = 0;
  per(i,0,5){
    sum*=10;
    sum+=A[i][4-i];
    ncnt+=A[i][4-i];
  }
  if(ncnt != s)return;
  if(p[sum])return;
  int sum0=0;
  int ncnt0=0;
  rep(i,0,4){
    sum0+=A[i][i];
    sum0*=10;
    ncnt0+=A[i][i];
  }
  int sum1=0;
  int ncnt1=0;
  rep(j,0,4){
    sum1+=A[4][j];
    sum1*=10;
    ncnt1+=A[4][j];
  }
  int sum2=0;
  int ncnt2=0;
  rep(i,0,4){
    sum2+=A[i][4];
    sum2*=10;
    ncnt2+=A[i][4];
  }
  if(ncnt0 != ncnt1 || ncnt0 != ncnt2)return;
  int i = s - ncnt0;
  if(i < 0 || i > 10 || i%2 == 0)return ;
  if((!p[sum0+i]) && (!p[sum1+i]) && (!p[sum2+i])){
    // printf("sum:%d\n",sum);
    A[4][4] = i;
    print();
  }
}

bool precheck(int ij){
  rep(i,ij+1,5){
    int pre = 0;
    rep(j,0,ij+1){
      pre*=10;
      pre+=A[i][j];
    }
    if(!sum2v[pre].size())return false;
  }
  rep(j,ij+1,5){
    int pre = 0;
    rep(i,0,ij+1){
      pre*=10;
      pre+=A[i][j];
    }
    if(!sum2v[pre].size())return false;
  }
  if(ij == 2){
    int sum = 0;
    int pre = 0;
    per(i,0,5){
      pre*=10;
      pre+=A[i][4-i];
      sum+=A[i][4-i];
    }
    if(s!=sum)return false;
    if(p[pre])return false;
  }
  return true;
}


void dfs(int ij){
  if(ij == 4){
    check();
    return ;
  }
  int prerow = 0;
  int precol = 0;
  rep(j,0,ij){
    prerow *=10;
    prerow += A[ij][j];
  }
  if(ij == 0){
    prerow = A[0][0];
  }

  rep(i,0,ij){
    precol += A[i][ij];
    precol *=10;
  }

  // A[2][2]
  if(ij == 2){
    int mid = s- A[4][0]-A[3][1]-A[1][3]-A[0][4];
    if(mid < 0 || mid > 9)return;
    int v = A[4][0]*10000+A[3][1]*1000+mid*100+A[1][3]*10+A[0][4];
    if(p[v])return;// 左下到右上
    prerow = prerow*10+mid;
  }

  for(auto vrow:sum2v[prerow]){
    int pre0 = false;
    per(j,0,5){
      A[ij][j]=vrow%10;
      vrow/=10;
      if(ij == 0 && A[ij][j] == 0){
        pre0 = true;
        break;
      }
    }
    if(pre0)continue;
    int pcol = precol+A[ij][ij];
    for(auto vcol:sum2v[pcol]){
      pre0 = false;
      per(i,0,5){
        A[i][ij]=vcol%10;
        vcol/=10;
        if(ij == 0 && A[i][ij] == 0){
          pre0 = true;
          break;
        }
      }
      if(pre0)continue;
      if(!precheck(ij))continue;
      dfs(ij+1);
    }
  }
}

void init(){
  rep(i,2,100000){
    if(!p[i]){
      if(i>=10000){
        int sum = 0;
        int ii = i;
        rep(idx,0,5){
          sum+=ii%10;
          ii/=10;
        }
        if(sum == s){
          int ii = i;
          rep(idx,0,5){
            sum2v[ii].push_back(i);
            ii/=10;
          }
        }
      }
      for(long long j = i*i;j<100000;j+=i){
        p[j] = 1;
      }
    }
  }
}

int main(){
  usefile();
  cin>>s>>A[0][0];
  init();
  dfs(0);
  for(auto item:ss){
    static bool pn = false;
    if(pn){
      printf("\n");
    }else{
      pn = true;
    }
    printf("%s",item.c_str());
  }
  return 0;
}

提交后测试

  1. 把precheck 去掉， 发现也能过，甚至更快XD，说明其作用 小于 其副作用
  2. 把A[2][2] 预处理去掉 会超时第8个点

Electric Fences

题目大意

<=150条线段(和X 轴或 Y轴平行) ， 坐标 范围0<= x,y<=100

求一个点(可以非整数,最多1位小数)，从这个点 向每一条线段连出一个线段，使连出的线段长度综合最小，求点坐标和 最小总长度

题解

如果我们得到了一个点，那么 这个点到一条线段做垂线，如果垂线的垂点在线段上那么为这条垂线，否则为点到这条线段其中一个端点的长度

显然 和计算几何有关因为都和坐标轴平行了，完全用不到计算几何

有什么用呢？到所有线段都刚刚是垂线段最好？

显然有反例 (0,0)-(1,0),(0,0)-(0,1),(1,1)-(2,1), 如果是所有线段都刚刚垂线段那么显然选点(1,1),然而选点0,0可以得到更好的线段长度总和，说明(1,1)不是最优点

  1. 一个办法是 坐标乘10 ，然后枚举O(1000*1000*150)
  2. 一个算法是模拟退火！！！
  3. 精度逼近法,如果 一个区域的 最大距离 小于 另一个区域的最小距离，那么显然抛弃另一个，对这个区域可以进行再划分,至于怎么划分 还没具体方法
  4. 二维三分,求助！证明 在x和y方向 ，距离值函数都是凹函数(上凸)

基于未证明的 凸 假设 下的简化模拟退火, AC

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "fence3";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

double absarrow(double derx,double dery){
  return sqrt(derx*derx+dery*dery);
}

struct re{
  int x1,y1,x2,y2;
}l[160];
double dis(double x,double y,int idx){
  if(l[idx].x1==l[idx].x2){
    if(y<l[idx].y1)return absarrow(x-l[idx].x1,y-l[idx].y1);
    if(y>l[idx].y2)return absarrow(x-l[idx].x2,y-l[idx].y2);
    return fabs(x-l[idx].x1);
  }else{
    if(x<l[idx].x1)return absarrow(x-l[idx].x1,y-l[idx].y1);
    if(x>l[idx].x2)return absarrow(x-l[idx].x2,y-l[idx].y2);
    return fabs(y-l[idx].y1);
  }
}

int main(){
  usefile();
  srand(size_t(time(NULL)));
  int n=0;
  cin >> n;
  double x=rand()%100;
  double y=rand()%100;
  double step=100;
  tuple<double,double,double>ans;
  rep(i,0,n){
    scanf("%d %d %d %d", &l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
    // 因为平行于坐标轴 所以 必定有一组相等，所以只用换一组
    if(l[i].x1>l[i].x2)swap(l[i].x1,l[i].x2);
    if(l[i].y1>l[i].y2)swap(l[i].y1,l[i].y2);
    get<2>(ans) += dis(x,y,i);
  }
  int d=31;
  while(step>10e-3){
    rep(i,0,500){
      // 以任意方向 长度为step进行下降 d((x,y),(newx,newy)) = step
      double newx,newy;
      newx=step*(double(rand())/double(RAND_MAX))*(2*(rand()%2)-1); // [-step,step]
      newy=sqrt(step*step-newx*newx)*(2*(rand()%2)-1)+y; // 保证x y变化的向量长度是 step
      newx+=x;
      double lencnt=0;
      rep(idx,0,n){
        lencnt+=dis(newx,newy,idx);
      }
      // 如果更优下降
      if(lencnt-get<2>(ans)<0){
        x=newx;
        y=newy;
        ans={newx,newy,lencnt};
      }
    }
    d++;
    // 约从 1.1568910657987959 速率开始
    step/=log10(d)/log10(20);
  }
  printf("%.1lf %.1lf %.1lf\n",get<0>(ans),get<1>(ans),get<2>(ans));
  return 0;
}

延伸思考， 1.如何证明凸性质，2.如果增加线段，加一些不平行于坐标轴的线段，是否还是有凸的性质

Wisconsin Squares

题目大意

考英语了 考英语了 Guernseys (A), Jerseys (B), Herefords (C), Black Angus (D), and Longhorns (E).

4*4 的矩阵

原来有3*A0,3*B0,4*C0,3*D0,3*E0 现在需要有3*A1,3*B1,3*C1,4*D1,3*E1

现在的操作是 每次替换一个某种0 为 任意一种1,直到把4*4的所有替换完

限制，每次操作后，保证 没有相邻(8向)的相同字母, 如C0和C0算相同字母， A1和A0算相同字母

输入 初始 布局

输出 字典序最小的可行的方案过程和 可行的方案过程的总数

题解

一看就想暴搜啊

……然后 真的就过了，只有一个测试点

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)

using namespace std;

const string filename = "wissqu";

pair<int,int> v[10][10];
char s[10][10];

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}

int cnt[10];
bool success = false;
int anscnt = 0;
tuple<char,int,int> pick[100];

int di[]={-1,-1,-1,0,0,0,1,1,1};
int dj[]={-1,0,1,-1,0,1,-1,0,1};

void dfs(int deep){
  if(deep == 16){
    anscnt++;
    if(!success){
      success = true;
      rep(i,0,16){
        printf("%c %d %d\n",get<0>(pick[i]),get<1>(pick[i]),get<2>(pick[i]));
      }
    }
    return ;
  }
  rep(k,0,5){
    if(deep == 0 && k != 3)continue;
    if(!cnt[k])continue;
    rep(i,0,4){
      rep(j,0,4){
        if(v[i][j].second)continue;
        bool conflict = false;
        rep(m,0,9){
          int newi = i+di[m];
          int newj = j+dj[m];
          if(newi < 0 || newj < 0 || newi > 4 || newj > 4){
            continue;
          }
          if(v[newi][newj].first == k){
            conflict = true;
            break;
          }
        }
        if(conflict)continue;
        auto old = v[i][j];
        v[i][j] = {k,1};
        pick[deep] = {'A'+k,i+1,j+1};
        cnt[k]--;
        dfs(deep+1);
        cnt[k]++;
        v[i][j] = old;
      }
    }
  }
}

int main(){
  usefile();
  rep(i,0,4){
    scanf("%s",s[i]);
  }
  cnt[0] = 3;
  cnt[1] = 3;
  cnt[2] = 3;
  cnt[3] = 4;
  cnt[4] = 3;
  rep(i,0,4){
    rep(j,0,4){
      v[i][j] = {s[i][j]-'A',0};
    }
  }
  dfs(0);
  printf("%d\n",anscnt);
  return 0;
}

总结

我发现 普通的题，基本是一眼算法+分析复杂度+实现

而这种搜索剪枝的是，先上暴搜，逐个尝试加剪枝看效果XD,因为只能大概猜剪枝对效率的影响，而无法很直接的估计复杂度

另外，具体实现的常数有时很重要

和上一章的各种剪枝相比，这一章真的easy

本文其它博客地址

牛客: https://blog.nowcoder.net/n/911e9688897749a888ed979a19d1cf20

博客园: https://www.cnblogs.com/CroMarmot/p/11130744.html