0%

注:流程支持M1的mac、Intel的Mac以及Ubuntu 20.04。

  1. MacOS:brew install qemu x86_64-elf-gcc x86_64-elf-binutils

    Ubuntu: apt install qemu-system-i386 gcc

  2. 最新的代码在: git clone git://pintos-os.org/pintos-anon,但是建议使用我的修改版本: git clone https://github.com/leoleoasd/pintos_configuration.git

  3. 修改~/.bashrc(如果echo $0输出了-bash)或者~/.zshrc(如果echo $0输出了-zsh),增加以下内容到文件末尾:

    export PINTOSHOME=<你的Pintos路径>
    export GDBMACROS=$PINTOSHOME/src/misc/gdb-marcos
    export PATH=$PATH:$PINTOSHOME/src/utils
    

    然后执行:source ~/.bashrc 或者 source ~/.zshrc

  4. cd src/utils && make

  5. cd src/threads && make && cd build && pintos --qemu --

  6. src/threads新建一个 bash 脚本,写入以下内容:

    #!/usr/bin/env bash
    make
    cd build || exit
    killall qemu-system-i386 # 杀掉上一次打开的QEMU。Clion不能在停止Debug的时候关闭QEMU。
    
    CMD="run alarm-signle" # 你要运行的指令。
    nohup bash -c "DISPLAY=window ../../utils/pintos --qemu --gdb -- $CMD > pintos.log" &
    echo "Done!"
    
  7. 用 clion 打开项目。如果之前打开过项目,删除.idea文件夹后再打开。点击右上角的 Add configurations, 选择 GDB Remote Debug, 填入以下信息:

    ’target remote‘ args: tcp:localhost:1234

    Symbol file: 选择你 src/threads/build/kernel.o

    Path mappings:

    ​ remote: ../../threads

    ​ local: 你的项目的完整路径/src/threads

    Before launch: 添加一个Run external tool, 选择上面新建的 bash 脚本

  8. Cmd+D or Ctrl+D即可调试。

安装

  1. 安装依赖:sudo apt install qemu-system-i386

  2. 最新的代码git clone git://pintos-os.org/pintos-anon

  3.  export GDBMACROS=$PINTOSHOME/src/misc/gdb-marcos
     export PATH=$PATH:$PINTOSHOME/src/utils
    
  4. cd src/utils && make

  5. 按照这里

    comment out #include <stropts.h> in both squish-pty.c and squish-unix.c, and comment out lines 288-293 in squish-pty.c.

  6. pintos --qemu --

个人题解,和比赛官方无关,仅供参考

2020工大杯题解 - A - I同学的课间

题面

I 同学的课间自然离不开家喻户晓门当户对怡情益智的小游戏消消乐,但是 I 同学很懒,聪明美丽善良大方机智勇敢勤劳可爱的你快来帮帮他,找到每一回合得分最大的走法吧!

输入

题目有多组输入数据(不超过 100 组),每组数据为消消乐某一回合棋盘。

第一行为空格分割的两个整数 ,分别代表消消乐游戏棋盘的行数和列数,当 N,MN, M0,00, 0 时,代表多组数据结束,不做输出,否则保证 1N,M401 \leq N, M \leq 40

接下来的 NN 行,每行为 MM 个非空字符。其中 O 代表黑色子,_ 代表白色子。每一回合,可以交换同一行或同一列中任意一对相邻棋子。如果交换后,在同一行或同一列当中出现连续三个或以上相同颜色的棋子,则这一步得分为上述相同颜色棋子的个数的最大值,否则得分为 00,棋盘恢复原状。

输出

对于每组数据,输出一行,包含一个整数,为该回合得分最大的一步的得分。

样例输入和输出

Input

4 4
__O_
__O_
OO_O
__O_
1 1
O
0 0

Output

4
0

限制 2s/256M

思路

首先进行时间复杂度分析。 NN4040,暴力算法的时间复杂度是O(n4)O(n^4) (n2n^2枚举交换,n2n^2求当前分数),可以接受。因此,暴力枚举交换,计算当前分数即可。

伪代码

