秃头小白 - 个人主页动态 - 牛客网

发布(208) 评论刷题收藏

2020-10-03 21:35

青岛大学运营

题目连接 https://ac.nowcoder.com/acm/contest/5881/D 解题思路 一开始我随便举了几个例子，感觉像是数学题，应该有数学公式，所以就手工画了个表，结果还真就神了，表格关于对角线对称。乍一看数值1，6，10……，想到会不会和组合数有关，比划了比划，还真就扯出关系了。 l\x 1 2 3 4 5 1 1 1 1 1 1 2 1 2 3 4 5 3 1 3 6 10 15 4 1 4 10 20 35 5 1 5 15 35 70 l和x自减后： l\x 0 1 2 3 4 0 1 1 1 1 1 1 1 2 3 4 5 2 1 3 6 10 15 3 1 4 ...

0 点赞评论收藏

分享

2020-10-03 15:47

青岛大学运营

题目连接 https://ac.nowcoder.com/acm/contest/7226/C  解题思路 我吐了。思路明确：S1：输入S2：遍历，把能达到的点（宝藏）的值保存下来S3：对保存下来的值进行去重操作S4：尺取法，维护最大值与最小值的差保持最小S5：判断输出条件并输出 有一点需要注意：遍历统计宝藏值的时候要用bfs。用一般的dfs是没办法访问到能到达的全部位置的，因为dfs中存在步数的特判，所以有些样例是没法遍历全部位置的，也就是没法统计全部的宝藏。而bfs总是通过最短路径访问每个位置，所以只要是能达到的位置，一定能通过最短路径的方式访问到。这只针对一般的dfs，通过其他方式维护一...

0 点赞评论收藏

分享

2020-10-03 15:37

青岛大学运营

题目连接 https://ac.nowcoder.com/acm/contest/7226/B 解题思路 先统计下所有珠子。二维遍历左端点和右端点，遍历右端点的时候判断统计不同颜色珠子的个数，每遍历到一个右端点ans就加上不同的珠子数，遍历左端点时cnt置零。cnt数组的生存周期与每个左端点是相同的，cnt[i]表示此时左端点开始的区间颜色为i的珠子的个数，只要统计过这个颜色，就不再让w+1了。不是特别好讲，希望你能理解什么意思。这个方法在统计一段内不同种类有多少比较好用。 AC代码 #include<bits/stdc++.h> using namespace std; int ...

0 点赞评论收藏

分享

2020-10-03 15:26

已编辑

青岛大学运营

Wireless Network

题目连接 https://vjudge.net/contest/397891#problem/B密码：20201002 解题思路 并查集，半个板子题。并查集讲解区别在于，本题并非一条边一条边的join的，而是每次插入一个点，让插入的这个点和已经插入的所有距离满足条件的点join，不满足的只标记插入，但是不进行join。对于修理电脑操作而言如上。对于询问两台电脑是否相连，本质上是判断二者是否连通，即根是否相同且必须二者已经插入（其实只要根相同必然是插入的，可以不用判断flag，不过我没试）。 AC代码 #include<iostream> #include<cmath> ...

0 点赞评论收藏

分享

2020-10-01 18:53

青岛大学运营

题目链接 https://ac.nowcoder.com/acm/contest/7509/D 解题思路 实现过程对于添加边的操作而言，如果两点之间有边，那么可以忽略本次加边操作；如果没边：——如果两点的度均为0，添加一条边之后，大小不为一的树的数量++，即ans++；——如果两点的度均不为0，说明两点都分别与两棵树相连，添加一条边之后，两树合并为一树，ans--；（因为可能存在重复的边，因此用set存边而不用vector）判断完毕之后，通过set的insert函数实现插入新边。对于删除边的操作而言，如果两点之间没边，那么可以忽略本次删边操作；如果有边：——如果两点的度均大于等于2，说明两点除...

0 点赞评论收藏

分享

2020-09-30 16:55

青岛大学运营

题目链接 https://ac.nowcoder.com/acm/contest/7509/B 解题思路 我的思路：pos记录属于puleyaknoi中字符的位置，pos_of_p_in_pos记录p在pos中的位置。从pos_of_p_in_pos数组的最后一个p开始往后找字符串，按顺序puleyaknoi中的字符，若能找全，刷新ans。大佬思路：核心是用v[i]表示puleyaknoi中所有第i个字符的位置，是从小到大排序的，因为是从小到大push的。枚举p的位置，作为区间左端点，字符串最右端作为右端点，check参数为i和二分的区间长度。长度可行刷新ans，同时缩短区间。 我的AC代码 ...

0 点赞评论收藏

分享

2020-09-29 19:48

青岛大学运营

题目链接 https://ac.nowcoder.com/acm/contest/7509/A 解题思路 也不能算纯暴力，也是考点思维的，我不会wtcl。基本思路：枚举区间左端点，枚举区间右端点，判断这个区间内存在多少个属于puleyaknoi中的字符（出现多次算一次统计，例如pppppak，遇到p，cnt+1，遇到a，cnt+1，遇到k，cnt+1，所以cnt=3），如果统计到了10个，也就是包含了puleyaknoi的所有字符，此时break，并更新一下ans，最后输出ans。 AC代码 #include<bits/stdc++.h> using namespace std; ...

