YeXiaoRain Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 869 所需閱讀時間 ≈ 3 分鐘
D (DP)

D

原题链接

大意

n*n正方形 有黑有白

每次可以选择一个 矩形把它全变成白色，代价是max(长,宽)

求吧 整个正方形 全变白 的最小代价

数据范围

n <= 50

题解

首先如果 我们刷了两个有相邻边或重叠的 白色矩形

那么 假设他们的代价分别为 x和y

那么 一定有 一个 变长为x+y的正方形 完全覆盖了这两个白色矩形

dis|row| <= rowX+roxY <= costX+costY = x+y

dis|col| <= colX+roxY <= costX+costY = x+y

所以综上所述 两两不重叠

再来，证明 如果 最优结果要么选择的单一矩形，要么一定能 垂直 或水平分化,即是 不会出现类似 弦图 这样的分化

假设存在，那么意味这有n*m的矩形，和对应选择多个图画方案，使得

  1. 图画方案是最优的
  2. 子选择矩形个数大于1
  3. 不存在按竖着 分化,或横着分化，使得子选择被分开

对于横向来看，意味着任意选择分割线 都会和最优解的选择中的矩形的横着的边冲突，

也就意味着，从min横向点 到 max横向点，所有点都有边。

即是，从横向看 最优解的 cost 横向 >= (max横向点-min横向点)

由对称性，从纵向看 最优解的 cost 纵向 >= (max纵向-min纵向点)

那么我们直接用 相应的大矩形(max横向点-min横向点,max纵向-min纵向点) 从面积上覆盖 最优解答

即

大矩形 cost (从覆盖关系，和最优解答定义)>= 最优解答cost (根据横向和纵向边的关系)>= 大矩形cost

综上

  1. 没有重叠 至多相邻
  2. 要么 单一选择的矩形(如大矩形)，要么可纵向 或 可横向分割

所以

1
2
3
4
5
6
dp[top i0 -> bottom i1][left j0 -> right j1]
=min(
  max(i1-i0,j1-j0),
  dp[i0 -> k][j0->j1] + dp[k+1->i1][j0->j1],
  dp[i0 -> i1][j0 -> k] + dp[i0->i1][k+1->j1],
)

时间复杂度 O(枚举长 * 枚举宽 * 枚举左上角坐标 * 状态转移) = O(n * n * (n * n) * n) = O(n^5)

能过

代码 Rust

920ms/1s 强行 过了,慢应该是用Vec的原因,如果换成c++的直接数组的话，应该能快很多，// 我暂时还没玩会Rust的多维数组

CODE URL

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
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;

struct Scanner {
   buffer : std::collections::VecDeque<String>
}

impl Scanner {

   fn new() -> Scanner {
      Scanner {
         buffer: std::collections::VecDeque::new()
      }
   }

   fn next<T : std::str::FromStr >(&mut self) -> T {

      if self.buffer.len() == 0 {
         let mut input = String::new();
         std::io::stdin().read_line(&mut input).ok();
         for word in input.split_whitespace() {
            self.buffer.push_back(word.to_string())
         }
      }

      let front = self.buffer.pop_front().unwrap();
      front.parse::<T>().ok().unwrap()
   }
}

fn main() {
    let mut s = Scanner::new();
    let n : usize = s.next();
    // dp[top i][left j][bottom i][right j] 全部清理 需要的最小代价
    let mut dp = vec![vec![vec![vec![0;n+1];n+1];n+1];n+1];
    for i in 0..n {
        let line:String = s.next();
        for (j, ch) in line.chars().enumerate() {
            if ch == '#' {
                dp[i][j][i][j] = 1;
            }
        }
    }
    // 枚举 矩形大小从小到大
    for i in 0..n {
        for j in 0..n {
            if i == 0 && j == 0 {
                continue;
            }
            // 枚举 矩形左上角坐标
            for p in 0..n-i {
                for q in 0..n-j {
                    // 右下角坐标
                    let (x,y) = (i+p,j+q);
                    dp[p][q][x][y] = max(i,j)+1;
                    for k in p..x {
                        dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][k][y]+dp[k+1][q][x][y]);
                    }
                    for k in q..y {
                        dp[p][q][x][y]=min(dp[p][q][x][y],dp[p][q][x][k]+dp[p][k+1][x][y]);
                    }
                }
            }
        }
    }
    println!("{}",dp[0][0][n-1][n-1]);
}

