BestCoder Round #57(Div.2) (2/4) (Div.1) (1/4)

maksyuki 发表于比赛分类，标签: 比赛-bestcoder

27 9月 2015

Scaena Felix

Problem Description

Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('.

If we want every not empty <b>substring</b> of this parentheses sequence not to be "paren-matching", how many times at least to modify this parentheses sequence?

For example, "()","(())","()()" are "paren-matching" strings, but "((", ")(", "((()" are not.

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases contains a parentheses sequence S only consists of '(' and ')'.

1≤|S|≤1,000.

Output

For every test case output the least number of modification.

Sample Input

()

((((

(())

Sample Output

102

Source

BestCoder Round #57 (div.2)

题目类型：简单字符串处理

算法分析：由题目可知，只要存在()的话就会进行操作来修改，则易知最后结果中只会出现全是左括号的，全是右括号的和左边是左括号，右边是右括号的这三种情况，则可以直接枚举答案来选择最小的

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define LL long long
#define ULL unsigned long long
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e3 + 6;

char sa[maxn];

int main()
{
//    CFF;
    int t;
    scanf ("%d", &t);

    while(t--)
    {
        scanf ("%s", sa);
        int resa = 0, resb = 0, resc = INF;
        for (int i = 0; sa[i]; i++)
        {
            if (sa[i] == '(')
                resa++;

            else
                resb++;
        }

        int tt;
        for (int i = 0; sa[i]; i++)
        {
            tt = 0;
            for (int j = 0; j <= i; j++)
                if(sa[j] == '(')
                    tt++;

            for (int j = i + 1; sa[j]; j++)
                if (sa[j] == ')')
                    tt++;

            resc = min (resc, tt);
        }
        printf ("%d\n", min (resa, min (resb, resc)));
    }
    return 0;
}

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define LL long long

#define ULL unsigned long long

#define DB(ccc) cout << #ccc << " = " << ccc << endl

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e3 + 6;

char sa[maxn];

int main()

{

// CFF;

int t;

scanf ("%d", &t);

while(t--)

{

scanf ("%s", sa);

int resa = 0, resb = 0, resc = INF;

for (int i = 0; sa[i]; i++)

{

if (sa[i] == '(')

resa++;

else

resb++;

}

int tt;

for (int i = 0; sa[i]; i++)

{

tt = 0;

for (int j = 0; j <= i; j++)

if(sa[j] == '(')

tt++;

for (int j = i + 1; sa[j]; j++)

if (sa[j] == ')')

tt++;

resc = min (resc, tt);

}

printf ("%d\n", min (resa, min (resb, resc)));

}

return 0;

}

B Conturbatio

Problem Description

There are many rook on a chessboard, a rook can attack the row and column it belongs, including its own place.

There are also many queries, each query gives a rectangle on the chess board, and asks whether every grid in the rectangle will be attacked by any rook?

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with four integers n,m,K,Q.
K is the number of Rook, Q is the number of queries.

Then K lines follow, each contain two integers x,y describing the coordinate of Rook.

Then Q lines follow, each contain four integers x1,y1,x2,y2 describing the left-down and right-up coordinates of query.

1≤n,m,K,Q≤100,000.

1≤x≤n,1≤y≤m.

1≤x1≤x2≤n,1≤y1≤y2≤m.

Output

For every query output "Yes" or "No" as mentioned above.

Sample Input

22 2 1 21 11 1 1 22 1 2 22 2 2 11 11 22 1 2 2

Sample Output

Yes

HintHuge input, scanf recommended.

Source

BestCoder Round #57 (div.2)

题目类型：简单数学+枚举

算法分析：维护前i行和i列中被覆盖的数量(前缀和)，然后对于每次查询，都先求出所在矩形范围内的行、列中被覆盖的数量，然后通过计算就可得到结果

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

#define CPPFF ifstream cin ("aaa.txt")
#define CFF freopen ("aaa.txt", "r", stdin)
#define LL long long
#define ULL unsigned long long

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 66;

int row[maxn], col[maxn];

int main()
{
//    CFF;
    int t;
    scanf ("%d", &t);

    while (t--)
    {
        int n, m, k, q;
        scanf ("%d%d%d%d", &n, &m, &k, &q);
        int u, v;
        memset (row, 0, sizeof (row));
        memset (col, 0, sizeof (col));
        for (int i = 1; i <= k; i++)
        {
            scanf ("%d%d", &u, &v);
            row[u] = 1, col[v] = 1;
        }

        for (int i = 1; i <= n; i++)
            row[i] += row[i-1];

        for (int i = 1; i <= m; i++)
            col[i] += col[i-1];


        int x1, y1, x2, y2, ta, tb, a, b;
        for (int i = 1;i <= q;i++)
        {
            scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
            ta = row[x2] - row[x1-1];
            tb = col[y2] - col[y1-1];
            a = x2 - x1 + 1;
            b = y2 - y1 + 1;
            if (ta * b + tb * a - ta * tb == a * b)
                puts ("Yes");

            else
                puts ("No");
        }
    }
    return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

#define CPPFF ifstream cin ("aaa.txt")

#define CFF freopen ("aaa.txt", "r", stdin)

#define LL long long

#define ULL unsigned long long

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const int MOD = 1e9 + 7;

const int maxn = 1e5 + 66;

int row[maxn], col[maxn];

int main()

{

// CFF;

int t;

scanf ("%d", &t);

while (t--)

{

int n, m, k, q;

scanf ("%d%d%d%d", &n, &m, &k, &q);

int u, v;

memset (row, 0, sizeof (row));

memset (col, 0, sizeof (col));

for (int i = 1; i <= k; i++)

{

scanf ("%d%d", &u, &v);

row[u] = 1, col[v] = 1;

}

for (int i = 1; i <= n; i++)

row[i] += row[i-1];

for (int i = 1; i <= m; i++)

col[i] += col[i-1];

int x1, y1, x2, y2, ta, tb, a, b;

for (int i = 1;i <= q;i++)

{

scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);

ta = row[x2] - row[x1-1];

tb = col[y2] - col[y1-1];

a = x2 - x1 + 1;

b = y2 - y1 + 1;

if (ta * b + tb * a - ta * tb == a * b)

puts ("Yes");

else

puts ("No");

}

return 0;

}

一	二	三	四	五	六	日
« 6月
						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

超客的水墨烟雨

BestCoder Round #57(Div.2) (2/4) (Div.1) (1/4)

Scaena Felix

B Conturbatio

分类目录

标签云

书签

近期评论