0%

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

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

编程中极值的选取

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

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?"<<endl;
        } else {
            cout<<x<<" "<<y<<endl;
        }
    }
    return 0;
}

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