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

發表於 更新於 分類於 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 感觉刚学完网络流的时候 就知道拆点，好像没什么特别的。

發表於 更新於 分類於 Disqus： 文章字數： 3.3k 所需閱讀時間 ≈ 11 分鐘
Heuristic Search,IDDFS,离散化,scc,块状矩阵

相关讲解可在USACO上看原文，也可以搜索nocow找到翻译的！ (nocow上有些微翻译是有问题的，如果想看nocow翻译的建议也对着英文看)

以下记录以下 自己之前未掌握的一些要点,以及按自己的括号表述的形式来记录。

USACO Section 5.3 启发式搜索

启发式搜索的主要思想是通过评价一个状态有”多好”来改进对于解的搜索.

0<= 可行的估价函数 <= 实际代价

  1. 启发式剪枝: 若搜到最小值，已经搜索到的最优值为C，当前的代价为A(从起始状态到这里的实际代价)，启发的期望剩余代价为B（从当前点到目标的估价），如果A+B>C也就是期望总代价比已经搜索的还大，那么剪枝，注意到上面有提到：估价函数是小于等于实际代价，也就意味实际代价>=A+B>C,所以可以剪枝

  2. Best-First Search最佳优先: 深搜 中，在子节点访问顺序部分做估价处理，调整搜索顺序，再结合上面的剪枝

  3. A* 可以和第二条相对，看做广搜中加入了顺序估价。

关于估价函数
如果为0，可以看做毫无优化的默认算法。
如果为实际代价，那么就直接可以最快向目标前进。

Milk Measuring - milk4

题意

从P个数中选 取任意个数，使得它们的整数倍数的和=Q

如P: 3,3,5,7

Q:16

16=3*2+5*1

目标，1选的数的个数尽量小，2在个数尽量小的时候，字典序最小

1<=Q<=200000

1<=P<=100

1<=每个数<=10000

输出选择的方案

通过不了的题解

emmmm 我为什么一看就是个sort(从大到小)+dp[当前第几个数][和的值]= {最小选取的个数,最后选择的index,选择的个数,倒数第一次选择的index}

空间O(Q*P),时间O(Q*P) 能得到最小的个和方案,

dp时 优先个数(目标要求个数)，其次上一次的index(因为sort过 且目标要求字典序)，个数用来反向输出方案

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

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

tuple<int,int,int,int>dp[110][20010]; // {usecnt+1,lastuseidx,lastusecnt,preidx};
int val[110];
int Q;
int P;

int main(){
  usefile();
  cin>>Q;
  cin>>P;
  rep(i,0,P){
    scanf("%d",val+i);
  }
  sort(val,val+P,greater<int>());
  rep(p,0,P){
    dp[p][0] = {1,-1,0,-1};
  }
  rep(p,0,P){
    if(p>0){
      rep(q,0,Q+1){
        dp[p][q]=dp[p-1][q];
      }
    }
    rep(q,0,Q){
      auto & item = dp[p][q];
      if(get<0>(item) > 0){
        if(q+val[p] > Q)break;
        auto & pre = dp[p][q+val[p]];
        tuple<int,int,int,int> now = {
          get<0>(item)+ (p !=get<1>(item)),
          p,
          (p!=get<1>(item))?1:get<2>(item)+1,
          (p!=get<1>(item))?get<1>(item):get<3>(item)
        };
        if(get<0>(pre) == 0 || get<0>(pre) >= get<0>(now)){
          pre = now;
        }
      }
    }
  }
  // rep(p,0,P){
  //   cout<<"P:"<<p<<endl;
  //   rep(q,0,Q+1){
  //     printf("[%d %d %d %d]",get<0>(dp[p][q]),get<1>(dp[p][q]),get<2>(dp[p][q]),get<3>(dp[p][q]));
  //   }
  //   cout<<endl;
  // }
  auto ans = dp[P-1][Q];
  printf("%d",get<0>(ans)-1);
  int qq = Q;
  while(1){
    printf(" %d",val[get<1>(ans)]);
    qq-= get<2>(ans) * val[get<1>(ans)];
    if(get<3>(ans) == -1){
      break;
    }
    ans = dp[get<3>(ans)][qq];
  }
  printf("\n");
  return 0;
}

然而不幸的是超空间限制了

Execution error: Your program (milk4’) exited with signal #11 (segmentation violation [maybe caused by accessing memory out of bounds, array indexing out of bounds, using a bad pointer (failed open(), failed malloc), or going over the maximum specified memory limit]). The program ran for 0.000 CPU seconds before the signal. It used 31552 KB of memory. `

