bef-> NO.20

Veröffentlicht am

[USACO12OPEN]平衡的奶牛群

题目描述

Farmer John’s owns N cows (2 <= N <= 20), where cow i produces M(i) units of milk each day (1 <= M(i) <= 100,000,000). FJ wants to streamline the process of milking his cows every day, so he installs a brand new milking machine in his barn. Unfortunately, the machine turns out to be far too sensitive: it only works properly if the cows on the left side of the barn have the exact same total milk output as the cows on the right side of the barn!

Let us call a subset of cows “balanced” if it can be partitioned into two groups having equal milk output. Since only a balanced subset of cows can make the milking machine work, FJ wonders how many subsets of his N cows are balanced. Please help him compute this quantity.

给n个数，从中任意选出一些数，使这些数能分成和相等的两组。

求有多少种选数的方案。

输入输出格式

输入格式：

* Line 1: The integer N.

* Lines 2..1+N: Line i+1 contains M(i).

输出格式：

* Line 1: The number of balanced subsets of cows.

输入输出样例

输入样例#1：

1
2
3
4
5
4 
1 
2 
3 
4

输出样例#1：

1
3

说明

There are 4 cows, with milk outputs 1, 2, 3, and 4.

There are three balanced subsets: the subset {1,2,3}, which can be partitioned into {1,2} and {3}, the subset {1,3,4}, which can be partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be partitioned into {1,4} and {2,3}..

题解

这题用了一种高级的搜索策略叫做meet in the middle.

就是将这些数分成两半，分别算出左右每个状态的值，然后对状态排序后双指针匹配。快的原因就是我们双指针匹配是近似线性的（假如一个和上一个相同那右指针就要跳回上一个最初的地方，但是这个事实上是没法卡的）

这个方法快的原因是避免了很对没有用的状态搜索，让左边小的匹配右边大的是种很合理的策略。

然后我们最后算法的时间复杂度是

对于本题跑的飞快

Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 21
struct Node{
    int sum , Status;
}L[1<<maxn] , R[1<<maxn];
int n , p[maxn] , cntl , cntr , ans;
bool vis[1<<maxn];
inline bool cmp(Node x , Node y){return x.sum < y.sum ;}
inline bool cmp2(Node x , Node y){return x.sum > y.sum;}
void dfs(int b , int e , int sum , int Status)
{
    if(b > e)
    {
        if(e == n/2) L[++cntl].sum = sum , L[cntl].Status = Status;
        else    R[++cntr].sum = sum , R[cntr].Status = Status;
        return;
    }
    dfs(b+1 , e , sum+p[b] , Status + (1<<b));
    dfs(b+1 , e , sum - p[b] , Status + (1<<b));
    dfs(b+1 , e , sum , Status);
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&p[i]);
    dfs(1,n/2,0,0);
    dfs(n/2+1,n,0,0);
    std::sort(L+1,L+cntl+1,cmp);
    std::sort(R+1,R+cntr+1,cmp2);
    int l = 1 , r = 1;
    while(l <= cntl && r <= cntr)
    {
        while(L[l].sum + R[r].sum > 0 && r <= cntr) ++r;
        int pre = r;
        while(L[l].sum + R[r].sum == 0 && r <= cntr)
        {
            if(!vis[L[l].Status|R[r].Status])
                vis[L[l].Status|R[r].Status] = true , ++ans;
            ++r;
        }
        if(L[l].sum == L[l+1].sum) r = pre;
        ++l;
    }
    printf("%d",ans-1);
}

[NOI2015]软件包管理器

题目描述

Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优秀的软件包管理器。

你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包A依赖软件包B，那么安装软件包A以前，必须先安装软件包B。同时，如果想要卸载软件包B，则必须卸载软件包A。现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除0号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而0号软件包不依赖任何一个软件包。依赖关系不存在环（若有m(m≥2)个软件包A1,A2,A3,⋯,Am，其中A1依赖A2，A2依赖A3，A3依赖A4，……，A[m-1]依赖Am，而Am依赖A1，则称这m个软件包的依赖关系构成环），当然也不会有一个软件包依赖自己。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为0。

输入输出格式

输入格式：

从文件manager.in中读入数据。

输入文件的第1行包含1个整数n，表示软件包的总数。软件包从0开始编号。

随后一行包含n−1个整数，相邻整数之间用单个空格隔开，分别表示1,2,3,⋯,n−2,n−1号软件包依赖的软件包的编号。

接下来一行包含1个整数q，表示询问的总数。之后q行，每行1个询问。询问分为两种：