读入 n,m
如果 n,m 均为 0,退出
读入矩阵
枚举每个点:
	如果他右边有点,和右边交换后计算分数,如果分数超过历史最大值,保存分数。换回来。
	下边同理
输出最高分数。

代码

#include 
using namespace std;
#define MAXN 50
#define O 0
#define _ 1
int map[MAXN][MAXN] = {0};
int n,m;

int score(){ // 计算分数
    int m_c = 0;
    int last = -1;
    int last_count = 0;
    for(int i = 0; i < n; ++ i){
        last = -1;
        last_count = 0;
        for(int j = 0; j < m; ++ j){
            if (map[i][j] == last){
                last_count ++;
            } else {
                last_count = 1;
                last = map[i][j];
            }
            m_c = m_c > last_count ? m_c : last_count;
        }
    }
    for(int j = 0; j < m; ++ j){
        last = -1;
        last_count = 0;
        for(int i = 0; i < n; ++ i){
            if (map[i][j] == last){
                last_count ++;
            } else {
                last_count = 1;
                last = map[i][j];
            }
            m_c = m_c > last_count ? m_c : last_count;
        }
    }
    return m_c >= 3 ? m_c : 0;
}
void swap(int x1, int y1, int x2, int y2){ // 交换
    int t = map[x1][y1];
    map[x1][y1] = map[x2][y2];
    map[x2][y2] = t;
}

int main(){
    char c;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m_s = 0;
    int c_s;
    while(cin>>n>>m, n!=0 && m!=0){
        m_s = 0;
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < m; ++ j){
                cin>>c;
                map[i][j] = c == '_' ? _ : O;
            }
        }
        for(int i = 0; i < n; ++ i){
            for(int j = 0; j < m; ++ j){
                if(i+1 < n){
                    swap(i,j,i+1,j);
                    c_s = score();
                    if(c_s > m_s){
                        m_s = c_s;
                    }
                    swap(i,j,i+1,j);
                }
                if(j+1 < m){
                    swap(i,j,i,j+1);
                    c_s = score();
                    if(c_s > m_s){
                        m_s = c_s;
                    }
                    swap(i,j,i,j+1);
                }
            }
        }
        cout<

TL;DR: :memory:为每个链接打开一个新的数据库.
使用 file::memory:?cache=shared 也可能碰到问题, 配置 MaxOpenConnection 为 1 即可. (db.DB().SetMaxOpenConns(1))

Gorm这一ORM框架很好的屏蔽了不同的RDMS之间的差异, 在运行单元测试时使用sqlite的内存数据库 :memory: 显得尤为方便.

在我的 EduOJ 项目中, 数据库相关的测试没有使用 sqlmock 等, 而是使用了基于SQLite内存数据库. 但是, 在我开始编写代码的过程中出现了玄学问题: 一旦开启单元测试的 Parallel 模式, 就会随机的出现 table xxx not found 错误. 甚至, 在运行代码的过程中, 通过调试模式可以看到, 上一行还存在数据表, 到了下一行就不存在了.

以为这是一个 Race condition, db的值被替换了, 拿着
race detector 看了半天啥也没有. 又经过各种测试, 发现这个问题 当且仅当两个需要数据库的测试同时运行 时发生.

绝望之中, 搜索了一下 gorm sqlite race condition, 找到了 go-sqlite3#204 这个 issue. issue中提到, sqlite 会给每一个数据库连接单独开启一个内存数据库. 现在看起来, 这一点也非常合理: 连接与连接之间本身就是应该不 share 任何信息的. issue中给出的解决方案是, 使用 file::memory:?cache=shared 替换 :memory:.

替换为 :memory: 后, sqlite又报错说 “table xxx is locked”. 根据Django文档, 可以发现这个问题源自 sqlite 对于并发请求的处理能力偏弱. 因此, 在使用 sqlite 进行单元测试的时候, 相对好的解决方案还是配置连接池的最大连接数为1.

db, _ := gorm.Open("sqlite3",":memory:")
db.DB().SetMaxOpenConns(1)

