祝馀宫

题面题目链接大秦 为你打开 题目传送门 备用题面将一个数字水平倒置之后，如果和原来一样，那么它就是一个镜像数。 比如 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 ...

题面题目链接大秦 为你打开 题目传送门 备用题面定义平衡数：对于出现的数字，奇数数字出现偶数次，偶数数字出现奇数次。比如 77, 211, 6222 和 112334445555677 都是平衡数，而 351, 21, 和 662 都不是请统计 $[N,M]$ 区间内的平衡数的个数。 思路首先这是一道数位 DP 题。我们考虑统计每一种数字的出现次数（$0$ ~ $9$），但是肯定不可以直接统计数量，我们可以考虑进制压缩。我们这里使用 $3$ 进制，因为我们要考虑没有，有奇数，有偶数的情况。而不用二进制的原因是，没有和有偶数是不一样的。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101#include<bits/stdc++.h>usi ...

题面题目链接大秦 为你打开 题目传送门 备用题面将 $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; ...

题面大秦为你打开题目传送门 题目描述请统计从 $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 ...

题面大秦为你打开题目传送门 题目描述一个集合 $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 ...

题面题目链接大秦 为你打开 题目传送门 备用题面构造一个长度为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 ...

题面题目链接大秦 为你打开 题目传送门 题目翻译给定一棵点数为 $N$ 的树，节点从 $1$ 到 $N$ 编号，以点 $1$ 为根，每个点有权值。 对树进行 $M$ 个操作，操作有两种： $1\ u\ val$ ：把节点 $u$ 的权值增加 $val$ ，$u$ 的儿子节点权值增加 $−val$ ，$u$ 的儿子的儿子的节点权值增加 $−(−val)$ ，依此类推。 $2\ u$ ：查询节点 $u$ 的权值。 思路这个加减加减的，很不好处理，网上大多数做法都是维护两颗线段树，这里提供一个不一样的做法。 我们考虑让深度为奇数的根的子树修改的时候直接加 val，偶数的直接减去 val。这样我们就消除了所加的子树根结点深度不同的问题，所以我们的懒标记就可以合并了。 因为先前我们对深度不同的结点做出的调整，所以最后我们只需要在访问到每个点的时候判断一下深度的奇偶性，对应的加减就行了。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545 ...

题面大秦为你打开题目传送门 题目描述在 $2016$ 年，佳媛姐姐喜欢上了数字序列。因而她经常研究关于序列的一些奇奇怪怪的问题，现在她在研究一个难题，需要你来帮助她。 这个难题是这样子的：给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种： 0 l r 表示将区间 $[l,r]$ 的数字升序排序 1 l r 表示将区间 $[l,r]$ 的数字降序排序 注意，这里是对下标在区间 $[l,r]$ 内的数排序。最后询问第 $q$ 位置上的数字。 输入格式输入数据的第一行为两个整数 $n$ 和 $m$，$n$ 表示序列的长度，$m$ 表示局部排序的次数。 第二行为 $n$ 个整数，表示 $1$ 到 $n$ 的一个排列。 接下来输入 $m$ 行，每一行有三个整数 $\text{op},l,r$，$\text{op}$ 为 $0$ 代表升序排序，$\text{op}$ 为 $1$ 代表降序排序, $l,r$ 表示排序的区间。 最后输入一个整数 $q$，表示排序完之后询问的位置 输出格式输出数据仅有一行，一个整数，表示按照 ...

题面大秦为你打开题目传送门 题目描述有一棵点数为 $N$ 的树，以点 $1$ 为根，且树有点权。然后有 $M$ 个操作，分为三种： 操作 $1$：把某个节点 $x$ 的点权增加 $a$。 操作 $2$：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$。 操作 $3$：询问某个节点 $x$ 到根的路径中所有点的点权和。 输入格式第一行包含两个整数 $N,M$。表示点数和操作数。接下来一行 $N$ 个整数，表示树中节点的初始权值。接下来 $N-1$ 行每行两个正整数 $\mathit{from},\mathit{to}$， 表示该树中存在一条边 $(\mathit{from},\mathit{to})$。再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类，之后接这个操作的参数。 输出格式对于每个询问操作，输出该询问的答案。答案之间用换行隔开。 样例 #1样例输入 #112345678910115 51 2 3 4 51 21 42 32 53 31 2 13 52 1 23 3 样例输出 #11236913 提示对于 $100\%$ 的数据，$1\le ...