USACO 5.4 章节

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