【拾题杂谈】POJ3584 T-Shirt Gumbo
题面大秦 为你打开 题目传送门
题目翻译一场NOI比赛即将举行。现在有X名队员，要给该些队员发放T恤。每名队员有一个合适的T恤尺码区间，然后给出每种尺码T恤的数目，问是否每个队员能分配到合适的尺码T恤。
T恤尺码由小到大依次是S(小号)，M(中号)，L(大号)，X(特大号)，T(超特大号)。
思路那么显而易见的，这种队员和衣服对应的关系就是一张二分图，我们发现这里的 $N$ 实在是太太太小了，区区 $20$ ，我们直接用它给我们的区间大力建图，跑二分图最大匹配，搞定。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include<bits/stdc++.h>using namespace std;const int N = 510;const int M = ...
【算法介绍】二分图相关算法
算法简介：水中幻愿这是一篇关于二分图的全面讲解，里面会从二分图的基本介绍开始，到匈牙利算法的几个运用。二分图的大多数题目就是这些了。接下来我们就开始最最基础的讲解。
算法介绍：星命定轨二分图检验：灭绝的预言所谓二分图，主打一个二分。指的是如果一个图的点可以分为两个不重合的点集 $U,V$ ，且只有 $U,V$ 两个点集间有点连通，同一个点集内没有边连通的图。
那么首先，对于一张图，如果他没有环，他一定是 二分图。毕竟如果没有环，我只需要奇偶奇偶的分开就可以，都不需要担心会有环边在一个点集内。但是如果有环就不一样了，我们来看下面的两个图，分别代表的是奇环和偶环。
我们发现，对于偶环还是奇偶分点集没有问题。但是对于奇环，就不一样了，因为容斥原理，最后一定会多一个，而这个多出的一个，就会导致他会比偶环在某一个点集里有一条边相连，这样是不符合二分图条件的。所以说，验证二分图的本质其实就是判断奇环，奇偶染色。
12345678910111213141516int flag[N]; // 0 未走过 1 奇 2 偶Graph G;void Dfs(int u, int fa) { ...
【算法介绍】数位DP
算法简介：出发！火之国数位DP，字面意思上来讲，就是按位做 DP，他的原理是基于类似于前缀和的思想，统计 0 ~ n 这部分的某种数字然后利用前缀和思想求出一段区间内某种数字的算法。
算法演示：以燔燎铸名说实话，这是一个随机应变的算法，要更据题目给的数字用合适的方法计算数字，这里只能给出一点基础的建议。
我们思考，对于一个 $n$ 我们要制造出小于等于它的数字，怎么办？由于高位对于地位有绝对压制， 所以说如果当前位是 $P$ ，那么如果我选了数字 $i(i < P)$ ，那么往后的我们就可以随便选，如果 $i = P$ 我们还得继续考虑。
其次就是前导零。对于前导零我们还得开一个标记记录，如果前导零的标记还在，但是我们选了0，那这个是不算数的。
模板大概就是：
1234567891011121314151617int dp[50]; // DP数组// 当前到了哪一位（从高到低），是否还有限制，是否有前导零，等等要维护的变量ll Dfs(int len, int lim, int top, ...) { if(len == 0) { // 没了 ...
【拾题杂谈】517八段第四课D
题面题目链接大秦 为你打开 题目传送门
备用题面将一个数字水平倒置之后，如果和原来一样，那么它就是一个镜像数。
比如 0,1,8,101都是镜像数，而100，3 则不是。
询问区间 $[N,M]$ 里面有多少镜像数。
思路直接记录我们选择的数字一边递归一边做（因为要保证回文）其他的没什么了。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 50;char a[N], b[N];ll dp[N][N][2];char num[N];int tmp[N];inline void Input() { scanf("%s%s", a, b);}inline ll Dfs ...
【拾题杂谈】517八段第四课C
题面题目链接大秦 为你打开 题目传送门
备用题面定义平衡数：对于出现的数字，奇数数字出现偶数次，偶数数字出现奇数次。比如 77, 211, 6222 和 112334445555677 都是平衡数，而 351, 21, 和 662 都不是请统计 $[N,M]$ 区间内的平衡数的个数。
思路首先这是一道数位 DP 题。我们考虑统计每一种数字的出现次数（$0$ ~ $9$），但是肯定不可以直接统计数量，我们可以考虑进制压缩。我们这里使用 $3$ 进制，因为我们要考虑没有，有奇数，有偶数的情况。而不用二进制的原因是，没有和有偶数是不一样的。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101#include<bits/stdc++.h>usi ...
【拾题杂谈】517八段第四课B
题面题目链接大秦 为你打开 题目传送门
备用题面将 $N$ 到 $M$ 的数字依次写在一张纸上，问出现多少个 $0$ 。
思路就是一道数位DP板子题，不想说话了。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586// #pragma GCC optimize(2)// #pragma GCC optimize(3, "Ofast", "inline")#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef __int128 int128;namespace FastIO { // char buf[1 << 20], *p1, *p2; ...
【拾题杂谈】HDU3355 Bomb
题面大秦为你打开题目传送门
题目描述请统计从 $1$ 到 $N$ 的整数中有多少个包含 $49$ 。
例如：49315， 734949418， 8449814都是包含 $49$ 的整数。
但是，41159虽然含有 $4$ 和 $9$ ，但不是 $49$ 连号，所以不属于统计范围。
思路数位DP模板题。我们用 $\tt mask$ 表示当前格子的状态。
啥也没有
以四结尾
有 $49$ 。
这样子的话就可以正常的递归求解了。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182// #pragma GCC optimize(2)// #pragma GCC optimize(3, "Ofast", "inline")#include<bits/stdc++.h>using ...
【拾题杂谈】HDU4288 Coder
题面大秦为你打开题目传送门
题目描述一个集合 $S$ ，初始为空。现有三个操作：
$add$ ：向集合里加入数 $x$ ，保证加入前集合中没有数 $x$ ；
$del$ ：从集合中删除数 $x$ ，保证删除前集合中有 $x$ ；
$sum$ ：设当前集合中有 $k$ 个数字，将集合中的数字进行升序排序，结果为 $a_1 <a_2 <a_3 <… <a_k$ 询问将集合里的数从小到大排序后，求 $\sum\limits_{ i \mod 5 = 3}^{i≤k} a_i$ 。
现有 $n$ 次操作，对于每个 $sum$ 操作，输出答案。
思路这道题目很简单，对于每次插入，维护这段区间模五以后的和（当然是权值线段树）
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889 ...
【拾题杂谈】517八段第三课K
题面题目链接大秦 为你打开 题目传送门
备用题面构造一个长度为n的非负整数序列 $a_1,a_2,a_3,…,a_n$ 。
使得其满足 $m$ 个限制条件，限制条件的形式为 $l,r,q$ ，表示 $a_l\ \&\ a_l+1\ \&\ …\ \&\ a_{r−1}\ \&\ a_r = q$ 。
思路首先要保证这些数字和起来等于 $q$ ，那么在做修改操作的时候得用或，而查询的时候要求按位和操作，所以合并用按位和。
代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120// #pragma GCC opt ...
【拾题杂谈】CF384E - Propagating tree
题面题目链接大秦 为你打开 题目传送门
题目翻译给定一棵点数为 $N$ 的树，节点从 $1$ 到 $N$ 编号，以点 $1$ 为根，每个点有权值。
对树进行 $M$ 个操作，操作有两种：
$1\ u\ val$ ：把节点 $u$ 的权值增加 $val$ ，$u$ 的儿子节点权值增加 $−val$ ，$u$ 的儿子的儿子的节点权值增加 $−(−val)$ ，依此类推。
$2\ u$ ：查询节点 $u$ 的权值。
思路这个加减加减的，很不好处理，网上大多数做法都是维护两颗线段树，这里提供一个不一样的做法。
我们考虑让深度为奇数的根的子树修改的时候直接加 val，偶数的直接减去 val。这样我们就消除了所加的子树根结点深度不同的问题，所以我们的懒标记就可以合并了。
因为先前我们对深度不同的结点做出的调整，所以最后我们只需要在访问到每个点的时候判断一下深度的奇偶性，对应的加减就行了。
代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545 ...
