扎红颜

分类

未归档(20) 杭电1(6) 杭电10(1) 杭电3(3) 杭电5(3) 杭电7(2) 牛客10(1) 牛客2(5) 牛客4(4) 牛客6(2) 牛客8(4)

/ 注册

全部文章（共50篇）

杭电3：Game on Plane

题面：平面上有n条直线，Alice会进行n次操作，每次选出k条直线(k=1,2,3,…n),Bob将画一条直线，若与选中的直线有交点则惩罚加一。Alice想让惩罚最大，Bob反之。最后输出每次操作的惩罚值。解析：画出的直线只能是平行关系才没有公共点。Alice每次会尽量选出斜率不一样的直线，若是斜率...

2021-07-28

0 500

杭电1：Mod, Or and Everything

题面：给定一个数n，求n%1,...,到n%(n-1)的按位或。解析：按位或操作不改变二进制数的长度。答案与n取模的最大值有关，依题意知会出现1到n取模的最大值，所以所有数按位或后，结果的二进制数每一位都为1。代码： #include<bits/stdc++.h> using names...

2021-07-28

0 516

杭电1：Minimum spanning tree

题面：已知2到n个节点，每个点的边长为两点的最小公倍数，求最小生成树。解析：复杂度告诉我们最小生成树板子是行不通的。我们知道互质的两个数的最小公倍数是两数的乘积，一个数是另一个数的因子则最小公倍数就是大的那个数。所以只要我们将所有大于2的质数与2相连，其他合数与其某个因子相连，所得就是最小生成树。代...

2021-07-28

0 343

杭电1：KD-Graph

题面：已知n个点,m条边，要求对所有点分成k块，D大于等于一块区域最大路径，D小于不在同一区域两点距离的最小值。求D的最小值。解析：依题知，求D的最小值，K块中的路径尽可能小。假设开始时n个点构成n块。于是我们可以对边从小到大排序，将小的边的起始点并入终点，进行并查集操作，n--。直至构成构成k块，...

2021-07-25

0 402

牛2 I

Penguins 题面：已知两只企鹅的始末位置，按照题目规则最短路并且有最小字典序。解析：两只企鹅规定是同时行动，构造一个四维数组来表示两企鹅同时到两点的状态。然后直接bfs求出最短路径。用pre[][][][]数组来记录前驱状态，之后用爆搜终点到起始点，将经过的每个点变为'A'，再记录行动方向。...

2021-07-25

0 393

杭电1 ：1008

Maximal submatrix 题面：给定一个的矩阵，求其最大子矩阵的面积，要求每列都是不递减的。多组输入。解析：将给定矩阵转换成0，1矩阵，运用悬线法。用h[ ]数组记录这个点开始的悬线高度，用w[]记录左临界位置的坐标，当遇到悬线高度小于前一悬线，开始更新结果，更新完之后，删除前一个w，...

2021-07-23

0 441

牛2K

K. Stack 题面:有n个数，依次加进栈中，每次加入前将栈顶比a[i]大的所有元素弹掉，加入后b[i]记为栈的大小。现在给你若干时刻单调栈的大小，让你求a数组的一种合法方案，其中1~n在a中各出现了一次。解析：设若没提及单调栈大小，则为前一时刻栈大小加一。若比已知单调栈要小，则不存在。即构造出...

2021-07-20

0 392

牛2F

F. Girlfriend 题面：多组输入，已知四个点，和动点到两点距离的比值范围，求轨迹交出来的体积。（计算几何）解析：先把它看作二维，方便理解。一个点到两定点的距离成比例，初中老师告诉过我们叫阿波罗尼斯圆。如果不记得也没有关系，用样例推一下，两个动点的轨迹都是圆，自然而然地向外推广。而...

2021-07-20

0 449

牛2D

D. Er Ba Game 题面：模拟题，按照题意讨论即可。解析与提示：用三目运算符判断输出，更方便debug。多用函数，思路更清晰。另外看别人的代码发现可以学习的地方：构造函数设置优先级把有2和8的设为12，a==b设为11，剩下的返回（a+b)%10;接下来就只要比较优先级，若是相等还要比较...

2021-07-20

0 346

牛2c

C Draw Grids 题面：给定n×m点阵，每次选相邻的点连线，直到不能操作则失败。解析：生成图不能连成环，共有n×m-1次操作,判断齐偶即可。 #include<bits/stdc++.h> using namespace std; int n,m; int main() {...

2021-07-20

0 351