- 博客(596)
- 收藏
- 关注
RSS订阅
原创 换博客辣
由于csdncsdncsdn的界面以及广告不是很令这个菜鸡OIerOIerOIer喜欢，所以从2019.12.212019.12.212019.12.21开始，将不再在csdncsdncsdn更新博客，博客将转移到cnblogscnblogscnblogs上去。新的博客链接：Link: cnblogs\Large\texttt\color{red}\colorbox{lightblue...
2019-12-21 13:36:38
683
6
原创 二十世纪爱因斯坦逻辑难题 推理过程
首先先画出一个表格： 然后先找到指定线索。 8.住中间的人喝牛奶。 9.挪威人住在第一个房子里面。 然后根据 14.挪威人和住蓝房子的人相邻。 之后由于第四条“绿房子紧挨着白房子”可得绿房子和白房子一定在蓝房子右边（因为左边只有一个位置，不可能放下两个房子），又由于第一条“英国人住红色房子里”，而一号房子已经被挪威人住了，那么英国人的房子就不是一号房子，综上可得，一号房子...
2018-08-18 16:40:53
4255
8
原创 【洛谷P3480】KAM-Pebbles
题目题目链接：https://www.luogu.com.cn/problem/P3480有 nnn 堆石子，除了第一堆外，每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子，但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。Q≤10,n≤1000Q\leq 10,n\leq 1000Q≤10,n≤1000。思路阶梯博弈的板子是这样的：有 nnn 个阶梯，每一个阶梯上有若干石子，每次从一个阶梯上取若干式子，放到上一级阶梯上。到了 0
2021-03-22 16:59:19
280
原创 【CF739E】Gosha is hunting
题目题目链接：https://codeforces.com/problemset/problem/739/E你要抓神奇宝贝！现在一共有 NNN 只神奇宝贝。你有 aaa 个『宝贝球』和 bbb 个『超级球』。『宝贝球』抓到第 iii 只神奇宝贝的概率是 pip_ipi ，『超级球』抓到的概率则是 uiu_iui 。不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。请合理分配每个球抓谁，使得你抓到神奇宝
2021-03-22 16:34:05
323
原创 【洛谷P6046】纯粹容器
题目题目链接：https://www.luogu.com.cn/problem/P6046白王制造了 nnn 个容器，并将它们排成了一队，从左到右依次编号为 1∼n1 \sim n1∼n。第 iii 个容器的强度为 aia_iai，保证 aia_iai 互不相同。为了挑选出最纯粹的容器，白王会进行 n−1n-1n−1 轮操作，每轮操作中，他会等概率随机挑选两个 位置相邻 且 未被击倒的容器，令它们进行决斗，在一次决斗中，强度较小的容器将会被击倒并移出队列。显然最后留下的是强度最大的容器，但是，可怜
2021-03-20 13:58:24
536
原创 【洛谷P3631】方格染色
题目题目链接：https://www.luogu.com.cn/problem/P3631Sam 和他的妹妹 Sara 有一个包含 n×mn \times mn×m 个方格的表格。他们想要将其中的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个 2×22 \times 22×2 的方形区域都包含奇数个（ 111 个或 333 个）红色方格。例如，下面是一个合法的表格染色方案（R 代表红色，B 代表蓝色）：B B R B RR B B B BR R B R B可是昨天晚上，有人已经给表
2021-03-20 10:06:34
647
1
原创 【牛客挑战赛48 E】速度即转发
题目题目链接：https://ac.nowcoder.com/acm/contest/11161/E给定一个长度为 nnn 的数组 aaa。支持 mmm 次操作：给定 l,r,kl,r,kl,r,k，求 [0,105][0,10^5][0,105] 内满足 ∑i=lrmax(ai−x,0)≥k\sum^{r}_{i=l}\max(a_i-x,0)\geq k∑i=lrmax(ai−x,0)≥k 的最大正整数 xxx。给定 x,yx,yx,y，将 axa_xax 修改为 yyy。n,m,
2021-03-20 07:36:56
133
原创 【CF103D】Time to Raid Cowavans
题目题目链接：https://codeforces.com/problemset/problem/103/D给一个序列 aaa ，mmm 次询问，每次询问给出 t,kt, kt,k 。求 at+at+k+at+2k+⋯+at+pka_t + a_{t+k}+a_{t+2k}+\cdots+a_{t+pk}at+at+k+at+2k+⋯+at+pk 其中 t+pk≤nt+pk \leq nt+pk≤n 且 t+(p+1)k>nt+(p+1)k > nt+(p+1)k>n。n,m
2021-03-19 18:01:47
104
原创 【洛谷P4280】逆序对
题目题目链接：https://www.luogu.com.cn/problem/P4280暑假到了，小可可和伙伴们来到海边度假，距离海滩不远的地方有个小岛，叫做欢乐岛，整个岛是一个大游乐园，里面有很多很好玩的益智游戏。碰巧岛上正在举行“解谜题赢取免费门票”的活动，只要猜出来迷题，那么小可可和他的朋友就能在欢乐岛上免费游玩两天。迷题是这样的：给出一串全部是正整数的数字，这些正整数都在一个范围内选取，谁能最快求出这串数字中“逆序对”的个数，那么大奖就是他的啦！当然、主办方不可能就这么简单的让迷题被解开，
2021-03-18 21:51:12
264
原创 【洛谷P3273】棘手的操作
由于 cnblogs 到 3 月 25 号前需要整改，无法写博客，所以这几天就暂时在 CSDN 写，到时候再搬过去。题目题目链接：https://www.luogu.com.cn/problem/P3273有 nnn 个节点，标号从 111 到 nnn，这 nnn 个节点一开始相互不连通。第 iii 个节点的初始权值为 a[i]a[i]a[i]，接下来有如下一些操作：U x y: 加一条边，连接第x个节点和第y个节点A1 x v: 将第x个节点的权值增加vA2 x v: 将第x个节点所在的连通
2021-03-18 21:18:17
120
原创 【洛谷P4178】Tree【分块】
题目：题目链接：https://www.luogu.com.cn/problem/P4178给你一棵树，以及这棵树上边的距离，问有多少对点它们两者间的距离小于等于kkk。思路：这道题是应该加强数据了。。。当然如果这道题不打算做点分治模板题的话可以不用O(nn logn)O(n\sqrt n\ \log \sqrt n)O(nn logn)分块在洛谷优秀的O2...
2019-12-20 22:00:19
211
原创 【JZOJ4817】square【二维rmq】【二分】
题目题目链接：https://jzoj.net/senior/#main/show/4817给出一个010101矩阵，每次询问子矩阵中的最大111正方形。思路：二分最大正方形的边长midmidmid，那么对于询问(x,y)(xx,yy)(x,y)(xx,yy)(x,y)(xx,yy)的子矩阵，我们其实就是要判断子矩阵(x+mid−1,y+mid−1)(xx,yy)(x+mid-1,y+m...
2019-12-14 15:44:51
186
原创 【JZOJ4815】ksum【堆】
题目：题目链接：https://jzoj.net/senior/#main/show/4815求一个数列前kkk大的字段和。思路：由于∑i=kna[i]<∑i=kn+1a[i]\sum_{i=k}^na[i]<\sum_{i=k}^{n+1}a[i]∑i=kna[i]<∑i=kn+1a[i]，所以我们直接建立一个大根堆，装对于每一个数a[i]a[i]a[i]的sum...
2019-12-14 15:40:15
149
原创 【牛客练习赛55】E - 树【线段树】【换根法】【dfs】
题目题目链接：https://ac.nowcoder.com/acm/contest/2927/E你有一颗大小为 n\mathit nn 的树，点从 1\mathit 11 到 n\mathit nn 标号。设dis(x,y)\operatorname{dis}(x,y)dis(x,y)表示 x\mathit xx 到 y\mathit yy 的距离。求∑i=1n∑j=1ndis2(i,...
2019-12-14 07:48:58
223
原创 【JZOJ3920】噪音【dp】
题目：题目链接：https://jzoj.net/senior/#main/show/3920FJ有M个牛棚，编号1至M，刚开始所有牛棚都是空的。FJ有N头牛，编号1至N，这N头牛按照编号从小到大依次排队走进牛棚，每一天只有一头奶牛走进牛棚。第i头奶牛选择走进第p[i]个牛棚。由于奶牛是群体动物，所以每当一头奶牛x进入牛棚y之后，牛棚y里的所有奶牛们都会喊一声“欢迎欢迎，热烈欢迎”，由于声音很...
2019-12-07 14:35:07
339
原创 【JZOJ3919】志愿者【线段树】【换根法】
题目：题目链接：https://jzoj.net/senior/#main/show/3919给出一棵树以及若干个标记点，树有边权，求分别从每一个点出发经过所有的标记点所需的最小边权和。思路：首先我们设TTT为能包含所有标记点的最小的树，sizeTsizeTsizeT为TTT的边权和。考虑所有x∈Tx\in Tx∈T的点xxx，如果我们要求最终需要回到出发点(x)(x)(x)，那么显然...
2019-12-07 14:26:54
175
原创 【JZOJ3918】蛋糕【二分】
题目：题目链接：https://jzoj.net/senior/#main/show/3918给出一个n×mn\times mn×m的矩阵，将这个矩阵横切三下，竖切三下，使得每一块的数字之和的最小值最大。思路：枚举横切分别切在哪里。然后可以二分最小值，转变为判定性问题。每次二分就O(n)O(n)O(n)暴力向右扫，看看列能否分成444部分，每部分每一块都≥mid\geq mid≥mid...
2019-12-07 13:56:21
181
原创 【洛谷P5068】我回来了【bfs】
题目题目链接：https://www.luogu.com.cn/problem/P5068珂朵莉给你一个无向图，每次查询的时候给一堆二元组(xi,yi)(x_i,y_i)(xi,yi)求图中有多少个点uuu与至少一个这次询问给出的二元组(xi,yi)(x_i,y_i)(xi,yi)满足dist(u,xi)≤yidist(u,x_i)\leq yidist(u,xi)≤yi，dist...
2019-11-30 22:56:14
203
原创 【洛谷P5652】基础博弈练习题【dfs】【博弈论】
题目：题目链接：https://www.luogu.org/problem/P5652YSGH和YGSH在打膈膜，YSGS在旁边围观。规则是这样的，先给定一个正整数mmm和一个nnn个数序列BBB，一开始有一个棋子在BBB的第一个位置，并将B1B_1B1减去111。此后双方轮流操作，每次操作，假设当前棋子在iii，可以把棋子移到一个位置jjj，满足j∈[i,min(i+m,n)]j\in[...
2019-11-13 20:32:49
278
原创 【洛谷P5651】基础最短路练习题【dfs】【并查集】
题目：给定nnn个点mmm条边的无向简单联通图GGG，边有边权。保证没有重边和自环。定义一条简单路径的权值为路径上所有边边权的异或和。保证GGG中不存在简单环使得边权异或和不为0。QQQ次询问xxx到yyy的最短简单路径。思路：题目保证了每一个简单环的异或和均为0。也就是说对于环上的任意两点(x,y)(x,y)(x,y)，从x→yx\to yx→y的两条路径的权值相等。所以对于每一...
2019-11-13 19:07:16
495
原创 战略威慑【LCA】【树的直径】
题目：思路：我们可以暴力枚举其中一条路径，那么问题就是在剩余的路径中找到一条长度最长的来匹配。所以其实就是暴力枚举+树的直径。枚举完一条路径后，求出端点的LCALCALCA，然后暴力标记已经使用过的的点。然后原本的一棵树就被分为了很多棵树。在每一个树中分别跑直径即可。时间复杂度O(n2logn+n3)O(n^2\log n+n^3)O(n2logn+n3)代码：#includ...
2019-11-12 14:55:37
188
原创 逮虾户【二分】
题目：思路：我们设第iii次开车的时间为tit_iti，那么就是我们要解方程组{t1(v1+d)=s1t2(v2+d)=s2⋮t3(v3+d)=s3t1+t2+...+tn=t\left\{\begin{matrix}t_1(v_1+d)=s_1\\ t_2(v_2+d)=s_2\\ \vdots \\ t_3(v_3+d)=s_3\\t_1+t_2+...+t_n=t\end{mat...
2019-11-12 14:51:50
189
原创 赛艇表演【最短路】
题目：思路：由于如果要经过一条道路就肯定会经过两次，所以我们直接将所有边的边权乘2即可。然后我们把每一个点的disdisdis设为在该地看比赛的价格。然后将每一个点扔进优先队列内跑最短路即可。如果一个地点经过某一条道路到另外的地点观看比赛会更优，那么最短路就可以跑出来。最终答案就是disdisdis代码：#include <queue>#include <cs...
2019-11-12 14:46:46
229
原创 【洛谷P1903】【BZOJ2120】数颜色 / 维护队列【带修莫队】
题目大意：题目链接：洛谷：https://www.luogu.org/problemnew/show/P1903BZOJ：https://www.lydsy.com/JudgeOnline/problem.php?id=2120nnn只画笔，维护以下操作:Q L RQ\ L\ RQ L R代表询问你从第LLL支画笔到第RRR支画笔中共有几种不...
2019-11-11 20:07:01
195
原创 【洛谷P3370】【模板】字符串哈希【哈希】
题目大意：题目链接：https://www.luogu.org/problemnew/show/P3370 给定NNN个字符串（第i个字符串长度为M[i]M[i]M[i]，字符串内包含数字、大小写字母，大小写敏感），请求出NNN个字符串中共有多少个不同的字符串。思路：字符串哈希的模板题。 我用的是单哈希。 把字符串的每一位看成一个basebasebase进制的数字，用ansa...
2019-11-11 20:06:46
574
原创 【JZOJ3889】序列问题【dp】【高精度】
题目：题目链接：https://jzoj.net/senior/#main/show/3889小H是个善于思考的学生，她正在思考一个有关序列的问题。她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。这两个集合要满足以下的条件：两个集合中的元素都为整数，且都在 [1, n] 里，即Si，Ti ∈ [1, n]。对于集合S中任意一个元素x，集合T中任意一个元素y，满...
2019-11-11 20:05:04
169
1
原创 【JZOJ3888】正确答案【模拟】【dfs】
题目：题目链接：https://jzoj.net/senior/#main/show/3888小H与小Y刚刚参加完UOIP外卡组的初赛，就迫不及待的跑出考场对答案。“吔，我的答案和你都不一样！”，小Y说道，”我们去找神犇们问答案吧”。外卡组试卷中共有m道判断题，小H与小Y一共从其他n个神犇那问了答案。之后又从小G那里得知，这n个神犇中有p个考了满分，q个考了零分，其他神犇不为满分或零分。这...
2019-11-11 15:54:35
804
原创 【洛谷P2051】中国象棋【dp】
题目：题目链接：https://www.luogu.org/problem/P2051这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！...
2019-11-11 11:54:04
203
原创 【51nod 1326】遥远的旅途【最短路】
题目：题目链接：http://www.51nod.com/Challenge/Problem.html#problemId=1326给出一张nnn个点mmm条边的无向图，询问是否有一条从1到nnn的路径的距离为ttt。2≤n≤50,1≤m≤50,1≤t≤10182\leq n\leq 50,1\leq m\leq 50,1\leq t\leq10^{18}2≤n≤50,1≤m≤50,1≤t≤...
2019-11-10 21:19:25
231
原创 【JZOJ1405】电缆建设【最小生成树】
题目：题目链接：https://jzoj.net/senior/#main/show/1405 教主上电视了，但是蔚蓝城郊区沿河的村庄却因电缆线路老化而在直播的时候停电，这让市长SP先生相当的愤怒，他决定重修所有电缆，并改日播放录像，杜绝此类情况再次发生。 河流两旁各有n，m个村庄，每个村庄可以用二维坐标表示，其中河流一旁的村庄横坐标均为x1，河流另一旁的村庄横坐标均为x2。由于地势十分开...
2019-11-09 16:24:10
210
原创 【JZOJ1404】菱形内的计数【并查集】
题目：题目链接：https://jzoj.net/senior/#main/show/1404给出一个菱形，问这个菱形中有多少个内部不含边的平行四边形。思路：我们先把这个菱形转换为正方形。例如样例的转换方式如下：那么接下来我们就是要求有多少个中间没有边的矩形。我们可以记录每一个矩形的大小和最右上方(x1,y1)(x1,y1)(x1,y1)和最左下方的点(x2,y2)(x2,y2)(...
2019-11-09 16:20:34
177
原创 【JZOJ1402】偷懒的小X【dfs】
题目：题目链接：https://jzoj.net/senior/#main/show/1402给出一组数，输出字典序最大的满足堆性质的排列。思路：考虑某一个情况时的最大值，一定是放在堆的叶子中。而且任意叶子均可。但是为了字典序尽量大，所以肯定放在dfsdfsdfs序最小的节点。所以我们就深度优先搜索这棵二叉树，当递归完这棵树的子树后，我们就将这个位置赋值为序列中还没选择的最大值。时间...
2019-11-09 16:06:20
137
原创 【洛谷P1005】矩阵取数游戏【区间dp】【高精度】
题目：帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n \times mn×m的矩阵，矩阵中的每个元素ai,ja_{i,j}ai,j均为非负整数。游戏规则如下：每次取数时须从每行各取走一个元素，共nnn个。经过mmm次后取完矩阵内所有元素；每次取走的各个元素只能是该元素所在行的行首或行尾；每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值×2i\tim...
2019-11-09 07:25:24
327
原创 【JZOJ1247】【洛谷P2870】队列变换【hash】【二分】【贪心】
题目：题目链接：https://www.luogu.org/problem/P2870FJ打算带他的N(1 <= N <= 30,000)头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的...
2019-11-08 14:42:01
169
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人