牛客练习赛19

发表于 | 更新于 | 阅读次数：
本文字数： 7.3k | 阅读时长 ≈ 7 分钟

链接：https://www.nowcoder.com/acm/contest/111/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

作为故事主角的托米是一名老师。

一天，他正在为解析算术表达式的课程准备课件。 在课程的第一部分，他只想专注于解析括号。 他为他的学生发明了一个有趣的正确括号序列的几何表示，如下图所示:

几何表示的定义：

1.

对于一个括号序列A，我们定义g(A)是A的几何表示形式,则

“()”的表示是一个1*1的方块，高度为1;

2.对于一个括号序列A，”(A)”的表示是由一个比g(A)宽2个单位高1个单位的矩形包围g(A)，它的高度为A+1;
3.对于两个括号序列A和B，A+B的几何表示形式为把g(B)放置在g(A)右边的一个单位，且高度为A和B的高度的较大值。
其中+指的是字符串的连接符。

在完成课件后，托米老师开始玩他做好的图片。 他将图像的有限区域交替地涂成黑色和白色，使最外面的区域全部涂成黑色。 对于上面的例子，这个着色如下所示：

现在给你一个合法的括号序列。 请计算颜色为黑色的区域的面积。

输入描述:

输入的第一行包含一个整数T，表示指定测试用例的数量。
每个测试用例前面都有一个空白行。
每个测试用例由一个合法括号序列组成。 每行只包含字符’(‘和’)’。

输出描述:

对于每个测试用例，输出一行包含一个整数,表示相应几何表示的黑色部分的面积。

示例1

输入

复制

2

((()))

(())(()(()))

输出

复制

10

20

说明

第二个测试案例是上图中显示的案例。

备注:

1≤T≤10

一个合法括号序列长度≤4 x 105

这题主要是处理三个问题 一个是长方体的高度，一个长度，白色还是黑色。

首先预处理，颜色，和高度

颜色，判断是第几个奇偶就行了，第一个肯定是黑色，第二个就是白色。

注意处理的时候每匹配一个’)’ 数量就要减1；

长方体的高，用一棵树就行了，然后每个‘（’的度就是每个长方形的高度。

长度容易处理 直接找到匹配的括号直接距离 -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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const long long mod=1e9+7;
const int maxn=1e7+25;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int a[maxn];
int p[maxn],b[maxn];

char ch[maxn];
int n;
stack<int> s;

