企业网站的建设多少钱,设计素材网站哪个最好用,百度关键词优化多少钱,黑客是如何攻击网站的因为只有std#xff0c;没有自我实现#xff0c;所以是无码专区
主要是为了训练思维能力
solution才是dls正解#xff0c;但是因为只有潦草几句#xff0c;所以大部分会有我自己基于正解上面的算法实现过程#xff0c;可能选择的算法跟std中dls的实现不太一样。
std可能…因为只有std没有自我实现所以是无码专区
主要是为了训练思维能力
solution才是dls正解但是因为只有潦草几句所以大部分会有我自己基于正解上面的算法实现过程可能选择的算法跟std中dls的实现不太一样。
std可能也会带有博主自己的注释。
problem
给定 nnn 个数选择一个子集然后加起来统计十进制结果数位表示中有多少个 444。
对所有的 2n2^n2n 种方案都统计一边计算总和。
n≤40,ai≤44444444n\le 40,a_i\le 44444444n≤40,ai≤44444444。
时限1s256MS1s\ 256MS1s 256MS 我的想法
这种计数类题目一般是两条线。
差分然后数位 dpdpdp。每一位单独求解计算贡献即每一位的贡献乘以这一位所在的合法情况数。
本题的 nnn 非常小而这种 nnn 一般都是折半搜索的标志。
但是我不知道怎么处理低位进位导致高位数字改变这就导致了无法抽离子集本身进行求解必须放在具体的两个子集内才能计数。 solution
折半搜索每一位分开统计答案。
假设计算第 kkk 位为 444 的贡献。
结论考虑两边各取一个数分别为 s,ts,ts,t求和为 www如果 www 对 10k110^{k1}10k1 取模后最高位是 444那么一定满足 s,ts,ts,t 分别对 10k110^{k1}10k1 取模后再加起来的结果属于 [4×10k,5×10k)[4\times 10^k,5\times 10^k)[4×10k,5×10k) 或 [14×10k,15×10k)[14\times 10^k,15\times 10^k)[14×10k,15×10k)。
将左右两边按 10k110^{k1}10k1 取模后升序排序指针线性扫描即可。
直接排序时间复杂度 O(2n2nlogm)O(2^{\frac{n}{2}}n\log m)O(22nnlogm)比较悬。
考虑优化将 kkk 从小到大进行计算。
每次排序相当于是在取模 10k10^k10k 的基础上加上了最高位。
用类似于双关键字的基排做法在 O(2n2)O(2^{\frac{n}{2}})O(22n) 时间内解决。
总时间复杂度 O(2n2logm)O(2^\frac{n}{2}\log m)O(22nlogm)。
参考代码
#include bits/stdc.husing namespace std;
const int maxn 2e6 10;
struct node {long long l, r;
};
vectornode a, b, c[10], d[10];
int n, val[maxn];void solve(int *a, int k, vectornode b) {for (int i 0; i (1 k); i) {long long s 0;for (int j 0; j k; j)if (i (1 j))s a[j];b.push_back(node{s, 0});}
}long long get_jin0(vectornode a, vectornode b, long long base) { //处理没有进位的答案int point b.size() - 1;long long ans 0;for (int i 0; i a.size(); i) {while (point 0 a[i].r b[point].r base)point--;ans (point 1);}return ans;
}long long get_jin1(vectornode a, vectornode b, long long base) { //处理进位后的使当前位为4的答案int point 0;long long ans 0;int siz b.size();for (int i a.size() - 1; i 0; i--) {while (point siz - 1 a[i].r b[point].r base)point;ans (b.size() - point);}return ans;
}int main() {freopen(four.in, r, stdin);freopen(four.out, w, stdout);scanf(%d, n);for (int i 1; i n; i)scanf(%d, val[i]);solve(val 1, n / 2, a);solve(val 1 n / 2, n - (n / 2), b);long long base 1, ans 0;for (int w 0; w 8; w) {for (int i 0; i 10; i)c[i].clear(), d[i].clear();for (int i 0; i a.size(); i)c[a[i].l % 10].push_back(node{a[i].l / 10, a[i].r});for (int i 0; i b.size(); i)d[b[i].l % 10].push_back(node{b[i].l / 10, b[i].r});for (int i 0; i 10; i) { //枚举左半边的和的当前位的数字int k1 (14 - i) % 10, k2 (13 - i) %10; //求右半边对应的和的当前位的数k1表示在不进位的情况下的值k2表示在后面有进位的情况下的需要的ans get_jin0(c[i], d[k1], base) get_jin1(c[i], d[k2], base);}int now 0;for (int i 0; i 10; i)for (int j 0; j c[i].size(); j)a[now] node{c[i][j].l, c[i][j].r i * base};now 0;for (int i 0; i 10; i)for (int j 0; j d[i].size(); j)b[now] node{d[i][j].l, d[i][j].r i * base};base * 10;}printf(%lld\n, ans);
}
