菜鸡aaa - 个人主页动态 - 牛客网

发布(12) 评论刷题收藏

2024-03-22 21:51

齐鲁工业大学

题解 | #字串比较#

暴力做法：  切割出s1的[l1,r1]子串 ，再切割出s2的[l2,r2]子串，比较两个子串的字典序  优化  利用字符串哈希，可以在o(1)复杂度判断某两个子串是否相等。二分出第一个不匹配的字母  代码如下： #include<bits/stdc++.h> #define ull unsigned long long #define endl "\n" using namespace std; const int N=2e5+10,P=131; ull h1[N],h2[N],p[N]; int n,m,q; int l1,r1,l2,r2; string s1,s2; ull...

0 点赞评论收藏

分享

2024-02-02 23:22

齐鲁工业大学

题解 | #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_stdio(false); cin.tie(0); cout.tie(0); cin>>t; while(t--) { memset(st,0,sizeof st); bool flag1=false; bool flag2=false; cin>>n; cin>>s;...

0 点赞评论收藏

分享

2023-08-13 19:32

齐鲁工业大学

题解 | #[NOIP2017]奶酪#

三种解法：bfs，dfs，并查集 方法一：bfs 两个点之间的距离如果小于等于2*r，那么这两个点可以相互到达。将所有可以互相到达的两个点之间连一条边。将所有与下表面相交的点入队，从这些点开始进行bfs搜索，对于每个搜索到的点进行判断：该点是否与上表面相交，若能找到与上表面相交的点，则输出yes，若无法找到这样的点则输出no。需要注意的是初始所有与下表面相交入队的点，这些点可能同时也与上表面相交，所以要确保判断了这些点是否与上表面相交。 #include<bits/stdc++.h> #define int long long using namespace std; const ...

0 点赞评论收藏

分享

2023-08-11 22:45

已编辑

齐鲁工业大学

题解 | #拆路#

思路： 1、维护每个集合的最大繁荣值，只需要将最大繁荣值的节点设置成根节点，每次查找x所在集合的最大繁荣值时只需要找到x的根节点，根节点的繁荣值即为最大繁荣值。每次合并两个集合时，让较小繁荣值的根节点指向较大繁荣值的根节点。 2、如果按照普通方法先进行m次建边操作，再遍历q次询问或删边操作，会发现并查集难以维护删边操作。如何避免进行删边操作呢？ 3、先用mp存储下这m个建边操作，再用op存储这q个询问或删边操作，对于每个删边a-b的操作，我们将mp中存储的这条边a-b删掉。这样mp中剩余的边都是不再需要进行删边的操作。所以可以直接遍历剩余的mp中的所有边进行建边操作。然后从后往前遍历这op中存...

0 点赞评论收藏

分享

2023-08-08 18:09

齐鲁工业大学

题解 | #迷宫#

题目大意： 从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的距离sk，k到e的距离ke。比较se和sk+ke的大小取较小者即为答案。显然计算se，sk，ke的时候要注意se不能经过d，sk也不能经过d，只有ke可以经过d。bfs函数的参数是两个点(x1,y1)和(x2,y2)。当(x1,y1)是点s的时候不能经过d。 #include<bits/stdc...

0 点赞评论收藏

分享

2023-08-06 02:27

已编辑

齐鲁工业大学

题解 | #Parity game#

题目链接：https://ac.nowcoder.com/acm/problem/51097 知识点： 并查集，维护每个节点到根节点的距离 题目描述： 一段长为n的由0和1组成的序列，依次给出q个回答，每个回答包括该序列的一个片段子序列的起点位置x，终点位置y，和该子序列【x，y】内有奇数个1还是偶数个1。问一段序列最多能满足前几个回答。 输入描述： 第一行输入n表示序列长度，第二行输入q表示有q个回答。接下来q行，每行包括2个数字（表示子序列的起点和终点）和一个字符串，表示该子序列有奇数个1还是偶数个1，even表示有偶数个1，odd表示有奇数个1 输出描述： 输出一个数字，表示一段序列最多...

0 点赞评论收藏

分享

2023-08-05 17:57

齐鲁工业大学

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

