pamhip level
获赞
133
粉丝
13
关注
14
看过 TA
237
男
华南理工大学
2023
C++
IP属地：美国
暂未填写个人简介
私信
关注
发布(148) 评论 刷题 收藏
2020-05-01 14:42
已编辑
华南理工大学 C++
CF1342D Multiple Testcases（构造题）
题意 有      n    n   n 个数      {    a   i    }    \{a_i\}   {ai​}，每个       a   i    ≤   k    a_i\leq k   ai​≤k 。 每个背包大于等于      i    i   i 的数的个数不能超过       c   i    (   i   =   1   ,   2   ,   .   .   ,   k   )    c_i(i=1,2,..,k)   ci​(i=1,2,..,k)。 问最少要多少个背包才能放所有数，并且输出每个背包中的数。      n   ,   k   ≤   20000...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:42
华南理工大学 C++
CF1342E Placing Rooks（第二类斯特林数）
题意  有      n   ∗   n    n*n   n∗n 的棋盘，有      n    n   n 个车，放置      n    n   n 个车使之满足下面条件：  每个格子都被攻击到 恰好有      k    k   k 个车互相攻击  求方案数，对      998244353    998244353   998244353 取模。      n   ,   k   ≤   200000    n,k\leq 200000   n,k≤200000 分析 看了题解和听了学长讲解，觉得这题没那么难，可是比赛时就是没想到啊，果然还是实力不够啊！ 因为每个格子都被攻击到，所以...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-05-01 14:42
已编辑
华南理工大学 C++
exBSGS算法学习笔记
BSGS算法(北上广深算法 用于求解       a   x    ≡   b  <mtext>   </mtext>  (   m   o   d  <mtext>   </mtext>  p   )    a^x\equiv b~(mod~p)   ax≡b (mod p) 的非负整数解      x    x   x，其中      (   a   ,   p   )   =   1    (a,p)=1   (a,p)=1。 算法过程 令      x   =   A   ⌈    p    ⌉   −   B    x=A\lceil\...
各种题解及学习笔记~
0 点赞 评论 收藏
分享
2020-04-23 19:28
华南理工大学 C++
NC14301 K-th Number(二分+尺取）
题意 有T组数据。每组数据给定长度为 的数组 ，对所有长度大于等于 的连续子段，取出其第 大放入数组 中。求数组 的第 大。 分析 先吐槽一下，第 大表意真的不明啊！！这题简直是套路套路套路题。前几天刚做过类似的。。。考虑二分答案然后检查可行性。（没做过的话真难想啊！！我们不妨设 ，看看满足这个条件的情况是什么。其实就是数组大于等于 的至少有 个。现在我们就要求 数组大于等于 的数有多少个，即有多少个区间的第 大大于等于 。然后我们让：   时，  时，  记 为 的前缀和。当区间 的和大于等于 时，说明这个区间有至少个大于等于 的数，那么这个区间的第 大一定大于等于 。因此，假设 为右端点，...
每日一题
0 点赞 评论 收藏
分享
2020-04-23 11:54
已编辑
华南理工大学 C++
NC17065 子序列（简单dp）
题意 小美有一个由n个元素组成的序列{a1,a2,a3,...,an}，她想知道其中有多少个子序列(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,..., < pm ≤ n)，满足对于所有的i,j(1 ≤ i < j ≤ m), 成立。 分析 ，我们同时取对数，就有： 移一下项，可以得到： 于是子序列满足的条件相当于 单调增。那这个问题就很简单了啊。。设 表示以 结尾的子序列个数。那么 最后 还要加上 ，因为一个数本身可以作为子序列。那么 即可。 代码如下 #include <bits/stdc++.h> #define N 105 using namespac...
每日一题
0 点赞 评论 收藏
分享
2020-04-23 11:25
华南理工大学 C++
NC14583 糖糖别胡说，我真的不是签到题目(前缀和）
题意 从前，有n只萌萌的糖糖，他们分成了两组一起玩游戏。他们会排成一排，第i只糖糖会随机得到一个能力值bi。从第i秒的时候，第i只糖糖就可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的糖糖。 为了使游戏更加有趣，糖糖的爸爸，娇姐，会发功m次，第i次发功的时间为ci，则在第ci秒结束后，b1,b2,.....,bci都会增加1. 现在，娇姐想知道在第n秒后，会有多少只糖糖存活下来。 分析 考虑第 只糖糖能杀死多少只糖糖不太好想，那我们来看第 只糖糖会不会被杀死。我们记 为第 只糖糖在第 秒的时候的能力值增量， 为 的前缀和。假设第 只糖糖会在第 秒被杀死，即是被第 只糖糖杀死，那么需满...
每日一题
0 点赞 评论 收藏
分享
2020-04-16 19:54
华南理工大学 C++
NC51180 Accumulation Degree
题意 给定一颗 个点 条边的树，每条边有一个最大流量 。选择一个点为根，使得根到叶子节点的流量和最大，求最大值。（一条路径的流量指叶子节点到根节点的边权最小值） 分析 先以 号点为根节点，那么很容易得到从一个点出发的流量（是儿子节点）： 接下来考虑不以 为根。设 表示以 为根的流量和。那么考虑从 到 的转移。让我们从这个图看看以 为根时， 的流量来源。首先是 ，就是一开始求的。然后还有红色箭头标出来的部分，流经 这条边，流量其实就是。现在我们要知道，红色部分怎么得到。从这个图可以看到，红色部分其实就是用 减去 。从上面的推理，那么我们可以得到：最后 即可。 代码如下 #include <...
每日一题
0 点赞 评论 收藏
分享
2020-04-16 18:28
华南理工大学 C++
NC23049 华华给月月准备礼物
题意 二月中旬虐狗节前夕，华华决定给月月准备一份礼物。为了搭建礼物的底座，华华需要若干根同样长的木棍。华华手头上有一些长度参差不齐的木棍，他想将每根都裁剪成若干段自己想要的长度，并丢掉多余的部分。因为华华的手很巧，所以他的裁剪过程不会有任何的失误。也就是说，对于一根长度为N的木棍，华华可以精准的将它们裁剪为若干段木棍，使它们的长度之和为N。华华不知道裁剪成多长比较好，所以干脆越长越好。不过由于华华有点强迫症，所以他希望长度为非负整数。保证所有木棍的原长也是非负整数。那么请问华华最终得到的每根木棍多长呢？ 分析 答案具有单调性，考虑二分答案然后检查可行性。假设长度为 。检查可行性的话，只需要看 ...
每日一题
0 点赞 评论 收藏
分享
2020-04-16 14:37
华南理工大学 C++
NC14247 Xorto
题意 给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。 分析 对于一个区间 ，我们统计 前面的区间中，和 前缀异或和相等的有多少即可。我们用一个桶记录异或和出现多少次。这样，枚举 ，对于一个 ，枚举小于等于 的 ，将 的异或和加入桶中。然后枚举大于 的 ，统计 的异或和出现多少次。加起来就是答案了。要得到 的异或和，只需要将 的异或和异或上 的异或和即可，所以要预处理一下前缀异或和。 代码如下 #include <bits/stdc++.h> #include<ext/pb_ds/hash_policy.hpp> #includ...
每日一题
0 点赞 评论 收藏
分享
2020-04-16 12:14
已编辑
华南理工大学 C++
NC13229 二分图染色(弱化版) （组合数学+容斥）
题意 给一个 个点的完全二分图（即有 条边），每条边可以染红色，蓝色，绿色。一个点不能连出超过一条红色边，也不能连出超过一条蓝色边。问将这些边染色的方案数有多少种，答案对 取模。() 分析 给这题跪了！我还是太菜了。完全二分图可以转化为一个 的矩阵，第 行第 列的点表示左边第 个点和右边第 个点。如果我们把染绿色看成不染色，这样子，问题可以转化为： 的矩阵，每个点可以染红色或蓝色，每一行每一列最多有一个红色，每一行每一列最多有一个蓝色。求涂色方案数。同时有两种颜色很烦，要是能只考虑一种颜色就好了！我们不妨看看两种颜色的方案能不能由一种颜色的推过来。设 表示只有红色的方案数， 表示有红有蓝的方案...
每日一题
0 点赞 评论 收藏
分享
2020-04-09 22:55
已编辑
华南理工大学 C++
NC24870 Video Game Troubles
题目难度 中等 推荐理由 考验对背包问题的理解 题目知识点 分组背包，0/1背包 题意 农夫约翰有预算 ,有 台游戏机，每台游戏机价格为 。每台游戏机有个独立游戏，只有买了这台游戏机才能玩对应的游戏，每个游戏价格为 ，玩了之后奶牛产量增加 。问应该买哪些游戏机和游戏，使得奶牛产量最大，求最大产量。其中，。 解题思路 第一反应：这不是 NOIP2006金明的预算方案 吗？那么这就是一个简单的分组背包问题！！！！关于分组背包，我这里简要说说。分组背包是这样一种题：有容量为 的背包，有 个组，每个组有 个组合，每个组合重量为 ,价值为 ，每个组只能选一个组合，求最大价值和。其实每个组是独立的，所以我...
每日一题
0 点赞 评论 收藏
分享
2020-04-08 20:00
华南理工大学 C++
NC13249 黑白树
题意 一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 分析 首先呢，涂色肯定是从叶子节点开始涂的，因为没有其他节点可以使叶子节点涂色，如图。现在我们已经将叶子节点涂色了，要开始涂红色箭头指的点，记为 。那么，这次我们是使 到 往上 个点都涂色吗？其实，这样答案并不一定是最优的。可能...
每日一题
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客网在线编程
牛客网题解
牛客企业服务