int main() {
    scanf("%d",&n);
    while(n--) {
        scanf("%s",ch);
        int l=strlen(ch);
        a[0]=1;
        int x=1,y=0;
        p[0]=-1;
        b[0]=1;
        int k=0;
        for(int i=1; i<l; i++) {
            if(ch[i]=='(') {
                a[i]=a[i-1]+1;
                p[i]=k;
                k=i;
                b[k]=1;
            } else {
                b[p[k]]=max(b[p[k]],b[k]+1);
                k=p[k];
                a[i]=a[i-1]-1;
            }
        }
//        for(int i=0;i<l;i++)
//            printf("%d%c",b[i],i+1==l?'\n':' ');
        long long flag=1,sum=0;
        for(int i=0; i<l; i++) {
            if(ch[i]=='(') {
                s.push(i);
            }
            else {
                int k=s.top();
                s.pop();
                if(a[k]%2==1)sum=sum+(i-k)*(b[k]);
                else sum-=(i-k)*(b[k]);
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}

D：

链接：https://www.nowcoder.com/acm/contest/111/D来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K 64bit IO Format: %lld

题目描述

此时的托米老师已经出任CEO，迎娶白富美，走向了人生巅峰！于是这个暑假，托米老师打算在北京一个偏僻的小农村里度过他的假期。

由于这里什么都没有，于是他去超市选了很多生活用品，更多的是吃的，然后推着堆满零食的购物车到柜台等待结账。
当然，我们都知道他的钱包里有很多钱。但是，作为一名为生活精打细算的男孩子，他更愿意使用其他支付方式如：饭券，礼券，不同类型的优惠券等。但是饭券只能用于购买食物，而礼券通常只限于某种类型的礼物。
现在给你托米购物车中物品的数量N和每件物品的价格。也会给出他钱包中的代金券数量M以及允许使用的信息 。 在为他的购物付款时，托米可能使用代金券的金额超过他所购物品的成本。也可以在多张代金券之间拆分商品的成本，并使用代金券支付多件商品。 请你计算托米需要为购物支付的额外现金的最小金额。

输入描述:

1
输入的第一行包含一个整数T，用于指定测试用例的数量。 每个测试用例前面都有一个空白行。 每个测试用例从包含两个正整数N(物品数量)和M(券数量)的行开始。 接下来一行包含N个数字，第i个数字表示托米购物车里第i件物品的价格。 接下来一行包含M个数字，第i个数字表示第i张券的金额。 接下来有M行，当中的第 i 行描述第 i 张卷可以买哪些商品。每行的第一个数字是 K,代表第 i 张卷可以为 K 件商品付款，接下来还有 K 个数，是这 K 件商品的编号

输出描述:

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const long long mod=1e9+7;
const int maxn=2e2+25;
const int maxm=4e3+25;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;

int n,m,T;
int a[maxn],b[maxm];

struct edge {
    int to,cap,rev;
};
vector <edge> G[maxn+maxm];
bool used[maxn+maxm];
int level[maxn+maxm];
int iter[maxn+maxm];

void bfs(int s) {
    memset(level,-1,sizeof(level));
    queue<int> que;
    level[s]=0;
    que.push(s);
    while(!que.empty()) {
        int v= que.front();
        que.pop();
        for(int i=0; i<G[v].size(); i++) {
            edge & e=G[v][i];
            if(e.cap>0&&level[e.to]<0) {
                level[e.to]=level[v] + 1;
                que.push(e.to);
            }
        }
    }
}



void add(int from,int to,int cap) {
    edge eg;
    eg.to=to;
    eg.cap=cap;
    eg.rev=G[to].size();
    G[from].push_back(eg);
    eg.to=from;
    eg.cap=0;
    eg.rev=G[from].size()-1;
    G[to].push_back(eg);
}

//int dfs(int v,int t,int f) {
//    if(v == t)return f;
//    used[v]=true;
//    for(int i = 0; i < G[v].size(); i++) {
//        edge &e=G[v][i];
//        if(!used[e.to]&&e.cap>0) {
//            int d=dfs(e.to,t,min(f,e.cap));
//            if(d>0) {
//                e.cap-=d;
//                G[e.to][e.rev].cap+=d;
//                return d;
//            }
//        }
//    }
//    return 0;
//}

int dfs(int v,int t,int f) {
    if(v == t)return f;
    for(int &i = iter[v]; i < G[v].size(); i++) {
        edge &e=G[v][i];
        if(e.cap>0 && level[v]<level[e.to]) {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0) {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
/*
int maxflow(int s,int t) {
    int flow=0;
    for(;;) {
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0)return flow;
        flow += f;
    }
}
*/
int maxflow(int s,int t) {
    int flow=0;
    for(;;)
    {
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f = dfs(s,t,INF))>0)
        {
            flow +=f;
        }
    }
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        int sum=0;
        for(int i=0;i<=m+n+1;i++)G[i].clear();
        for(int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            sum+=a[i];
            add(i,n+m+1,a[i]);
        }
        for(int j=1; j<=m; j++) {
            scanf("%d",&b[j]);
            add(0,n+j,b[j]);
        }
        for(int i=1; i<=m; i++) {
            int k;
            scanf("%d",&k);
            for(int j=0; j<k; j++) {
                int x;
                scanf("%d",&x);
                add(n+i,x,a[x]);
            }
        }
        cout<<sum-maxflow(0,n+m+1)<<endl;
    }
    return 0;
}