平凡的小白 level
获赞
486
粉丝
17
关注
14
看过 TA
27
男
咖喱炖小学
2023
行政专员/助理
IP属地：江西
虽然中奖机会小，还是再想中一次
私信
关注
发布(113) 刷题
头像
平凡的小白
2020-05-05 11:53
已编辑
行政专员/助理
【每日一题】Removeal
戳我传送 题意： 题目描述：Bobo有整数s1，s2，...，sn，其中1 ≤ si ≤ k。删除m个后问有多少种序列,然后对（1e9 + 7）取模。 输入描述： 输入包含多个测试用例，并以文件结尾终止。 每个测试用例的第一行包含三个整数n，m和k。 第二行包含n个整数s1，s2，...，sn。输出描述： 对于每个测试用例，请打印一个表示结果的整数。 思路： 计数类dp。 表示前i个数字删掉j个元素的序列数。如果不考虑重复，状态转移方程就是 ， 表示取第i个数， 表示不取第i个数。看数据就知道大部分案例一定会有很多重复的数字，接下来考虑重复的情况：……1，4，7，8，5，11.这一段删除...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-04 16:16
已编辑
行政专员/助理
【每日一题】换个角度思考
戳我传送题意：思路：离线+值域树状数组，保存每个点和每次询问的编号，每个点按照值的大小升序排序，每次询问按照k值大小升序排序。原理：1.处理k1的答案时（k最小的询问），树状数组中小于k1的位置都会被1标记，k1的答案就是树状数组 [l,r] 中1的个数。2.处理k2时（k2>=k1），之前被1标记的位置的数都是小于等于k2的，不需要从头标记，只要继续找还有没有小于等于k2的数，标记它的位置就可以了。3.后面每次询问重复1、2步骤，最多只要标记n个点。4.每个点升序排序方便找小于等于k的数。5.复杂度 。Code： #include <iostream> #include &...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-04 13:11
行政专员/助理
【每日一题】Rinne Loves Edges
戳我传送题意：这个题意是关键，首先n个点n-1条无向边边，接触过树的同学应该都知道这是一颗树，而度就是与这个点相连的边的数量，度为1就是叶子结点了，现在问题就变成了：在以S为根的树上删掉权值之和尽量小的一些边使得根和每一个叶子节点都不连通。思路：这是一个典型的树型dp，而树型dp本质上可以说是个搜索——遍历这棵树，在返回的时候维护相关的值。不管是写dp还是写搜索其实都是要分析原问题和子问题分别是什么的，我们要分析的大问题就是使s和所有的叶子都不联通的最小代价是多少，小问题就是s的儿子和子树上的叶子都不联通的最小代价是多少。因为s可以选择断掉和儿子的边，或者让儿子与子树的叶子结点不连通，所以转移...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-03 23:33
行政专员/助理
【每日一题】城市网络
戳我传送题意：给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询（此时v是u的父亲），问你从u->v的最长上升子序列长度。思路：倍增+dfs题目表明v一定在u去网1的最短路径上，如果从u一直往上走到v，再去判断到达的每一个城市，需不需要购买。这种算法的极端情况，形成了一条长为n的链，时间复杂度达到了O(nq)，后面数据加强就会超时了。正确的做法是用倍增，f[i][k]表示i结点的第 个比i大的父亲的位置（是那个结点），这个理解清楚看代码得看半天。不难得出状态转移方程f[i][k]=f[...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-03 00:25
行政专员/助理
【每日一题】3月27日数学考试
戳我传送 题意： 思路 求两个不连续的区间的最大和，很容易想到前缀和，[l,r]的区间和是sum[r]-sum[l-1]。朴素方法一个指针枚举左区间的起点，另一个指针枚举右区间的起点，两层循环复杂度 （n^2）,应该会超时。枚举右区间的起点时，可以发现左区间的起点不需要从1开始找，此时的最优解一定是左区间最大，而此时右区间左边全部的左区间已经出现过了，只要一直保存最大的左区间起点，在枚举右区间的起点时就可以 （1）的找到最优左区间起点。总复杂度 （n）。 Code； #include<bits/stdc++.h> #define ll long long using...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-02 22:56
已编辑
行政专员/助理
【每日一题】3月30日滑动窗口
戳我传送 题意： 给一个长度为N的数组，一个长为K的滑动窗体从最左端移至最右端，你只能看到窗口中的K个数，每次窗体向右移动一位，你的任务是找出窗体在各个位置时的最大值和最小值。思路：就和邓老师说的那样，每次滑动一个区间，区间从[l,r]到[l+1,r+1]，只是增加了a[r+1]减少了a[l]，所以完全没有必要重新扫一遍区间。以最大值为例：1.将新进入区间的这个元素往双端队列里放，但放进来之前需要判断队尾（也就是还有可能成为最大值的最后一个元素）是不是小于他小于他，如果是，就把这个队尾删掉（r- -），一直到前一个元素大于等于它为止。这样得出来的队列实际是单调递减的。2.可以输出时先判断队...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-02 18:24
已编辑
行政专员/助理
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-29 09:31
已编辑
行政专员/助理
牛客算法周周练4
闲话A、B看了这位大佬的博客看懂的 传送门，B题我想化简，结果出了问题求助这位大佬，然后同学发现我多算了一个 ，大佬也很快发现了，我自己找了半天，QAQ。戳我传送 [SDOI2016]齿轮 题意： n个齿轮m条链，链上两点u、v的转述比为x：y，若不同链条的传动比不相容，则有些齿轮无法转动，就输出no，反之yes。思路： 若不同链条的传动比不相容，则有些齿轮无法转动，意思是确定一个点后沿着链，根据题目输入的转速比确定其它点，当形成环时，会再次推到起点，若有矛盾就是不相容。真的题意后，就会想到以前的每日一题边的染色 （我的博客）和它的思路非常相似。1.链式向前星存图。2.对于任一连通块，...
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-04-28 15:00
行政专员/助理
【每日一题】边的染色
戳我传送 思路： 1.链式向前星存图后，dfs跑一遍判读是否自身矛盾。2.dfs再跑一遍，对每个联通块的元素个数sum-1求和k。3.dfs再跑一遍，对每个涂了颜色的边组成的连通块的元素个数sum-1求和，再用k减去总和，ans=2^k。 原理 1.边的值可以看作两个端点的异或值。2.对每个涂了颜色的边组成的连通块，假设一个点为1，其余的点的值也随之确定了。比如1-3边的值为1，3-2边的值为0，如果给1取1，那么可以得到3=0，2=0。（这个联通快如果不是环，就不会自身矛盾，如果是环才有可能自身矛盾）如果又涂回到了起点（即这个连通块是圆），如果颜色和原来的一致就不矛盾，如果此时应该涂...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-04-23 17:34
已编辑
行政专员/助理
【每日一题】子序列
戳我传送 思路： 传送门看这位大佬的题解看懂了，太秀了。子序列首先我们会想到动态规划，状态dp[i]表示以a[i]结尾符合条件的子序列个数。状态转移方程不难写出是dp[i]=1+ 。建议仔细看清楚a的上下标，a[i]的上标是j，a[i]的下标是i，如果像我一样没看清楚的话，真不知道题目在说什么。接着是判断 是不是成立，比较常用的是做差法和做商法，当遇到最差的情况100^100显然做差法是不现实的，会直接溢出，取余也不行，可以考虑做商法，K= ，（假设 ），如果如果y>=x， 一定不成立，接着就是考虑y<x的时候，y/x<1可以先求出y/x的幂然后乘y到K>1结束，...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-09-03 18:37
已编辑
行政专员/助理
【每日一题】K-th Number
中文题意这个大佬博客有翻译 戳我。 思路： 如果遍历每一个大于等于k的区间找第k大的数，复杂度不敢想， （n^2）级别。所以这时候就要用到尺取法了，专栏的办法太秀了。其实我们不在乎第m大的数以外是什么，只要知道第m大的数是什么，所以我们可以二分答案把求值变成验证，再用尺取法找到符合要求的区间数。原理：1.居然是找B中第m大的数，那么B中有至少有m个数且至少有m个数大于等于第m大的数。2.（m个数大于等于第m大的数），这m个数都是A中区间第k大数，也就是第K大数大于B中第m大的数的区间至少有m个。3.第k大的数大于B中第m大的数的区间，说明区间至少有k个数大于等于k，找到一个符合要求的区间，...
每日一题
0 点赞 评论 收藏
转发
头像
平凡的小白
2020-05-29 09:12
已编辑
行政专员/助理
糖糖别胡说，我真的不是签到题目
戳我传送题意：n个糖糖排成一排，每个糖糖有一个能力值，第i秒第i个糖糖就会杀死前面能力比他小的人，进行m次区间加的操作，每次输入ci，表示第ci秒1~ci的糖糖能力值加一，输出最后有多少糖糖存活。 思路： 前m次操作可以用前缀和模拟区间加，得到每个糖糖的新能力值后从后往前维护每个队伍的最大值，当前糖糖的能力值如果大于后面敌对队伍糖糖的最大值，也就是比后面的糖糖都强，那么他存活，反之白给。复杂度 (n)。如果从前往后判断第i糖糖能不能存活，还要搜索后面i-1个糖糖，复杂度 (n^2)。刚开始没看懂题目看大佬博客，整了一个后缀和，一下愣是没看懂，看了2个多小时才看懂，你信？，大佬还提到扩展到n个队...
每日一题
0 点赞 评论 收藏
转发
工具箱
牛客网
牛客企业服务