扎红颜

杭电1

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

/ 注册

全部文章 / 杭电1 （共6篇）

杭电1 ：Pass!

题面：有n个人每过一秒传一次球，现知道t秒能有x种最后传回第一个人的可能，求t的最小值。解析：设x=f(t),所以易得接着求解特征方程，得到特征根-1，n-1;带入t=0时f(t)=1,和t=1时f(t)=0;之后因为已知f(x)和n,分奇偶考虑，就可以用bsgs求t。 bsgs :形如 ,若 ,方...

2021-08-17

0 373

杭电1：Xor sum

题面：给定一个长度为n的序列，求一个异或不小于k的最小子序列，输出最小的左端点和其右端点。解析：暴力方法是将序列的每一个点当作左端点，找到最小的子序列。复杂度o(n^2),显然是不行的。我们知道a xor b= c;a xor b xor c= 0;若用sun[i]表示前i个数的异或值，则sum[i...

2021-07-31

0 362

杭电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

杭电1 ：1008

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

2021-07-23

0 441