FOJ有奖月赛-2015年03月 题解

月赛链接：http://acm.fzu.edu.cn/contest/index.php?cid=141

神牛题解：http://blog.csdn.net/accelerator_/article/details/44564417

本题解是参照楼上神牛题解编出来的（最后一题完全抄袭了~

前面打星的是和神牛思路不同的

*A:由于字符串长 < 1000所以可以展开第一个串，每次展开长度用第二个串长限制就好了，然后跑KMP

B:树状数组大法好

*C:首先思考对于最少化路径的障碍是什么，xeryj是分叉，那么考虑如何高效的消除树叶。第一问：贪心，一条路径最多消灭两个叶子。第二问：想象从树的边缘开始对分叉两两合并，最后还有一个长条，这样贪心一定是最优的。

D:求任意两个宝藏直接的最短路（小明也看做宝藏），得到一个11*11的图，可以想到状态压缩搞，但是有回路，需要多出一维保存当前到了什么位置（完整的状态定义是 小明去的第一个宝藏+小明走过宝藏的集合+小明现在所在的宝藏，只用后两个就可以了，这样就等价于穷举小明去的第一个宝藏取最小的保存在状态数组里），还是不明白可以看货郎担问题（旅行商问题）的dp解法，需要注意的一点是:如果小明的位置是墙，直接输出-1

E、扫描线线段树

F、定义好状态bfs搜最短路就好了，就是判的有点多，两岸船上都要判断

