Ligh0x74's Blog

2023-08-29发表2023-08-30更新课程 / 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 表，比较简单。

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):

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

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。

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。

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 秒），具体不知道为什么，以下是它们的执行计划。

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

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 很容易写，但是性能和官解差两秒，等以后学习怎么优化再来看吧。

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');

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 %。

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):

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

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 的实现，只能说真想不出来。

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;

作业小结

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

2023-08-28发表2023-08-28更新算法 / LeetCode8 分钟读完 (大约1134个字)

第 360 场力扣周赛

距离原点最远的点

核心：要距离原点最远，那么可选的位置肯定是向同一个方向移动。

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int n = moves.length(), dis = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            char c = moves.charAt(i);
            if (c == 'L') dis--;
            else if (c == 'R') dis++;
            else cnt++;
        }
        return Math.max(cnt - dis, cnt + dis);
    }
}

找出美丽数组的最小和

和上周一样的题目。

class Solution {
    public long minimumPossibleSum(int n, int target) {
        long m = Math.min(target / 2, n);
        return (m * (m + 1) + (target * 2 + n - m - 1) * (n - m)) / 2;
    }
}

使子序列的和等于目标的最少操作次数

比赛时思路满天飞，各种乱写。其实最后的思路是对的，但是基于之前的代码改写，导致有很多 Bug。赛后 15 分钟 AC。从低位到高位枚举 \(target\) 中的 \(1\)，假设当前 \(1\) 对应的值为 \(x\)，那么 \(nums\) 中所有小于等于 \(x\) 的值都可以用来填补 \(x\)，如果不够那么肯定需要将下一个大于 \(x\) 的值分解为 \(x\)。（更优的做法）

class Solution {
    public int minOperations(List<Integer> nums, int target) {
        Collections.sort(nums);
        int n = nums.size();
        int idx = 0, sum = 0, ans = 0;
        for (int i = target; i != 0; ) {
            int x = i & -i;
            i -= x;
            while (idx < n && nums.get(idx) <= x) {
                sum += nums.get(idx++);
            }
            sum -= x;
            if (sum < 0) {
                if (idx == n) return -1;
                ans += Integer.numberOfTrailingZeros(nums.get(idx) / x);
                sum += nums.get(idx++);
            }
        }
        return ans;
    }
}

在传球游戏中最大化函数值

参考大佬的题解。

方法一：倍增 DP

因为 CPU 缓存的原因，数组开成 new int[35][n] 会更快。因为这样转移的时候只从上一行转移，具有空间局部性；而下面的代码是从左边一列转移，不具有空间局部性。

class Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int n = receiver.size();
        int[][] f = new int[n][35];
        long[][] w = new long[n][35];
        for (int i = 0; i < n; i++) {
            f[i][0] = receiver.get(i);
            w[i][0] = i;
        }
        for (int j = 1; j < 35; j++) {
            for (int i = 0; i < n; i++) {
                f[i][j] = f[f[i][j - 1]][j - 1];
                w[i][j] = w[i][j - 1] + w[f[i][j - 1]][j - 1];
            }
        }
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            long cur = 0L;
            int pos = i;
            for (int j = 0; j < 35; j++) {
                if ((k >> j & 1) == 0) continue;
                cur += w[pos][j];
                pos = f[pos][j];
            }
            ans = Math.max(ans, cur + pos);
        }
        return ans;
    }
}

方法二：内向基环树

class Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int n = receiver.size();
        // 建立环外节点的反向边
        int[] in = new int[n];
        List<Integer>[] reverse = new List[n];
        Arrays.setAll(reverse, r -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            in[receiver.get(i)]++;
            reverse[receiver.get(i)].add(i);
        }
        // 拓扑序去除环外节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            if (--in[receiver.get(x)] == 0) {
                q.offer(receiver.get(x));
            }
        }
        // 计算每个环的前缀和，并记录每个节点在哪个环的哪个位置
        int[] cirNum = new int[n];
        int[] cirPos = new int[n];
        boolean[] vis = new boolean[n];
        List<List<Long>> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && in[i] != 0) {
                List<Long> cir = new ArrayList<>();
                cir.add(0L); // 前缀和的冗余节点
                // 存储环的节点，并记录每个节点在哪个环的哪个位置
                for (int cur = i; !vis[cur]; cur = receiver.get(cur)) {
                    vis[cur] = true;
                    cirNum[cur] = circles.size();
                    cirPos[cur] = cir.size();
                    cir.add((long) cur);
                }
                // 重复存储环的节点，方便计算从任意节点开始和结束的价值和
                for (int t = cir.size() - 1, j = 1; t > 0; t--, j++) {
                    cir.add(cir.get(j));
                }
                // 计算前缀和
                for (int j = 1; j < cir.size(); j++) {
                    cir.set(j, cir.get(j) + cir.get(j - 1));
                }
                circles.add(cir);
            }
        }
        // 对环内的每个节点向环外进行 dfs，从而计算出以每个节点作为起点的价值和
        long ans = 0L;
        // 存储环外节点的前缀和
        List<Long> outSum = new ArrayList<>();
        outSum.add(0L);
        for (int i = 0; i < n; i++) {
            // 注意传递 k + 1，表示总节点数量
            if (in[i] != 0) ans = Math.max(ans, dfs(i, circles.get(cirNum[i]), cirPos[i], reverse, in, outSum, k + 1));
        }
        return ans;
    }

    private long dfs(int x, List<Long> cir, int pos, List<Integer>[] reverse, int[] in, List<Long> outSum, long k) {
        long res = 0L;
        int outLen = outSum.size() - 1;
        if (outLen < k) {
            int n = cir.size() / 2; // 因为 cir 多存储了 n - 1 个环内节点，以及一个冗余节点，所以 cir.size() / 2 就是环的长度
            res = (k - outLen) / n * cir.get(n) + cir.get(pos + (int) ((k - outLen) % n) - 1) - cir.get(pos - 1);
        }
        res += outSum.get(outLen) - outSum.get((int) Math.max(0L, outLen - k));
        for (int y : reverse[x]) {
            if (in[y] != 0) continue;
            outSum.add(outSum.get(outLen) + y);
            res = Math.max(res, dfs(y, cir, pos, reverse, in, outSum, k));
            outSum.remove(outLen + 1);
        }
        return res;
    }
}