优化可以优化掉p，在实现记录的时候用指针的方式，没有尝试能不能改过

可通过的解

IDDFS 迭代加深搜索，使用场景，在低的层级找到解就是最优/目标解。

和广搜的区别是，广搜过程中会用内存记录，而迭代加深每次都是深搜，但是逐次增加深度。

可行性：每次加深深度，新的状态和上一层的状态是数量级差异，所以其实只和最后成功搜索到的层数的数量级相关。

综上，IDDFS有着接近广搜的性能，有着接近深搜的空间消耗。

实现pass如下

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

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

int vis[20010];
int ans[110];
int val[20010];
int Q;
int P;
int dep;

bool check(){
  rep(i,1,Q+1){
    vis[i]=0;
  }
  rep(i,0,dep){
    rep(j,0,Q+1-ans[i]){
      if(vis[j]){
        vis[j+ans[i]]=true;
      }
    }
  }
  if(vis[Q]){
    return true;
  }
  return false;
}

bool dfs(int idx,int cnt){
  ans[cnt] = val[idx];
  if(cnt+1 == dep){
    return check();
  }
  rep(j,idx+1,P+2+cnt-dep){
    if(dfs(j,cnt+1)){
      return true;
    }
  }
  return false;
}

void output(){
  printf("%d",dep);
  rep(i,0,dep){
    printf(" %d",ans[i]);
  }
  printf("\n");
}

int main(){
  usefile();
  cin>>Q;
  cin>>P;
  rep(i,0,P){
    scanf("%d",val+i);
  }
  sort(val,val+P);
  vis[0]=1;
  for(dep=1;dep<=P;dep++){
    rep(i,0,P+1-dep){
      if(dfs(i,0)){
        output();
        return 0;
      }
    }
  }
  return 0;
}

Window Area - window

题意

在电脑上窗口的操作,5种

  • 新建窗口(标识符，x1,y1,x2,y2)
  • 置顶t(标识符)
  • 置底b(标识符)
  • 删除d(标识符)
  • 输出窗体可见百分比s(I) ,询问数<=500

窗体个数上限(2*26+10=62)

坐标范围[1->32767]

题解

那么显然 横纵坐标只有((2×62)^2)个，离线+离散+没了？

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
#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--)
typedef long long ll;

using namespace std;

const string filename = "window";

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

list<int>Is[240][240]; // 大小猜的

vector<int>x;
vector<int>y;

vector<tuple<int,int> >q;

int itr = 0;
vector<tuple<int,int,int,int> >xys;

tuple<int,int,int,int> xyxy[123];

void rm(int ix,int iy,char I){
  for (list<int>::iterator it=Is[ix][iy].begin(); it!=Is[ix][iy].end(); ++it){
    if(*it == I){
      Is[ix][iy].erase(it);
      return ;
    }
  }
}

void top(int ix,int iy,char I){
  rm(ix,iy,I);
  Is[ix][iy].push_front(I);
}

void bot(int ix,int iy,char I){
  rm(ix,iy,I);
  Is[ix][iy].push_back(I);
}

int main(){
  usefile();
  char op;
  while(~scanf("%c",&op)){
    if(op!='w' && op!='t' && op!='b' && op!='d' && op!='s')continue;
    if(op == 'w'){
      char I;
      int x1,y1;
      int x2,y2;
      scanf("(%c,%d,%d,%d,%d)",&I,&x1,&y1,&x2,&y2);
      if(x1> x2){
        swap(x1,x2);
      }
      if(y1>y2){
        swap(y1,y2);
      }
      x.push_back(x1);
      x.push_back(x2);
      y.push_back(y1);
      y.push_back(y2);
      q.push_back({op,I});
      xys.push_back({x1,y1,x2,y2});
    }else{
      char I;
      scanf("(%c)",&I);
      q.push_back({op,I});
    }
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  for(auto item:q){
    int op = get<0>(item);
    int I = get<1>(item);
    if(op == 'w'){
      xyxy[I] = xys[itr++];
    }
    int x1idx=lower_bound(x.begin(),x.end(),get<0>(xyxy[I]))-x.begin();
    int y1idx=lower_bound(y.begin(),y.end(),get<1>(xyxy[I]))-y.begin();
    int x2idx=lower_bound(x.begin(),x.end(),get<2>(xyxy[I]))-x.begin();
    int y2idx=lower_bound(y.begin(),y.end(),get<3>(xyxy[I]))-y.begin();
    switch(op){
      case 'w':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              Is[ix][iy].push_front(I);
            }
          }
          break;
        }
      case 't':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              top(ix,iy,I);
            }
          }
          break;
        }
      case 'b':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              bot(ix,iy,I);
            }
          }
          break;
        }
      case 'd':
        {
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              rm(ix,iy,I);
            }
          }
          break;
        }
      case 's':
        {
          ll sshow = 0;
          rep(ix,x1idx,x2idx){
            rep(iy,y1idx,y2idx){
              sshow+= ((*Is[ix][iy].begin() == I)?(x[ix+1]-x[ix])*ll(y[iy+1]-y[iy]):0);
            }
          }
          ll scnt = (x[x2idx]-x[x1idx])*ll(y[y2idx]-y[y1idx]);
          printf("%.3lf\n",sshow*100/double(scnt));
          break;
        }
    }
  }
  return 0;
}

