铁厂打工人

分类

题解(7)

/ 注册

全部文章（共7篇）

2022牛客多校第一场J（启发式合并）

题意 Serval要完成一篇英文论文，论文中有n个论点。一个论点的正确性依赖这个论点的前置，如果一个论点的前置论点都是正确的，那么这个论点就是正确的。初始情况下，所有论点都无法被证明是正确的，Serval可以从n个论点中选择一个论点作为论据基础，认为这个论点是正确的，求正确论点数量的最大值。对题目...

2022-08-18

2 228

比武招亲（上）

题目链接 https://ac.nowcoder.com/acm/contest/9985/B 解题思路所有可能的序列中，最大值最小值之差d满足0<=d<n，分别求每一种情况所有可能的序列再相加，就可以得到最终的结果。对于每一种差值d的取值，最小值为x，最大值为x+d，又有(n-d)...

2021-02-23

6 507

武辰延的字符串

题目链接https://ac.nowcoder.com/acm/contest/9984/B 解题思路字符串哈希+二分首先，当s[x]!=t[x]时，如果i>=x，此时不存在当s[x]==t[x]时，需要寻找s的一个最长的前缀使得，这就需要用字符串哈希快速判断字符串是否相等，二分缩小答案...

2021-02-21

1 543

公交线路

公交线路解题思路Dijkstra算法，基于贪心思想，适用于边的权值非负算法流程：1.初始化dis[s]=0,其他节点值为无穷大2.找出一个未标记的，dis[x]最小的节点x,标记x3.更新x的所有出边4.重复2~3，直到所有点被标记邻接矩阵写法 #include <bits/stdc+...

2021-02-10

3 658

丢手绢

丢手绢解题思路尺取法（双指针）先计算距离和，即圆圈周长。之后定义两个指针i，j，用res表示最长距离，当i和j之间的距离大于等于周长的一半时，更新res的值。 AC代码 #include <iostream> #include <algorithm> using name...

2021-01-17

22 749

第k小数

解题思路采用快排的思想，每次确定第k小数所在的区间，直到区间只剩下一个元素，或者k处在mid位置 AC代码 #include <iostream> using namespace std; const int N=5000010; int a[N]; int finding(int ...

2021-01-16

4 620

毒瘤xor

毒瘤xor 解题思路用前缀和预处理31位二进制数每一位1的个数，区间[L, R]上每一位如果1的个数多于0的个数，X对应二进制位上值为0，否则为1注意若有多组可行解，需要输出较小的解，则当0和1个数一样时，X对应二进制位上取0 AC代码 #include <iostream> usi...

2021-01-15

5 597