YeXiaoRain Blog(hexo的搜索高亮会破坏latex)

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 4 分鐘
E(AC自动机(Aho–Corasick automaton))

E

原题链接

大家都会ac自动机就我不会

本题目2500评分

大意

字符串$t$

和长$n$字符串列表 $s$

对于 所有$(i,j)$, 求s[i]+s[j]在t中的出现次数的和

数据范围

$|t|\le 200’000$

$n \le 200’000$

$|s_i| \in [1,200’000]$

$\sum |s_i| \le 200’000$

题解

显然

$ans = \sum \mathrm{suffix}i \cdot \mathrm{prefix}{i+1}$ 也就是 以$i$结尾匹配到 的次数 乘上$i+1$为开头匹配到的次数

那么问题来了，如何计算成功匹配的次数

引理 Aho–Corasick automaton

前置知识: Trie树, KMP

AC自动机 是什么?

答: 一种算法可以自动AC所有题目,多个模式同时匹配

AC自动机 从数据结构上看起来是个什么？

Trie Tree(字典树) + 匹配失败时的目标跳转指针(仿照KMP)

trie tree and fail

对于字典建立的自动机

1
2
3
4
5
6
7
a
ab
bab
bc
bca
c
caa

其中 后缀链接(suffix links/fail边)为蓝色, 字典后缀链接(dictionary suffix links)为绿色, 字典项为高亮蓝圆

建立Trie树

节点内容

1
2
3
4
5
map<char,Node*> next 黑色边
cnt 蓝色圆(条目计数)
dep 长度/高度
fail 仿照kmp失配边, 绿色边
last 后缀链接 蓝色边

在建立过程中，结束的位置计数cnt++ (蓝色圆)

记录深度dep

计算next

建立 fail边

fail边的意义, 这来自于kmp中的fail, 假设当前为s, 则是指向s的最长后缀, 且为某个模式的前缀

1
2
3
4
5
s: ????abcde
           |
           |
           v
t:     abcde 且t是某个最长前缀

默认值为所有fail边指向根节点

按深度(dep)从小到大广搜，

第一层节点的fail都指向根节点(一个字符更短的只有空字符串

每个节点的子节点扩展

p->next[charX] = p->fail->next[charX]

如果p->fail的后续节点没有charX呢? 实际上会递归fail(p->fail->fail->next[charX]),去找首个有charX的(和kmp里的一样)

匹配字符串

当建立完fail边就可以拿来匹配字符串了, 每次失去匹配通过fail进行跳转

建立last边

如何计数 当有 abba和bb的时候，如何能计数到bb?

每个节点增加一个last，指向 dep小于该节点的，存在的是该字串后缀的末节点。

1
2
3
root-a-b-b-a
    \
     b-b

这样的情况下，需要一条last，从a-b-b指向b-b的后一个b,其余节点的last指向根节点

所有last默认指向根节点

要是某个后缀，那么cnt>0,又要小于该字符串的最长的

则 ->fail(当->fail->cnt >0) 或->fail->last(->fail->cnt ==0 )

这样增加了last指针后，在匹配时，如果当前链下是后缀，则开始计数，如果不是则从当前->last开始计数

换句话说, last的本质是 把fail链上中间的cnt==0的点移除了, 只留了cnt>0的点和起始节点

递归代价? 复杂度分析?

fail边

不妨把fail 指针看到它指向的dep, 那么在树上, 显然每个点要么比它父节点指向的dep大1, 要么比父节点小, 每个从根到叶子的相邻变化和非负,且小于链长度, 正变化+|负变化| <= 2长度, 所以所有变化次数和 <= 2所有t的长度和, 和O(trie)建树一样的复杂度

当每层节点较少，比如只包含所有小写字母时，可以增加每层节点优化掉这递归过程

last边

很显然 每个点操作代价为常数 所以O(点 < sum |字典|)

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
const int MAX = 2e5+10;
struct AC_Automaton {
  static const int K=26;//may need change
  static const int MAX_NODE=2e5+10;
  int getid(char c) {//may need change
    return c-'a';
  }
  struct AC_NODE{
    AC_NODE * next[K];
    AC_NODE * fail;
    AC_NODE * last;
    int cnt;
    int dep;
    void init(AC_NODE * ac_n){
      rep(i,0,K){
        next[i] = ac_n;
      }
      fail = ac_n;
      last = ac_n;
      cnt = 0;
      dep = 0;
    }
  }nodes[MAX_NODE];
  AC_NODE * root;
  int tot;
  AC_NODE * newnode() {
    nodes[tot].init(&nodes[0]);
    return &nodes[tot++];
  }
  void init() {
    tot=0;
    root=newnode();
  }
  void insert(char *s) {
    AC_NODE * now = root;
    int len=strlen(s);
    rep(i,0,len){
      int t=getid(s[i]);
      if(now->next[t] == root) {
        now->next[t] = newnode();
        now->next[t]->dep = i+1;
      }
      now=now->next[t];
    }
    now->cnt++;
  }
  void setfail() {
    queue<AC_NODE *>q;
    rep(i,0,K){
      if(root->next[i] != root){
        q.push(root->next[i]);
      }
    }
    while(!q.empty()){
      AC_NODE * now=q.front();
      q.pop();
      //suffix link
      now->last = now->fail->cnt > 0 ? now->fail : now->fail->last;
      rep(i,0,K){
        if(now->next[i] != root) {
          now->next[i]->fail=now->fail->next[i];
          q.push(now->next[i]);
        }else{
          now->next[i]=now->fail->next[i];
        }
      }
    }
  }
  ll be[MAX],en[MAX];
  void work(char *s) {
    int n = strlen(s);
    AC_NODE * now = root;
    rep(i,0,n+1){
      be[i]=en[i]=0;
    }
    rep(i,0,n){
      now=now->next[getid(s[i])];
      AC_NODE * tmp = root;
      if(now->cnt){
        tmp=now;
      }else if(now->last->cnt){
        tmp=now->last;
      }
      while(tmp != root){
        en[i]+=tmp->cnt;
        if(i-tmp->dep+1>=0){
          be[i-tmp->dep+1]+=tmp->cnt;
        }
        tmp=tmp->last;
      }
    }
    ll ans=0;
    rep(i,0,n-1){
      ans+=en[i]*be[i+1];
    }
    printf("%lld\n",ans);
  }
}ac;
char s[MAX],tmp[MAX];
int main() {
  int q;
  scanf("%s",s);
  ac.init();
  scanf("%d",&q);
  while(q--) {
    scanf("%s",tmp);
    ac.insert(tmp);
  }
  ac.setfail();
  ac.work(s);
  return 0;
}

参考

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm

https://oi-wiki.org/string/ac-automaton/

TODO 抽个板子

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

0%