2020工大杯题解-C

发表于 2020-11-23 更新于 2020-12-05 分类于题解本文字数： 1.2k 阅读时长 ≈ 4 分钟

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

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

题目描述

午休期间，I同学最爱做的就是追跑打闹了。

由于I同学力气很大，I同学追跑打闹的时候，每一步都是从学校的一个教学楼跳到另一个教学楼。

但是学校的教学楼太多，为了避免迷路，I同学决定用一根绳子跟在身后。

然而I同学在教学楼之间跳跃的动作会发出巨大声响，每一步都会得罪附近某栋教学楼中的同学们。

为了向I同学复仇，这些教学楼中的同学们决定沿着I同学跳跃时留下的绳子寻找位置和速度不能同时确定的I同学。聪明的I同学有时会记得身后刚刚留下的绳子，但是更多时候，聪明的I同学会忙着赶路，留下搭在刚刚跳过的两栋教学楼之间的绳子。

然而I同学很懒，他不知道向自己复仇的同学们能不能只沿着绳子就找到自己，聪明的你快来帮帮他，让I同学知道自己的人身是否安全吧！

输入

第一行为两个整数N和Q，用一个空格分割，分别为学校教学楼的数目和I同学跳跃的总次数。 $1 \leq N \leq 1000000$ , $1 \leq Q \leq 500000$ 。
学校的教学楼编号 $1$ 到 $N$ ，I同学初始在 $1$ 号教学楼。
接下来的Q行，每行为三个整数 $X Y Z$ ，其中X表示I同学跳跃的目标楼号，Y表示I同学完成此次跳跃后得罪的同学所在教学楼的编号，Z的取值为0或1，0表示I同学忘记切断绳子，1表示I同学切断了绳子。

输出

每次I同学跳跃后，输出一行，如果I同学很安全，输出 “MHAHAHAHAHAHAHAHA!!!”，否则，如果I同学可能会遇到危险，输出 “HEEEEEEELP!!!”。
考虑到输出可能过大，如果Q > 10，则只输出一个整数，为 “MHAHAHAHAHAHAHAHA!!!” 的个数，其余不进行输出。

样例输入和输出

Input

Output

HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!
MHAHAHAHAHAHAHAHA!!!
HEEEEEEELP!!!!!!!!!!!

提示

I同学很聪明，如果两栋楼之间已经有绳子了，I同学就不会自寻死路了

题解

题目重述

有n个教学楼， I （大写i）同学从1号楼出发，每次跳跃到一个教学楼。有一定可能把两个教学楼用绳子连接起来。

每跳到一个教学楼会得罪附近的一些人。附近的人可以沿着绳子自由移动。于是，我们可以把绳子连接起来的几栋教学楼视为一个整体。只要跳到了一个包括得罪的人的教学楼组中，就凉凉了。

题目解法

复杂度分析：首先，一遍更新一遍查询，应使用在线算法。

其次，查询、更新次数为 $500000$ ，并查集时间复杂度为 $O (α (n))$ ，可以接受。

于是用并查集。每链接一条绳子，就把两个教学楼所在集合合并到一起。每次得罪某栋楼的人，就把他所在的集合标记为已得罪。如果每次跳跃结束后，当前集合为已得罪，就凉了。反之，就稳了。

伪代码

初始化并查集
读入数据
对于每组数据：
	如果没切断绳子： 合并（当前所在，上一次所在）
	标记得罪了的集合
	输出状态或者保存 MAAAA 的次数

AC代码

#include <iostream>
using std::cin;
using std::cout;
using std::ios;
#define MH "MHAHAHAHAHAHAHAHA!!!"
#define HELP "HEEEEEEELP!!!!!!!!!!!"
#define endl '\n'
#define MAXN 1000001
// 并查集
int father[MAXN] = {0};
int size[MAXN] = {0};

int annoyed[MAXN] = {0}; // 是否惹了

int find(int i){
    if(father[i] == i) return i;
    return father[i] = find(father[i]);
}