G、这一发说实话没搞明白。。。能想到小数据暴力，大数据贪心，但是没法证明。。。。

 1 /*
 2  * Problem:  FOJ 2183
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/3/23 星期一 14:36:33
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: BF KMP
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 const int MaxA=1e3+7;
17 const int MaxB=1e6+7;
18 
19 char cs[MaxA], ns[MaxA];
20 char str[MaxB];
21 int nt[MaxB];
22 int lc, ln, len;
23 void getFail(char* P, int* f) {
24     int m=strlen(P);
25     f[0]=0; f[1]=0;
26     for(int i=1; i<m; i++) {
27         int j=f[i];
28         while(j && P[i]!=P[j]) j=f[j];
29         f[i+1]=P[i]==P[j]?j+1:0;
30     }
31 }
32 bool find(char* T, char* P, int* f) {
33     int n=strlen(T), m=strlen(P);
34     getFail(P, f);
35     int j=0;
36     for(int i=0; i<n; i++) {
37         while(j && P[j]!=T[i]) j=f[j];
38         if(P[j]==T[i]) j++;
39         if(j==m) return true;
40     }
41     return false;
42 }
43 int main() {
44 #ifndef ONLINE_JUDGE
45     freopen("in", "r", stdin);
46     //freopen("out", "w", stdout);
47 #endif
48     while(~scanf("%s%s", cs, ns)) {
49         lc=strlen(cs); ln=strlen(ns);
50         len=0;
51         for(int i=0; i<lc; i++) {
52             if('a'<=cs[i] && cs[i]<='z') {
53                 str[len++]=cs[i];
54             } else {
55                 int tmp=0;
56                 i++;
57                 while(cs[i]!=']') {
58                     tmp=tmp*10+cs[i++]-'0';
59                 }
60                 tmp=min(tmp, ln);
61                 while(--tmp) {
62                     str[len]=str[len-1];
63                     len++;
64                 }
65             }
66         }
67         str[len]=0;
68         if(find(str, ns, nt)) printf("True
");
69         else printf("False
");
70     }
71     return 0;
72 }
A、简单题
 1 /*
 2  * Problem: FOJ 2185 逆序数还原 
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/3/25 星期三 23:06:56
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: Fenwick
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 const int MaxA=1e3+7;
17 
18 struct Fenwick {
19     int n;
20     int c[MaxA];
21 
22     void init(int n) {
23         this->n=n;
24         memset(c, 0, sizeof(c[0])*(n+3));
25     }
26 
27     int lowbit(int x) {
28         return x&-x;
29     }
30 
31     void update(int x, int v) {
32         for(int i=x; i<=n; i+=lowbit(i)) c[i]+=v;
33     }
34 
35     int query(int x) {
36         int res=0;
37         for(int i=x; i>0; i-=lowbit(i)) res+=c[i];
38         return res;
39     }
40 } fw;
41 
42 int N;
43 int find(int x) {
44     int l=1, r=N+1, m;
45     while(l<r) {
46         m=(l+r)>>1;
47         if(fw.query(m)>x) r=m;
48         else l=m+1;
49     }
50     return l;
51 }
52 int main() {
53 #ifndef ONLINE_JUDGE
54     freopen("in", "r", stdin);
55     //freopen("out", "w", stdout);
56 #endif
57     while(~scanf("%d", &N)) {
58         fw.init(N+1);
59         for(int i=1; i<=N; i++) {
60             fw.update(i, 1);
61         }
62 
63         for(int i=0; i<N; i++) {
64             int x;
65             scanf("%d", &x);
66             int tmp=find(x);
67             printf("%d%c", tmp, " 
"[i==N-1]);
68             fw.update(tmp, -1);
69         }
70     }
71     return 0;
72 }
B、逆序数还原
 1 /*
 2  * Problem: FOJ 2185 树的路径覆盖
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/3/24 星期二 09:25:45
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: greedy
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 
14 using namespace std;
15 
16 const int MaxA=1e5+7;
17 
18 int n;
19 int dg[MaxA];
20 int main() {
21 #ifndef ONLINE_JUDGE
22     freopen("in", "r", stdin);
23     //freopen("out", "w", stdout);
24 #endif
25     int T;
26     scanf("%d", &T);
27     while(T--) {
28         scanf("%d", &n);
29         if(n==1) {
30             printf("0 0
");
31             continue;
32         }
33         memset(dg, 0, sizeof(dg));
34         for(int i=1; i<n; i++) {
35             int x;
36             scanf("%d", &x);
37             dg[i]++;
38             dg[x]++;
39         }
40         int cnt=0, ans2=0;
41         for(int i=0; i<n; i++) {
42             if(dg[i]==1) cnt++;
43             else ans2+=(dg[i]-1)>>1;
44         }
45         printf("%d %d
", (cnt>>1)+(cnt&1), ans2+1);
46     }
47     return 0;
48 }
C、树的路径覆盖
  1 /*
  2  * Problem: FOJ 2186 小明的迷宫
  3  * Author:  SHJWUDP
  4  * Created Time:  2015/3/24 星期二 12:30:09
  5  * File Name: 233.cpp
  6  * State: Accepted
  7  * Memo: bfs dp
  8  */
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13 #include <queue>
 14 
 15 using namespace std;
 16 
 17 const int MaxA=100+7;
 18 const int MaxB=11+7;
 19 const int MaxC=MaxA*MaxA;
 20 
 21 struct Point {
 22     int x, y;
 23     Point() {}
 24     Point(int x, int y):x(x), y(y) {}
 25 } p[MaxB];
 26 
 27 int n, m;
 28 int grid[MaxA][MaxA];    //original graph
 29 int id;                    //宝藏编号
 30 int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 31 int x[MaxC], y[MaxC], dist[MaxC];
 32 int vis[MaxA][MaxA];
 33 
 34 int G[MaxB][MaxB];
 35 int f[MaxB][(1<<10)+7];    //f[当前位置][已遍历集合]
 36 int super;    //最终态
 37 int ans;
 38 inline bool inlaw(int x, int y) {
 39     if(x>=0 && x<n && y>=0 && y<m
 40             && grid[x][y]>=0
 41             && !vis[x][y]) 
 42         return true;
 43     else return false;
 44 }
 45 bool bfs(int st) {        //如果宝藏不联通，返回false
 46     memset(vis, 0, sizeof(vis));
 47     int f=0, r=1;
 48     x[f]=p[st].x; y[f]=p[st].y;
 49     vis[x[f]][y[f]]=1;
 50     int cnt=0;
 51     while(f!=r) {
 52         for(int k=0; k<4; k++) {
 53             x[r]=x[f]+dir[k][0];
 54             y[r]=y[f]+dir[k][1];
 55             if(inlaw(x[r], y[r])) {
 56                 vis[x[r]][y[r]]=1;
 57                 if(grid[x[r]][y[r]]>0) {
 58                     G[st][grid[x[r]][y[r]]]=dist[f]+1;
 59                     cnt++;
 60                 }
 61                 dist[r++]=dist[f]+1;
 62             }
 63         }
 64         f++;
 65     }
 66     if(cnt!=id-1) return false;
 67     return true;
 68 }
 69 void dp(int u, int sta) {
 70     if(sta==super) {
 71         ans=min(ans, f[u][sta]+G[u][1]);
 72         return ;
 73     }
 74     for(int i=2; i<=id; i++) {
 75         int k=i-2;
 76         if(!(sta & (1<<k))
 77                 && f[i][sta|(1<<k)]>f[u][sta]+G[u][i]) {
 78             f[i][sta|(1<<k)]=f[u][sta]+G[u][i];
 79             dp(i, sta|(1<<k));
 80         }
 81     }
 82 }
 83 int main() {
 84 #ifndef ONLINE_JUDGE
 85     freopen("in", "r", stdin);
 86     //freopen("out", "w", stdout);
 87 #endif
 88     while(~scanf("%d%d", &n, &m)) {
 89         id=1;    //小明是一号宝藏
 90         for(int i=0; i<n; i++) {
 91             for(int j=0; j<m; j++) {
 92                 scanf("%d", &grid[i][j]);
 93                 if((i||j) && grid[i][j]>0) {
 94                     grid[i][j]=++id;
 95                     p[id]=Point(i, j);
 96                 }
 97             }
 98         }
 99         if(grid[0][0]<0) {    //这里有个坑，小明的位置是墙的话直接 -1
100             printf("-1
");
101             continue;
102         }
103         p[grid[0][0]=1]=Point(0, 0);
104 
105         memset(G, 0, sizeof(G));
106         bool ok=true;
107         for(int i=1; i<=id && ok; i++) {
108             ok=bfs(i);
109         }
110         if(!ok) {
111             printf("-1
");
112             continue;
113         }
114 
115         memset(f, 0x7f, sizeof(f));
116         super=(1<<(id-1))-1;
117         f[1][0]=0;    //初始位置代价为0
118         ans=0x7fffffff;
119         dp(1, 0);
120         printf("%d
", ans);
121     }
122     return 0;
123 }
D、小明的迷宫
  1 /*
  2  * Problem: FOJ 2187 回家种地 
  3  * Author:  SHJWUDP
  4  * Created Time:  2015/3/24 星期二 19:47:35
  5  * File Name: 233.cpp
  6  * State: Accepted
  7  * Memo: segmentTree
  8  */
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <algorithm>
 13 
 14 using namespace std;
 15 
 16 typedef long long LL;
 17 
 18 const int MaxA=1e5+7;
 19 
 20 struct Segment {
 21     int l, r, h, v;
 22     Segment() {}
 23     Segment(int l, int r, int h, int v):l(l), r(r), h(h), v(v) {}
 24 
 25     bool operator<(const Segment& x) const {
 26         return this->h < x.h;
 27     }
 28 } seg[MaxA<<1];
 29 
 30 struct SegmentTree {
 31     struct STNode {
 32     //len 0：未覆盖区域长度 1：覆盖一次区域长度 2:覆盖多次区域长度
 33         int cov, len[3];    
 34     } *c;
 35     int n;
 36     int L, R, v;
 37     int* X;
 38 
 39 #define lson l, m, rt<<1
 40 #define rson m+1, r, rt<<1|1
 41 
 42     SegmentTree(int n, int* X) {
 43         this->n=n; this->X=X;
 44         c=new STNode[n<<2];
 45         build(0, n-1, 1);
 46     }
 47     ~SegmentTree() {
 48         delete c;
 49     }
 50 
 51 
 52     void build(int l, int r, int rt) {
 53         c[rt].cov=0;
 54         memset(c[rt].len, 0, sizeof(c[rt].len));
 55         c[rt].len[0]=X[r+1]-X[l];
 56         if(l==r) return ;
 57         int m=(l+r)>>1;
 58         build(lson);
 59         build(rson);
 60     }
 61 
 62     void pushUp(int l, int r, int rt) {
 63         memset(c[rt].len, 0, sizeof(c[rt].len));
 64         if(l==r) {
 65             c[rt].len[min(2, c[rt].cov)]=X[r+1]-X[l];
 66         } else {
 67             for(int i=0; i<=2; i++) {
 68                 c[rt].len[min(2, c[rt].cov+i)]+=c[rt<<1].len[i]+c[rt<<1|1].len[i];
 69             }
 70         }
 71     }
 72 
 73     void doUpdate(int l, int r, int rt) {
 74         if(L<=l && r<=R) {
 75             c[rt].cov+=v;
 76             pushUp(l, r, rt);
 77             return ;
 78         }
 79         int m=(l+r)>>1;
 80         if(L<=m) doUpdate(lson);
 81         if(m<R) doUpdate(rson);
 82         pushUp(l, r, rt);
 83     }
 84 
 85     void update(int L, int R, int v) {
 86         this->L=L; this->R=R; this->v=v;
 87         doUpdate(0, n-1, 1);
 88     }
 89 #undef lson
 90 #undef rson
 91 };
 92 
 93 int n;
 94 int table[MaxA<<1];
 95 
 96 template<class T>
 97 int bin(T* ll, T* rr, const T& x) {
 98     return lower_bound(ll, rr, x)-ll;
 99 }
100 int main() {
101 #ifndef ONLINE_JUDGE
102     freopen("in", "r", stdin);
103     //freopen("out", "w", stdout);
104 #endif
105     int T, now=0;
106     scanf("%d", &T);
107     while(T--) {
108         scanf("%d", &n);
109         int sn=0, tn=0;
110         for(int i=0; i<n; i++) {
111             int x1, x2, y1, y2;
112             scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
113             seg[sn++]=Segment(x1, x2, y1, 1);
114             seg[sn++]=Segment(x1, x2, y2, -1);
115             table[tn++]=x1;
116             table[tn++]=x2;
117         }
118         sort(seg, seg+sn);
119         sort(table, table+tn);
120         tn=unique(table, table+tn)-table;
121 
122         SegmentTree st(tn, table);
123         LL ans=0;
124         for(int i=0, lim=sn-1; i<lim; i++) {
125             int l=bin(table, table+tn, seg[i].l);
126             int r=bin(table, table+tn, seg[i].r)-1;
127             if(l<=r) st.update(l, r, seg[i].v);
128             ans+=LL(seg[i+1].h-seg[i].h)*st.c[1].len[1];
129         }
130         printf("Case %d: %I64d
", ++now, ans);
131     }
132     return 0;
133 }
E、回家种地
 1 /*
 2  * Problem:  FOJ 2188 过河I
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/3/25 星期三 10:02:28
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: dp
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <queue>
14 
15 using namespace std;
16 
17 const int MaxA=200+7;
18 
19 struct State {
20     int x, y, sign, dep;
21     State(int x, int y, int s, int d):x(x), y(y), sign(s), dep(d) {}
22 };
23 
24 int x, y, n;
25 int f[MaxA][MaxA][2];
26 void insert(queue<State>& Q, const State& u, int a, int b) {
27     int lx, ly, rx, ry;
28     if(u.sign==0) {
29         lx=u.x-a; ly=u.y-b;
30         rx=(x-u.x)+a; ry=(y-u.y)+b;
31     } else {
32         lx=u.x+a; ly=u.y+b;
33         rx=(x-u.x)-a; ry=(y-u.y)-b;
34     }
35     //if(lx<0 || ly<0 || rx<0 || ry<0) return ;
36     if((lx>=ly || lx==0)
37             && (rx>=ry || rx==0)
38             && f[lx][ly][u.sign^1]>f[u.x][u.y][u.sign]+1) {
39         f[lx][ly][u.sign^1]=f[u.x][u.y][u.sign]+1;
40         Q.push(State(lx, ly, u.sign^1, u.dep+1));
41     }
42 }
43 int bfs() {
44     memset(f, 0x7f, sizeof(f));
45     f[x][y][0]=0;
46     queue<State> Q;
47     Q.push(State(x, y, 0, 0));
48     while(!Q.empty()) {
49         State u=Q.front(); Q.pop();
50         if(!u.x && !u.y && u.sign) return u.dep;
51         for(int i=1, lim1=min(n, u.sign?x-u.x:u.x); i<=lim1; i++) {
52             for(int j=0, lim2=min(n-i, min(i, u.sign?y-u.y:u.y)); j<=lim2; j++) {
53                 insert(Q, u, i, j);
54             }
55         }
56         for(int j=1, lim=min(n, u.sign?y-u.y:u.y); j<=lim; j++) {
57             insert(Q, u, 0, j);
58         }
59     }
60     return -1;
61 }
62 int main() {
63 #ifndef ONLINE_JUDGE
64     freopen("in", "r", stdin);
65     //freopen("out", "w", stdout);
66 #endif
67     while(~scanf("%d%d%d", &x, &y, &n)) {
68         printf("%d
", bfs());
69     }
70     return 0;
71 }
F、过河I
 1 /*
 2  * Problem:  FOJ 2189 过河II
 3  * Author:  SHJWUDP
 4  * Created Time:  2015/3/25 星期三 19:10:27
 5  * File Name: 233.cpp
 6  * State: Accepted
 7  * Memo: greedy+dp
 8  */
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <algorithm>
13 #include <queue>
14 
15 using namespace std;
16 
17 const int MaxA=21;
18 
19 struct State {
20     int x, y, sign, dep;
21     State(int x, int y, int s, int d):x(x), y(y), sign(s), dep(d) {}
22 };
23 
24 int m, n;
25 int f[MaxA][MaxA][2];
26 void insert(queue<State>& Q, const State& u, int a, int b) {
27     int lx, ly, rx, ry;
28     if(u.sign==0) {
29         lx=u.x-a; ly=u.y-b;
30         rx=(m-u.x)+a; ry=(m-u.y)+b;
31     } else {
32         lx=u.x+a; ly=u.y+b;
33         rx=(m-u.x)-a; ry=(m-u.y)-b;
34     }
35     if((lx>=ly || !lx)
36             && (rx>=ry || !rx)
37             && f[lx][ly][u.sign^1]>f[u.x][u.y][u.sign]+1) {
38         f[lx][ly][u.sign^1]=f[u.x][u.y][u.sign]+1;
39         Q.push(State(lx, ly, u.sign^1, u.dep+1));
40     }
41 }
42 int bfs() {
43     if(m>20) return -1;
44     memset(f, 0x7f, sizeof(f));
45     f[m][m][0]=0;
46     queue<State> Q;
47     Q.push(State(m, m, 0, 0));
48     while(!Q.empty()) {
49         State u=Q.front(); Q.pop();
50         if(!u.x && !u.y && u.sign) return u.dep;
51         for(int i=1, lim1=min(n, u.sign?m-u.x:u.x); i<=lim1; i++) {
52             for(int j=0, lim2=min(n-i, min(i, u.sign?m-u.y:u.y)); j<=lim2; j++){
53                 insert(Q, u, i, j);
54             }
55         }
56         for(int j=1, lim=min(n, u.sign?m-u.y:u.y); j<=lim; j++) {
57             insert(Q, u, 0, j);
58         }
59     }
60     return -1;
61 }
62 int main() {
63 #ifndef ONLINE_JUDGE
64     freopen("in", "r", stdin);
65     //freopen("out", "w", stdout);
66 #endif
67     while(~scanf("%d%d", &m, &n)) {
68         int ans;
69         if(n<4) {
70             ans=bfs();
71         } else {
72             ans=0;
73             int x=(n>>1)-1;
74             while(m-x>n) {
75                 m-=x;
76                 ans+=2;
77             }
78             if(m>n && (n&1) && n>=m-(n>>1)) {
79                 ans+=5;
80             } else {
81                 while(m>n) {
82                     m-=x;
83                     ans+=2;
84                 }
85                 if((m<<1)<=n) ans++;
86                 else if(m==n) ans+=5;
87                 else ans+=3;
88             }
89         }
90         printf("%d
", ans);
91     }
92     return 0;
93 }
G、过河II
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/shjwudp/p/4386844.html