install x：表示安装软件包x

uninstall x：表示卸载软件包x

你需要维护每个软件包的安装状态，一开始所有的软件包都处于未安装状态。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

输出格式：

输出到文件manager.out中。

输出文件包括q行。

输出文件的第i行输出1个整数，为第i步操作中改变安装状态的软件包数。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

输出样例#1：

1
2
3
4
5
3
1
3
2
3

输入样例#2：

复制

1
2
3
4
5
6
7
8
9
10
11
12
13
10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

输出样例#2：

复制

1
2
3
4
5
6
7
8
9
10
1
3
2
1
3
1
1
1
0
1

说明

【样例说明 1】

img

一开始所有的软件包都处于未安装状态。

安装5号软件包，需要安装0,1,5三个软件包。

之后安装6号软件包，只需要安装6号软件包。此时安装了0,1,5,6四个软件包。

卸载1号软件包需要卸载1,5,6三个软件包。此时只有0号软件包还处于安装状态。

之后安装4号软件包，需要安装1,4两个软件包。此时0,1,4处在安装状态。最后，卸载0号软件包会卸载所有的软件包。`

【数据范围】

img

【时限1s，内存512M】

题解

显然安装一个软件x就是1~x这条链都被安装，卸载是整个子树被卸载。于是树链剖分之后就变成了线段树上的线段覆盖。线段树的线段覆盖就是可以将当前区间覆盖多次，但有新的一条来了就要立刻改成新的值。这样tag和node对于这道题只需要记录是否被覆盖就可以。

所以我pushdown判断是否下推用0结果害得我调了5个小时，请注意覆盖0的标记和空标记

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
int head[maxn] , cnt , hs[maxn] , sz[maxn] , id[maxn] , idx , f[maxn] ,top[maxn] ,dep[maxn] , n , m, num[maxn];
std::string s;
struct edge{
    int next , to;
}e[maxn*2];
struct SegmentTree
{
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    #define pushup(x) sum[x] = sum[ls(x)] + sum[rs(x)]
    int sum[maxn<<2] , tag[maxn<<2];
    inline void pushdown(int Node , int ln , int rn)
    {
        if(tag[Node] != -1)
        {
            sum[ls(Node)] = tag[Node] * ln;
            sum[rs(Node)] = tag[Node] * rn;
            tag[ls(Node)] = tag[Node];
            tag[rs(Node)] = tag[Node];
        }
        tag[Node] = -1;
    }
    void build(int l , int r , int Node , int s[])
    {
        if(l == r)
        {
            sum[Node] = s[l];
            tag[Node] = -1;
            return;
        }
        int mid = l + r >> 1;
        build(l,mid,ls(Node) , s);
        build(mid + 1, r , rs(Node), s);
        pushup(Node);
    }
    void update(int L , int R , int l , int r , int Node , int v)
    {
        if(L <= l && r <= R)
        {
            sum[Node] = v * (r-l+1);
            tag[Node] = v;
            return;
        }
        int mid = l + r >> 1;
        pushdown(Node , mid - l + 1 , r - mid);
        if(L <= mid)    update(L , R , l , mid , ls(Node) , v);
        if(R > mid)     update(L , R , mid + 1, r , rs(Node) , v);
        pushup(Node);
    }
    int query(int L , int R , int l , int r , int Node)
    {
        if(L <= l && r <= R)
            return sum[Node];
        int mid = l + r >> 1 , ans = 0;
        pushdown(Node , mid - l + 1 , r - mid);
        if(L <= mid)    ans += query(L , R , l , mid , ls(Node));
        if(R > mid)     ans += query(L , R , mid + 1, r , rs(Node));
        return ans;
    }
}sgt;
void dfs1(int x , int fx)
{
    f[x] = fx;
    dep[x] = dep[fx] + 1;
    sz[x] = 1;
    int maxx = -1 ;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs1(e[i].to,x) , sz[x] += sz[e[i].to];//dfs1(e[i].to,x)  not dfs1(e[i].to,fx)!!!!!!!!!!!!!!
    for(int i = head[x] ; i ; i = e[i].next)
        if(sz[e[i].to] > maxx && e[i].to != fx)
            maxx = sz[e[i].to] , hs[x] = e[i].to;
}
void dfs2(int x , int topV)
{
    id[x] = ++idx;
    // v[idx[x]] = val[x];
    top[x] = topV;
    if(!hs[x]) return;
    dfs2(hs[x],topV);
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != f[x] && e[i].to != hs[x])
            dfs2(e[i].to , e[i].to);
}
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
void update(int x , int y , int v)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
        sgt.update(id[top[x]] , id[x] , 1 , n , 1 , v);
        x = f[top[x]];
    }
    if(dep[x] < dep[y]) std::swap(x,y);
    sgt.update(id[y] , id[x] , 1 , n , 1 , v);
}
int query(int x, int y)
{
    int ans = 0;
    // printf("%d %d\n",x,y);
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) std::swap(x,y);
        ans += sgt.query(id[top[x]] , id[x] , 1 , n , 1);
        x = f[top[x]];
    }
    if(dep[x] < dep[y]) std::swap(x,y);
    ans += sgt.query(id[y] , id[x] , 1 , n , 1);
    return ans;
}
void updSt(int x)
{
    // printf("updSt %d\n",x);
    sgt.update(id[x] , id[x] + sz[x] - 1 , 1 , n , 1 , 0);
}
int querySt(int x)
{
    int ans = sgt.query(id[x] , id[x] + sz[x] - 1 , 1 , n , 1);
    // printf("queryST %d (id[%d] = %d): %d\n",x , id[x] , ans);
    return ans;
}
int main()
{
    // freopen("SAC.in","r",stdin);
    // freopen("data.out","w",stdout);
    // n = 100;
    // sgt.update(1,9,1,n,1,1);
    // sgt.update(2,10,1,n,1,1);
    // sgt.update(3,11,1,n,1,1);
    // std::cout<<sgt.query(1,11,1,n,1)<<std::endl;
    // sgt.update(1,11,1,n,1,0);
    // std::cout<<sgt.query(1,11,1,n,1)<<std::endl;
    // sgt.update(2,7,1,n,1,1);
    // sgt.update(2,3,1,n,1,0);
    // std::cout<<sgt.query(2,7,1,n,1);
    scanf("%d",&n);
    int x;
    for(int i = 2 ; i <= n ; ++i)
        scanf("%d",&x) , add(1 + x , i) , add(i , x + 1);
    dfs1(1,1);
    dfs2(1,1);
    sgt.build(1,n,1,num);
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("id[%d] = %d\n",i,id[i]);
    // puts("OK");
    scanf("%d",&m);
    for(int i = 1 ; i <= m ; ++i)
    {
        std::cin>>s;
        if(s == "install")
        {
            scanf("%d",&x);
            ++x;
            int ans = query(1,x);
            // printf("bef %d\n",ans);
            // int ans = sgt.query(1,n,1,n,1);
            update(1,x,1);
            ans = query(1,x) - ans;
            // printf("now %d\n" , ans);
            // printf("curSGT : %d\n",sgt.query(1,n,1,n,1));
            printf("%d\n",ans);
            // system("pause");
        }
        else{
            scanf("%d",&x);
            ++x;
            int ans = querySt(x);
            // printf("bef %d\n",ans);
            updSt(x);
            // ans = querySt(x) - ans;
            // // printf("now %d\n",ans);
            if(ans < 0) ans = - ans;
            // printf("curSGT : %d\n",sgt.query(1,n,1,n,1));
            printf("%d\n",ans);
        }
    }
}

[ZJOI2008]树的统计

题目描述

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

输入输出格式

输入格式：

输入文件的第一行为一个整数n，表示节点的个数。

接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

接下来一行n个整数，第i个整数wi表示节点i的权值。

接下来1行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

输出格式：

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

输出样例#1：

1
2
3
4
5
6
7
8
9
10
4
1
2
2
10
6
5
6
5
16

说明

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

题解

HPD的简单题，线段树单点修改即可。

Code：

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define ll long long
int head[maxn] , cnt , hs[maxn] , sz[maxn] , id[maxn] , idx , n , m , v[maxn] , val[maxn] , f[maxn] ,top[maxn] , dep[maxn];
struct edge{
    int next , to;
}e[maxn*2];
struct SegmentTree
{
    int sum[maxn<<2] , add[maxn<<2] , maxx[maxn<<2];
    #define ls(x) (x<<1)
    #define rs(x) (x<<1|1)
    #define INF 0x7fffffff
    inline void pushup(int Node)
    {
        sum[Node] = sum[ls(Node)] + sum[rs(Node)];
        maxx[Node] = std::max(maxx[ls(Node)] , maxx[rs(Node)]);
    }
    inline void pushdown(int Node , int ln , int rn)
    {
        if(add[Node])
        {
            sum[ls(Node)] += ln * add[Node];
            sum[rs(Node)] += rn * add[Node];
            maxx[ls(Node)] += add[Node] ;
            maxx[rs(Node)] += add[Node] ;
            add[ls(Node)] += add[Node];
            add[rs(Node)] += add[Node];
        }
        add[Node] = 0;
    }
    void build(int l , int r , int Node , int s[])
    {
        if(l == r)
        {
            sum[Node] = maxx[Node] = s[l];
            return;
        }
        int mid = l + r >> 1;
        build(l, mid , ls(Node) ,s);
        build(mid + 1, r , rs(Node) , s);
        pushup(Node);
    }
    void update(int L , int R , int l , int r , int Node , int v)
    {
        if(L <= l && r <= R)
        {
            sum[Node] += (r - l + 1) * v;
            maxx[Node] += v;
            add[Node] += v;
            return;
        }
        int mid = l + r >> 1;
        if(L <= mid)    update(L , R , l , mid , ls(Node) , v);
        if(R > mid)     update(L , R , mid + 1 , r , rs(Node) , v);
        pushup(Node);
    }
    void updOne(int P , int l , int r , int Node , int v)//modify to v
    {
        if(l == r)
        {
            sum[Node] = maxx[Node] = v;
            return;
        }
        int mid = l + r >> 1;
        if(P <= mid) updOne(P , l , mid , ls(Node) , v);
        else updOne(P , mid + 1, r , rs(Node) , v);
        pushup(Node);
    }
    int querySum(int L , int R , int l , int r , int Node)
    {
        if(L <= l && r <= R)
            return sum[Node];
        int mid = l + r >> 1 , ans = 0;
        // pushdown(Node , mid - l + 1 , r - mid);
        if(L <= mid)    ans += querySum(L , R , l , mid , ls(Node));
        if(R > mid)     ans += querySum(L , R , mid + 1 , r , rs(Node));
        return ans;
    }
    int queryMax(int L , int R , int l , int r , int Node)
    {
        if(L <= l && r <= R)
            return maxx[Node];
        int mid = l + r >> 1 ,  ans = -INF;
        // pushdown(Node , mid - l + 1 , r - mid);
        if(L <= mid)    ans = std::max(ans , queryMax(L , R , l , mid , ls(Node)));
        if(R > mid)     ans = std::max(ans , queryMax(L , R , mid + 1, r , rs(Node)));
        return ans;
    }

}sgt;
void dfs1(int x , int fx)
{
    f[x] = fx;
    dep[x] = dep[fx] + 1;
    sz[x] = 1;
    int hson = 0;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs1(e[i].to , x) , sz[x] += sz[e[i].to];
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx && sz[e[i].to] > sz[hson])
            hson = e[i].to;
    hs[x] = hson;
}
void dfs2(int x , int TopV)
{
    id[x] = ++idx;
    v[id[x]] = val[x];
    top[x] = TopV;
    if(!hs[x])  return;
    dfs2(hs[x] , TopV);
    for(int i = head[x] ; i ; i =e[i].next)
        if(e[i].to != f[x] && e[i].to != hs[x])
            dfs2(e[i].to , e[i].to);
}
void updNode(int x , int v)
{
    sgt.updOne(id[x] , 1 , n , 1 , v);
}
int Qmax(int u , int v)
{
    int ans = -0x7fffffff;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])   std::swap(u,v);
        ans = std::max(ans , sgt.queryMax(id[top[u]] , id[u] , 1 , n , 1));
        u = f[top[u]];
    }
    if(dep[u] < dep[v]) std::swap(u,v);
    ans = std::max(ans , sgt.queryMax(id[v] , id[u] , 1, n , 1));
    return ans;
}
int Qsum(int u , int v)
{
    int ans = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]])   std::swap(u,v);
        ans += sgt.querySum(id[top[u]] , id[u] , 1 , n , 1);
        u = f[top[u]];
    }
    if(dep[u] < dep[v]) std::swap(u,v);
    ans += sgt.querySum(id[v] , id[u] , 1 , n , 1);
    return ans;
}
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    head[x] = cnt;
}
int main()
{
    scanf("%d",&n);
    int x , y , d;
    for(int i = 1 ; i <= n -1 ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&val[i]);
    dfs1(1,1);
    dfs2(1,1);
    sgt.build(1,n,1,v);
    int q;
    scanf("%d",&q);
    std::string op;
    for(int i = 1 ; i <= q ; ++i)
    {
        std::cin>>op;
        if(op == "QSUM")    scanf("%d%d",&x,&y) , printf("%d\n",Qsum(x,y));
        if(op == "QMAX")    scanf("%d%d",&x,&y) , printf("%d\n",Qmax(x,y));
        if(op == "CHANGE")  scanf("%d%d",&x,&y) , updNode(x,y);
    }
}

[USACO06NOV]玉米田Corn Fields

题目描述

Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can’t be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.

Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

输入输出格式

输入格式：

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

输出格式：

一个整数，即牧场分配总方案数除以100,000,000的余数。

输入输出样例

输入样例#1：

1
2
3
2 3
1 1 1
0 1 0

输出样例#1：

1
9

题解

少有的我会做的状态压缩dp

将每个行合法的状态预处理（常数优化），然后每次在当前行与上一行转移的时候只需要判断两个行状态一起合不合法。计数就是加法原理，对于当前行状态之前所有与当前行合法的行状态的方案数都是当前行状态的方案。

Code:

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 15
#define mod 100000000
int S , s[maxn][maxn] , n , m , c[maxn] , f[maxn][1<<maxn] , sta[maxn][1<<maxn];
inline bool check(int row , int Sta)
{
    for(int i = 1 ; i <= m ; ++i)
        if(!s[row][i] && (Sta & (1<<(i-1))))
            return false;
    return true;
}
void write(int x)
{
    if(!x) return;
    write(x/2);
    putchar((x&1)+48);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; ++i)
        for(int j = 1 ; j <= m ; ++j)
            scanf("%d",&s[i][j]);
    S = (1<<m)-1;
    for(int i = 1 ; i <= n ; ++i)//            if(check(j))    continue; if((j & (j<<1)) || (j & (j >> 1)))  continue;
        for(int j = 0 ; j <= S ; ++j)
            if(check(i,j) && !(j & (j<<1)) && !(j & (j>>1)))
                sta[i][++c[i]] = j;
    // for(int i = 1 ; i <= n ; ++i)
    // {
    //     for(int j = 1 ; j <= c[i] ; ++j)
    //         write(sta[i][j]) , putchar(32);
    //     putchar(10);
    // }
    for(int i = 1 ; i <= c[1] ; ++i)
        f[1][sta[1][i]] = 1;
    for(int i = 2 ; i <= n ; ++i)
        for(int j = 1 ; j <= c[i] ; ++j)
            for(int k = 1 ; k <= c[i-1] ; ++k)
            {
                if(sta[i][j] & sta[i-1][k]) continue;
                (f[i][sta[i][j]] += f[i-1][sta[i-1][k]]) %= mod;
            }
    int ans = 0;
    for(int i = 1 ; i <= c[n] ; ++i)
        (ans += f[n][sta[n][i]]) %= mod;
    printf("%d",ans);
}

「一本通 5.1 练习 1」括号配对

题目描述

Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。

以下是 GBE 的定义：

  1. 空表达式是 GBE
  2. 如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
  3. 如果 A 与 B 都是 GBE，那么 AB 是 GBE

输入格式

输入仅一行，为字符串 BE

输出格式

输出仅一个整数，表示增加的最少字符数

样例

样例输入

1
[])

样例输出

1
1

数据范围与提示

对于 100%的数据，输入的字符串长度小于 100。

题解

区间dp基础练习。

题目似乎已经把如何转移告诉你了。。

设

表示这个区间变成合法区间的最少字符数，对于条件二，有

对于条件3

初始状态也就是区间长度是1的时候只需要一个字符匹配。

这题没有恶心的细节，实现起来非常自然qwq！

Code:

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include<iostream>
#define maxn 105
int f[maxn][maxn] , n;
char s[maxn];
int main()
{
    scanf("%s",s+1);
    while(s[++n] != '\0');
    // printf("%d",--len);
    --n;
    for(int i = 1 ; i <= n ; ++i)
        f[i][i] = 1;
    // for(int i = 1 ; i <= n ; ++i)
    //     putchar(s[i]);
    for(int i = 2 ; i <= n ; ++i)
        for(int j = 1 ; j <= n - i + 1 ; ++j)
        {
            int to = j + i - 1;
            f[j][to] = 0x7fffffff;
            for(int k = j ; k < to ; ++k)
                f[j][to] = std::min(f[j][k] + f[k+1][to] , f[j][to]);
            if((s[j] == '[' && s[to] ==']') || (s[j] == '(' && s[to] == ')'))   f[j][to] = std::min(f[j+1][to-1] , f[j][to]);
            // printf("f[%d][%d] = %d\n",j,to,f[j][to]);
        }
    printf("%d",f[1][n]);
}