tzyt's Blog

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Update on 2022/7/14: I added the sysinfo lab. Lab 2 is now completely documented. Update on 2022/9/14: I recently put the lab code on GitHub. If you need a reference, you can find it here: https://github.com/ttzytt/xv6-riscv The different branches contain the different labs. Lab 2: system calls The system-call process As its name suggests, ...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. C. Train and Queries Problem statement Problem links: (Codeforces, Luogu). You are given an array uuu of length n(1≤n≤2⋅105)n (1\le n \le 2 \cdot 10 ^ 5)n(1≤n≤2⋅105) representing all train stations. A train can travel only from a station on the left to a station on the right. In other words, it starts at u1u_1u1​, then proceeds to u2, u3u_2,...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Update on 2022/9/14: I recently put the lab code on GitHub. If you need a reference, you can find it here: https://github.com/ttzytt/xv6-riscv The different branches contain the different labs. Before beginning, I have to complain: why is the style of the xv6 source code so strange? The return type of a function is not even on the same line...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Book link, Chinese translation: https://github.com/duguosheng/6.S081-All-in-one Chapter Zero I could understand most of this chapter, but the example program involving a pipe confused me for a long time. I finally understood it, so I will record my interpretation here. 1234567891011121314151617int p[2];// p[0] stores the receiving descriptor...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Problem links: (CF, Luogu) | I strongly recommend reading it on the blog. This problem is genuinely difficult to think of. I spent a long time reading the Codeforces solution before understanding it (I am too inexperienced). Problem Statement Given a permutation aaa of length nnn, find how many permutations bbb of the same length are similar...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Background I read the book Complexity a little over a year ago. A recent competition reminded me of the genetic algorithm introduced in the book. Since the book provides a detailed line of thought, I wanted to implement it myself. About Complexity: I will not introduce its contents at length. My only feeling after finishing it was that it wa...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Problem links: (CF, Luogu) | I strongly recommend reading it on the blog. Problem Statement Given an n×mn \times mn×m (1≤n,m≤10001 \le n, m \le 10001≤n,m≤1000) grid, the value of each cell is either −1-1−1 or 111. Determine whether there is a path from (1,1)(1, 1)(1,1) to (n,m)(n, m)(n,m) such that the sum of the values of the cells traverse...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Problem links: (CF, Luogu) | I strongly recommend reading it on the blog. The first CF Div. 4 I participated in. This problem is the kind that becomes very, very simple once you think of the key point, but if you do not, then… you are done for (I was one of those who were done for). 1. Problem Statement: Given an array aaa of length n (∑n<...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. After publishing the Treap blog post today, I read through it myself and suddenly felt very annoyed. That Treap post uses pointers and arrow operators extensively. Because the blog’s font does not support ligatures, they looked particularly silly. So I decided to change the blog’s font to Iosevka. Here are some websites I referred to: https...

The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version. Some rambling I recently discovered how easily I forget algorithms I studied before. Suffix automata, AC automata, plug DP, and many others have almost completely disappeared from memory. Even KMP and network flow become hazy after I have not implemented them for a long time. I am simply not good enough. I therefore thought that I could take...