wlj_ss - 个人主页动态 - 牛客网

发布(88) 刷题

2019-10-31 07:56

已编辑

C++

洛谷10月月赛 III 【小C与桌游】

贪心 该问题可以分为两个子问题： 1.求一种拓扑顺序使点的编号最大值的更新次数最多。 2.求一种拓扑顺序使点的编号最大值的更新次数最少。 对于第一个子问题，我们贪心的想，每次走到所有能走的点中编号最小的点。这种贪心显然是正确的，因为如果我们先走编号较大的点，再走编号较小的点，显然不如先走编号较小的点更优一些。所以我们将原先拓扑排序中的普通队列换成维护最小值的优先队列即可。 priority_queue<int, vector<int>, greater<int> >Q; for (int i = 1; i <= n; ++i) ...

0 点赞评论收藏

转发

2019-10-25 20:48

C++

在牛客打卡24天，今天也很努力鸭！

0 点赞评论收藏

转发

2020-01-19 09:24

已编辑

C++

洛谷10月月赛 II & X Round 4 Div.1 【XR-4】题

数学推式子 先膜拜一下考场上直接切掉的燃情巨佬。 首先分析一下部分分。（蒟蒻并没有分析出\(b=0\)的解法） 对于\(a=b\)的情况，只要满足\(x=y\)即可，所以一共有\(inf\)组解。 对于\(a\le 1000\)的情况，我们直接暴力判断一下即可。 对于\(a=0\)的情况，我们需要求\(y^2 - x^2=b\),就是\((y-x)\times(y+x)=b\),发现这两项都是\(b\)的约数，所以我们\(\sqrt n\)枚举一下\(b\)的约数，若是要有正整数解，就需要\(b- \frac{b}{i}\)是偶数（想一想，为什么）,累加一下答案即可。 void s...

0 点赞评论收藏

转发

2019-10-31 07:55

已编辑

C++

洛谷10月月赛 II & X Round 4 Div.1 【XR-4】题

数学推式子 先膜拜一下考场上直接切掉的燃情巨佬。 首先分析一下部分分。（蒟蒻并没有分析出\(b=0\)的解法） 对于\(a=b\)的情况，只要满足\(x=y\)即可，所以一共有\(inf\)组解。 对于\(a\le 1000\)的情况，我们直接暴力判断一下即可。 对于\(a=0\)的情况，我们需要求\(y^2 - x^2=b\),就是\((y-x)\times(y+x)=b\),发现这两项都是\(b\)的约数，所以我们\(\sqrt n\)枚举一下\(b\)的约数，若是要有正整数解，就需要\(b- \frac{b}{i}\)是偶数（想一想，为什么）,累加一下答案即可。 void s...

0 点赞评论收藏

转发

2020-01-19 09:24

已编辑

C++

NOI.AC CSP-S全国模拟赛第四场子段与子段

题目描述 对于一个序列a1,a2,…,an，子段是指它的一个连续部分，即al,al+1,…,ar 容易发现，一个长度为n的序列有$\frac{n(n+1)}{2} $ 个子段。例如序列3,7,4有下列子段： (3),(3,7),(3,7,4),(7),(7,4),(4) Mia希望分别求出这些子段的异或和，再将它们异或起来。但是Cierra觉得这太简单了，所以她提出了q个询问，每次给出一个区间[L,R]，希望你将这个下标区间对应的子段截取出来，回答上面的询问。 具体来说，对询问[L,R]，你需要回答aL,aL+1,…,aR的所有子段异或和的异或和。 输入格式 第一行包含两个用空格隔...

0 点赞评论收藏

转发

2019-10-31 07:55

已编辑

C++

NOI.AC CSP-S全国模拟赛第四场子段与子段

题目描述 对于一个序列a1,a2,…,an，子段是指它的一个连续部分，即al,al+1,…,ar 容易发现，一个长度为n的序列有$\frac{n(n+1)}{2} $ 个子段。例如序列3,7,4有下列子段： (3),(3,7),(3,7,4),(7),(7,4),(4) Mia希望分别求出这些子段的异或和，再将它们异或起来。但是Cierra觉得这太简单了，所以她提出了q个询问，每次给出一个区间[L,R]，希望你将这个下标区间对应的子段截取出来，回答上面的询问。 具体来说，对询问[L,R]，你需要回答aL,aL+1,…,aR的所有子段异或和的异或和。 输入格式 第一行包含两个用空格隔...

0 点赞评论收藏

转发

2020-01-19 09:25

已编辑

C++

洛谷10月月赛 P5587 【打字练习】

模拟 题意很清晰，需要我们模拟一下计算正确的单词的个数。对于"<"我们退格处理。正解好像需要用类似栈的数据结构来维护，但并不卡常，直接模拟也可以。 说一下几个注意事项： 1.范文里面有"<",并不是我们需要打上"<",而是删除范文里的内容。（详见代码） 2.对于一整行并且还有空格的输入，我们不能用cin和scanf，因为它们不能读取空格，我们需要用getline 来读取一整行，就像下面这样： while (getline(cin, a[++n])) { ...... } 3.范文和输入的行数可能...

0 点赞评论收藏

转发

2019-10-31 07:55

