zrzring

题解

/ 注册

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

题解 | D-Points Construction Problem

https://www.cnblogs.com/zrzring/p/NC55994D.html 将图上恰好 nnn 个点染成黑色，使得图上相邻的黑白点对数量恰好为 mmm 考虑 nnn 个黑点如果不相邻，则两个点的贡献互不影响考虑相邻的情况，我们把相邻的点连边，则贡献为每一个连通块的贡献的和，...

C++ 脑筋急转弯构造

2023-05-01

1 319

题解 | B - 包含

用一个bool数组表示每个数是否能被表示，初始化把Q所有元素设为1，然后跑一个高维前缀和算出所有的子集，类似多源最短路，这个过程可以同时多源进行 #include <iostream> #include <cstdio> #include <cmath> #inc...

2020-10-24

0 676

题解 | A - GCD

考虑数的唯一分解 f(px)=p,f(∏pixi)=1f(p^x) = p, f(\prod p_i^{x_i}) = 1f(px)=p,f(∏pixi)=1 #include <iostream> #include <cstdio> #include <cmath...

数论

2020-10-24

0 668

牛半仙的妹子图

按边权排序后并查集维护在一个连通块的点，bitset维护出现的颜色集合，对于询问求一个前缀和来回答询问就行了 #include <iostream> #include <cstdio> #include <cmath> #include <cstring&g...

并查集 bitset

2020-10-23

1 709

牛牛的凑数游戏

更好的阅读体验原题 - 【FJOI2016】神秘数如果只有一次全局询问，可以排序之后扫一遍数组，每次和比较，更新答案，直到不能更新为止区间询问不能排序，但是如果不排序的话，进行上述操作，最多扫次就能得出答案考虑每次更新时，可以更新的数一定比上一次更新时的大(否则在上一次更新就计入里了)，于是...

主席树

2020-10-19

1 767

牛牛的猜球游戏

更好的阅读体验考虑如何利用差分的思路，即知道起始状态和目标状态如何求出过程量我们并不关心具体过程，只关心一步到位的过程，于是去找相对位置的位移即可，记录这组位移，再用一个原始序列去进行这样的位移即可 #include <iostream> #include <cstdio>...

差分

2020-10-19

0 669

牛牛的方程式

更好的阅读体验裴蜀定理的推广，若，则，负数可以转化为正数处理 #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorit...

数论

2020-10-19

0 678

NC211969 集合操作

更好的阅读体验这种题一般都需要用到容斥因为操作可以改变顺序，原题就变成了将到的排列分成两个集合，，对于每个元素，都最多有个，求划分方案数考虑枚举集合的大小，为了满足条件，时可以选择任意的数放入，时只能在从到里选择个 #include <iostream> #include &...

组合数学

2020-10-14

1 638

NC54042 十二桥问题

更好的阅读体验题意：求从1出发经过给定的条关键路径回到1的最短路，注意到条边的两个端点，再加上起点1，只有这些点是关键点，其他的点都无关紧要预处理出每两个关键点之间的最短路，然后类似于旅行者问题跑一个状压dp，讨论一下每个关键路径的两个端点转移即可 #include <iostrea...

最短路状压dp

2020-10-14

0 724