AcWing第150场周赛题解

type

status

date

slug

summary

📝 主旨内容

成绩比较

某班有 n个学生，编号 1∼n。

他们上学期的编程成绩分别为 a1,a2,…,an。

他们本学期的编程成绩分别为 b1,b2,…,bn。

请你判断，是否有学生出现成绩退步的情况。

输入格式

第一行包含整数 n。

第二行包含 n 个整数 a1,a2,…,an。

第三行包含 n 个整数 b1,b2,…,bn。

输出格式

如果有学生出现成绩退步的情况，则输出 YES，否则，输出 NO。

数据范围

前3个测试点满足 1≤n≤10。

所有测试点满足 1≤n≤100，1≤ai,bi≤100。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

💡

直接判断就好，签到题

残垣断壁

贝茜盖了一面长方形的墙，该墙恰好由 N×M个边长为 1 的正方形砖块堆叠而成。

作为一头缺乏生活常识的奶牛，它并不懂得使用水泥等胶凝材料让墙变得坚固。

所以仅仅一场台风，就让该墙变为了残垣断壁。

墙面上的一些砖块还存在（用 B 表示），另一些砖块已经消失了（用 . 表示）。

受重力影响，每个幸存的砖块要么位于地面上（最下面一行），要么位于另一块砖块的顶部，不会出现浮空而立的超自然情况。

给定墙面的现状，请你分析当前墙面中一共包含多少个由砖块构成的连通块。

每个砖块视为与其上、下、左、右四个邻近砖块相连。

输入格式

第一行包含两个整数 N,M。

接下来 N 行，包含一个 N×M 的由 B 和 . 构成的字符矩阵，表示整面墙体的当前状况。

输入保证至少存在一个砖块。

输出格式

一个整数，表示当前墙面中包含的由砖块构成的连通块的数量。

数据范围

前 3 个测试点满足 1≤N,M≤10。

所有测试点满足 1≤N,M≤100。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

💡

直接求联通块就可以过(因为数据范围小，最大10^4)，根据题意

受重力影响，每个幸存的砖块要么位于地面上（最下面一行），要么位于另一块砖块的顶部，不会出现浮空而立的超自然情况

直接求最后一行的联通情况即可

盖楼

约翰计划在农田附近盖一栋 H 层的高楼。

楼层自下而上依次编号为 1∼H。

为了防止奶牛们集体反对，约翰需要贿赂两头奶牛头目----贝茜和贝蒂。

约翰和两头奶牛约定，在高楼建成后，约翰需要挑选其中的 N 个楼层送给贝茜，M 个楼层送给贝蒂。

显然，一个楼层最多只能送给一头奶牛。

贝茜不喜欢能被质数 x 整除的数字，因此它不接受编号能被 x 整除的楼层。

贝蒂不喜欢能被质数 y 整除的数字，因此它不接受编号能被 y 整除的楼层。

请你计算，为了让两头奶牛都能满意从而使得高楼可以顺利搭建，这栋高楼至少需要盖多少层，即请你计算满足条件的 H 的最小可能值。

输入格式

共一行，包含四个整数 N,M,x,y。

输出格式

一个整数，表示 H 的最小可能值。

数据范围

前 3 个测试点满足 1≤N,M≤10。

所有测试点满足 1≤N,M<10^9，N+M≤10^9，2≤x<y≤30000，保证 x,y 均是质数。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

💡

容斥原理，正难则反。盖得越高越可以满足，所以问题具有二段性可以二分。先计算能被x整除、能被y整除以及同时被x和y整除的数字数量，贪心地将仅能被x整除的分给贝蒂，将仅能被y整除的数分给贝茜，最后再看能同时分给两个人的数字是否能满足二者剩下的需求

🤗 总结归纳

整体还是比较简单的，有思维在里面，如果第二题整个图是一个10^5*10^5，传统BFS，DFS就会因为超时过不了了

DFS爆栈，下次直接BFS不偷懒了

第三题很容易想到二分，关键是check函数，直接联系到容斥原理，卡在了判断max(远远大于需求)这，WA了两次

如果xy不是质数，那就需要求出xy的最大公约数得到最小公倍数，x*y/gcd(x,y)

📝 主旨内容

成绩比较

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

残垣断壁

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

输入样例3：

输出样例3：

题解：

盖楼

输入格式

输出格式

数据范围

输入样例1：

输出样例1：

输入样例2：

输出样例2：

题解：

🤗 总结归纳

📎 参考文章