D OR  链接：D-OR_2021牛客暑期多校训练营8 (nowcoder.com) 题意：给定你序列，其中。求符合条件的序列有多少种 首先：，定义，其中 可以看出，对的比特位值进行了限定。当我们给定时，可以依靠上述序列，直接确定后续的所有（），以此并反推给定的是否合法。所以我们去考虑枚举，依靠和，去位枚举​的每一个数位，确定合法性并统计答案 对于任意位下，设为在连锁下确定的当前位为的可能。设，表示在递推确定时，序列前一位确定下来的数位是否能够为，设，表示当前序***定，当前这位是否能够为​​。则有下表：（牛客表格有问题就只能传图片了）  这里特别解释一下​的情况：这个情况确定了和必有一个为...

K Yet Another Problem About Pi  链接：K-Yet Another Problem About Pi_2021牛客暑期多校训练营8 (nowcoder.com) 题意：平面上有无穷个长，宽为的矩形方格。你有一条长度为​的曲线可以任意弯折，起点任意，求曲线最多经过的方格数目（不计边界） 先考虑最坏情况：对应时，我们不能越过任何一个方格，此时我们的最佳方案应该是以四个矩形方格的交点为起点，向周围走一圈，最小结果为4     如果我们能够越过方格，我们可以认为以下的所有情况都是有上方（结果为4）的情况推广而来，因为上述拿法是开局最佳。并且因为是无限循环小数，我们可以认为...

E 简洁的数  题意：给定区间，求区间内不超过个数位在间的数有多少个 区间，将区间转换为求解，但是因为这里，所以这样转换不太方便。注意到判断单个数是否合法比较容易，就可以转换为，并且单独判定是否合法。 对于判定区间中有多少合法的数，我们去从高到低去枚举数位，并判定合法情况计数 将按数位从低到高分解，并且存入中，其中代表第位的数位，代表第位时，有个非的数的数字的个数 从高到低去枚举数位，设当前枚举的位为，为了确保枚举的数小于，我们需要知道枚举的位上的数字是否等于，若不等于，则位的数可以取，否则取 对于没有任何限制的数，我们将其记忆化使用。反之直接枚举   #include <bits/st...

A 简单数学  题意：给一个正整数，问n是否存在，使得能整除，并且是奇数？ 签到题，多琢磨一下就能知道做法：判定是否是2的幂次，不是则有解 这里是正经的推导： 设为正整数，为质数，则由唯一分解定理： 我们知道，除2之外，所有的质数都是奇数。也就是说，要想在中找到奇数因子，只需要有除2之外的质数即可 所以直接判定是否为2的幂次即可 判定2的幂次可使用判定，若结果为0，则为2的幂次   #include <bits/stdc++.h> using namespace std; signed main() { long long n; while(cin >> n) { pu...

小圆前辈的数组  题意：求连续子序列的满足有多少个 两个条件中任意一种都很好解决 ，可以用前缀和优化，枚举起点，然后二分终点就可以求出序列个数  可以前缀和取模，然后放入桶中优化，结果就是（也就是取的倍数 + 取的情况（此时多出来的能减掉））  当两个条件在一起的时候，我们考虑先满足一个情况，然后再去满足另外一个情况。这里先去满足的情况 先将前缀和取模处理，再将其对应的前缀和的值存入桶内，即 中加入。显然的是，在桶内数字单调递增。所以枚举起点，然后二分终点统计  #include <bits/stdc++.h> #define sc(x) scanf("%lld", &(x...

小圆前辈的暴力枚举  思路：或者排列组合，这里选择求解 设为行为 列为 的方案数目 初始化：  当仅有行或列时，方案数明显是全不放+每个格子放一次，即种可能  即 ：，其中  否则，对于有行列的格子而言：  选择最后一行，有种选法（即每个格子选一边，但是仅能选一个），选择一个后，剩下能放的格子，除去本行、列外，还有行列 不选择最后一行：即为选取行列的方案数  所以：，记得取模即可  #include <bits/stdc++.h> #define endl '\n' typedef long long ll; typedef unsigned long long ull; usin...

替罪羊树  前置知识：二叉搜索树（建议没学过的先去学，很多操作都只有小修改，会更容易理解） 替罪羊树是基于权值，由暴力重构实现并保证平衡的的一颗二叉搜索树。其基本是依靠因子暴力重构实现平衡。并且它与普通的二叉搜索树的不同还有：二叉搜索树是将相同值放入一个节点并统计出现次数，而替罪羊树为了重构操作，将相同值的元素分别分配一个节点，以便于重构时操作 注意：以下所有的区间操作均为闭区间操作，请注意范围。并且所有的游标均为范围有效，节点默认不使用。并且会频繁使用传引用，请务必看清楚使用区域。并且根节点有可能变化，不一定恒为节点，所以请使用变量记录根节点编号 基础变量名如下：  int n, root;...

试题A :门牌制作  题意：计算1——2020有多少个2出现 直接暴力跑一边统计就好  #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 7; const int mod = 1000000009; typedef long long ll; int cnt(int x) { int re = 0; while(x) { if(x % 10 == 2) ++re; x /= 10; }return re; } signed main() { ll ans = 0; for(int i = 1; i &l...

试题 A: 组队  题意：在给定的20个人中，分别选五个人放到五个不同位置上，使得最后权值最大 暴力就完事了，对个位置进行，并在搜索过程中记录最大值即可。当然也可以五重循环暴力跑一下  #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 7; const int mod = 1000000009; typedef long long ll; vector<int> id[7]; bitset<32> vis; int ans = 0; void dfs(int s, int val...

解析  题意：求2000/5/4是当年的第几天  明显的是判断闰年的题，判断闰年： 可知2000年为闰年，所答案为：31 + 29 + 31 + 30 + 4。即  #include<bits/stdc++.h> using namespace std; signed main() { cout << 31 + 29 + 31 + 30 + 4; return 0; }   题意：给你待解密的共10个汉字，每个汉字由16个8位有符号整数组成，将其转换为点阵格式，输出题目要求  由题意可知，每个字节8位，一行2个字节，一个汉字由16 * 16 的点阵构成，将其每一位提取出...