發表於 更新於 分類於 ， Disqus： 文章字數： 905 所需閱讀時間 ≈ 3 分鐘
E (dp+sort+二分)

原题链接

2300分

大意

俄罗斯套娃，每个有内容半径in和外围半径out

in_i<out_i

如果 in_i >= out_j ,那么j可以放在i内

定义残留空间 = 一列嵌套的套娃 未使用的半径和 ,如 {1,2},{2,5},{7,9},未使用的白净和为(1-0)+(2-2)+(7-5) = 3

有效残留空间，如果 一列嵌套的套娃，还能从给出的套娃中选择一个加入这一列，那么原本的残留空间为无效值。如给{1,2},{2,3},{2,5},{7,9},只选择{1,2},{7,9}是无效的嵌套列，而选择{1,2},{2,3},{7,9}是有效的

令M = 最小的有效残留空间

求有效残留空间=M的方案数 % MOD

数据范围

套娃个数<= 200'000

半径<=1'000'000'000

MOD = 1'000'000'007

题解 翻译自官方题解

赛内我写了大概十多分钟没写出来,算法是想到n方的 但是没想到怎么优化到时间复杂度内

https://codeforces.com/blog/entry/68615

首先我们 把它们按照内半径排序in_i,

dp[i] = {x,y} 从末尾到第i个，最小的有效残留空间x, 这样的情况下的方案数 y

dp[i] = {in_i,1} 如果没有 能套在i外面的

如果有能套在i外面的j 那么

dp[i].x = min(d[j].x - (out_i-in_i)) = min(d[j].x) - (out_i-in_i)

我自己考虑漏的一点，假设 我们在尝试i了，那么min[d[ all j such in_j>=out_i ].x] 对于>=i 来说,一定是有效的,当时考虑漏了，在想怎么维护左右游标，来计算有效范围内的最小值

反证法

因为我们 要把i放在j内，如果不是有效的，

首先我们的dp定义保证了 不会插入其它在j以后

那么意味着，在i和j之间还能插入其它，假设为k

那么有d[k].x < d[j].x 和我们刚刚假设的min矛盾

综上

读入O(n)

排序O(n log n)

维护一个minx数组

每次计算dp[i] 二分>=out_i的坐标,计算完后更新minx 每次O(log n)

总共O(n log n)

代码 (Rust)

https://codeforces.com/contest/1197/submission/57928269

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
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use std::ops::Bound::*;
 
struct Scanner {
   buffer : std::collections::VecDeque<String>
}
 
impl Scanner {
 
   fn new() -> Scanner {
      Scanner {
         buffer: std::collections::VecDeque::new()
      }
   }
 
   fn next<T : std::str::FromStr >(&mut self) -> T {
 
      if self.buffer.len() == 0 {
         let mut input = String::new();
         std::io::stdin().read_line(&mut input).ok();
         for word in input.split_whitespace() {
            self.buffer.push_back(word.to_string())
         }
      }
 
      let front = self.buffer.pop_front().unwrap();
      front.parse::<T>().ok().unwrap()
   }
}
 
fn main() {
    const MOD:i32 = 1_000_000_007;
    let mut s = Scanner::new();
    let n : usize = s.next();
    let mut arr:Vec<(i32,i32)> = Vec::new();
    for _i in 0..n {
        let out_i: i32 = s.next();
        let in_i: i32 = s.next();
        arr.push((in_i,out_i));
    }
    arr.sort();
    let mut minx:BTreeMap<i32,(i32,i32)> = BTreeMap::new(); // (in>=, (mincost,cnt))
    let mut ans:i32 = 0;
    for i in arr.iter().rev() {
        let out_i = i.1;
        let in_i = i.0;
 
        // 二分找到 >= out_i 的minx
        //
        let bin_res:(i32,i32) = match minx.range((Included(&out_i), Unbounded)).next() {
            Some(val) => *(val.1),
            None => (out_i,1)
        };
 
        let cost = (bin_res.0 - (out_i - in_i), bin_res.1);
        // 获取当前>=in_i 的 minx 如果没有则是 0
 
        let cur = match minx.range((Included(&in_i), Unbounded)).next() {
            Some(val) => *(val.1),
            None => (cost.0,0)
        };
 
        let count = minx.entry(in_i).or_insert(cur);
        if count.0 > cost.0 {
            ans = cost.1;
            (*count) = cost;
        } else if count.0 == cost.0 {
            (*count).1 += cost.1;
            (*count).1 %= MOD;
            ans = (*count).1;
        }
        // println!("{:?} {:?}", i , count);
    }
    println!("{}",ans );
}