已编辑

C++

洛谷10月月赛 P5587 【打字练习】

模拟 题意很清晰，需要我们模拟一下计算正确的单词的个数。对于"<"我们退格处理。正解好像需要用类似栈的数据结构来维护，但并不卡常，直接模拟也可以。 说一下几个注意事项： 1.范文里面有"<",并不是我们需要打上"<",而是删除范文里的内容。（详见代码） 2.对于一整行并且还有空格的输入，我们不能用cin和scanf，因为它们不能读取空格，我们需要用getline 来读取一整行，就像下面这样： while (getline(cin, a[++n])) { ...... } 3.范文和输入的行数可能...

0 点赞评论收藏

转发

2019-10-12 16:55

C++

区间异或和异或区间最大值异或区间最小值题解

单调栈&可持久化0/1trie树 更好的阅读体验 题目链接 题目描述 小w学会了RMQ算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值。在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和。现在你给了他一个长度大小为n的数组，为了考察小w写RMQ以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为xorsum，记该子区间的最大值为max，记该子区间的最小值为min，你要求使得xorsum⊕max⊕min最大。其中⊕为位运算异或操作。 输入描述: 第一行输入一个正整数n，表示数组的长度。接下来一行n个非负整数a[i]表示数组中的...

0 点赞评论收藏

转发

2020-01-19 09:25

已编辑

C++

牛客OI月赛12-提高组区间异或和异或区间最大值异或区间最小值题解

单调栈&可持久化0/1trie树 题目链接 题目描述 小w学会了RMQ算法，他现在可以求出一个给定数组某一段子区间的最大值，最小值。 在这之前，他也学会了前缀和，并且他知道前缀和可以扩展到位运算求出区间异或和。 现在你给了他一个长度大小为n的数组，为了考察小w写RMQ以及前缀异或和的正确性，你要求他求出该数组的某一个子区间，记该子区间的异或和为xorsum，记该子区间的最大值为max，记该子区间的最小值为min，你要求使得xorsum⊕max⊕min最大。其中⊕为位运算异或操作。 输入描述: 第一行输入一个正整数n，表示数组的长度。 接下来一行n个非负整数a[i]表示数组中的...

0 点赞评论收藏

转发

2020-01-19 09:22

已编辑

C++

\(CSP-S\)前膜拜大佬RP++ Think twice, code once. 血的教训：样例解释不可信 杜教筛 数字帝国 珂朵莉树指南 珂朵莉树详解 min_25筛详解 生成函数初步 斯特林数及斯特林反演 生成函数进阶与简单的图计数 狄利克雷卷积与莫比乌斯反演 NTT(快速数论变换)用到的各种素数及原根 快速傅里叶变换入门 快速数论变换入门 多项式总结 FFT&NTT 图论画板 洛谷最高楼 图床生成器 超多模板集合 点击获得随机图片 B站学习视频1 B站学习视频2

0 点赞评论收藏

转发

2019-10-31 07:54

已编辑

C++

\(CSP-S\)前膜拜大佬RP++ Think twice, code once. 血的教训：样例解释不可信 \(\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad{\colorbox{white}{\large{\scriptsize\texttt{wljss}}}}\) 杜教筛...

0 点赞评论收藏

转发

2019-09-29 20:41

C++

在牛客打卡23天，今天也很努力鸭！

0 点赞评论收藏

转发

2020-01-19 09:25

已编辑

C++

AT2060 【Minimum Sum】

单调栈 这是某次olinr巨佬给我们出的考试题。首先暴力\(O(n^2)\)是不能过的(废话)，我们考虑每一个数值对答案的贡献，也就是ta能当最小值的序列个数。 倘若ta能成为最小值，那么也就是在这个数列里没有比ta大的数值，这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这完全珂以用单调栈来完成，每次栈顶的元素被弹出的值的位置就是我们所求的被弹的元素的右边第一个比ta小的值的位置。当前元素不在弹出栈顶元素的时候，我们就求出了当前的元素的左边第一个比ta小的值的位置。因为每一个数值仅仅进了一次栈，所以时间复杂度是\(O(n)\).(不要脸的搬了自己的另一...

0 点赞评论收藏

转发

2019-10-31 07:55

已编辑

C++

AT2060 【Minimum Sum】

单调栈 这是某次olinr巨佬给我们出的考试题。首先暴力\(O(n^2)\)是不能过的(废话)，我们考虑每一个数值对答案的贡献，也就是ta能当最小值的序列个数。 倘若ta能成为最小值，那么也就是在这个数列里没有比ta大的数值，这也就转化为了求出右边第一个比ta小的值的位置和左边第一个比ta小的值的位置的问题。这完全珂以用单调栈来完成，每次栈顶的元素被弹出的值的位置就是我们所求的被弹的元素的右边第一个比ta小的值的位置。当前元素不在弹出栈顶元素的时候，我们就求出了当前的元素的左边第一个比ta小的值的位置。因为每一个数值仅仅进了一次栈，所以时间复杂度是\(O(n)\).(不要脸的搬了自己的另一...

0 点赞评论收藏

转发

工具箱

TA的圈子

TA的笔记

牛客网
牛客企业服务