emmmmmm 在第11个点的时候 出现了唯一标识复用的情况，也就是说 先创建 再删除 再创建，所以期望的边数也就不只 (26*2+10)*2，我这里尝试的是开到240*240才能过

所以基本上是 离散化 O(长乘宽(分化的区块个数)*62(每次操作代价)*(t+b+r操作个数)+长乘宽(分化区块个数)*1(操作代价)*(w+s操作个数))

以上代码还可以优化的地方:

  1. 通过预处理 真实值到离散值，让每个这样的计算只发生一次。

  2. 再建立一个表来优化top,bot,rm到接近O1每次，额外的指针访问时间，缺点是1增加空间，2本身数据不大的情况，枚举查找的效率是不差的

然后有一些博文有 两个矩形之间处理的优化，也就是 不分成9块，而是分成最多5块，类似旋图，然后平时只记录相对的层数(z-index)，然后在查询的时候，才自值开始向上查找。

Network of Schools - schlnet

题意

有向图,(N<=100)个节点

  1. 求最少选取多少个点，通过这些点能够沿着有向边到达所有的点
  2. 求最少加多少边，让真个图变成全连通

题解

emmmm一眼

  1. 直接求强连通，然后缩点，然后按照出度排序，从0开始删，直到为最后只剩独立点，进行统计？
  2. 把这些缩点后的 max(出度为0的点,入度为0的点)

强连通直接tarjan

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

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

int n;

vector<int>p2[110];

const int N=100;


int id = 0;
bool vis[N+10];
int low[N+10];
int dfn[N+10];
vector<int>stk;
bool instk[N+10];

int incnt[N+10];
int outcnt[N+10];

void scc(int idx){
  // cout<<"scc"<<idx<<endl;
  dfn[idx] = low[idx] = ++id;
  vis[idx] = true;
  stk.push_back(idx);
  instk[idx] = true;
  for(auto item:p2[idx]){
    if(!vis[item]){
      scc(item);
      low[idx]=min(low[idx],low[item]);
    }else if(instk[item]){
      low[idx]=min(low[idx],dfn[item]); // dfn->low
    }
  }
  if(low[idx] == dfn[idx]){
    // cout<<"zip:"<<idx<<endl;
    // for(auto item:stk){
    //   printf("\t\tstk[%d]\n",item);
    // }
    int u;
    do{
      u = *(stk.end()-1);
      // cout<<"\tu:"<<u<<endl;
      dfn[u] = idx;
      instk[u] = false;
      stk.pop_back();
    }while(u != idx);
  }
}

void tarjan(){
  rep(i,1,n+1){
    if(!vis[i]){
      scc(i);
    }
  }
  // rep(i,1,n+1){
  //   cout<<"dfn:"<<i<<" = "<<dfn[i]<<endl;
  // }
}

int main(){
  usefile();
  cin>>n;
  rep(i,1,n+1){
    while(1){
      int v;
      scanf("%d",&v);
      if(v == 0)break;
      p2[i].push_back(v);
    }
  }
  tarjan();
  rep(i,1,n+1){
    if(dfn[i]!=i){
      for(auto item:p2[i]){
        p2[dfn[i]].push_back(dfn[item]);
      }
    }else{
      for(auto &item:p2[i]){
        item = dfn[item];
      }
    }
  }
  rep(i,1,n+1){
    if(dfn[i] == i){
      sort(p2[i].begin(),p2[i].end());
      p2[i].erase(unique(p2[i].begin(),p2[i].end()),p2[i].end());
      for(auto item:p2[i]){
        if(item == i)continue;
        // printf("%d -> %d\n",i,item);
        incnt[item]++;
        outcnt[i]++;
      }
    }
  }
  int in0cnt=0,out0cnt=0;
  rep(i,1,n+1){
    if(dfn[i] == i){
      in0cnt+=incnt[i] == 0;
      out0cnt+=outcnt[i] == 0;
    }
  }
  printf("%d\n",in0cnt);
  // single check
  int pcnt = 0;
  rep(i,1,n+1){
    pcnt+=dfn[i]==i;
  }
  if(pcnt == 1){
    printf("0\n");
  }else{
    printf("%d\n",max(in0cnt,out0cnt));
  }
  return 0;
}

