发表更新算法 / Codeforces4 分钟读完 (大约547个字)

Educational Codeforces Round 154 (Rated for Div. 2)

Prime Deletion

从 \(1\) 到 \(9\) 的序列中删除一些数（至少保留两位），使得结果为质数。可以发现 \(13\) 和 \(31\) 都是质数，所以判断 \(1\) 和 \(3\) 的先后顺序，然后输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            io.println(13);
            return;
        } else if(s[i] == '3') {
            io.println(31);
            return;
        }
    }
}

Two Binary Strings

比赛时我是从左往右遍历记录不相等的数量，如果有不相等的，那么就需要一个 \(0\)，否则遇到 \(1\) 就输出 YES。和正解的思路是一样的，就是麻烦一点。正解是有相同的 \(01\) 出现时就输出 YES。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    char[] a = io.next().toCharArray();
    char[] b = io.next().toCharArray();
    int n = a.length;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
            io.println("YES");
            return;
        }
    }
    io.println("NO");
}

Queries for the Array

比较简单的写法就是用一个标记数组做记录，递增会向左传递，递减会向右传递，然后判断是否冲突即可。更进一步观察，可以发现只需要记录最大的递增位置，和最小的递减位置。

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
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = true;
    int pos = -1, neg = n, cur = -1;
    for (char c : s) {
        if (c == '+') {
            cur++;
        } else if (c == '-') {
            if (cur-- == neg) {
                neg = n;
            }
            pos = Math.min(pos, cur);
        } else if (c == '0') {
            if (cur == pos || cur <= 0) {
                ok = false;
                break;
            }
            neg = Math.min(neg, cur);
        } else {
            if (neg <= cur) {
                ok = false;
                break;
            }
            pos = cur;
        }
    }
    io.println(ok ? "YES" : "NO");
}

Sorting By Multiplication

没想到啊。枚举负数前缀的长度：在负数前缀中，如果 \(a[i]<=a[i+1]\)，就需要操作一次；在正数后缀中，如果 \(a[i]>=a[i+1]\) 就需要操作一次。（下面的代码很妙啊，不需要加额外的判断语句。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int cnt = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] >= a[i + 1]) {
            cnt++;
        }
    }
    int ans = cnt;
    for (int i = 1; i < n; i++) {
        if (a[i - 1] >= a[i]) cnt--;
        ans = Math.min(ans, cnt + 1);
        if (a[i - 1] <= a[i]) cnt++;
    }
    io.println(ans);
}
发表更新算法 / Codeforces3 分钟读完 (大约424个字)

Pinely Round 2 (Div. 1 + Div. 2)

Channel

如果同时在线人数到达 \(n\)，就表示所有人都阅读过；否则，如果总上线人数大于等于 \(n\)，则有可能所有人阅读过；否则，不可能所有人阅读过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt(), a = io.nextInt(), q = io.nextInt();
    String s = io.next();
    int cur = a, tot = a;
    for (int i = 0; i < q && cur < n; i++) {
        if (s.charAt(i) == '+') {
            cur++;
            tot++;
        } else {
            cur--;
        }
    }
    if (cur == n) {
        io.println("YES");
    } else if (tot >= n) {
        io.println("MAYBE");
    } else {
        io.println("NO");
    }
}

Split Sort

对于每个 \(p_{i}=k+1\) 和 \(p_{j}=k\) 并且 \(i<j\)，那么就一定要选一次 \(x=k+1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int n = io.nextInt();
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt() - 1;
    }
    int[] map = new int[n];
    for (int i = 0; i < n; i++) {
        map[p[i]] = i;
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (map[i] < map[i - 1]) {
            ans++;
        }
    }
    io.println(ans);
}

MEX Repetition

每执行一次操作，就会去除最后一个数，并将 \(MEX\) 添加到序列头部。所以可以通过在数组末尾加上原始数组的 \(MEX\)，将操作看成是向左移动循环数组的起始索引。求原始数组的 \(MEX\) 可以使用求和公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    long sum = 0L;
    int[] a = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    a[n] = (int) ((long) (1 + n) * n / 2 - sum);
    k = k % (n + 1);
    for (int i = 0; i < n; i++) {
        io.print(a[(-k + n + 1 + i) % (n + 1)] + " ");
    }
    io.println();
}