总结

最近在看Rust，想说 这lower_bound 用range来写,写得我自闭,但是回过头来看

感觉用match比c++写 成lower_bound 再判断是否等于.end()更加清晰

再比如 下面

entry+or_insert这里

最开始我的两个if里分别时minx.insert和count操作，这样 连编译都通不过，因为一个变量不允许同时 两个mutable

此外 赞美一下 .0,.1相对于 c++中的 .first,.second或者说 get<0>(...),get<1>(...)

简洁而不失去意义

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

All Latin Squares

题目大意

n x n矩阵(n=2->7)

第一行1 2 3 4 5 ..N

每行每列，1-N各出现一次，求总方案数

题解

n最大为7 显然打表

写了个先数值后位置的暴搜

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

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

int n;
int v[10][10]; // [row][col]

int vis[10][10]; // [val][col]

int anscnt =0;

void dfs(int val,int row){
  if(val > n){
    anscnt++;
    return ;
  }
  rep(j,1,n+1){
    if(v[row][j] == 0 && !vis[val][j]){
      v[row][j] = 1;
      vis[val][j] = 1;
      if(row+1 < n){
        dfs(val,row+1);
      }else{
        dfs(val+1,1);
      }
      vis[val][j] = 0;
      v[row][j] = 0;
    }
  }
}

int main(){
  //  usefile();
  cin>>n;
  rep(i,1,n+1){
    v[0][i]=i;
    vis[i][i]=1;
  }
  dfs(1,1);
  cout<<anscnt<<endl;
  return 0;
}

6能搜出来，7要等好久,考虑改算法

但是数列嘛,当然先上OEIS看看http://oeis.org/search?q=1%2C2%2C24%2C1344%2C1128960&sort=&language=english&go=Search

7的时候答案是12198297600,看来直接暴搜是不太可能

考虑 一个成功的方案， 把它的非首行的两行交换，也是合法的

所以考虑第一列也定为1到N,最后乘上(N-1)!

这样计算的次数是16942080

在我i7-7700HQ上跑是

1
2
3
4
5
6
> time echo 7 | ./6.5.1
12198297600

real	0m17.194s
user	0m17.190s
sys	0m0.006s

固定第一列的代码

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 = "latin";

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

int n;
int v[10][10]; // [row][col]

// [0->n-1][1->n]
int vis[10][10]; // [val][col]

long long anscnt =0;

void dfs(int val,int row){
  if(val > n){
    anscnt++;
    return ;
  }
  if(val == row+1){
    if(row+1 < n){
      dfs(val,row+1);
    }else{
      dfs(val+1,1);
    }
    return ;
  }
  rep(j,1,n+1){
    if(v[row][j] == 0 && !vis[val][j]){
      v[row][j] = 1;
      vis[val][j] = 1;
      if(row+1 < n){
        dfs(val,row+1);
      }else{
        dfs(val+1,1);
      }
      vis[val][j] = 0;
      v[row][j] = 0;
    }
  }
}

int main(){
  //  usefile();
  cin>>n;
  rep(j,1,n+1){
    v[0][j]=j;
    vis[j][j]=1;
  }
  rep(i,1,n){
    v[i][1]=i+1;
    vis[i+1][1]=1;
  }
  dfs(1,1);
  rep(i,1,n){
    anscnt*=i;
  }
  cout<<anscnt<<endl;
  return 0;
}

网上搜了一下方法，有一种是 靠循环节 置换圈 大概群论相关

而我决定 放弃，打表吧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
#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 = "latin";

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

int n;

map<int,long long >ans;

int main(){
  usefile();
  ans[2]= 1;
  ans[3]= 2;
  ans[4]= 24;
  ans[5]= 1344;
  ans[6]= 1128960;
  ans[7]= 12198297600;
  cin>>n;
  cout<<ans[n]<<endl;
  return 0;
}

Closed Fences

题目大意

计算几何

逆时针给一系列点(<=200个),坐标范围(| |<=2^16)检查 这些点是否能围成一个围栏

如果可行,再给一点 输出 从该点发出射线，能照到的线段 (只要部分能被照到 就输出整段)

如果 给的点，和一条线段共线，视作无法照到

