YeXiaoRain Blog

發表於 更新於 分類於 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

發表於 更新於 分類於 Disqus： 文章字數： 2.7k 所需閱讀時間 ≈ 9 分鐘
搜索,剪枝,二分,字符串hash,搜索顺序

emmm……..很久很久以前 把6.2过了 所以emmmmmm 直接跳过 ，从6.1到6.3吧

Fence Rails

题目大意

N<=50个数A1,A2...

1023个数,每个数数值<=128,B

问 A 们能拆分成多少个B,求最多的个数

样例 解释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
A:
30=30
40=18+19+3
50=15+16+17+2
25=24
B:
15 (ok)
16 (ok)
17 (ok)
18 (ok)
19 (ok)
20
21
25
24 (ok)
30 (ok)

所以最多7个

题解

首先 如果对B 排序，假设最优个数为k个

显然 如果k个可行，那么排序后的B 的前k个可行

又 如果k个可行那么k-1个可行，综上又满足二分

先 sort+二分+从大到小放b （第4个点就超时了）

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
#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 = "fence8";

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

int n;
int a[100];
int la[100];
int suma;
int R;
int r[1100];
int sumr[1100];

int dfs(int idx){
  per(i,0,n){
    if(a[i] < r[idx]){
      return false;
    }
    if(a[i] ==  a[i+1] && la[i] == la[i+1]){
      continue;
    }
    if(la[i] < r[idx]){
      continue;
    }
    if(idx == 0){
      return true;
    }
    la[i] -= r[idx];
    int ret = dfs(idx-1);
    la[i] += r[idx];
    if(ret){
      return true;
    }
  }
  return false;
}

bool test(int idx){
  if(sumr[idx] > suma)return false;
  return dfs(idx);
}

int main(){
  usefile();
  scanf("%d",&n);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(i,0,n){
    la[i]=a[i];
    suma += a[i];
  }
  sort(a,a+n);

  scanf("%d",&R);
  rep(i,0,R){
    scanf("%d",r+i);
  }
  sort(r,r+R);
  if(r[0] > a[n-1]){
    cout<<0<<endl;
    return 0;
  }
  sumr[0]=r[0];
  rep(i,1,R){
    sumr[i]=sumr[i-1]+r[i];
  }
  int l=0,r=R;
  while(l+1<r){
    int mid = (l+r)/2;
    if(test(mid)){
      l = mid;
    }else{
      r = mid;
    }
  }
  cout<<l+1<<endl;
  return 0;
}

对B 的枚举过程加了相同长度的枚举优化 tle 5

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
int dfs(int idx,int stn = n){
  per(i,0,stn){
    if(a[i] < r[idx]){
      return false;
    }
    if(a[i] ==  a[i+1] && la[i] == la[i+1]){
      continue;
    }
    if(la[i] < r[idx]){
      continue;
    }
    if(idx == 0){
      return true;
    }
    la[i] -= r[idx];
    int ret;
    if(r[idx] == r[idx+1]){
      ret = dfs(idx-1,i+1);
    }else{
      ret = dfs(idx-1);
    }
    la[i] += r[idx];
    if(ret){
      return true;
    }
  }
  return false;
}

增加了 无效残余木料 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
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
#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 = "fence8";

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

int n;
int a[100];
int la[100];
int suma;
int R;
int r[1100];
int sumr[1100];

int dfs(int idx,int stn = n){
  if(suma < sumr[idx]){
    return false;
  }
  per(i,0,stn){
    if(a[i] < r[idx]){
      return false;
    }
    if(a[i] ==  a[i+1] && la[i] == la[i+1]){
      continue;
    }
    if(la[i] < r[idx]){
      continue;
    }
    if(idx == 0){
      return true;
    }
    la[i] -= r[idx];
    suma-=r[idx];
    bool predel = la[i] < r[0];
    if(predel){
      suma -= la[i];
    }
    int ret;
    if(idx > 0 && r[idx-1] == r[idx]){
      ret = dfs(idx-1,i+1);
    }else{
      ret = dfs(idx-1);
    }
    if(predel){
      suma += la[i];
    }
    suma+=r[idx];
    la[i] += r[idx];
    if(ret){
      return true;
    }
  }
  return false;
}

bool test(int idx){
  if(sumr[idx] > suma)return false;
  return dfs(idx);
}

int main(){
  usefile();
  scanf("%d",&n);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(i,0,n){
    la[i]=a[i];
    suma += a[i];
  }
  sort(a,a+n);

  scanf("%d",&R);
  rep(i,0,R){
    scanf("%d",r+i);
  }
  sort(r,r+R);
  if(r[0] > a[n-1]){
    cout<<0<<endl;
    return 0;
  }
  sumr[0]=r[0];
  rep(i,1,R){
    sumr[i]=sumr[i-1]+r[i];
  }
  int l=0,r=R;
  while(l+1<r){
    int mid = (l+r)/2;
    if(test(mid)){
      l = mid;
    }else{
      r = mid;
    }
  }
  cout<<l+1<<endl;
  return 0;
}

综上 二分+暴搜+减枝+处理顺序贪心

Cryptcowgraphy

题目大意

一个字符串能否通过 正数次操作使得变为

Begin the Escape execution at the Break of Dawn

一次操作: 选取 ...C...O...W...,把C->O的字符串和O->W的字符串交换，然后去掉这三个选中C,O,W

题解

显然 特判打表

我们已经知道 目标串 和 起始串

所以如果可行，那么 个数关系有C=O=W =(len(起始串)-len(目标串))/3,所以预先筛选的一个优化是，统计各个字符的个数，和目标串进行比较

所以 当比较是可能时，答案要么0 0,要么 1 字母C 的个数