0 点赞评论收藏

分享

2020-09-28 23:39

青岛大学运营

题目链接 https://ac.nowcoder.com/acm/problem/20270 解题思路 暴力枚举+dfs赋值枚举起点和终点，dis存起点到终点要推的箱子数；dis通过dfs更新 AC代码 #include<bits/stdc++.h> using namespace std; const int N=1000; int dir[4][2]={-1,0,1,0,0,-1,0,1}; int ans; int dis[N];//表示当前点到达i位置最少需要推多少箱子 int mp[N]; int n,m,t; string tmpstr[50]; void dfs(in...

0 点赞评论收藏

分享

2020-09-28 21:39

青岛大学运营

祝（原题来自计蒜客染色（简单））

题目链接 https://vjudge.net/contest/397650#problem/Ahttps://nanti.jisuanke.com/t/48301 解题思路 简单dp+简单贪心，甚至不能算贪心。S1：先用dp[i]存，在不算特殊区间的情况下，前i个位置染色的最大值；S2：对pos的all赋值，pos[i].all表示区间左端点为i的特殊区间全涂为自己特定颜色的情况下，此区间为不加额外美感情况下，涂为纯色的美观度；S3：比较每一段特殊区间涂为纯色的美观度和dp数组中此区间的美观度比较，若前者大，就把此区间换成纯色，反之不变。 AC代码 //题目：https://vjudge.n...

0 点赞评论收藏

分享

2020-09-28 16:56

青岛大学运营

题目链接 https://vjudge.net/contest/397323#problem/D 解题思路 最大值最小（或最小值最大），暂时我就知道两种方法一个是二分，一个是贪心。本题一看就可以二分，所以二分试了试，真行。稍微有点难度的就是如何去判断枚举到的这个距离到底能不能安排B个。我也卡了一会，因为一直不知道到底要不要一定选第一个，如果不一定选第一个，那么就要枚举第一个选取的石子的位置，这样一来时间复杂度明显太大；如果一定选第一个，那么就方便多了，只要从第一个开始，判断下一个是不是与它相距超过枚举的距离，超过就再从当前点往后判断，没超过就跳过当前点，判断当前点的下一个点是否满足条件。但是！...

0 点赞评论收藏

分享

2020-09-28 15:30

青岛大学运营

有关x^p的一些运算

包含求解x^p的高n位，低n位，总位数的方法。#大佬讲解 大佬讲解  模板代码 #include<bits/stdc++.h> #define ll long long using namespace std; int Low3(int,int);//x的p次方后三位 int High3(int,int);//x的p次方前三位 int Num(int,int);//x的p次方总位数 int main(){ int x=1234567,p=1234567; cout<<"x^p的低n位为："<<Low3(x,p)<<endl; ...

0 点赞评论收藏

分享

2020-09-27 21:34

已编辑

青岛大学运营

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2544 解题思路 Dijkstra算法典型例题讲解  AC代码 #include<bits/stdc++.h> #define pb push_back using namespace std; const int INF=0x3f3f3f3f; const int N=110; int n,m; struct edge{ int to,cost; }; vector<edge> G[N]; int dis[N]; typedef pair<int,int> P;...

0 点赞评论收藏

分享

2020-09-27 12:12

青岛大学运营

单词记忆方法

题目链接 https://ac.nowcoder.com/acm/contest/7412/C 解题思路 递归匹配呗，反正我不会！WTCL！WTCL！WTCL！！！请骂我！！！难就难在实现上，方法谁都懂，就是实现不出来！ AC代码1 我感觉代码1比代码2好理解，但是比代码2难自己实现。 #include<bits/stdc++.h> #define ll long long using namespace std; int i=0;//i要全局 string s; ll solve(){ ll res=0,a=0; for(;i<s.size();i++){ ll tmp=0...

小白月赛28题解或部分题...

0 点赞评论收藏

分享

2020-11-02 22:27

已编辑

青岛大学运营

大佬讲解线段树 https://blog.csdn.net/zearot/article/details/48299459 模板1题目链接  区间修改，区间查询 例题  AC代码 #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10; ll sum[N<<2]; int lazy[N<<2]; ll a[N]; void Getsum(ll pos){ sum[pos]=sum[pos<<1]+sum[pos<<1|1]...

0 点赞评论收藏

分享

2020-09-25 08:12

青岛大学运营

上学要迟到了

题目链接 https://ac.nowcoder.com/acm/contest/7412/H 解题思路 单源最短路径问题 Dijkstra算法 需要优先队列优化 这是我写的模板与讲解  问题转化 我们尝试这把这个题对应转化成单源最短路径问题。S1：每个车站就代表图中的每个点；S2：每种公交车能停车的地方就是单向可达的，就可以在图中表现为有向边。注意一点，我们要存的有向边并非每个车站到其后面所有能停车的车站的有向边，而是与之相邻的可停车站的有向边，比如1 2 2 1 2 1 1 2 1，对于第一个位置的1车而言，我们只需要将其与第四个位置的1车构建一条单向边即可，不需要与第六个位置的1车构建有...

小白月赛28题解或部分题...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

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