Two-Colored Dominoes

横放的牌只会对列有影响，竖放的牌只会对行有影响，所以分别处理。按行遍历竖放的牌，每当遇到 \(U\) 就染上和上次相反的颜色，如果该行只包含奇数个 \(U\)，就返回 \(-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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    char[][] s = new char[n][];
    for (int i = 0; i < n; i++) {
        s[i] = io.next().toCharArray();
    }
    final char[] aux = {'B', 'W'};
    for (int i = 0; i < n - 1; i++) {
        int xor = 0;
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'U') {
                s[i][j] = aux[xor];
                s[i + 1][j] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int j = 0; j < m - 1; j++) {
        int xor = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] == 'L') {
                s[i][j] = aux[xor];
                s[i][j + 1] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(new String(s[i]));
    }
}

Speedrun

其实思路是知道的，就是不知道怎么写。这个解法看着有点懵，可能其他解法会更好理解一点。注意题目给定 \(a_{i}<b_{i}\)。

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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
    int[] h = new int[n];
    for (int i = 0; i < n; i++) {
        h[i] = io.nextInt();
    }
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, idx -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int a = io.nextInt() - 1, b = io.nextInt() - 1;
        g[a].add(b);
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从 h[i] 开始）
    long[] dp = new long[n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j : g[i]) {
            dp[i] = Math.max(dp[i], dp[j] + (h[j] - h[i] + k) % k);
        }
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从零开始）
    long max = 0L;
    for (int i = 0; i < n; i++) {
        dp[i] += h[i];
        max = Math.max(max, dp[i]);
    }
    // 按照 h[i] 的大小，从小到大枚举起点
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> h[i] - h[j]);
    long ans = Long.MAX_VALUE;
    for (int i : aux) {
        ans = Math.min(ans, max - h[i]);
        // 如果起点大于 h[i]，那么任务 i 的完成时间需要加 k，从而导致 dp[i] + k
        // 其实只要枚举入度为 0 的任务就行，但是即使任务 i 不是入度为 0 任务也没有关系，因为对答案没有影响
        max = Math.max(max, dp[i] + k);
    }
    io.println(ans);
}
发表更新课程 / CMU 15-4456 分钟读完 (大约917个字)

Homework #1 - SQL

作业准备

项目地址：Homework #1 - SQL。

准备工作：阅读 Chapters 1-2 27 3-5，学习 Lecture #01 #02，以及阅读课堂笔记。

Q1 [0 points] (q1_sample):

Ctrl + C，Ctrl +V。

Q2 [5 points] (q2_not_the_same_title):

查询只涉及 titles 表，比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SELECT
	premiered,
	primary_title || ' (' || original_title || ')'
FROM
	titles
WHERE
	primary_title != original_title
	AND type = 'movie'
	AND genres LIKE '%Action%'
ORDER BY
	premiered DESC,
	primary_title
LIMIT
	10;

Q3 [5 points] (q3_longest_running_tv):

题目描述很不清晰啊，类型都不知道具体是什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT
	primary_title,
	IIF(ended IS NULL, 2023, ended) - premiered AS runtime
FROM
	titles
WHERE
	primary_title IS NOT NULL
	AND type = 'tvSeries'
ORDER BY
	runtime DESC,
	primary_title
LIMIT
	20;

Q4 [10 points] (q4_directors_in_each_decade):

唯一要注意的就是使用 DISTINCT。

1
2
3
4
5
6
7
8
9
10
11
12
13
SELECT
	CAST(born / 10 * 10 AS TEXT) || 's' AS decade,
	COUNT(DISTINCT(people.person_id)) AS num_directors
FROM
	people
	INNER JOIN crew USING(person_id)
WHERE
	category = 'director'
	AND born >= 1900
GROUP BY
	decade
ORDER BY
	decade;

Q5 [10 points] (q5_german_type_ratings):

德语的缩写是 de。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
SELECT
	t.type,
	ROUND(AVG(r.rating), 2) AS avg_rating,
	MIN(r.rating),
	MAX(r.rating)
FROM
	akas as a
	INNER JOIN ratings as r USING(title_id)
	INNER JOIN titles as t USING(title_id)
WHERE
	a.language = 'de'
	AND a.types IN ('imdbDisplay', 'original')
GROUP BY
	t.type