我们可以优化的点

  1. 字母个数统计
  2. 被C O W 分割的在任意时刻是 目标串的子串
  3. 搜索顺序先O
  4. 字符串hash [注意 这个方法 如果你是在打cf，那么很可能被hack

注意输入是一行….所以不要scanf %s

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
#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 = "cryptcow";

void usefile(){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
const char Goal[] = "Begin the Escape execution at the Break of Dawn";
const int Mod = 999983;

char s[110];
int ans, cnt;
bool hsh[Mod];

// 删除a b c位置上的, 交换a->b b->c
void work(int a, int b, int c) {
  static char tmp[100];
  int len = strlen(s), tot = 0;
  for(int i = 0; i < a; ++i) {
    tmp[tot++] = s[i];
  }
  for(int i = b + 1; i < c; ++i) {
    tmp[tot++] = s[i];
  }
  for(int i = a + 1; i < b; ++i) {
    tmp[tot++] = s[i];
  }
  for(int i = c + 1; i < len; ++i) {
    tmp[tot++] = s[i];
  }
  tmp[tot] = 0;
  strcpy(s, tmp);
}

int getHash() {
  int ret = 0, len = strlen(s);
  for(int i = 0; i < len; ++i) {
    int num = (s[i]==' ')?1:(isupper(s[i]) ? s[i] - 'A' + 2 : s[i] - 'a' + 28);
    ret = (ret * 57 + num) % Mod;
  }
  return ret;
}

bool dfs(int depth) {
  if(strcmp(s, Goal) == 0) {
    ans = depth;
    return true;
  }
  int x = getHash();
  if(hsh[x]) {
    return false;
  }
  hsh[x] = true;
  ++cnt;
  // 被C O W 分割的 字串应该是Goal的连续子串
  static char sub[100];
  int len = strlen(s);
  int c[20], o[20], w[20];
  c[0] = o[0] = w[0] = 0;
  for(int i = 0, j = 0; i < len; ++i) {
    if(s[i] == 'C' || s[i] == 'O' || s[i] == 'W') {
      if(s[i] == 'C') {
        c[++c[0]] = i;
      }
      if(s[i] == 'O') {
        o[++o[0]] = i;
      }
      if(s[i] == 'W') {
        w[++w[0]] = i;
      }
      sub[j] = 0;
      if(!strstr(Goal, sub)) { //
        return false;
      }
      j = 0;
    }
    else {
      sub[j++] = s[i];
    }
  }
  // C = W = O
  if(o[0] != c[0] || o[0] != w[0] || w[0] != c[0]) {
    return false;
  }
  char pre[100];
  strcpy(pre, s); // 递归暂存
  // 查找顺序 先找O
  rep(j,1,o[0]+1){
    per(k,1,w[0]+1){
      if(w[k] < o[j])break;
      rep(i,1,c[0]+1){
      if(c[i] > o[j])break;
        work(c[i], o[j], w[k]);
        bool ret = dfs(depth + 1);
        if(ret){
          return true;
        }
        if(cnt > 200000) { // ............................
          return false;
        }
        strcpy(s, pre);
      }
    }
  }
  return false;
}


int main() {
  usefile();
  cin.getline(s,100);
  // scanf("%s",s);
  int ret = dfs(0);
  printf("%d %d\n", ret, ans);
  return 0;
}

Cowcycles

题目大意

25 <= F1 < F2 <= 80

在[F1,F2]范围找[1,5]个数f1,f2..

5 <= R1 < R2 <= 40

在[R1,R2]范围找[1,10]个数r1,r2..

ratio(i,j) = fi/rj

在max ratio/min ratio >= 3的限制下

把所有ratio(i,j)排序，最小化 排序后数组相邻值 的差 的方差

求具体方案

题解

ratio(i1,j1)/ratio(i2,j2) = i1*j2/i2*j1

要使这个值的最大值大于3,注意到都是正数，也就是(max(i)*max(j))/(min(i)*min(j)) >= 3

然后因为ratio要先sort，再最小化 差 的方差，就感觉 无路可推，只能暴搜

优化

  1. 默认的限制减枝
  2. 个数少，运算过程相对有序 –> 计算顺序+插入排序
  3. 搜一搜初中的方差变形公式，省掉最外层的1/n 有只用比较sum{平方}+(sum{}平方)/n

注意 以下代码过了USACO 但是有潜在风险，浮点数比大小！！ 如果是打cf，可能会被叉

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
#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 = "cowcycle";

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

int s1[20],s2[20];
int ans1[20],ans2[20];
int F,F1,F2;
int R,R1,R2;
int cnt;
double rate[100],diff[100];
double minvf=10000000;

void count(){
  int k=0;
  double sum=0,avg,vf=0,sumf=0,p;
  // 数据量小 采用插入排序
  rep(i,0,F){
    rep(j,0,R){
      p=(double)s1[i]/s2[j];
      int l=++k;
      while (rate[l-1]>=p) {
        rate[l]=rate[l-1];
        l--;
      }
      rate[l]=p;
    }
  }
  rep(i,1,cnt){
    diff[i]=rate[i+1]-rate[i];
    sum+=diff[i];
    sumf+=diff[i]*diff[i];
  }
  avg=sum/(cnt-1);// 相邻值的差的个数 比值的个数少1
  vf=sumf-sum*avg;
  if (vf<minvf)  {
    minvf=vf;
    memcpy(ans1,s1,sizeof(int)*F);
    memcpy(ans2,s2,sizeof(int)*R);
  }
}

// 枚举后齿轮 从w 到R2-R+k+1
void sc2(int k,int w){
  if (k==R){
    if (s1[F-1]*s2[R-1]<3*s1[0]*s2[0]) // 题目限制条件剪枝
      return;
    count();
    return;
  }
  rep(i,w,R2-R+k+2){
    s2[k]=i;
    sc2(k+1,i+1);
  }
}

// 枚举前齿轮 从w到F2-F+k+1
void sc1(int k,int w){
  if (k==F)  {
    sc2(0,R1);
    return;
  }
  rep(i,w,F2-F+k+2){
    s1[k]=i;
    sc1(k+1,i+1);
  }
}

int main() {
  usefile();
  cin>> F >> R >> F1 >> F2 >> R1 >> R2;
  cnt=F*R;
  sc1(0,F1);
  rep(i,0,F){
    cout << ans1[i] << " \n"[i==F-1];
  }
  rep(i,0,R){
    cout << ans2[i] << " \n"[i==R-1];
  }
  return 0;
}

总结

搜索+剪枝，剪究竟要怎么剪

引用一个大佬的话https://apps.topcoder.com/forums/?module=Thread&threadID=669047&start=0&mc=6#1216077

Well, if the optimizations change the complexity of the solution asymptotically, you can quite sure.

Otherwise you can’t depend on anything, I think.

重要的是 找到 能明确改变算法 复杂度的剪枝。

反过来分析

第1题

剩余 体积 处理，应该能优化了搜索树的叶节点个数，十分关键

重复体积的搜索处理，优化了枚举体积的次数，对相同体积有多个的情况，从 可放空间数的相同个数次方，优化到了？？？，不知道怎么表示，但是 大量减少了重复枚举是肯定的

从大到小尝试，优化了末端个数？（吗）

第2题

对于错误的预处理 直接一边就否定掉了

目标串的子串是一个有效的大优化，当 在 去掉COW 以后，连接出了 不应该的字符串，可以立刻剪掉，对搜索空间优化大

搜索顺序 先O 还好 大概是常数倍数优化

字符串hash，除了上面的方法，还可以 用其它的 比如神奇的偏移+异或字符串等等， 优化的是很大的字符串比较代价，常数倍数

第3题

基本没有剪枝[题目限制的剪枝是当然

主要靠的是算法使用的性能优化

优化 排序[数量少的时候插入,在具体工程实践中，数量较少的时候 也同样会采取 数组取代map 进行遍历，冒泡取代其它排序 ]

优化 方差运算，目前这样公式变化

默认 n-1次加法 1次除法，算平均数，n次减法,n次乘法,n-1次加法得到结果

优化后 2(n-1)次加法 1次除法,1次减法n+1次乘法,得到结果

假设所有 运算类型时间代价相同，那么算是优化掉了约1/4时间[然而一般来说减法的速度是比乘除快很多，再加上CPU的指令pipeline运算优化，可能影响有，但不大

本文其它博客链接

牛客:https://blog.nowcoder.net/n/2773db6ff811467a922070d9a5c64a39

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

發表於 更新於 分類於 Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
插头DP,高精度,高精度加法,最大子矩阵,模型分析,异或前缀,字典树

Postal Vans

题目大意

4*n的网格，要经过所有点的有向有环，不重复经过点的路径总数

n<=1000

题解

显然 插头dp

以4为切面

问题是，会发现 超精度

解决呢要么实现高精度，要么换python XD

c++实现 未+高精度，会爆掉

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
#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 = "vans";

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

int n;

const int S1001 = 0;
const int S1122 = 1;
const int S1100 = 2;
const int S0110 = 3;
const int S0011 = 4;
const int S1221 = 5;
const int S0000 = 6;

long long dp[1010][10];
int s2[10][10];

void init(){
  s2[S1001][S0000] = 1;
  s2[S1001][S1100] = 1;
  s2[S1001][S0110] = 1;
  s2[S1001][S0011] = 1;
  s2[S1001][S1221] = 1;

  s2[S1122][S1001] = 1;
  s2[S1122][S1122] = 1;
  // s2[S1122][S1100] = 1; 不应该自闭
  // s2[S1122][S0011] = 1; 不应该自闭
  // s2[S1122][S0000] = 1; 不应该自闭

  s2[S1100][S1122] = 1;
  s2[S1100][S1001] = 1;

  s2[S0110][S1001] = 1;

  s2[S0011][S1122] = 1;
  s2[S0011][S1001] = 1;

  // s2[S1221][S1001] = 1; 不应该自闭
  s2[S1221][S0000] = 1;
  s2[S1221][S1100] = 1;
  s2[S1221][S0011] = 1;
  s2[S1221][S1221] = 1;
}

int main(){
  usefile();
  init();
  cin>>n;

  dp[0][S1001] = 1;
  dp[0][S1122] = 1;
  rep(i,1,n){
    rep(stateS,0,6){
      rep(stateE,0,7){
        if(s2[stateS][stateE]){
          dp[i][stateE]+=dp[i-1][stateS];
        }
      }
    }
  }
  // rep(i,0,n){
  //   rep(state,0,7){
  //     cout<<dp[i][state]<<"\t";
  //   }
  //   cout<<endl;
  // }
  cout<<dp[n-1][S0000]*2<<endl;
  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
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
#include <bits/stdc++.h>
typedef long long ll;
#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--)
#define pb push_back


using namespace std;

const string filename = "vans";

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

class hpa{
  int DIGITS = 100'000'000; // 08lld
  vector<ll>vals;
public:
  hpa(){
  }
  hpa(ll v){
    vals.pb(v);
  }
  void print(){
    if(vals.size() == 0){
      printf("0");
      return;
    }
    printf("%lld",vals[vals.size()-1]);
    per(i,0,vals.size()-1){
      printf("%08lld",vals[i]);
    }
  }
  hpa operator +(const hpa &another) const {
    hpa ret;
    rep(i,0,vals.size()){
      ret.vals.pb(vals[i]);
    }
    rep(i,0,another.vals.size()){
      if(i >= ret.vals.size()){
        ret.vals.pb(another.vals[i]);
      }else{
        ret.vals[i]+=another.vals[i];
        if(ret.vals[i] >= DIGITS){
          if(i == ret.vals.size()-1){
            ret.vals.pb(0);
          }
          ret.vals[i+1]+=ret.vals[i]/DIGITS;
          ret.vals[i]%=DIGITS;
        }
      }
    }
    return ret;
  }
};

int n;

const int S1001 = 0;
const int S1122 = 1;
const int S1100 = 2;
const int S0110 = 3;
const int S0011 = 4;
const int S1221 = 5;
const int S0000 = 6;

hpa dp[1010][10];
int s2[10][10];

void init(){
  s2[S1001][S0000] = 1;
  s2[S1001][S1100] = 1;
  s2[S1001][S0110] = 1;
  s2[S1001][S0011] = 1;
  s2[S1001][S1221] = 1;

  s2[S1122][S1001] = 1;
  s2[S1122][S1122] = 1;
  // s2[S1122][S1100] = 1; 不应该自闭
  // s2[S1122][S0011] = 1; 不应该自闭
  // s2[S1122][S0000] = 1; 不应该自闭

  s2[S1100][S1122] = 1;
  s2[S1100][S1001] = 1;

  s2[S0110][S1001] = 1;

  s2[S0011][S1122] = 1;
  s2[S0011][S1001] = 1;

  // s2[S1221][S1001] = 1; 不应该自闭
  s2[S1221][S0000] = 1;
  s2[S1221][S1100] = 1;
  s2[S1221][S0011] = 1;
  s2[S1221][S1221] = 1;
}

int main(){
  usefile();
  init();
  cin>>n;

  dp[0][S1001] = 2;
  dp[0][S1122] = 2;
  rep(i,1,n){
    rep(stateS,0,6){
      rep(stateE,0,7){
        if(s2[stateS][stateE]){
          dp[i][stateE]=(dp[i][stateE]+dp[i-1][stateS]);
        }
      }
    }
  }
  // rep(i,0,n){
  //   rep(state,0,7){
  //     cout<<dp[i][state]<<"\t";
  //   }
  //   cout<<endl;
  // }
  dp[n-1][S0000].print();
  printf("\n");
  return 0;
}

A Rectangular Barn

Mircea Pasoi – 2003

题目大意

(<=3000)*(<=3000)的矩阵

上面有<=30000 个坏点

求 最大不含坏点的矩形面积

题解

因为求的是最大矩形，那么它的四周要么是边界，要么是坏点

证明：反证明

如果存在一条边既没有邻接 边界，也没有邻接坏点。

那么对该边延伸 ，可以得到更大的矩形，矛盾

观察到这个性质后

我们考虑对任意 点(i,j)

以 i0<i,其中(i0,j)为距离(i,j)最远的点 且 线段(i0->i,j)上无坏点

线(i0->i,j)为高，做横向扩张，找左右两侧的最近的坏点 或边界，则有以(i,j)搜寻的矩形面积=(i0->i,j) * 该线段左右扩张的最大宽度

  1. 这样找到的矩形 一定是 合法矩形 所以这样找到的矩形面积小于等于 最大面积
  2. 这样一定能找到最大的矩形，因为我们证明了最大矩形 一定邻接着坏点或边界，那么该最大矩形上方边界所对应的 坏点，正下方的的点 在运算过程会计算到

所以O(3000*3000),以所有点计算出一个矩形，每个矩形计算复杂度为O(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
#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 = "rectbarn";

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

int L[3010],R[3010]; // j列当前线段 左右扩展的可行最远距离
int H[3010]; // j列 当前 的线段长度
bool g[3010][3010];
int n,m,ans;
int main(){
  usefile();
  freopen("rectbarn.in","r",stdin);
  freopen("rectbarn.out","w",stdout);
  int k;
  cin>>n>>m>>k;
  while(k--){
    int i,j;
    scanf("%d%d",&i,&j);
    g[i][j]=1;
  }
  rep(j,0,m+1){
    H[j]=0;
    L[j]=1;
    R[j]=m;
  }
  rep(i,1,n+1){
    // 处理所有 坏点
    rep(j,1,m+1){
      if(g[i][j]){
        H[j]=0;
        L[j]=1;
        R[j]=m;
      }
    }
    // 计算所有 左侧 和 右侧 最远
    int lm = 1;
    rep(j,1,m+1){
      if(!g[i][j]){
        H[j]++;
        L[j]=max(L[j],lm);
      } else{
        lm=j+1;
      }
    }
    int rm = m;
    per(j,1,m+1){
      if(!g[i][j]){
        R[j]=min(R[j],rm);
      }else{
        rm=j-1;
      }
    }
    // 计算面积
    rep(j,1,m+1){
      if(!g[i][j]){
        ans=max(ans,(R[j]-L[j]+1)*H[j]);
      }
    }
  }
  printf("%d\n",ans);
  return 0;
}

Cow XOR

Adrian Vladu – 2005

题目大意

n(<=100,000)个数,数值范围是[0,2^21 - 1]

求连续子区间 的最大xor值，输出 最大xor值，区间起始点，区间结束点

如果有多个区间满足最大异或，返回结束点index最小的，如果还有多个，返回长度最短的。

题解

首先

我们证明一下题目描述的结果唯一

如果多个 子区间 异或值相同，且结束点不同，那么 只有唯一可以选

如果两个 子区间 异或值相同，且结束点相同，那么 它们一定起始点不同，所以它们长度不同，只有最短可选

综上，题目描述结果唯一

然后

显然

xor[l->r] = xor[1->l-1]^xor[1->r]

所以 我们要找最大值，等于找两个前缀异或的最大值

从高位到低位，对所有前缀建立trie树,再for一遍贪心走trie树,贪心规则 有和当前位不同的走不同的路径，否则才走相同,（尽量在高位产生1）

空间 O(n*21),时间O(n*21)

空间节点数

1
2
3
4
s=0;
for i in range(0,22):
    s+=min(2**i,100000)
print(s)

631071 个，然而 我开这么大会炸空间，开500000过的 （按道理讲 这样空间上看是开得有问题，开小了，不过过了测试）

我在实现过程中是找 区间左右端点靠的是 lower_bound二分，多用了空间,

然而，我们发现 最优区间必定有一个是 其前缀值的最小坐标

所以 如果枚举i去寻找 其期望的 前缀值对应的最小坐标，一定能找到最优值,可以优化

通过的，但空间开得不合理的代码,(我之前还用struct来写，虽然阅读上更好理解，但空间更加不够XD)

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
#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 = "cowxor";

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

int n;
int a[100010];
int p[100010];
int ns[500010][2];

int nsi=0;

int *root = ns[nsi++];

map<int,vector<int> > pv2idx; // 前缀异或 到 下表

void build(int idx){
  int v = p[idx];
  pv2idx[v].push_back(idx); // ordered
  int * po = root;
  per(i,1,21){
    int bit = !!(v&(1<<i));
    if(!po[bit]){
      po[bit] = nsi++;
    }
    po=ns[po[bit]];
  }
  int bit = !!(v&1);
  po[bit] = v;
}

int query(int idx){
  int v = p[idx];
  int * po = root;
  per(i,1,21){
    int bit = !(v&(1<<i));
    if(!po[bit]){
      po = ns[po[bit^1]];
    }else{
      po = ns[po[bit]];
    }
  }
  int bit = !(v&1);
  return po[bit] == 0?po[bit^1]:po[bit];
}

int ans=-1,ansl,ansr;

void setAns(int v1,int l,int r){
  // cout<<"SETANS:"<<v1<<" l:"<<l<<" r:"<<r<<endl;
  if(l > r){
    swap(l,r);
  }
  if(v1 < ans)return;
  if(v1 > ans){
    ans = v1;
    ansl = l;
    ansr = r;
    return ;
  }
  if(r < ansr){
    ansl = l;
    ansr = r;
    return ;
  }
  if(r > ansr){
    return ;
  }
  if(l > ansl){
    ansl = l;
    return ;
  }
}

int main(){
  usefile();
  scanf("%d",&n);
  rep(i,0,n){
    scanf("%d",a+i);
  }
  rep(i,0,n){
    p[i+1]=p[i]^a[i];
  }
  rep(i,0,n+1){
    build(i);
  }
  // for(auto item:pv2idx){
  //   cout<<"--------"<<item.first<<endl;
  //   for(auto z:item.second){
  //     cout<<z<<"\t"<<endl;
  //   }
  //   cout<<endl;
  // }
  rep(i,0,n+1){
    int ret = query(i);
    int reti = lower_bound(pv2idx[ret].begin(),pv2idx[ret].end(),i)-pv2idx[ret].begin();
    // cout<<"find:"<<i<<"["<<p[i]<<"]:"<<ret<<"("<<pv2idx[ret][reti]<<")"<<endl;
    if(ret == p[i]){
      if(i > 0){
        setAns(ret^p[i],i-1,i);
      }
    }else if(reti > 0){
      setAns(ret^p[i],i,pv2idx[ret][reti-1]);
    }else{
      setAns(ret^p[i],i,pv2idx[ret][reti]);
    }
  }
  printf("%d %d %d\n",ans,ansl+1,ansr);
  return 0;
}

發表於 更新於 分類於 Disqus： 文章字數： 3.1k 所需閱讀時間 ≈ 10 分鐘
离散化,扫描线,最小值性质,DP,按位逼近

Picture

题目大意

IOI 1998

求n (<=5000)个矩形 覆盖的图形 的周长(包括洞), 坐标范围[-10000,10000]

题解

一眼离散化+2维线段树，但仔细一想 空间不太够,时间勉强接受

然后目测可能1维线段树+扫描线了?

然后 竟然 裸的扫描线可以过，如下面代码

总数量级上来讲，输入O(n),排序O(n log n),扫描过程O(sum(len周长)) 约5000*20000*4的上限[ 不过USACO给过了，

所以还是线段树好?

从实现来讲，把矩形拆分成x和y方向，靠计算每个块的累计层数 来判断边界

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
#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 = "picture";

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

int N,ans=0;
// OX向和OY向的 线段分离处理，互不影响
tuple<int,bool,int,int> Lx[10010],Ly[10010]; // {位置idx坐标,结束边bool?,st->end}
int level[20010];


void Scan(tuple<int,bool,int,int> *L) {
  sort(L,L+N);
  rep(i,0,20001)
    level[i]=0;
  rep(i,0,N){
    rep(j,get<2>(L[i]),get<3>(L[i])){
      if (!get<1>(L[i])){
        ans += level[j+10000]==0;
        level[j+10000]++;
      } else {
        level[j+10000]--;
        ans += level[j+10000]==0;
      }
    }
  }
}


int main(){
  usefile();
  scanf("%d",&N);
  rep(i,0,N){
    int x1,x2,y1,y2;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    // OX 方向边
    Lx[i*2] = {y1,false,x1,x2};
    Lx[i*2+1] = {y2,true,x1,x2};
    // OY 方向边
    Ly[i*2] = {x1,false,y1,y2};
    Ly[i*2+1] = {x2,true,y1,y2};
  }
  N*=2;
  Scan(Lx);
  Scan(Ly);
  printf("%d\n",ans);
  return 0;
}

Hidden Password

ACM South Eastern Europe – 2003

题目大意

字符串L(长度<=100’000)

求 以该字符串，平移后的， 所有字符串中 字典序最小的字符串的首字母在原字符串中的下标

如cba

所有字符串 acb bac cab, (排序后),第一个字符串首字母对应原来字符串位置为2 (从0计数)

题解

枚举！

这样 我们首先找到最小字母 扫一遍O(n)

然后找到这些开始的坐标

逐步增加长度

那么我们由递归关系，保证每次增加长度后，当前还剩余的坐标只有最小的留下，

因此当增加长度到l时，我们 的维持的起始坐标是 整个字符串里，长度从1到l都是字典序最小的

那么我们有两种长度改变方式

  1. +1

假设所有点按照长度扩充 都不属于当前维护的点，那么，长度加1，保留，增加字符最小的点

例子 abcabdzzzabc

初始所有a的坐标[0,3,9]，长度1

扩充，扩充目标分别为[1,4,10]，都不是当前维护的点([0,3,9])

所以比较元素，全为b，长度=1+1=2

接下来，扩充目标为[2,5,11],也都不是维护的点

比较字符，两个abc,一个abd,所以维护的点变为[0,9],长度变为=2+1=3

再扩充，扩充目标为[3,0],注意到0是我们当前维护的[0,9]中的元素，所以不采取+1的方案

  1. 倍增

假设字符aabbabbb，

那么在找完最小字符后，起始坐标还剩下[0,1,4],一旦发现任意一个扩充的下一步([1,2,5]) 是一个维持的点，那么长度翻倍，后一个点删除，在这种情况下，扩充的位置不是最小坐标的点直接移除。

因为我们维持的点 == 从1到该长度下，每个长度 都是字典序最小的，所以没有在维护中的点，都是非字典序最小的,所以 可以倍增

删除右边的点是因为 扩充右边的维护点的字典序一定大于等于 左边的点，等于的情况由判环处理

如上在一次扩充后发现0的下一个扩充是1，而1是我们维持着的点，所以长度=1*2,1点删除，4扩充是5，那么5没有被维持，所以4点也被删除，综上最后剩下0

以上描述存在的问题：起始点是哪个点？

假设字符串 aaazzaaza,

显然在初始操作后 需要维护的点有[0,1,2,5,6,8]

注意到，如果从左向右来处理，按照上面的算法会 变成[0,6,8???],而实际 从环的性质来看，期望的应该是得到[1,6,8]，也就是8位置的看做[8,0,1,2]这一段的起始点。

这里加一个父节点的查找，找到环意义上该点所对应的最左的点即可，在下方函数看的话就是circle,

同时，circle这里如果发现，整个保存的点构成了环,那么也就是 这些点仅对于环上字典序的等价了，根据题目期望这种情况下最小index，就取出即是答案

空间复杂度，emmmm没啥好说，看变量即可，维持在O(n)

时间复杂度,

每一次倍增会让点数至少除以2，因为一个点要留下来，那么首先它的扩展点要在原来的维护里，并且下一次维护需要消失，所以每次要留一个点，就一定要删一个点，还有的点不会被留下，所以留下的一定小于等于上一次的一半

O(n+n/2+n/4) = O(2n) = O(n)

考虑对任意长度，都是执行+1，那么每次能执行+1的限度为

sum(n*(1+1/2+...1/n))

众所周知这是一个无穷级数，所以时间复杂度无穷大

大自也是O(12n)=O(n)的复杂度，

下面就是实际上，是这两种穿插 ，那么一定小于等于O(2n+12n)=O(n), (数学的习惯懒得分类讨论不等的情况 能用就行，所以留一个等于)

综上 时间空间均满足

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
char s[100010];
int sz=0;

bool pos[100010];
vector<int>p;
vector<int>q;
int L;

bool circle(int idx,int len,int &newidx){
  newidx = (idx+L-len)%L;
  while(newidx != idx){
    if(!pos[newidx]){
      (newidx+=len)%=L;
      return false;
    }else{
      newidx = (newidx+L-len)%L;
    }
  }
  while(newidx - L > 0){
    newidx -= L;
  }
  printf("%d\n",newidx);
  return true;
}

int main(){
  usefile();
  // 同步增长，冲突取前，倍增 其余删除(因为保证最小)
  scanf("%d",&L);
  while(sz<L){
    scanf("%s",s+sz);
    sz+=strlen(s+sz);
  }
  char minch = s[0];
  rep(i,1,L){
    minch = min(minch,s[i]);
  }
  rep(i,0,L){
    if(s[i] == minch){
      p.push_back(i);
      pos[i]=true;
    }
  }
  int l = 1;
  while(p.size() > 1){
    int state = 0; // 0 for +1, 1 for *2
    minch = s[(p[0]+l)%L];
    for(auto idx : p){
      if(pos[(idx+l)%L] == true){
        state = 1;
        break;
      }
      minch = min(minch,s[(idx+l)%L]);
    }
    if(state == 0){
      q.clear();
      for(auto idx:p){
        if(!pos[idx])continue;
        if(s[(idx+l)%L] == minch){
          q.push_back(idx);
        }else{
          pos[idx]=false;
        }
      }
      p=q;
      l++;
    }else{
      q.clear();
      int startidx ;
      int ret = circle(p[0],l,startidx);
      if(ret){
        return 0;
      }
      int pidx = 0;
      for(pidx=0;pidx<p.size();pidx++){
        if(p[pidx] == startidx){
          break;
        }
      }
      rep(i,pidx,p.size()){
        int idx = p[i];
        if(!pos[idx])continue;
        if(pos[(idx+l)%L]){
          q.push_back(idx);
          pos[(idx+l)%L] = false;
        }else{
          pos[idx]=false;
        }
      }
      rep(i,0,pidx){
        int idx = p[i];
        if(!pos[idx])continue;
        if(pos[(idx+l)%L]){
          q.push_back(idx);
          pos[(idx+l)%L] = false;
        }else{
          pos[idx]=false;
        }
      }
      p=q;
      l*=2;
    }
  }
  printf("%d\n",p[0]);
  return 0;
}

Twofive

题目大意

IOI 2001

A到Y构成的排列，满足 把这25个字母排成 5*5矩阵后 每行每列，单调递增，则为合法的

所有合法的排列，按照字典序 排序

请编写 字典序序号 到字符串 和 字符串反向转换为字典序序号的程序

尝试思路

看数据量，我自己也估计不到实际大小于是先写了一个打表，(上界 是25!但是有限制所以不知道是否会降低

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
#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 = "twofive";

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

int chars[30];
int vis[30];
int cnt = 0;

void print(){
  cout<<endl;
  rep(i,0,5){
    rep(j,0,5){
      cout<<char(chars[i*5+j]+'a')<<" ";
    }
    cout<<endl;
  }
}

void gen(int idx){
  if(idx%5==0){
    rep(i,0,25){
      if(vis[i] == 0){
        vis[i]=1;
        chars[idx] = i;
        gen(idx+1);
        vis[i]=0;
        return ;
      }
    }
  }
  if(idx == 24){
    cnt++;
    chars[24]=24;
    print();
    return ;
  }
  int sti = chars[idx-1];
  if(idx>5){
    sti=min(sti,chars[idx-5]);
  }

  rep(i,sti+1,26-(5-idx%5)*(5-idx/5)){
    if(vis[i])continue;
    vis[i]=1;
    chars[idx] = i;
    gen(idx+1);
    vis[i]=0;
  }
}


int main(){
  // usefile();
  gen(0);
  cout<<cnt<<endl;

  return 0;
}

跑了一下大概

1
2
3
4
5
6
7951237
a b c d e 
f g h l n 
i m k q w 
j p o r u 
s t v x y

以上的改动才到i,说明 数量级上，不可能期望打表了

接下来，注意到，如果我们有方法从数字序号转换到 对应的单词，那么 可以2分法 找到对应的单词

同理，如果我们找到 单词映射到序号的方法，那么2分（如果可以，因为这里二分单词似乎没那么好做）也能反过来找数字，所以分析上，任何一个问题 都可以解决对应的一个

还有个思路是，简单的排序，计算被删掉的个数,那么序列= 总排序-被删掉比它小的个数

题解

记忆化+dp

我们如果把数从小到大填入

那么显然，新插入的数在已经插入的数的行末,也在已经插入的数的列末，如

1
2
3
4
5
a b e
c d f
g
h
i

j可插入的位置 为g右侧或e右侧

所以 我们有dp

dp[i0][i1][i2][i3][i4] 表示 第0行i0个，第1行i1个数…第i4行个数的情况下，剩余未填部分的期望个数

不考虑具体，仅考虑题目基本限制的情况下, 满足 ij >= i(j+1),因为我们按照顺序放数字，所以上面的行的个数不小于下一行

有转移方程

dp[i0][i1][i2][i3][i4] = dp[i0-1][...]+dp[...][i1-1][...]+dp[...][i2-1][...]+dp[...][i3-1][...]+dp[...][i4-1]

其中 如果在-1时不满足 行之间个数的大小关系，那么 对应的dp直接为0

综上，我们有了在没有 具体求值下，能计算所有满足题目限制下的dp，时间复杂度 = O(空间*状态转移)=O(6^5*5),空间O(6^5)

求解

接下来是如何进行转换的问题求

因为所求的idx为实际的 合法twofive的字典序

那么我们可以按位逼近，//延伸阅读 BROP的按位枚举攻击方法

假设我们求的是

ADEFGBHIJKC...Y, 那么 它 的字典序 = AB...的所有+AC...的所有+…

简单的说，如果一个前缀小于 要求的等长前缀，那么加上该前缀的所有个数，

如果该前缀等于要求的值的等长前缀，那么前缀长度+1

外层for前缀长度，中间for字母， 时间复杂度小于 O(25*25)

以上我们可以 从 字符串转化为index

相反

同样用逼近的方法，可以O(25*25)时间复杂度内 index转化为 字符串

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
#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 = "twofive";

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

char s[100]; // 按位逼近的
char str[100]; // str2index

int dp[6][6][6][6][6];

int dfs(int a=0, int b=0, int c=0, int d=0, int e=0, char ch='A') {
  if(ch > 'Y') return 1;
  int &ret = dp[a][b][c][d][e];
  if(ret) return ret;
  // 每一行 一定小于等于上一行
  int w = 5;
  int *v[6]={&w,&a,&b,&c,&d,&e};
  rep(i,1,6){
    // 未填过 和 已经填过(按照 字母顺序扩展)
    int idx = *v[i]+(i-1)*5;
    if(*v[i] < *v[i-1] && (s[idx] == 0 || s[idx] == ch)){
      (*v[i])++;
      ret+=dfs(a,b,c,d,e,ch+1);
      (*v[i])--;
    }
  }
  return ret;
}

void index2word(){
  int n;
  scanf("%d",&n);
  rep(i,0,25){
    for(s[i] = 'A';; s[i]++) { // 按位逼近 时间复杂度25×25
      memset(dp, 0,sizeof(dp));
      int ret = dfs();
      // cout<<i<<" = "<<s[i]<<"\tret = "<<ret<<endl;
      if(ret >= n) break;
      n -= ret;
    }
  }
  printf("%s\n", s);
}

void word2index(){
  scanf("%s", str);
  int ans = 1;
  rep(i, 0, 25)  {
    for(s[i] = 'A'; s[i] < str[i]; s[i]++) {
      memset(dp, 0,sizeof(dp));
      ans += dfs();
    }
  }
  printf("%d\n", ans);
}

int main(){
  usefile();
  char c;
  cin >> c;
  if(c == 'N')  { // index 2 word
    index2word();
  } else if(c == 'W')  { // word 2 index
    word2index();
  }
  return 0;
}

上面实现中 dp过程是按照字母顺序填写，由ch保证，所以在最外层枚举dp的时候，就直接从A 到Y 了

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

Canada Tour

题目大意

双向连通图,点从左向右排列，

你需要先从最左的点到最右的点，（过程中只能从左向右走）

然后再从最右的点返回最左的点，（过程中只能从右向左走）

过程中除了最左的点，其它点都至多能经过一次

求最多能经过的点的个数

题解

从右向左走反过来，就是说从左向右走，题目变成从最左两条不相交到达最右的路径，经过最多的点

一个问题是如何解决没有重复的点

这里的解决方案是

dp[i][j]表示没有重复的点的情况下 一条路径走到点i，一条路径走到点j，经过的点的最大的个数

在状态转移的时候需要保证新的状态有i<j,

dp[i][j] = dp[i][k]+1 ,如果k->j有路径， 我们保证了除了初始点dp[0][0]=1以外，任何i不等于0，有dp[i][i] = 0,

证明一下

首先任何可达的状态不会遗漏，假设存在路径 一边到i，一边到j，（不妨设i<j）那么有它的来源一定能从[i][k]来

再不重复点证明

抛开初始点

因为保证了i<j,dp[i][j]的来源仅为dp[i][k],我们有k一定不等于i，所以只要dp[i][k]是没有重复点的即可

因此递归可证明，这样的dp是不会经过重复点，

最后考虑都到达最右的点，那么发现和dp[i][最右]的 经过的点数一致，注意的是 注意判断点i到最右点是否有路径

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
#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 = "tour";

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

char s[210],t[210];
map<string,int>str2idx;
int n,m,mp[110][110],dp[110][110];
int main(){
  usefile();
  scanf("%d%d",&n,&m);
  rep(i,0,n){
    scanf("%s",s);
    str2idx[s]=i;
  }
  rep(i,0,m){
    scanf("%s %s",s,t);
    mp[str2idx[s]][str2idx[t]]=1;
    mp[str2idx[t]][str2idx[s]]=1;
  }
  int ans=1;
  dp[0][0]=1;
  rep(i,0,n){
    rep(j,i+1,n){
      rep(k,0,j){
        if(mp[j][k]&&dp[i][k]&&dp[i][k]+1>dp[i][j]){
          dp[i][j]=dp[j][i]=dp[i][k]+1;
        }
      }
    }
    if(mp[i][n-1]){
      ans=max(ans,dp[i][n-1]);
    }
  }
  printf("%d\n",ans);
}

Character Recognition

题目大意

先提供空格和26个小写字母的 字符画01矩阵，每个字符都是20*20

然后 你需要解析一段n*20字符矩阵，n行20列

这段矩阵和标准的差异是，

  1. 对于一个字符，可能某一行被倍增了 变成21行，它紧接着倍增那行
  2. 对于一个字符，可能某一行被吞了 变成19行
  3. 0 和 1 和真实值不同

上面问题可以存在的组合有，和原始完全一致，单纯1，单纯2,1+3,2+3，其中 0和1 的改变率小于等于30%

题目呢，可以说相当于 USACO帮我们建了个OCR的模型！！！我们在该模型下实现算法

题解

f[i]表示从最开始到第i行最小误差

f[i] = min(f[i-19]+19行来匹配，f[i-20]+20行来匹配,f[i-21]+21行来匹配)

我们预先处理　所有字符的行(27*20)　和　目标匹配的行N

O(N*27*20)

然后 直接dp，O(N*(20*3)) 理论上如果做了前缀和后缀和优化

实现如下

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
#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 = "charrec";

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

int n,m;
char str[]=" abcdefghijklmnopqrstuvwxyz";
char s[30][30][30];// 标准字符集[idx][i][j]
char t[1210][30]; // 目标字符串[i][j]
int diff[30][30][1210]; // 预处理 [字符idx][字符的i行][目标的j行] = 01差异和
tuple<int,int,int>dp[1210]; // {最小代价，父节点，字符}
const int SUP = 1000000;


// 从st行开始匹配len行，返回{最小的代价，匹配的字符};
pair<int,int> solve(int st,int len){
  pair<int,int>ret= {SUP,-1};
  rep(i,0,27){
    if(len==20){
      int sum=0;
      rep(k,0,20){
        sum+=diff[i][k][st+k];
      }
      ret= min(ret,{sum,i});
    }else{
      // 这边重复计算了， 这里可以用前缀和 后缀和继续优化, 目测可以优化掉约10-20倍性能
      // 不过因为USACO的数据比较小 这样已经是0.1s内了 就没写优化了
      rep(j,0,20){ // 枚举删掉或增加的行
        int p=st,sum=0;
        rep(k,0,j){
          sum+=diff[i][k][p++];
        }
        if(len==21){ // 19为删掉 21为增加
          sum+=diff[i][j][p++];
          sum+=diff[i][j][p++];
        }
        rep(k,j+1,20){
          sum+=diff[i][k][p++];
        }
        ret= min(ret,{sum,i});
      }
    }
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  freopen("font.in","r",stdin);
  freopen("charrec.out","w",stdout);
  scanf("%d",&n);
  rep(idx,0,27){
    rep(i,0,20){
      scanf("%s",s[idx][i]);
    }
  }
  fclose(stdin);
  freopen("charrec.in","r",stdin);
  scanf("%d",&m);
  rep(i,0,m){
    scanf("%s",t[i]);
    dp[i] = {SUP,0,0};
  }
  // 预处理 把每个字符的每一行 都和 目标字符比
  // 目标k行 和 第x个字符 的y行 比较不同的01个数
  rep(idx,0,27){
    rep(i,0,20){
      rep(mm,0,m){
        rep(j,0,20){
          diff[idx][i][mm]+=s[idx][i][j]!=t[mm][j];
        }
      }
    }
  }
  rep(i,18,m){
    rep(len,19,22){
      auto [cost,idx]=solve(i-len+1,len);
      dp[i] = min(dp[i], {cost+(i-len<0?0:get<0>(dp[i-len])),i-len,idx});
    }
  }
  vector<char>ans;
  int i=m-1;
  do{
    ans.push_back(str[get<2>(dp[i])]);
  }while((i=get<1>(dp[i]))>0);
  per(itr,0,ans.size()){
    printf("%c",ans[itr]);
  }
  printf("\n");
  return 0;
}

Telecowmunication

题目大意

100点，无向图

网络流，最小字典序的最小割点

记得前不久才有一个USACO的 最大流问题

题解

老生常谈了，=。=难道是我练题的顺序不对，感觉在刚刚学完最大流 最小割的时候，就会学到拆点啊。

然后直接最小割点就出来了，然后字典序就依次枚举 再计算？想了想编码似乎不可行 1 + 100 vs 2+3若都是可行的，显然前面的字典序小

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
#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 = "telecow";

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

int n,m,c1,c2;

int p2p[210][210];

int vis[210];
int flow[210][210];

void clearvis(){
  rep(i,1,2*n+1){
    vis[i]=false;
  }
}

void dup(){
  rep(i,1,2*n+1){
    rep(j,1,2*n+1){
      flow[i][j]=p2p[i][j];
    }
  }
}

int stk[210];

int bfs(int idx,int dst){
  clearvis();
  int st = 0,rear=0;
  stk[rear++]=idx;
  vis[idx] = true;
  while(st<rear){
    int p = stk[st];
    rep(i,1,n*2+1){
      if(vis[i])continue;
      if(flow[p][i]){
        if(i == dst){
          return true;
        }
        stk[rear++]=i;
        vis[i]=true;
      }
    }
    st++;
  }
  return false;
}

int dfs(int idx,int dst){
  if(idx == dst){
    return 1;
  }
  vis[idx] = true;
  rep(i,1,2*n+1){
    if(vis[i])continue;
    if(!flow[idx][i])continue;
    int r = dfs(i,dst);
    if(r){
      flow[idx][i] -= r;
      flow[i][idx] += r;
      return r;
    }
  }
  return 0;
}

int maxflow(){
  int ret =0;
  while(bfs(c1*2,c2*2-1)){
    clearvis();
    ret+=dfs(c1*2,c2*2-1);
  }
  return ret;
}

void addp(int p1,int p2){
  int p1i=p1*2-1;
  int p1o=p1*2;
  int p2i=p2*2-1;
  int p2o=p2*2;
  if(p1!=c1 && p2 != c2){
    p2p[p2o][p1i] = 1;
  }
  if(p1!=c2 && p2 != c1){
    p2p[p1o][p2i] = 1;
  }
}

int main(){
  usefile();
  cin>>n>>m>>c1>>c2;
  rep(i,0,m){
    int a,b;
    scanf("%d %d",&a,&b);
    addp(a,b);
  }
  rep(i,1,n+1){
    p2p[i*2-1][i*2]=1;
  }
  dup();
  int ans = maxflow();
  cout<<ans<<endl;
  vector<int>ps;
  rep(i,1,n+1){
    if(i== c1 || i==c2){
      continue;
    }
    dup();
    flow[i*2-1][i*2]=0;
    int ret = maxflow();
    if(ret == ans-1){
      ps.push_back(i);
      ans-=1;
      p2p[i*2-1][i*2]=0;
    }
  }
  rep(i,0,ps.size()){
    printf("%d%c",ps[i]," \n"[i==ps.size()-1]);
  }
  return 0;
}

总结

第一题的DP的方法，我要是打cf没遇到，估计是想不出怎么处理路径不重复点 的 这样的状态转移

第二题的DP实现没啥好说的，但这样一个OCR模型 感觉也是很“实际”

第三题 emmmm 感觉刚学完网络流的时候 就知道拆点，好像没什么特别的。

0%