Z_L_G

题解

总结(20) 训练赛(18)

/ 注册

全部文章 / 题解（共129篇）

算法入门-大水题

题意给出n，求1~n之中，有多少数不是2，5，11，13的倍数思路容斥原理，用n减去即可代码 #include<bits/stdc++.h> using namespace std; long long n; void solve(){ cout <<...

容斥原理

2025-08-02

0 27

算法入门-[SDOI2008]仪仗队

#欧拉函数题意给定n，输出n*n方阵中站在(1,1)可以看到得点思路观察发现，能被看到得点一定x，y坐标互质由于对称性，只求下半个三角就行，也就是对于固定x，求和x互质的数的个数，也就是欧拉函数的板子边求边加，最后加上左下角三个点就行代码 #include<bits/st...

欧拉函数数学

2025-07-24

0 31

算法入门-华华给月月出题

#积性函数 #线性筛 #快速幂题意给定n，求解 n<=1.3e7 思路满足积性函数需要找到n以下每个数的n次方，可以用筛法，质数的用快速幂计算，合数的用质数递推因为空间限制，无法记录每个数的最小质因子，但其实可以直接暴力的乘上每一个质因子，同时开一个bool的vis数组保证每...

数学筛法积性函数快速幂

2025-07-24

0 34

算法入门-Ranking the Cows

题意 n个数，确定了m对关系(a>b) 求还需要多少对关系就能确定任意两个数之间的大小思路把大小关系视为一条有向边这个题就变成了任意两个点是否联通考虑使用FLoyd，但是n是1000量级的，刚好爆炸使用bitset优化足够 floyd算法可以传递闭包关系 bitset错误赋...

位运算优化 floyd传递闭包

2025-07-13

0 26

算法入门-HDUOJ5521Meeting

题意 n个点，m个集合，在i-th集合内相互移动的代价为t-th 两个人从1和n开始移动，求碰面最短时间和碰面的点思路强行给每个集合之间的点互相连边复杂度会到不可以对于这种集合/平台类的问题，我们通常选择给每个集合/平台单开一个点，集合中所有点到这个单开点建双向边，过去的代价为t，回...

妙妙题裂点最短路

2025-07-13

0 42

算法入门-[SCOI2012]滑雪与时间胶囊

题意给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点特别的，两个点一样高，就认为是双向边求出最多能到达的点的个数，以及到达这些点需要的最小距离思路先dfs一遍，确定哪些点能到类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两...

最小生成树深度优先搜索

2025-07-13

0 36

算法入门-[HNOI2015]菜肴制作

#反向建边 #拓扑排序题意有n个菜，m个条件约束条件(a,b)，表a必须在b之前除了约束条件外，要保证序号小的的尽可能先做在满足所有限制的前提下，1 号菜肴”尽量“优先制作；在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作；以此类推。例：共4 道菜肴，两条限...

拓扑排序反向建边

2025-07-11

0 34

算法入门-胖胖的牛牛

题意 n*n的正方形地图，从起点走到终点，图中有一些障碍物不能走求最小转弯次数思路图不大，迷宫问题，考虑搜索，不再记录步长，而是在走每一步的时候考虑和走过来的方向是否相同，如果不同就给转弯次数+1 用一个优先队列避免重复走不开vis，否则部分优势可能掩盖全局劣势也可以最短路做，每个点...

广度优先搜索

2025-07-11

0 40

算法入门-[NOIP2003]加分二叉树

题意一个1-base二叉树，n个结点，中序遍历为(1,2,3,...,n),每个点有一个val，选择一个子树的加分规则如下：如果某个子树为空，就视为val=1，叶子节点分数为本身的分数求符合中序遍历的加分最高的二叉树，输出加分和前序遍历思路对于一段中序遍历序号，总需要选择一个根，切分...

区间dp dp

2025-07-09

0 37

算法入门-树学

题意一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和求选择哪个点为根时可以使深度和最小思路让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和但是让每一个点跑一遍复杂度会爆炸能不能只跑一遍？如果只跑一遍，根变换怎么办对于一个选定根的树，如果...

深度优先搜索 dp

2025-07-09

0 22