又写了一天的水题，牛客多校第二场还没怎么补...我好咸鱼啊QAQ A-Oh Those Rollers（简单BFS） 题目链接：https://ac.nowcoder.com/acm/contest/997/A 题目大意：n个齿轮，每个齿轮有它的原点，半径，原点在0,0处的是主动轮，问最后一个被动轮是多少号齿轮。 思路：BFS，记录齿轮直接相连的有多少个。如果一组齿轮构成一个环，那么这个环里面的所有齿轮都不是最后一个被动轮，因为任意一个都能带动其他轮。然后找到最后一个只连接一个齿轮的轮子，这个就是最后的被动轮。 ACCode： #include<stdlib.h> #...

这次比赛是在家里打的。比赛一半的时候才想起来，从1小时40分钟开始写的。写完5道题之后还剩半个多小时，觉得也写不出什么题了，就直接放弃了（其实是发现6道也进不了rank50）。 Contest：https://ac.nowcoder.com/acm/contest/949#question A-小石的签到题 题目链接：https://ac.nowcoder.com/acm/contest/949/A 题目大意：中文题，较好理解题意。 思路：假设后取的人胜，那么只要先取的人取了1，那么后取的人相当于先取了，先取的人胜。假设先取的人胜，那么先取的人胜利了。。。发现总是先取的人胜利。注意只...

哎。。本来想写完之后在写博客的，但感觉剩下两道比较难啊，估计要等好久才能写出来了。。 A-Card Stacking 题目链接：https://ac.nowcoder.com/acm/contest/993/A 题目大意：n头牛坐在一圈，按顺序发牌。1,2,3,4,5.。。问自己最后都获得那些牌，从小到大输出自己活得的牌。 思路：简单deque模拟就好了，最后排一下序。 ACCode： #include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #...

随缘补题中我好菜啊QAQ... A-Equivalent Prefixes 题目链接：https://ac.nowcoder.com/acm/contest/881/A 题目大意：给出两个数组，分别包含n个数字。定义RMQ(u,l,r)=RMQ(v,l,r)是数组u和v在同样的[l,r]区间，最小值的位置是一样的。找到一个P满足所有的1<=l<=r<=P满足RMQ(u,l,r,)=RMQ(v,l,r)； 思路：对于每个数字，找到它在数组中的影响区间（在这个区间内他就是最小的），可用二分找到。然后从1开始，对于每个数字，判断是否能够被选中，要求所覆盖的区间重合，如果覆盖...

题目链接：http://poj.org/problem?id=3621 题目大意：给出一个有向图，每个节点有一个权值val，每条边有一个长度len。奶牛要逛不少于两个点，并且最后要回到原点。求Ans= 所逛过的节点权值之和 / 经过的边的距离之和 的最大Ans。 思路：讨论区有个大佬证明了最终答案必定是简单环。 证明如下： 假设最优解不是简单环，则其中必定有一个重复点，设为c1，对于这个点隔开到也是两个环，我们设两个环中除了这个点其他点权值和分别为，c2,c3;边权值为 a1,s2; 由于它是最优解所以有 ： 1.(c1+c2+c3)/(a1+a2) > (c1+c2)/a1...

题目链接：http://poj.org/problem?id=2728 题目大意：给出一个三维地图，每个村庄包含x，y，z三点坐标。要在村庄之间通上管子。每两个村庄之间的水平距离（x，y）是有效距离。两村庄之间的abs（高度差）是成本。让你找到一个生成树满足 总成本/总有效距离最小。 思路：最优比率生成树板子。对于所有的点： 边权变为：。跑最小生成树即可。 找到一个Ans的最小生成树满足F(Ans)=0即可。 上面的过程得出的是一个单增的一次函数。下面我写的是单减的一次函数。没什么区别（唯一的区别就是正负号，二分时注意移动）。 二分的时候注意上下界，一开始我用的1e...

题目链接：http://www.51nod.com/Challenge/Problem.html#problemId=1257 题目大意：中文题。 思路：0/1分数规划的入门。由于答案用分数表示。因此我们需要另开一个数组记录二分到Ans时的分子和分母，然后化简即可。 ACCode： #include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> #include<time.h> // srand(unsigned)time(NULL));ran...