ORDER BY
	avg_rating;

Q6 [10 points] (q6_who_played_a_batman):

坑点就是模糊查询时 Batman 两边要加上双引号，即 "Batman"。以及在连接 people 和 crew 表时，顺序很重要，如果使用 crew INNRE JOIN people USING(person_id) 会很慢（查询大概有 5 秒），具体不知道为什么，以下是它们的执行计划。

1
2
3
4
5
6
7
8
9
10
11
12
13
crew INNER JOIN people USING(person_id)

QUERY PLAN
|--SCAN crew USING INDEX ix_crew_person_id
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT

people INNER JOIN crew USING(person_id)

QUERY PLAN
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--USE TEMP B-TREE FOR DISTINCT
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
WITH t AS (
	SELECT
		DISTINCT(person_id),
		name
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		category = 'actor'
		AND characters LIKE '%"Batman"%'
)

SELECT
	name,
	ROUND(AVG(rating), 2) AS avg_rating
FROM
	t
	INNER JOIN crew USING(person_id)
	INNER JOIN ratings USING(title_id)
GROUP BY
	person_id
ORDER BY
	avg_rating DESC
LIMIT
	10;

Q7 [15 points] (q7_born_with_prestige):

SQL 很容易写，但是性能和官解差两秒，等以后学习怎么优化再来看吧。

1
2
3
4
5
6
7
8
9
SELECT
	COUNT(DISTINCT(person_id))
FROM
	titles
	INNER JOIN people ON titles.premiered = people.born
	INNER JOIN crew USING(person_id)
WHERE
	primary_title = 'The Prestige'
	AND category IN ('actor', 'actress');
1
2
3
4
5
QUERY PLAN
|--USE TEMP B-TREE FOR count(DISTINCT)
|--SCAN crew
|--SEARCH people USING INDEX sqlite_autoindex_people_1 (person_id=?)
`--SEARCH titles USING INDEX ix_titles_primary_title (primary_title=?)

Q8 [15 points] (q8_directing_rose.sql):

比官解快一秒。注意使用 Rose% 而不是 Rose %。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
SELECT
	DISTINCT(name)
FROM
	crew
	INNER JOIN people USING(person_id)
WHERE
	category = 'director'
	AND title_id IN (
		SELECT
			title_id
		FROM
			crew
			INNER JOIN people USING(person_id)
		WHERE
			category = 'actress'
			AND name LIKE 'Rose%'
	)
ORDER BY
	name;

Q9 [15 points] (q9_ode_to_the_dead):

这就是窗口函数么，学习了。

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
WITH t AS (
	SELECT
		category,
		name,
		died,
		primary_title,
		runtime_minutes,
		DENSE_RANK() OVER(
			PARTITION BY category
			ORDER BY died, name
		) AS rank_died_name,
		DENSE_RANK() OVER(
			PARTITION BY category, person_id
			ORDER BY runtime_minutes DESC, title_id
		) AS rank_runtime_title
	FROM
		crew
		INNER JOIN people USING(person_id)
		INNER JOIN titles USING(title_id)
	WHERE
		died IS NOT NULL
		AND runtime_minutes IS NOT NULL
)

SELECT
	category,
	name,
	died,
	primary_title,
	runtime_minutes,
	rank_died_name
FROM
	t
WHERE
	rank_died_name <= 5
	AND rank_runtime_title = 1
ORDER BY
	category,
	rank_died_name;

Q10 [15 points] (q10_all_played_by_leo):

不会。。json_each 函数有点神奇，也看了下递归 CTE 的实现，只能说真想不出来。

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
WITH t1(characters) AS (
	SELECT
		characters
	FROM
		people
		INNER JOIN crew USING(person_id)
	WHERE
		name = 'Leonardo DiCaprio'
		AND born = 1974
),
t2(value) AS (
	SELECT
		DISTINCT(value)
	FROM
		t1,
		json_each(t1.characters)
	WHERE
		value != ''
		AND value NOT LIKE '%SELF%'
	ORDER BY
		value
)

SELECT
	GROUP_CONCAT(value)
FROM
	t2;

作业小结

最难的是最后两题，前面几题还可以接受。因为比较在意连接顺序对查询性能的影响，所以多花了点时间。（虽然还没弄明白就是了）

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×