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

2020工大杯题解 - B - Classmate L’s PE course.

题目描述

Classmate L forgot to elect his course, so he had to take a strange PE course. On this strange course, students will play a weird game: each male student represent $a$, and each female students represent $b$. When a teacher says a non-zero positive integer number of $c$, $x$ male students and $y$ female students need to gather together and keep $ ax +
by = c $.

Classmate L is bad at math, he wants to know how many people he will be gathering together with.

Lots of students forgot to elect courses too, so we can assume that there is an infinite number of male and female students.

输入数据

One line containing three non-zero positive integer $n$, $a$, $b$. $\left(0 \leq n \leq 100, 2 \leq a,b \leq 10^4 \right)$.

Meaning of $a$ and $b$ are described above. $n$ means there will be $n$ queries.

For the next $n$ line, each line contains a non-zero positive integer $c$. $\left( 0 \leq c \leq 10^6 \right)$

输出数据

For each query, output the number of male students and the number of
female students separated by a space.

If it’s not possible form $c$, output ARE YOU KIDDING ME?.

If there are multiple answers, output the answer as the greatest
number of male students.

样例输入

1
2
3

2 2 3
1
100

样例输出

1
2

ARE YOU KIDDING ME?
49 0

题目大意

每个男生代表 $a$，每个女生代表$b$。每次询问一个数$c$，问你 L 同学需和要哪些人一起才能凑出来$c$。输出男生人数最大的方案。

相当于是求以下方程中 $x, y$ 的正整数解，同时要求$x \ge 1$， 输出$x-1, y$。

$$ax + by = c$$

思路

读入 $a, b, n$。 每次查询读入 $c$ , 起手直接 $c = c - a$ 。然后就是解方程。

进行时间复杂度分析：$0 \leq c \leq 10^6$， 直接暴力即可。

伪代码

1
2
3
4
5
6
7

读入a,b,n
循环 n 次：
	读入 c
	c = c - a
	枚举男生人数： 从（c/a） 到 0：
		算女生人数是否是整数， 是就输出
	如果失败， 输出ARE YOU KIDDING ME?

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;
int main(){
    int n,a,b,c;
    cin>>n>>a>>b;
    while(n--){
        cin>>c;
        int x = 0;
        int y = 0;
        c -= a;
        for(x = c / a; x >= 0; x --){
            if ((c - a * x) % b == 0){
                y = (c - a * x) / b;
                break;
            }
        }
        if (x == -1) {
            cout<<"ARE YOU KIDDING ME?"<<endl;
        } else {
            cout<<x<<" "<<y<<endl;
        }
    }
    return 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），增加以下内容到文件末尾：

   1 2 3

   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 脚本，写入以下内容：

   1 2 3 4 5 6 7 8

   #!/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, M $，分别代表消消乐游戏棋盘的行数和列数，当 $N, M$ 为 $0, 0$ 时，代表多组数据结束，不做输出，否则保证 $1 \leq N, M \leq 40$。

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

输出

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

样例输入和输出

Input

1
2
3
4
5
6
7
8

4 4
__O_
__O_
OO_O
__O_
1 1
O
0 0

Output

1
2

4
0

限制 2s/256M

思路

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

伪代码

1
2
3
4
5
6
7

读入 n，m
如果 n，m 均为 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

#include <iostream>
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<<m_s<<endl;
    }
    return 0;
}

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.

1
2

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

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

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

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

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

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

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

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