2023-08-28发表2023-08-28更新算法 / Codeforces6 分钟读完 (大约864个字)

Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

Increasing and Decreasing

比赛时漏看第三个条件，搞半天。而且似乎倒着减会比较容易做（差不多）。

public static void solve() {
    int x = io.nextInt(), y = io.nextInt(), n = io.nextInt();
    int z = (1 + n - 1) * (n - 1) / 2;
    if (z > y - x) {
        io.println(-1);
        return;
    }
    io.print(x + " ");
    int d = x + y - x - z;
    for (int i = n - 1; i >= 1; i--) {
        d += i;
        io.print(d + " ");
    }
    io.println();
}

Swap and Reverse

找规律。第一个操作表明奇数下标相互连通，偶数下标相互连通。第二个操作，如果 \(k\) 是奇数，则连通性不会改变，分别对奇偶字母排序，然后构造即可；如果 \(k\) 是偶数，则奇数下标和偶数下标相互连通，对所有字母排序即可。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    if (k % 2 == 0) {
        Arrays.sort(s);
        io.println(new String(s));
    } else {
        PriorityQueue<Character> list1 = new PriorityQueue<>();
        PriorityQueue<Character> list2 = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) list1.add(s[i]);
            else list2.add(s[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) sb.append(list1.poll());
            else sb.append(list2.poll());
        }
        io.println(sb.toString());
    }
}

Divisor Chain

比赛时瞎猜 AC 的，当时是想从 \(1\) 开始构造到 \(x\)，过程比答案复杂。正解是从 \(x\) 一直减去最低有效位的一（必定是除数），直到 \(x\) 等于 \(2\) 的幂（只剩一个一），然后让 \(x\) 一直减去 \(\frac{x}{2}\) 即可。

public static void solve() {
    int x = io.nextInt();
    List<Integer> ans = new ArrayList<>();
    ans.add(x);
    while ((x & (x - 1)) != 0) {
        x &= (x - 1);
        ans.add(x);
    }
    while (x != 1) {
        x /= 2;
        ans.add(x);
    }
    io.println(ans.size());
    for (int y : ans) {
        io.print(y + " ");
    }
    io.println();
}

Matrix Cascade

使用差分数组维护从上到下的翻转次数，需要注意的是正负需要分开存，正数每层左移一位，负数每层右移一位。PS：这题 \(p\) 和 \(q\) 总是写错，Debug 很久。以及大佬的代码看不懂。

public static void solve() {
    int n = io.nextInt();
    char[][] a = new char[n][];
    for (int i = 0; i < n; i++) {
        a[i] = io.next().toCharArray();
    }
    int ans = 0;
    int[] p = new int[n + 1];
    int[] q = new int[n + 1];
    int[] sum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] - '0' != sum[j + 1] % 2) {
                ans++;
                p[j] ^= 1;
                q[j + 1] ^= 1;
            }
        }
        p[0] ^= p[1];
        for (int j = 1; j < n; j++) {
            p[j] = p[j + 1];
        }
        q[n] ^= q[n - 1];
        for (int j = n - 1; j > 0; j--) {
            q[j] = q[j - 1];
        }
        for (int j = 0; j < n; j++) {
            sum[j + 1] = sum[j] ^ p[j] ^ q[j];
        }
    }
    io.println(ans);
}

Guess Game

有点难以描述，超出能力范围了。这是一个比较好理解的做法，分别考虑每一位。从最低位开始，如果前缀相同，那么就计算当前位 \(0\) 和 \(1\) 的个数，只有爱丽丝拿 \(1\)，鲍勃拿 \(1\) 或 \(0\) 的情况，当前位才会多走一轮。初始时，设置答案为 \(n \times n\)，因为每个组合至少会走一轮。最后需要使用快速幂求 \(n\) 的逆元。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);
    long ans = (long) n * n;
    for (int t = 0; t < 30; t++) {
        for (int l = 0, r = 0; l < n; l = r) {
            int[] cnt = new int[2];
            while (r < n && a[l] / 2 == a[r] / 2) {
                cnt[a[r] % 2]++;
                r++;
            }
            ans += (long) cnt[1] * (cnt[1] + cnt[0]);
        }
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
        }
    }
    ans = ans % MOD * pow(n, MOD - 2) % MOD * pow(n, MOD - 2) % MOD;
    io.println(ans);
}

private static int pow(int a, int n) {
    long res = 1, x = a;
    while (n != 0) {
        if (n % 2 == 1) {
            res = (res * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return (int) res;
}