题目链接：http://poj.org/problem?id=2976 题目大意：给出n次考试，每次考试都有 解决问题数Ai 和 问题总数两种Bi 属性。我们从中选择n-k场考试，使得最大。输出最大的答案（Ans）。 思路：0/1分数规划入门题： 二分Ans，前n-k项之和==0. ACCode： //#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> #include<math....

题目链接：http://poj.org/problem?id=3622 题目大意：给出n头牛，每头牛有两个属性：金钱，美味。m个产品，每个产品有两个属性：金钱，美味。只有一个产品的两个属性都大于等于牛的时候，这头牛才会去吃这个产品。问使n头牛都能吃上产品，最少花费多少。如果不能满足，输出-1； 思路：将牛的属性按照美味从大到小排列，将产品的美味从小到大排列。然后依次选牛。对于每头牛，二分出第一个可选的美味。将可选的美味都放入SplayTree中。然后从中找出最少花费的一个产品。移除SplayTree。总体复杂度O(n*log(m)*log(m))。 900+ms险过（SplayTree常...

第一次参加全国性质的比赛，能和大佬们同台竞技真是太紧张了！ 正式赛前一晚，做了好多梦，梦见打铁了3点多吓醒了QAQ 竟然能摸到一个铜，感觉也是很意外（运气成分居多），感觉全程瞎写。。。 一开始2分钟，队友看了一个签到L（真签到），然后我马上交上去了，AC，rank170+，赶紧看第二题，又发现了一道水题K，简单贪心sort一下求和就好，1A,看了看rank150+。还行，估摸了一下铜线300*0.6=180，感觉不是很稳（毕竟都是水题）。 然后我开始和神仙研究异或那道题F，文少看完A之后说这个是最短路，然后我看了看，跑了两组样例发现不是很容易，就和神仙一起推F的规律，文少看G（看完榜单...

Contest：https://ac.nowcoder.com/acm/contest/894#question A-华华教奕奕写几何（数学） 题目链接：https://ac.nowcoder.com/acm/contest/894/A 题目大意：中文题。 思路：得到公式，联立：,求R=r1+r2的最小值。 经过一堆化简得：，然后想到对勾函数，然后得到r1=r2=R/2；所以得： ACCode: int main(){ double S; while(~scanf("%lf",&S)){ printf("%.3lf\n",...

题目链接：http://poj.org/problem?id=2763 题目大意：给出一个树，每条边都有自己的权值，给你一个起点S，一个人从S开始走，有两种状态，1.将第i条边的边权修改为val。0.从当前位置走到T。每次0的时候输出行走的距离。 思路：这个是之前放置有一段时间的题了，当时还不会树剖，没什么思路，最近学过树剖之后，发现可以用树剖来解决。 类似洛谷的一道题：https://blog.csdn.net/qq_40482358/article/details/89853548。 同理转化成边权即可。另外还有一个就是由于修改的不是点，而是第几条边，怎么办呢？我的方法是将这些边都...

题目链接：https://www.luogu.org/problemnew/show/P2486 题目大意：中文题，如题。 思路：很明显的树剖，维护一条链的颜色个数，最左右节点的颜色。合并的时候注意要比较一下相连接的部分，如果颜色一样，就ans--。 比较连接处颜色的时候手残少些了个Top。结果一直WA。找了个过的对拍了一下。发现是手残。佛了。后面有对拍代码。觉得自己没问题的可以拍一下看看，把n开大一点总能拍出来的。 ACCode： // luogu-judger-enable-o2 //#pragma comment(linker, "/STACK:1024000000...

题目链接：https://www.luogu.org/problemnew/show/P2146 题目大意：中文题。给出一些依靠的关系，让你从中得到卸载，安装相关联的软件包个数。 思路：由于0节点是基础包，所以我们可以以0节点为根建一棵树，然后使用树链剖分，即：安装的时候讲0~x这个链全都置为1，卸载的时候将x节点的子树都置为0，每次查询他们之间的差值就是修改软件包的个数。板子，抄上去就行了。因为PushDown()手残写错了导致Debug了一个多小时。QAQ ACCode： //#pragma comment(linker, "/STACK:1024000000,1024...