题解

看上去像是可以枚举，按照角度，200次遍历射线，每次射线遍历200条边，一共就n方左右的复杂度

我们先 过一边所有线段如果不相交，那么可以围成（这里没有判断顺时针还是逆时针）

然后枚举所有线段，对每一条线段1000等分，枚举从给定的点 向等分点是否与其它线段有交点

时间复杂度O(n*n*1000);

[这题的核心还是说写计算几何的算法

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

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


pair<int,int> p;
pair<int,int> P[210];
int N;


double cross(pair<double,double> a,pair<double,double> b){
  return a.first*b.second-a.second*b.first;
}

pair<double,double> operator + (pair<double,double> a,pair<double,double> b)  {
  return {a.first+b.first,a.second+b.second};
}

pair<double,double> operator - (pair<double,double> a,pair<double,double> b)   {
  return {a.first-b.first,a.second-b.second};
}

bool isIntersect(pair<pair<double,double>,pair<double,double>> line1,pair<pair<double,double>,pair<double,double>> line2){
  return  !(
      (cross(line1.first -line2.first,line2.second-line2.first) > 0) ==
      (cross(line1.second-line2.first,line2.second-line2.first) > 0) ||
      (cross(line2.first -line1.first,line1.second-line1.first) > 0) ==
      (cross(line2.second-line1.first,line1.second-line1.first) > 0)
      );

}

bool isValid(){
  rep(i,0,N){
    rep(j,i+2,N){
      if(i == 0 && j == N-1)continue;
      if(isIntersect({P[i],P[i+1]}, {P[j],P[(j+1)%N]})){
        return false;
      }
    }
  }
  return true;
}

// 共线
bool isColine(int idx){
  return cross(P[idx]-P[(idx+1)%N],p) == cross(P[idx],P[(idx+1)%N]);
}

bool isSeen(int idx){
  int x1 = P[idx].first;
  int y1 = P[idx].second;
  int nsegments = 1000;
  rep(i,1,nsegments){
    pair<double,double> point_ =  {
      x1 + i * 1.0 / nsegments * (P[(idx + 1) % N].first  - x1),
      y1 + i * 1.0 / nsegments * (P[(idx + 1) % N].second - y1)};
    bool blocked = false;
    rep(j,0,N){
      if(j == idx)      {
        continue;
      }
      if(isIntersect({p,point_}, {P[j],P[(j+1)%N]})){
        blocked = true;
        break;
      }
    }
    if(!blocked)    {
      return true;
    }
  }
  return false;
}

vector<int> ans;
int main(){
  usefile();
  scanf("%d", &N);
  scanf("%d %d", &p.first,&p.second);
  rep(i,0,N){
    scanf( "%d %d", &P[i].first, &P[i].second);
  }
  if(!isValid())  {
    printf( "NOFENCE\n");
    return 0;
  }
  rep(i,0,N){
    if(!isColine(i) && isSeen(i))    {
      ans.push_back(i);
    }
  }
  if(ans.size() >= 2 && ans[ans.size() - 2] == N - 2){
    ans[ans.size() - 2] = N - 1;
    ans[ans.size() - 1] = N - 2;
  }
  printf("%d\n", int(ans.size()));
  rep(i,0,ans.size()){
    if(ans[i] == N - 1)    {
      printf("%d %d %d %d\n", P[0].first, P[0].second, P[ans[i]].first, P[ans[i]].second);
    }else{
      printf( "%d %d %d %d\n", P[ans[i]].first, P[ans[i]].second, P[ans[i] + 1].first, P[ans[i] + 1].second);
    }
  }
  return 0;
}

Betsy’s Tour

题目大意

n x n(n<=7) 的矩阵，从左上走到坐下，每个格子最多经过一次的方案数

题解

暴搜+打表

插头dp ? 像是

实现了一下 果然过了，注意处理n = 1

插头dp的话 直接百度文库 应该能搜到不少文章，我感觉我的边界处理和状态转移的代码写得好丑QAQ

  1. 这里的一个技巧是，想象在左边在多出一列，把这列从上连到下，这样原题就变成确定了一部分路线的欧拉回路的插头dp了,这样 起始和终点的就也和中间的过程块，看作联通其它两个块的 来处理了
  2. 状态表示，最无脑的是，相同数字，但是 这样的话状态转移会比较难写 比如100120332，注意到我们会一直维持合法性,所以可以用左右括号表示(__)(_()),这样的化就是3进制即可，然后4进制更容易操作，比如我下面用的位运算<<2 或 >>2
  3. 在上面两个优化下 初始状态是(______)这样的

时间复杂度O(i*j*state) = O(7*7*3^7)

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

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

int n;

// 中间的 每个块 连接 两个方向，

map<pair<int,long long>,long long> res;

int get_state(long long state,int pos){
  return (state >> (2*pos)) % 4;
}

int set_state(long long state,int pos){
  return state << (2*pos);
}

// ((    ) ())
// block: 的2进制位 0b3210
//   3
//  0 2
//   1
long long insert_state(long long old_state,int pos,int block){
  int arr[10];
  // 栈计算括号对
  int p[10];
  int stk[10];
  int stki = 0;
  rep(i,0,n+1){
    arr[i] = get_state(old_state,i);
    if(arr[i] == 0)continue;
    if(arr[i] == 1)stk[stki++]=i;
    if(arr[i] == 2){
      p[i] = stk[stki-1];
      p[stk[stki-1]] = i;
      stki--;
    }
  }
  int cnt = 0;
  rep(i,0,4){
    cnt+= !!(block & (1<<i));
  }
  assert(cnt == 2);
  // 插入的块和 被插入的位置 同时有或没有
  if( (!(block & 0b1000) != !arr[pos]) || (!(block & 0b0001) != !arr[pos+1]) ){
    return -1;
  }
  // 原来为空 新建边
  if( (block & 0b0100) && (block & 0b0010)){
    arr[pos] = 1;
    arr[pos+1] = 2;
  }else if( (block & 0b0100) || (block & 0b0010) ){ // 引出一条原来的边
    if(block & 0b0100){
      arr[pos] = arr[pos]+arr[pos+1];
      arr[pos+1] = 0;
    }else {
      arr[pos+1] = arr[pos]+arr[pos+1];
      arr[pos] = 0;
    }
  }else{ // 把原来两段 连接起来
    if(arr[pos] == 1 &&  arr[pos+1] == 2){
      arr[pos] = 0 ;
      arr[pos+1] = 0 ;
    }else{
      arr[pos] = 0;
      arr[pos+1] = 0;
      int p1 = p[pos];
      int p2 = p[pos+1];
      if(p1 > p2)swap(p1,p2);
      arr[p1] = 1;
      arr[p2] = 2;
    }
  }
  long long new_state = 0;
  rep(i,0,n+1){
    new_state += set_state(arr[i],i);
  }
  return new_state;
}

long long dp(int idxi,int idxj,long long state){
  long long &ret = res[{(idxi<<3)+idxj,state}];
  if(ret != 0){
    return ret;
  }
    // 右下角允许自连
  if(idxj == n-1 && idxi == n-1) {
    return ret = (get_state(state,n-1) == 1 && get_state(state,n) == 2);
  }
  // 过程中不允许自连
  //
  if (get_state(state,idxi) == 1 && get_state(state,idxi+1) == 2)return 0;
  rep(i,0,4){
    rep(j,i+1,4){
      int new_state = insert_state(state,idxi,(1<<i)+(1<<j));
      if(new_state == -1)continue;
      // 最后一列
      if(idxj == n-1) {
        if(get_state(new_state,idxi) != 0)continue;
      }
      // 最后一行
      if(idxi == n-1){
        if(get_state(new_state,idxi+1) != 0)continue;
        new_state <<=2;
        ret+=dp(0,idxj+1,new_state);
      }else{
        ret+=dp(idxi+1,idxj,new_state);
      }
    }
  }
  // printf("(%d,%d) {%lld,%lld,%lld} = %lld\n",idxi,idxj,(state)%4,(state>>2)%4,(state>>4)%4,ret);
  return ret;
}

int main(){
  usefile();
  cin>>n;
  if(n == 1){
    cout<<1<<endl;
  }else{
    cout<<dp(0,0,set_state(1,1)+set_state(2,n))<<endl;
  }
  return 0;
}

总结

6.5章其实有5个题,但后面两题 我很久很久很就以前做了 就不想再做一次了，所以这里只写了3题

本文其它链接

牛客: https://blog.nowcoder.net/n/c7f0a70d69254c9180dd0b7e475d1248

cnblogs: https://www.cnblogs.com/CroMarmot/p/11149313.html

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

0%