借鉴了别人的题解加上自己的理解 1、只有两座监狱，所以两个罪犯要么在同一个监狱要么在不同监狱 2、将影响力从大到小排序，从大到小枚举每个冲突，尽可能的让冲突避免（即将两个人分到不同监狱），直到出现无法避免冲突的情况，因为已经将冲突由大到小排序，之后的冲突都比这个冲突小，所以该冲突就是答案要求的。 3、模拟：按冲突从大到小枚举，假如a和b会产生冲突，为了避免a和b发生冲突，将a和b分到两个不同监狱去。继续枚举，发现a和c会产生冲突，为了避免a和c的冲突，你很自然的会把a和c放到不同监狱里。此时必然有b和c在同一个监狱。如果继续枚举发现b和c会发生冲突，而之前为了避免更大的冲突发生，b和c已经放进...

0 点赞评论收藏

分享

2023-08-05 15:17

齐鲁工业大学

题解 | #叠积木#

一、把每堆积木看作一个集合，最下方的积木是集合的根节点 二、只需要维护集合中每个元素到根节点的距离d[x](这题和食物链那题基本相同） 三、还需要维护每个集合中元素的数量s[x]，目的是为了方便后面维护d[x] 四、find(x)函数返回x的祖宗节点，同时更新从x节点到祖宗节点路径上所有的节点d[x] 五、将a集合加入到b集合要做3件事 1、a节点的祖宗节点指向b，p[a]=b 2、更新d[a]，d[a]表示a到祖宗节点b的距离，所以d[a]等于原来b集合中元素的数量，即d[a]=s[b] 3、更新b集合内元素的数量s[b]，a集合加到b集合内之后,b集合元素总数量要加上s[a] #inclu...

0 点赞评论收藏

分享

2023-08-05 11:28

齐鲁工业大学

题解 | #Let'sPlayCurling#

1、a[N]保存所有红色石头的位置，用b[N]保存所有蓝色石头的位置 2、对a[N]和b[N]都进行sort排序 3、遍历每两个相邻蓝色石头之间有多少个红色石块，最多的那个即为答案 4、需要注意的是第一个蓝色石头之前的所有红色石块也可以是答案，最后一块蓝队石头之后的红色石头也可以是答案 #include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+10; int n,m,res,T; int a[N],b[N]; signed main() { cin>>T; whi...

0 点赞评论收藏

分享

2023-08-05 15:51

已编辑

齐鲁工业大学

题解 | #星球大战#

1、用x[i],y[i]存储i号基地的横纵坐标。用ans[i]记录i号战舰摧毁基地的数量 2、遍历m个战舰，每个战舰有两种类型 3、第一类可以纵向摧毁直线x=b,即坐标为(b,?)的所有基地。用mx[b]=i记录(b,?)被i号战舰纵向摧毁 4、第二类可以横向摧毁直线y=b,即坐标为(?,b)的所有基地。用my[b]=i记录(?,b)被i号战舰横向摧毁 5、遍历每个基地i，一些基地即被某个战舰横向摧毁又被另外一个战舰纵向摧毁，有些基地只被摧毁一次 6、对于一个基地（x[i],y[i]），若my[y[i]]=0且mx[x[i]]!=0，则该基地只被纵向摧毁。mx[[x[i]]=k，则k号战舰摧毁...

0 点赞评论收藏

分享

2023-08-04 17:20

齐鲁工业大学

题解 | #[JSOI2010]缓存交换#

普通版： #include <bits/stdc++.h> using namespace std; int n, m; map<int,int> mp;//用于负责构造nexti[i]数组 bool boo[100050];//表示Cache中的内存。boo[2]=1表示a[2]在Cache中 int nexti[100050];//nexti[1]=3表示a[1]接下来最近的与a[1]相同的是a[3] int ar[100050]; priority_queue<int> q;//储存最近的与Cache中的元素相同的元素的下标 //boo中有多少个元素等...

0 点赞评论收藏

分享

2023-07-17 11:09

已编辑

齐鲁工业大学

题解 | #[USACO 2010 Feb S]Chocolate Eating#

1、显然最小幸福度范围是0~5e10，二分找出满足check(int x)条件的最大x即可。 2、check(int x)函数，用sum表示当天的幸福度，遍历每一天，确保每一天的幸福度都达到x即可 3、如果sum<x则表明当天幸福度不够，需要吃掉一个巧克力，sum+=h[i]直到sum>=x 4、每吃掉一个巧克力h[idx]，用a[idx]记录下第idx块巧克力在第几天被吃掉 5、如果顺利遍历完所有天数，则return true 6、如果巧克力已经吃光了，但是还有天数不满足sum>=x，则return false #include<bits/stdc++.h> #...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务