0%

编程中极值的选取

很多时候,在编程中我们都需要把一些变量初始化为极大、极小值。下面是对于一些常见极值的比较。

TL; DR:

比较时用 0x7fffffff, 需要参与运算(如 a = max(a+b, c) )时, 用 0x3fffffff0x3f3f3f3f

不用数了, 7 个 f。

如果是 long long, 用 0x7fffffffffffffffLL0x3f3f3f3f3f3f3f3fLL0x3fffffffffffffffLL

15 个 f。

10000000

此类极值无疑是最简单的一种, 随手写即可。初学阶段可以使用,但是后期就会产生风险。

首先,如果手欠多写了几个 0, 会发生什么呢?

可以运行一下代码测试一下:

printf("%d", 10000000000);
// Outputs 1410065408

这是为什么呢? 注意, 在 C 语言中, 字面量也是有类型的。 $10000000000$的类型是 int,但是他超过了 int 所能表示的最大值 $2147483647$,所以溢出为了 $1410065408$。

其次,如果少写了几个 0,会发生什么呢?

”极大值“选取的不够大,程序就会算出错误的结果。

所以, 不建议这样选取极大值。

0x7fffffff

当需要进行比较类型的运算时,(如保存最小值的变量要用一个极大值初始化),可以初始化为0x7fffffff

原因:

  1. 他是 int 类型变量的最大值,绝大部分情境下足够大。
  2. 比 10 进制下 int 变量最大值$\left(2147483647\right)$更好记忆。 (7 后 7 个 f)

缺点:

因为它是 int 最大值,加上 1 都会溢出为负数。所以仅能在不需要进行算数运算,仅需要进行比较时使用。

0x3fffffff / 0x3f3f3f3f

需要极值参与的运算大部分情况下都是这样的:

a = max(a+b, c);
// a 和 b 可能是极大值

这种情况下,仅需要保证 $a+b$ 的过程不溢出,既保证$a \leq INT_MAX / 2$ 即可。所以,a 可以初始化为0x3fffffff。(一样还是 7 个 f)

同样,在图论题中,我们经常需要把一整个二维数组赋值为极值。这种情况下,0x3fffffff不能使用memset进行一次性赋值。因此,采用略小一些的 0x3f3f3f3f 就可以一次性用memset赋值:

int data[MAXN][MAXM];
memset(data, 0x3f, sizeof data);

还记得吗? memset 函数是对于给定大小数组的每个字节赋值为指定的值。

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

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 , and each female students represent . When a teacher says a non-zero positive integer number of , male students and female students need to gather together and keep .

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 , , . .

Meaning of and are described above. means there will be queries.

For the next line, each line contains a non-zero positive integer .

输出数据

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 , output ARE YOU KIDDING ME?.

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

样例输入

2 2 3
1
100

样例输出

ARE YOU KIDDING ME?
49 0

题目大意

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

相当于是求以下方程中 的正整数解,同时要求, 输出

思路

读入 。 每次查询读入 , 起手直接 。然后就是解方程。

进行时间复杂度分析:, 直接暴力即可。

伪代码

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

代码

#include 
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?"<

  1. MacOS:brew install qemu i386-elf-gcc

    Ubuntu: apt install qemu gcc

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

    或者下载我的修改版本: git clone https://github.com/leoleoasd/pintos_configuration.git,并跳过第 4,5 ,10步。

  3.  export GDBMACROS=$PINTOSHOME/src/misc/gdb-marcos
     export PATH=$PATH:$PINTOSHOME/src/utils
  4. 修改 src/Make.config, 把ifneq (0, $(shell expr `uname -m` : '$(X86)')) 的 if 块替换为以下内容:

    ifeq (0, $(shell expr `uname` : 'Darwin'))
      ifneq (0, $(shell expr `uname -m` : '$(X86)'))
        CC = gcc
        LD = ld
        OBJCOPY = objcopy
      else
        ifneq (0, $(shell expr `uname -m` : '$(X86_64)'))
          CC = gcc -m32
          LD = ld -melf_i386
          OBJCOPY = objcopy
        else
          CC = i386-elf-gcc
          LD = i386-elf-ld
          OBJCOPY = i386-elf-objcopy
        endif
      endif
    else
      CC = x86_64-elf-gcc -m32
      LD = x86_64-elf-ld -m elf_i386
      OBJCOPY = x86_64-elf-objcopy
    endif
  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. cd src/utils && make

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

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

    #!/usr/bin/env bash
    make
    cd build || exit
    killall qemu-system-i386
    
    CMD="run alarm-signle"
    nohup bash -c "DISPLAY=window ../../utils/pintos --qemu --gdb -- $CMD > pintos.log" &
    echo "Done!"
  9. 在项目根目录(src外面)新建一个CMakeLists.txt用于使用 clion 提供的代码提示功能, 不能用于编译代码。 内容从 这里 复制。

  10. 用 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 脚本

  11. Cmd+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 组),每组数据为消消乐某一回合棋盘。

第一行为空格分割的两个整数 ,分别代表消消乐游戏棋盘的行数和列数,当 时,代表多组数据结束,不做输出,否则保证

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

输出

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

样例输入和输出

Input

4 4
__O_
__O_
OO_O
__O_
1 1
O
0 0

Output

4
0

限制 2s/256M

思路

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

伪代码

读入 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指令就都可能在不同的连接上进行, 而正如上文所述, 每一个连接对应了一个不同的内存数据库, 因此也就会出现 “上一行还正常, 下一行就不存在数据表” 的情况了.