zhangxixi的博客

通过奇偶性来构造：P9575 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132471708 对于没有思路的，和数有关的构造题，可以考虑2的情况，也就是用奇偶来构造 构造时需要考虑： 如何用奇偶构造合法 非法是否能用奇偶反证 例题：P9575 考虑到 xxx 不定，可以转化为奇偶问题。 发现在奇偶情况下容易构造，且非法可以奇偶反证。

解一元二次不定方程 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132385405 https://www.luogu.com.cn/problem/P5656 求解： 有解 充要 条件：令 d=gcd⁡(a,b),c mod d=0d=\gcd(a,b),c\bmod d=0d=gcd(a,b),cmodd=0 exgcd，背吧 12345678910int exgcd(int a, int b, int &x, int &...

因数、gcd等式子用莫比乌斯函数表示的一种简单方法 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132355546 对于此式，可以发现，本质就是把T的质因子集合全部抽出来，划分成两个不交的集合。假设 TTT 的集合大小为 w(T)w(T)w(T) ，那么这个式子本质上就是 2w(T)2^{w(T)}2w(T) 现在考虑用积性函数的形式表示，我们对 ddd 进行唯一素数表示，发现对于 d1,d2d_1, d_2d1​,d2​ ，若他们的底数种类相同，指数不...

质数与数差类题目：ZR2639三色堇 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132325425 Trick 1 题目要求维护差的平方和。但发现差得数量很少。 对于维护和差有关的东西（比如此题中的 ∑(ai−ai−1)2\sum(a_i-a_{i-1})^2∑(ai​−ai−1​)2 ），如果差的数量很少，可以直接维护差的数量 fif_ifi​ ，最后可以计算为 i2×fii^2\times f_ii2×fi​ Trick 2 考虑数之间的差怎么转...

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/17633348.html 说句题外话，这个博客不更是因为我转cnblogs了。 2023正睿金华暑假集训 7月15日，我跟随大队来到了金华 第一次参加暑假出省线下集训，之前在高中部集训过， 但都是校内的集训，没怎么出去过。唯一一次好像还是去六中集训，但最多也就是几个学校之间的小打小闹。 7月份是在C班集训，课没怎么听，主要是做C班的题目。那段时间，再加上7月初在高中的时候，补了一轮算法，省选基本算法大致都写了次模板了。 过来才知道，原来仅仅是C...

一道网络流题目和其相关套路：ZR2627紫罗兰 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132296366 http://zhengruioi.com/problem/2627 Trick1：二分套网络流 首先可以对原图建模 中间拆点是为了两对棋子走到同一个格子上 然后我们发现每条边除了容量还有一个边权， 而我们的目标是求出 每一个流量下的最小边权 对于网络流中出现边权最值问题，可以进行二分。二分过程时枚举最值，然后 保留可行边 ，来跑网络流 T...

遍历bitset中的1：_Find_first和_Find_next 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132282353 1234bitset<N> a;for(int v=a._Find_first();v!=a.size();v=a._Find_next(v)){ pre[v]=u,vis[v]=1,q.push(v);} 注意返回的 vvv 是 位数

c++accumulate()，partial_sum()，fill()函数 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132264428 accumulate() 求和，传入 begin指针、end指针，首项 12int a[5]={1, 2, 3, 4, 5}, b[5], c[5]; printf("%d\n", accumulate(a, a+5, 100)); 100+1+2+3+4+5=115 pa...

线段树记录系数维护动态信息：ZR2612 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132255084 http://zhengruioi.com/problem/2612 ai+bj≥0a_i+b_j\ge 0ai​+bj​≥0 => ai≥−bja_i\ge -b_jai​≥−bj​ 因此考虑把 bbb 去负， ai≥bja_i\ge b_jai​≥bj​ 也就是一个区间 aaa 最小值大于 bbb 最大值 套路1 （大小关系转不同） 对于此...

对平移类dp用数据结构优化：ZR2617 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132240791 http://zhengruioi.com/problem/2617 对于此类dp式子： dpi,j=∑dpk,j−w(k,i)dp_{i,j}=\sum dp_{k,j-w(k,i)} dpi,j​=∑dpk,j−w(k,i)​ 暴力计算为 O(n3)O(n^3)O(n3) ，但如果 w(j,i)w(j,i)w(j,i) 在 w(j,i−1)w(j,...