void uni(int a,int b){
    int fa = find(a);
    int fb = find(b);
    if (size[fa] < size[fb]) {
        return uni(b,a);
    }
    size[fa] += size[fb];
    size[fb] = 0;
    father[fb] = fa;
    annoyed[fa] += annoyed[fb];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    for(int i = 1; i <= n; ++ i){
        father[i] = i;
        size[i] = 1;
    }
    int nowpos = 1;
    int to, annoying, cut;
    int help = 0;
    int ma_sum = 0;
    for(int _ = 0; _ < q; ++ _){
        cin>>to>>annoying>>cut;
        help = 0;
        if(!cut){
            uni(nowpos, to);
        }
        nowpos = to;
        annoyed[find(annoying)] = 1;
        int nn = find(nowpos);
        help = annoyed[nn];
        if(q <= 10){
            cout<<(help?HELP:MH)<<endl;
        }
        ma_sum += (help == 0);
    }
    if(q > 10){
        cout<<ma_sum<<endl;
    }
    return 0;
}

编程中极值的选取

发表于 2020-11-22 更新于 2020-12-05 分类于教学本文字数： 582 阅读时长 ≈ 2 分钟

编程中极值的选取

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

TL; DR:

比较时用 0x7fffffff，需要参与运算（如 a = max(a+b, c) ）时，用 0x3fffffff 或 0x3f3f3f3f

不用数了， 7个f。

如果是 long long，用 0x7fffffffffffffffLL 或 0x3f3f3f3f3f3f3f3fLL 或 0x3fffffffffffffffLL

15个f。

10000000

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

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

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

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

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

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

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

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

0x7fffffff

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

原因：

他是int类型变量的最大值，绝大部分情境下足够大。
比10进制下int变量最大值 $(2147483647)$ 更好记忆。（7后7个f）

缺点：

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

0x3fffffff / 0x3f3f3f3f

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

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

这种情况下，仅需要保证 $a + b$ 的过程不溢出，既保证 $a \leq I N T_{M} A X / 2$ 即可。所以，a可以初始化为0x3fffffff。（一样还是7个f）

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

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

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

2020工大杯题解-B

发表于 2020-11-10 分类于题解本文字数： 527 阅读时长 ≈ 2 分钟

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

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 $a x + b y = 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$ . $(0 \leq n \leq 100, 2 \leq a, b \leq 10^{4})$ .

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$ . $(0 \leq c \leq 10^{6})$

输出数据

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 \geq 1$ ，输出 $x - 1, y$ 。

$a x + b y = c$

思路

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

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

伪代码

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

代码

#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;
}

Pintos 从编译到 Kernel Panic：在 CLion 里愉快的 Debug

发表于 2020-11-08 更新于 2023-03-26 分类于 Records 本文字数： 324 阅读时长 ≈ 1 分钟

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

MacOS：brew install qemu x86_64-elf-gcc x86_64-elf-binutils

Ubuntu: apt install qemu-system-i386 gcc
最新的代码在： git clone git://pintos-os.org/pintos-anon，但是建议使用我的修改版本： git clone https://github.com/leoleoasd/pintos_configuration.git。
修改~/.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
cd src/utils && make
cd src/threads && make && cd build && pintos --qemu --

在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!"

用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脚本
Cmd+D orCtrl+D即可调试。

Pintos 笔记

发表于 2020-11-05 更新于 2020-11-10 分类于 Records 本文字数： 75 阅读时长 ≈ 1 分钟

安装

安装依赖：sudo apt install qemu-system-i386
用最新的代码： git clone git://pintos-os.org/pintos-anon

 export GDBMACROS=$PINTOSHOME/src/misc/gdb-marcos
 export PATH=$PATH:$PINTOSHOME/src/utils

cd src/utils && make
按照这里：

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

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

发表于 2020-11-02 更新于 2020-11-03 分类于题解本文字数： 756 阅读时长 ≈ 3 分钟

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

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

题面

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

输入

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

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

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

输出

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

样例输入和输出

Input

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}$ 求当前分数)，可以接受。因此，暴力枚举交换，计算当前分数即可。

伪代码

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

代码

#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;
}