Big Barn - bigbrn

题意

NxN(N<=1000)矩阵A点上值有0或1

1的个数<=10000

求最大的全0正方形(不能斜着)

输出边长即可

题解

这感觉二分答案？因为二分的话如果大的可行，那么小的必定可行

又必定正方形的左侧和上侧都有点（边界看做全是点）

假设存在一个最优解左侧没有相邻点，则可以向左平移直到有点，对上侧同理。

emm 这样想下去，暂时没想到一个时间复杂度内能完成的解法，再看又像是二维线段树,跟着2维线段树的思路联想到前缀和的类似的矩阵处理

假设当前测试的长度为len

那么用B[i][j]表示 A[i->i+len-1][j]为1的个数

C[i][j]表示A[i->i+len-1][j->j+len-1]为1的个数,即是C[i][j->j+len-1]

根据前缀和类似的算法，A->B可以在O(N^2)完成B->C也同理,综上O(N^2*log(N))

然而很不幸的是 usaco给的空间是真的有限，就算换成 new 也会在第11个点挂掉,所以bit压位,然而事后发现，可以不用存储C，直接判断C的值就好了，从空间O(3N^2)变为O(2N^2)就能过

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

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

int n,t;

// bitset<8> A[1010][130];// [1010][1010]; // N*N
// bitset<8> B[1010][130];// [1010][1010]; // (N+1-len)*N
// //bitset<8> C[1010][130];// [1010][1010]; // (N+1-len)*(N+1-len)

// 如果注释掉下面两行用 上面bitset的A和B也能过
int A[1010][1010];
int B[1010][1010];

void setv(bitset<8> *arr,int idx,int v){
  arr[idx/8].set(idx%8,bool(v));
}

int getv(bitset<8> *arr,int idx){
  return arr[idx/8][idx%8];
}

void setv(int *arr,int idx,int v){
  arr[idx]=v;
}

int getv(int *arr,int idx){
  return arr[idx];
}

bool ok(int len){
  if(len == 0)return true;
  // A->B
  rep(j,0,n){
    int cnt = 0;
    rep(i,0,len){
      cnt+=getv(A[i],j);
    }
    setv(B[0],j,cnt);
    rep(i,1,n+1-len){
      cnt+=getv(A[i+len-1],j)-getv(A[i-1],j);
      setv(B[i],j,cnt);
    }
  }
  // B->C
  rep(i,0,n+1-len){
    int cnt= 0;
    rep(j,0,len)
      cnt+=getv(B[i],j);
    if(cnt == 0)return true;
    rep(j,1,n+1-len){
      cnt+=getv(B[i],j+len-1)-getv(B[i],j-1);
      if(cnt == 0)return true;
    }
  }
  return false;
}

bool all1(){
  rep(i,0,n){
    rep(j,0,n){
      if(A[i][j] == 0){
        return false;
      }
    }
  }
  return true;
}

int main(){
  usefile();
  cin>>n>>t;
  rep(i,0,t){
    int x,y;
    scanf("%d %d",&x,&y);
    setv(A[x-1],y-1,1);
  }

  int lenl=0,lenr=n+1;
  while(lenl+1<lenr){
    int mid=(lenl+lenr)/2;
    if(ok(mid)){
      lenl=mid;
    }else{
      lenr=mid;
    }
  }
  cout<<lenl<<endl;

  return 0;
}

总结

emmmmm所以这些题目和标题的启发式搜索的关系是?

發表於 更新於 分類於 ， Disqus： 文章字數： 710 所需閱讀時間 ≈ 2 分鐘
D (最值可达入门)

D原题

才2000分我自闭了

n(1<=n<=1000)个左括号和n个右括号组成合法括号序列

把所有合法序列来建立一个trie树

求问，给树的边上色或不上色，要求任意两个上色边不能共点，求最大上色边数

