SSuryxin

分类

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5) 题解(29)

/ 注册

TA的专栏 3篇文章 0人订阅

3篇文章 1162人学习

全部文章（共52篇）

题解 | #Ancestor#

Ancestor 题目描述：给你两棵树A和B，点的编号从1到n，根结点是1,且每个点都有一个价值，现在给你k个点，选任意k-1个不同的点，分别求这些点在两颗树上的最近公共祖先fa, fb，问存在多少种情况满足A树上fa的价值大于B树上fb的价值思路1：前缀和 + 后缀和这是最简单好写的一...

dfs 思维 dfs序

2022-07-25

0 595

题解 | #魔法学院#「差分 + 贪心」「线段树 + 贪心」「并查集 + 贪心」「珂朵莉树」

魔法学院题目描述：亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。目前她已经收集了n个不包括空格的可见字符，第i个字符为Si。可是她想要把自己收集的n个字符的价值和最大化，因此去请求了戴安娜的帮助。戴...

2022-02-23

0 590

题解 | #牛客小白月赛44#

牛客小白月赛44 深渊水妖题目描述：找到所有极长的不严格上升段，并找出它们当中右端点权值 - 左端点权值最大的那些个段，输出端点坐标思路：模拟就行，千万要注意是权值的差的最大值，而不是r - l + 1的最大值 #include <bits/stdc++.h> using...

2022-01-24

4 640

题解 | #数字游戏#

数字游戏题目描述：一个x ，当x不为零时进行如下操作如果二进制x中有奇数个1，则x二进制形式下最低位取反如果二进制xxx中有偶数个1，则x二进制形式下非前导零最高位取反询问对于一个x，操作几次后变为零思路1：对于奇数的情况，其实就对x异或了1 对于偶数的情况，其实就是把第一个...

2021-11-06

0 749

题解 | #牛客练习赛90#

梦想赛道题目描述：给出一颗树，你需要构造一个图使得这个树在这个图中是一个严格的次小生成树，问图的权值最小可以是多少思路：只需要在原树的基础上加一条边即可，因为是要最小权值，所以我们就加1，（加0的话就不是严格的次小生成树了，况且题目中给的最小权值就是1）有个特殊的情况就是如果这个树的...

2021-11-02

2 659

题解 | #憧憬#

憧憬题目描述：给出n个向量，以及一个目标向量，问能否通过n个向量中两个向量相加来构造出一个与目标向量平行的向量思路：签到题枚举+判断 n个向量两两组合得到所有的向量，然后挨个与目标向量进行判断即可判断向量(a, b) // (c, d)的条件是：a * d = b * c 坑点：...

2021-10-24

6 567

嗅探器

嗅探器题目描述：红蓝军队打演习，蓝军有两个信息中心，红军计划在某个中间服务器上安装一个嗅探器，来获得蓝军情报，而蓝军网络相当庞大，数据包从一个信息中心传到另一个信息中心不止一条路，你需要将嗅探器安装到哪个中间服务器才能保证所有数据包都能被捕获思路：转换一下其实是找割点，但不仅仅是割点，...

链式前向星 tarjan 缩点 dfs

2021-08-14

1 724

Cow Ski Area

Cow Ski Area 题目描述：滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点思路： ...

链式前向星缩点 tarjan dfs 拓扑排序

2021-08-13

1 537

[ZJOI2007]最大半连通子图

[ZJOI2007]最大半连通子图题目描述：给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模思路：这是一个比较复杂的题？主要思路是：tarjan缩点+拓扑排序+dp 首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点...

链式前向星缩点 tarjan 拓扑排序 dp

2021-08-13

1 612

[HAOI2006]受欢迎的牛

[HAOI2006]受欢迎的牛题目描述：众所周知，喜欢是可以传递的（bushi，给你N头牛，给你M对喜欢关系，如果A喜欢B，B喜欢C，则我们认为A也喜欢C，现在需要求有多少头牛被所有牛喜欢思路：还是先进行tarjan缩点，当且仅当存在一个出度为0的点集，则输出该点集的数量，否则输出0 ...

链式前向星缩点 tarjan 拓扑排序

2021-08-13

1 498