菜鸡aaa

分类

题解(12)

/ 注册

全部文章（共12篇）

题解 | #字串比较#

暴力做法：切割出s1的[l1,r1]子串，再切割出s2的[l2,r2]子串，比较两个子串的字典序优化利用字符串哈希，可以在o(1)复杂度判断某两个子串是否相等。二分出第一个不匹配的字母代码如下： #include<bits/stdc++.h> #define ull u...

字符串哈希表

2024-03-22

1 234

题解 | #DFS搜索#

A题：DFS搜索直接遍历字符串s，判断是否依次出现过dfs和DFS #include<bits/stdc++.h> using namespace std; int t,n; string s; bool st[6]; int main() { ios::sync_with...

2024-02-02

16 320

题解 | #[NOIP2017]奶酪#

三种解法：bfs，dfs，并查集方法一：bfs 两个点之间的距离如果小于等于2*r，那么这两个点可以相互到达。将所有可以互相到达的两个点之间连一条边。将所有与下表面相交的点入队，从这些点开始进行bfs搜索，对于每个搜索到的点进行判断：该点是否与上表面相交，若能找到与上表面相交的点，则输出yes，若...

C++ 深度优先搜索广度优先搜索并查集

2023-08-13

2 634

题解 | #拆路#

思路： 1、维护每个集合的最大繁荣值，只需要将最大繁荣值的节点设置成根节点，每次查找x所在集合的最大繁荣值时只需要找到x的根节点，根节点的繁荣值即为最大繁荣值。每次合并两个集合时，让较小繁荣值的根节点指向较大繁荣值的根节点。 2、如果按照普通方法先进行m次建边操作，再遍历q次询问或删边操作，会发现并...

C++ 并查集

2023-08-11

5 461

题解 | #迷宫#

题目大意：从S走到E，其中W是墙壁不能走，D是门，必须找到钥匙K才能经过门，求能从S走到E所用的最少步数方法一：从s到e有两种走法。第一种是不经过d，从s到达e。第二种是先从s到k，再从k到e。bfs函数实现求出从点(x1,y1)到（x2,y2)之间的最短距离。求出s到e的距离se，s到k的距...

C++ 广度优先搜索广度优先搜索

2023-08-08

3 559

题解 | #Parity game#

题目链接：https://ac.nowcoder.com/acm/problem/51097 知识点：并查集，维护每个节点到根节点的距离题目描述：一段长为n的由0和1组成的序列，依次给出q个回答，每个回答包括该序列的一个片段子序列的起点位置x，终点位置y，和该子序列【x，y】内有奇数个1还是偶...

C++ 并查集并查集

2023-08-06

3 493

题解 | #[NOIP2010]关押罪犯#

借鉴了别人的题解加上自己的理解 1、只有两座监狱，所以两个罪犯要么在同一个监狱要么在不同监狱 2、将影响力从大到小排序，从大到小枚举每个冲突，尽可能的让冲突避免（即将两个人分到不同监狱），直到出现无法避免冲突的情况，因为已经将冲突由大到小排序，之后的冲突都比这个冲突小，所以该冲突就是答案要求的。 3...

C++ 并查集

2023-08-05

2 591

题解 | #叠积木#

一、把每堆积木看作一个集合，最下方的积木是集合的根节点二、只需要维护集合中每个元素到根节点的距离d[x](这题和食物链那题基本相同）三、还需要维护每个集合中元素的数量s[x]，目的是为了方便后面维护d[x] 四、find(x)函数返回x的祖宗节点，同时更新从x节点到祖宗节点路径上所有的节点d[x...

C++ 并查集并查集

2023-08-05

4 583

题解 | #Let'sPlayCurling#

1、a[N]保存所有红色石头的位置，用b[N]保存所有蓝色石头的位置 2、对a[N]和b[N]都进行sort排序 3、遍历每两个相邻蓝色石头之间有多少个红色石块，最多的那个即为答案 4、需要注意的是第一个蓝色石头之前的所有红色石块也可以是答案，最后一块蓝队石头之后的红色石头也可以是答案 #inclu...

C++ 二分查找

2023-08-05

6 578

题解 | #星球大战#

1、用x[i],y[i]存储i号基地的横纵坐标。用ans[i]记录i号战舰摧毁基地的数量 2、遍历m个战舰，每个战舰有两种类型 3、第一类可以纵向摧毁直线x=b,即坐标为(b,?)的所有基地。用mx[b]=i记录(b,?)被i号战舰纵向摧毁 4、第二类可以横向摧毁直线y=b,即坐标为(?,b)的所有...

C++ 哈希表哈希表

2023-08-04

4 523