结果MOD 1e9+7

题解

首先我想到树上dp，f[当前配对数量][剩余左括号数量][是否染色边]

有关系

1
2
3
4
5
6
f[i][j][0] = max(
     f[i][j+1][1]+f[i+1][j-1][0],
     f[i][j+1][0]+f[i+1][j-1][1],
     );
f[i][j][1] =
     f[i][j+1][0]+f[i+1][j-1][0]+1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll f(ll p,ll l,int pick){
  if(p==n)return pick;
  if(ret[p][l][pick] != 0)return ret[p][l][pick];
  if(l==0){ // 没有剩余左括号了，所以在树上的向下分之一定是左括号
    return ret[p][l][pick]=f(p,l+1,1-pick)+pick; // 偏序关系?
  }
  if(p+l==n){ // 左括号已经达到上限只能用右括号
    return ret[p][l][pick]=f(p+1,l-1,1-pick)+pick;// 偏序关系?
  }
  if(pick == 1){ // 当前选下面则不选
    return ret[p][l][pick]=f(p,l+1,0)+f(p+1,l-1,0)+1;// 偏序关系?
  }else{
    return ret[p][l][pick]=
      max(f(p,l+1,1)+f(p+1,l-1,0),
          f(p,l+1,0)+f(p+1,l-1,1));
  }
}

那么只要访问f(0,1,1),就可以得到答案,然后就遇到了一个问题:最大值和取模运算是冲突的

那么有什么办法可以不用比较直接直到偏序关系?

我没想出来,那么现在一个办法是偏序关系，一个办法是做高精度，还有一个办法是换方法。

来自群友梦月大佬的一句话方法:奇数层节点个数

注:按题目原型来说 最初空白节点为0层

注意每次染色一条边，如果去看树上，实际就是奇数层次的点和偶数层次的点被各染色一个，因为不同染色边不能有交点，所以边=奇数层数染色的点=偶数层数染色的点。

下面又有因为是合法对，所以从根节点到叶子节点的点数永远是偶数也就意味着每一个奇数层数的点下方一定有至少一个节点(在偶数层数)

所以边<= min(奇数层数总节点数，偶数层数总结点数) =奇数层数总结点数

下面看可达性，同上述，每个奇数节点选一个下方的偶数节点染色边，即可，保证了不会共点，又达到了奇数层数的总节点数。

综上 我们找到了一个方案达到上限，那么这个上限也就是答案了。

[至于怎么算奇数节点上总个数就无脑dp了,我想没有必要赘述了吧.

發表於 更新於 分類於 ， Disqus： 文章字數： 483 所需閱讀時間 ≈ 2 分鐘
D (gcd入门)

D原题

这题分才2100 XD,没想到[a+b]是一个可行上限

大意:

青蛙在长度为i的区间内跳跃，要么向右a,要么向左b. f(i)=能跳到的不同点的个数

输入m(<=1e9),(1<=a<=1e5),(1<=b<=1e5)

求sum{i=0->m,f(i)}

题解

首先，假设在长度为x的时候，足够长，能够通过反复横跳,跳到gcd(a,b)的位置，那么也就意味着[0,x]可以到达gcd(a,b)

从而[gcd(a,b),gcd(a,b)+x] 能跳到2gcd(a,b)

注意到存在 a*n-b*m=gcd(a,b) 其中n和m非负

意味着如果令x=a+b,也就是区间给[0,a+b],

那么保证了任何一个点p，

p+a(向右跳)<=a+b(没有超过右边界)

和

p-b(向左跳)>=0(没有超过左边界)

至少有一个成立

即是说，如果不能向右跳时一定能向左再跳一次，如果不能向左跳一定能向右再跳一次

也意味着，每向右跳一次a的系数增加，且可以在[0,a+b]中系数增加任意次数，从而达到期望的n

对应的在达到n时，任然在区间内，向左跳的次数也就可以取到m，从而在[0,a+b]中一定能跳到gcd(a,b);

同理 a+b明显是gcd(a,b)的倍数，假设k倍

那么 a*(n*k)-b*(m*k)也是可达的，因为保证了b的次数，也就是向左跳的次数可以从0逐个增大到无穷，所以达到m*k时，对应可以让a填充达到a+b。

再同理,如果给定[0,a+b]，那这区间里所有gcd的倍数都可以达到。

因此大于[a+b]的简单计算gcd个数，我们只用关心0到a+b的情况.

显然f(0-a+b)的这部分 用dijkstra

0%