玖的数学&算法录
0%

ABC283

发表于 更新于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

D - Scope

题面

给你一个字符串只包括了”(“,”)”和小写字母，如果通过以下步骤，能使字符串为空，那么称字符串是好的：

  • 删除所有小写字母
  • 不停地删除连续的**()**

给定一个好的字符串，并且你有一个盒子，你有以下的操作：

1.如果当前 s[i] 是小写字母，将小写字母放入盒子中，盒子中不能出现两个相同的小写字母。

2.如果当前 s[i] 是 “(“ ， 那么什么都不做。

3.如果当前 s[i] 是 “)” ，取小于 i 的最大的 j , 使 Si ~ Sj 这个子串是好的，将 j 到 i 操作中放入的小球全部取出。

如果违背了1，那么输出No，否则输出Yes。

数据范围

$$1 \leq |S| \leq 3 \times 10^5$$

思路：模拟

1：如果当前字符为”(“，那么将cnt 增加1，为一个左括号。

2：如果当前字符为小写字母，如果说当前字符没有出现过，那么让它的值为cnt，反之输出No。

3：如果当前字符为”)”,那么遍历一次26个字母，如果满足等于cnt，那么将其清0。

代码

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
int st[30];

void JiuCherish(){
    std::string s;
    std::cin >> s;
    int n = s.length();
    int cnt = 1;
    memset(st,false,sizeof(st));
    for(int i=0;i<s.length();i++) {
        if(s[i] == '(') ++cnt;
        else if(s[i] >= 'a' && s[i] <= 'z') {
            if(st[s[i] - 'a']) {
                std::cout << "No" << endl;
                return;
            } else {
                st[s[i] - 'a'] = cnt;
            }
        } else if(s[i] == ')'){
            for(int j=0;j<26;j++) {
                if(st[j] == cnt) st[j] = false;
            }
            --cnt;
        }
    }
    std::cout << "Yes" << endl;
}

E - Don’t Isolate Elements

题面

给定一个 n * m 的 01 矩阵 a,称位于第 i 行第 j 列的元素为 ai,j。

你可以进行如下的操作任意次（可以为0次）：

  • 选择任意一行，翻转此行内的所有元素。

如果当前 [i,j] 的 01 性与 [i-1] [j], [i + 1] [j], [i] [j - 1],[i] [j + 1] 均不相同，那么我们称其点为被隔离点。

请输出使得给定矩阵中没有元素被隔离所需要的最小操作数，如果无论如何操作都无法满足要求则输出 -1。

数据范围

$$2 \leq n,m\leq1000$$

F - Permutation Distance

题面：

你有一个1~n 的排列 p = (p1,p2,…,pn)

你需要对每个 i 求得

$$\displaystyle D_i = \min_{j \neq i} {(|p_i - p_j| + |i - j|)}$$

数据范围：

$$\displaystyle 2 \leq n \leq 2 \times 10^5$$

思路一：暴力

对于每个点，向两边暴力枚举更新答案，如果下标太远则不可能更新到。

时间复杂度：O(n ^ {3 / 2})。

没明白：copy by ppip的思路

复杂度证明：显然一个点向两边最多跑 O(D_i) 次就会停止。所以复杂度为 O*(∑D**i)。

而每个点取离它最近的一个点连边，这个显然能构成一个基环树森林。

同时，在最小生成基环树森林中，每个点都必须要有一个出边， 所以给每个点钦定最短的那个出边是一定能构成最小生成基环树森林的。

而平面曼哈顿距离最小生成基环树（森林）在点的横纵坐标范围均是 [1,n] 的整数时，上界是 O(n\sqrt n) 的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[MAXN];

int dis(int x,int y) {
    return abs(x - y) + abs(a[x] - a[y]);
}

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=n;i++) {
        int d = 1e9; 
        for(int j = i + 1;j - i < d && j <= n;j++) {
            d = std::min(d,dis(i,j));
        }
        for(int j = i - 1;i - j < d && j >= 1;j--) {
            d = std::min(d,dis(i,j));
        }
        std::cout << d << " ";
    }
}

思路二：