那么, 为什么我在调试的过程中会见到如此之诡异的现象呢? 这得从库的设计说起. 由于数据库连接的建立和关闭开销较大, 是一种较为"昂贵"的资源, 因此成熟的数据库客户端库都会 使用连接池. 在需要连接的时候, 从连接池中取出一个已经建立好的连接, 使用完连接后, 放回连接池中, 就能花很大的加快应用程序的速度.

在我的使用情境中, 初始化数据库/建立数据表的SQL仅在第一个连接中执行了. 如果关闭单元测试的Parallel模式, 那么所有的单元测试都是顺序执行的, 始终会用到同一个连接, 不会出现上文的错误. 一旦开启Parallel模式, 每一次sql指令就都可能在不同的连接上进行, 而正如上文所述, 每一个连接对应了一个不同的内存数据库, 因此也就会出现 “上一行还正常, 下一行就不存在数据表” 的情况了.

码浪 - 新一代程序员献给自己的演讲.

那些口口声声,新技术太多学不动的人,应该看着咱们。

我们看着自己,满怀欣喜,程序员积攒了几十年的财富,所有的代码、论文、文档和教程,像是专门为咱们准备的礼物。 文档齐全、社区友好、生态成熟,计算机科学的成果被层层打开,可以尽情地享用。自由学习一门语言,学习一种技术,欣赏一段代码,去遥远的地方进修。 我们从小就能自由探索自己的兴趣,不在需要对着小霸王敲一行一行重启就消失了的BASIC,可以使用scratch进行图形化编程,甚至很多人在幼儿园就使用swift playground进入了不惑之年,不惑于递归是什么,回溯又是什么。人与人之间的壁垒被打破,我们只凭使用相同的库就能结交千万个一起讨论的朋友。我们有幸遇见这样的时代,但是时代更有幸遇见这样的我们。

我们看着自己,满怀敬意,向我们的开源精神致敬。我们正在把别人的变成自己的,把自己的变成别人的,把学术的变成大众的,把个人的变成世界的。随着保护开源者的协议的出现,我们的权益得到了保证。随着自由软件运动的不断推广,用户有了使用,复制,研究,修改和分发软件的权利。我们可以自由的参与、学习别人的项目,可以自由的修改我们所使用的程序来获得自己想要的功能。

任何人的想象力不足以想象我们的未来。奔涌吧,码浪!我们在同一条奔涌的河流。

布尔运算符的短路

首先, 什么是表达式?

表达式是运算符和它们的操作数的序列,它指定一项计算。

表达式的求值可以产生一个结果(比如 2+2 的求值产生结果 4),也可能产生副作用(比如对 std::printf(“%d”,4) 的求值在标准输出上打印字符 ‘4’)。

以下代码每一行的内容都是一个表达式:

a = 1
a++
a = a * a + a - a | a
foo()
foo(a+a)
a == a

注意, a++ 是表达式, a++; 就是一个语句了

其次, 什么是表达式的副作用?

表达式, 顾名思义, 是有一个值的. 很多情况下我们求一个表达式的值, 是为了使用它的值. 在求值的过程中对于变量的修改等操作被称为表达式的副作用.

比如, 对于表达式 y++, y的值+1就是这个表达式的副作用.

比如, 对于以下函数:

int foo(){
    static int i = 0;
    return ++i;
}

对于表达式 foo(), i 的值的变化就是他的副作用.

再比如, 对于表达式 printf("%d",a) + 1, 输出了a的值就是他的副作用.

布尔运算符的短路.

对于 “逻辑与(&&)” 和 “逻辑或(||)” 这两个运算, 他们有一个不同于其他运算符的特点, 就是运算符短路.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是假的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是假, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

对于与运算, 如果他左边的表达式(也叫第一操作数)计算完是真的话, 无论右边的表达式(也叫第二操作数)的结果是多少, 最终的结果一定是真, 因此此时不会计算第二操作数, 第二操作数的副作用也不会发生.

如, 对于以下代码:

int a,b,c;
a = 1;
b = 1;
c = a++ || b++;
printf("%d%d%d\n",a,b,c);

因为表达式a++的计算结果为1, 也就是真, 因此不会计算b++, 程序会输出211.