• 等级
  • 38788 访问
  • 204 原创
  • 1 转发
  • 21628 排名
  • 101 评论
  • 93 获赞

5911. 【NOIP2018模拟10.18】Travel

题目大意: EZ同学家里非常富有,但又极其的谦虚,说话又好听,是个不可多得的人才。 EZ常常在假期环游世界,他准备去N(N<=100000)个国家之多,一些国家有航线连接,由于EZ同学有一定的强迫症,任意两个国家之间都能通过航路直接或间接到达,并且这样的路径仅有一种。(简单来说,这些国家构成了一棵树) 由于EZ是C国人,因此将C国(1号国家)作为整棵树的根 每个国家有一个旅游热度A[i]和影...

2018-10-19 19:01:44

5910. 【NOIP2018模拟10.18】DuLiu(瞎搞)

题目大意: 具体来说,这N道题每题都有一个毒瘤值,它们构成了一个序列。李Fee心目中有一个理想的毒瘤值序列,这个序列并不一定每一题的毒瘤值都是原本N道题中出现的,所以李Fee准备进行一些改动。这些改动体现在毒瘤值上就是将某道题的毒瘤值改为所有题的毒瘤值的二进制异或值。但是,改动题目是很麻烦的,他想算出最少需要多少次改动才能将原本的毒瘤值序列改成理想的毒瘤值序列,李Fee忙于出毒瘤题,他想请发明O(...

2018-10-19 16:12:55

5909. 【NOIP2018模拟10.16】跑商(圆方树+树链剖分+SET)

题目大意: 基三的地图可以看做 n 个城市,m 条边的无向图,尊者神高达会从任意一个点出发并在起点购买货物,在旅途中任意一点卖出并最终到达终点,尊者神高达的时间很宝贵,所以他不会重复经过同一个城市,但是为了挣钱,他可能会去绕路。当然,由于工作室泛滥,所以一个城市的货物价格可能会发生改变。但是尊者神高达智商不足,他可能在一个很蠢的节点把货物卖掉,所以尊者神高达想知道每一次跑商最多能赔多少钱。 思路:...

2018-10-17 08:11:41

5908. 【NOIP2018模拟10.16】开荒(虚树+lca+线段树)

题目大意: 师门可以看做以 1 为根的一棵树,师门中的每一个人都有一定的装备分数。一共会有 q 个事件。每个事件可能是一次开荒,也可能是因为开荒出了好装备而导致一个人的装分出现了变化。对于一次开荒,会有 k 个人组织,由于师门的号召力很强,所以所有在组织者中任意两个人简单路径上的人都会参加。 思路: 我们可以设一个dis[i]dis[i]dis[i]表示每个点到根节点的权值和,然后我们发现修改是修...

2018-10-17 08:03:25

5907. 【NOIP2018模拟10.16】轻功()

题目大意: 一共有 n 个木桩,要求从起点(0)开始,经过所有梅花桩,恰好到达终点 n,尊者神高达一共会 k 种门派的轻功,不同门派的轻功经过的梅花桩数不同,花费时间也不同。但是尊者神高达一次只能使用一种轻功,当他使用别的门派的轻功时,需要花费 W 秒切换(开始时可以是任意门派,不需要更换时间)。由于尊者神高达手残,所以经过某些梅花桩(包括起点和终点)时他不能使用一些门派的轻功。尊者神高达想知道他...

2018-10-17 07:45:42

5906. 【NOIP2018模拟10.15】传送门(树形dp)

题目大意: 8102年,Normalgod在GLaDOS的帮助下,研制出了传送枪。但GLaDOS想把传送枪据为己有,于是把Normalgod扔进了一间实验室。这间实验室是一棵有n个节点的树。现在Normalgod在一号节点,出口也在一号节点,但为了打开它,必须经过每一个节点按下每个节点的开关,出口才能打开。GLaDOS为了杀死Normalgod,开始在实验室里释放毒气,因此Normalgod必须尽...

2018-10-15 22:25:37

5905. 【NOIP2018模拟10.15】黑暗之魂(darksoul)(tarjan缩点+环前缀和+单调队列)

题目大意: oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有n个篝火(也就是存档点)。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道(显然,通道是双向的),这些篝火之间都相互可达。也就是说,这是一张n个点,n条边的无向连通图。每条通道里都有一些怪物,经过oi_juruo的分析,他得到了每条边的怪物...

2018-10-15 22:07:28

5904. 【NOIP2018模拟10.15】刺客信条(AC)

题目大意: 故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。 这次的故事就是他暗杀一位作恶多端的红衣主教。...

2018-10-15 21:52:13

P2575 高手过招(博弈)

题目大意: 有一个n*20的棋盘,上面有若干棋子 对于一个棋子,能将它向右移动一格,如果右边有棋子,则向右跳到第一个空格,如果右边没有空格,则不能移动这个棋子,如果所有棋子都不能移动,那么将输掉这场比赛 思路: 我们考虑sg函数,显然最后一个状态下,右边全是一是必赢的,然后我们暴力搜出所有sg函数的,这样就可以o(1)判断了。 程序: #include<cstdio> #include...

2018-10-12 14:13:35

poj 2054 Color a Tree(贪心)

题目大意: 给你一棵树,你要给这棵树染色,染色的代价为时间乘上接点的代价。还有一个要求是这个节点被染色一定要父亲也被染色。 思路: 显然我们第一个染根节点,只有一条链也很简单。但是如果有很多儿子要选择哪一个呢。仔细思考我们发现染色可以想成是一个合并过程。我们设now[i]为合并到i的所有结点费用的平均值,cnt[i]为节点i合并的节点数。每次染色后染色费用更新,这样合并n-1就好了,顺序就选出来了...

2018-10-12 14:09:07

UVA378 Intersecting Lines(计算几何)

题目大意: 给你了两条线段,要你求他们是平行还是重合还是有交点,如果有交点就输出交点。 思路: 我们只需要一次跨立实验就可以判断两条线段是否重合,如果有向面积为0说明平行,如果两次叉积都为0说明重合,现在只需要讨论如何求交点了。 求交点:略略略…(直接看程序) 程序: #include<cstdio> #include<cstdlib> #include<algori...

2018-10-09 22:25:21

UVA10902 Pick-up Sticks

题目大意: 在一个坐标轴上抛棍子,问你哪些棍子上面没有被别的棍子覆盖过,输出个数和哪些棍子。 思路: 这是一道线段求相交的题目,用斜率显然可以做,但是好像讨论的要比较多…我们可以用向量来做,用A线段两个端点分别与B线段做两次跨立实验,如果叉积都为0说明线段重合,符号不同说明相交,符号相同说明不相交。 程序: #include<cstdio> #include<cmath> ...

2018-10-09 22:13:52

UVA190 Circle Through Three Points(计算几何)

题目大意: 给你三个不共线的点,求过三点圆的方程。写出一般式和标准式。 思路: 这题要求我们求出过给定三个点的圆的两个方程,一个是标准式,一个是一般式。 标准式:(x-h)2+(y-k)2=r^2 一般式:x2+y2+cx+dy-e=0; 学过三角形的同学都能知道,三角形的外心过三角形三点,所以圆心就是三角形外心,然后半径为一个点到圆心的距离。这样标准式答案就出来了。(h,k)是圆心坐标,r是半径...

2018-10-09 22:05:56

U41568 Agent1(瞎搞+组合数)

题目大意: 有n个互不相同的整数,分成A,B两组满足下面的关系 A队中能力最大的Agent的能力值要小于BB队能力最弱的Agent的能力值。 A,BA,B两队都要有人参战。 思路: 我们考虑枚举一个i一定是A队的,那么左边可以任意选就是2(i-1),右边除了全空都可以选2(n-i)-1,然后相乘为2n-1-2i-1,后面的是个等比数列,直接等比数列求和就好了,前面的是一个常数列随便搞搞。 程序: ...

2018-10-09 21:16:26

U41570 War1(网络流)

题目大意: ENLIGHTENED总部有NN个Portal,编号为11~NN,编号为ii的Portal初始能量值为A[i]A[i],在Portal之间有MM条LINK,每条LINK着连接着两个不同Portal,被连接着的两个Portal可以相互传输能量,每个Portal最多总共只能向其连接着的Portal传输A[i]A[i]点能量,现在ENLIGHTENED行动指挥想让每第ii个Portal的能量...

2018-10-09 21:09:44

P1070 道路游戏()

题目大意: 小新正在玩一个简单的电脑游戏。 游戏中有一条环形马路,马路上有 n n个机器人工厂,两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点,按顺时针顺序依次将这 n n个机器人工厂编号为1-n1−n,因为马路是环形的,所以第 nn 个机器人工厂和第 1 1个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 n 段马路也编号为 1-n1−n,并规定第 i i段马路...

2018-10-08 20:42:25

P1290 欧几里德的游戏

题目大意: 欧几里德的两个后代Stan和Ollie正在玩一种数字游戏,这个游戏是他们的祖先欧几里德发明的。给定两个正整数M和N,从Stan开始,从其中较大的一个数,减去较小的数的正整数倍,当然,得到的数不能小于0。然后是Ollie,对刚才得到的数,和M,N中较小的那个数,再进行同样的操作……直到一个人得到了0,他就取得了胜利。下面是他们用(25,7)两个数游戏的过程: Start:25 7 Sta...

2018-10-08 20:28:16

5899. 【NOIP2018模拟10.6】资源运输(矩阵树定理)

题目大意: 要你求一张图的生成树的边权乘积期望。 思路: 这题是一个矩阵树和变元矩阵树定理的应用题,矩阵树可以求出来生成树的数量,变元后的矩阵树可以求出所有生成树乘积和,然后除一下就好了。 矩阵树写法如下: 先定义两个矩阵,一个是度数矩阵,一个是连接矩阵,用度数矩阵剪掉连接矩阵,然后去掉一行一列,然后高斯消元,把对角线所有数乘起来就好了。 程序: #include<cstdio> #i...

2018-10-08 19:46:59

5895. 【NOIP2018模拟10.5】旅游

题目大意: 思路: 这题目比较特殊点在于他的边权是2^i,比赛的时候傻,没有想到有什么用,后来看到题解,如果构出一颗最小生成树,那么最短路一定在最小生成树上面,这样子就变成了一棵树上在原图中的奇点要配对,因为树上的一些奇怪性质,我们可以之间贪心得出答案,最后答案就是所有边权加上最小生成树上面贪心的结果。 程序: #include<cstdio> #include<cstdlib...

2018-10-06 14:42:37

2242: [SDOI2011]计算器(数论)

题目大意: 给你三个操作 1:求a^b=x(%p) 2:求a*b=x(%p) 3:求a^x=b(%p) 思路: 这是数论里面比较好的题了,第一问快速幂,第二问扩展gcd,第三问BSGS。 第三问a^x=b(%p),因为过p个肯定有一个循环节,飞马小定理可得,那么我们把x分成根号p块,设为a ^(i*m)a ^j=b(%p),移项可得aj=b∗ine(ai∗m)a^j=b*ine(a^{i*m})a...

2018-09-27 16:23:47

波波i

此微博用来学习,和嘿嘿嘿。
关注
  • 电子·微电子/学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