Z_L_G

题解

总结(19) 训练赛(13)

/ 注册

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

算法入门-数据结构

题意对于一个长为n的序列a，你需要完成q次询问，每次询问有四种情况输出(l,r)区间和输出(l,r)区间平方和 (l,r)所有元素+=x (l,r)所有元素*=x 其中n为1e4量级，m为2e5量级思路线段树变种对于区间和，维护第一个线段树对于区间平方和，维护第二个线段树 ...

线段树妙妙题

2025-08-03

0 10

算法入门-青蛙

题意 m块石头，n只青蛙，第i青蛙步长求解所有被踩过的石头的编号(0-base)和思路观察发现，对于一只青蛙，他能踩到的石头是暴力会炸考虑从m入手，的结果一定是m的因子枚举m的因子，标记是gcd倍数的因子，这些因子会产生贡献用一个cnt记录每个因子还需要计算贡献的次数从...

组合数学

2025-08-02

0 12

算法入门-[HAOI2016]放棋子

题意长为n的排列，第i为不能放i，求解方案数思路典型的错排问题 c++得写高精度代码 n=int(input()) f=[0,0,1] for i in range(3,n+1): f.append((i-1)*(f[i-1]+f[i-2])) print(f[n])

组合数学错排

2025-08-02

0 11

算法入门-[SCOI2010]字符串

题意把n个1，m个0组成字符串，要求任意前k个字符中，1的个数不少于0的个数求解满足要求的字符串有多少个思路总保证前缀和大于0 卡特兰数板子题求解f(n) 组合数求解要开逆元，x%p的逆元和x的逆元相等代码 #include<bits/stdc++.h> using ...

组合数学卡特兰数

2025-08-02

0 9

算法入门-[HAOI2012]容易题(EASY)#

题意长度为m的序列，每个位置可选1~n，有k条限制，限制位置a不能选择b 求解所有序列内部求积的和思路加法原理和乘法原理如果没有限制，每个位置可以选择1~n，m个位置每个位置的贡献为(n*(n+1)/2)总价值为(n*(n+1)/2)^m 然后对于没限制的部分就按照公式算有限制的部...

组合数学

2025-08-02

0 10

算法入门-大水题

题意给出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 11

算法入门-[SDOI2008]仪仗队

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

欧拉函数数学

2025-07-24

0 17

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

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

数学筛法积性函数快速幂

2025-07-24

0 13

算法入门-Ranking the Cows

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

位运算优化 floyd传递闭包

2025-07-13

0 19

算法入门-HDUOJ5521Meeting

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

妙妙题裂点最短路

2025-07-13

0 18