DAY16共3题:
奇♂妙拆分(简单数学)
区区区间间间(单调栈)
小AA的数列(位运算dp)
? 作者:Eriktse
? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?
? 阅读原文获得更好阅读体验:https://www.eriktse.com/algorithm/1119.html
奇♂妙拆分(简单数学)
根据贪心的想法,若要使得因子尽可能多,那么因子应当尽可能小,大于根号n的因子至多一个,从小到大枚举[1, sqrt(n)]的所有整数,如果i
能够整除n
就作为一个因子。
Code:
#include #define int long longusing namespace std;void solve(){ int n;cin >> n; set st; for(int i = 1;i <= n / i; ++ i) if(n % i == 0)st.insert(i), n /= i; st.insert(n); cout << st.size() <> _; while(_ --)solve(); return 0;}
区区区间间间(单调栈)
题意:给定一个数组,求所有子区间的最大值与最小值的差的和。
如果暴力枚举肯定不行,单单是子区间个数就有n ^ 2
个,所以我们应该考虑每一个元素对答案的贡献,也就是说我们需要知道某个元素a[i]
它会在多少个区间里作为最大值,在多少个区间里作为最小值。
我们预处理出四个数组,分别是lmax[], rmax[], lmin[], rmin[]
表示点i
作为最大值的左右最远位置,和作为最小值的左右最远位置(lmax[i] = j
,表示在区间[j, i]
中的最大值都是a[i]
,其他的三个数组类似定义)。
用单调栈可以处理出这四个数组,一下以求lmax[]
举例,维护一个单调不增栈,栈内存放的是下标。
初始时栈内仅有一个a[0] = inf
。
当我们遇到一个a[i]
时,不断地判断栈顶元素,如果栈顶元素比a[i]
小,说明这个栈顶应当弹出。
当更新完毕后,此时的栈顶的右边相邻位置就是a[i]
往左的最远的位置了,因为此时栈顶是a[i]
往左的第一个大于等于a[i]
的位置,那么这中间的元素都会小于a[i]
。
其他的三个数组类似,注意,如果我们处理lmax
用的是单调不增栈,那么处理rmax
就应当用单调递增栈,而不是单调不减栈,否则可能出现区间重复表示或没有归属的问题(自己思考)。
Code:
#include #define int long longusing namespace std;const int N = 1e5 + 9, inf =8e18;int a[N], stk[N], top, lmax[N], rmax[N], lmin[N], rmin[N];void solve(){ int n;cin >> n; for(int i = 1;i > a[i]; a[0] = a[n + 1] = inf; top = 0; stk[++ top] = 0; for(int i = 1;i a[stk[top]])top --; lmax[i] = stk[top] + 1; stk[++ top] = i; } top = 0; stk[++ top] = n + 1; for(int i = n;i >= 1; -- i) { while(top && a[i] >= a[stk[top]])top --; rmax[i] = stk[top] - 1; stk[++ top] = i; } a[0] = a[n + 1] = -inf; top = 0; stk[++ top] = 0; for(int i = 1;i <= n; ++ i) { while(top && a[i] = 1; -- i) { while(top && a[i] <= a[stk[top]])top --; rmin[i] = stk[top] - 1; stk[++ top] = i; } int ans = 0; for(int i = 1;i <= n; ++ i) { ans += a[i] * (rmax[i] - i + 1) * (i - lmax[i] + 1); ans -= a[i] * (rmin[i] - i + 1) * (i - lmin[i] + 1); } cout << ans <> _; while(_ --)solve(); return 0;}
小AA的数列(位运算 | 前缀和)
这道题一看有点懵,感觉不是很好处理,但依然是套路题。
看到异或,我们应该想把每一个二进制位拆分开,实际上这里约32位二进制位可以先认为是相互独立的,对于每一位都计算出贡献,然后按照位权重加和即可。
异或题的套路基本都是拆分二进制,整体考虑起来比较复杂,拆分后会简单很多。
先不管L, R
。
假如我们考虑数组1 2 3 4 5
的第0
位:
获取第0
位后得到b
数组:1 0 1 0 1
。
因为我们要得到区间内1
的个数,所以处理一个异或前缀和p[]
是自然而然的,然后我们枚举每一位作为左端点,看看会得到一个怎样的式子:
\[sum=\sum_{j=i + 1}^{j += 2, j \le n}p[j]\oplus p[i-1]\]
我们知道异或其实就是% 2
的加法,也是% 2
减法,所以我们将异或前缀和改为普通前缀和p[],以上的柿子可以转化为:
\[sum=\sum_{j=i + 1}^{j += 2, j \le n}[(p[j] – p[i-1]) (mod 2)]\]
那么我们就可以对p
再做一个前缀和p2
,但是p2
的步长应为2。
然后上面的柿子就等价于(其中l, r
为j
的上下限,需要保证与i - 1
奇偶性相同,j
的个数为(r - l + 2) / 2
):
\[sum=| p2[r] – p2[l – 1] – p[i – 1] * ((r – l + 2) / 2))|\]
因为这个p2
存在p2[-1]
的情况,所以我们做个小小的便宜,方便代码的编写(其实你想要特判也行,只是不太方便,也容易出错)。
注意一下其他细节即可。
Code:
#include #define int long longusing namespace std;const int N = 1e5 + 109, p = 1e9 + 7, T = 100;int a[N], b[N], p1[N], p2[N];signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n, l, r;cin >> n >> l >> r; for(int i = 1;i > a[i]; int ans = 0; for(int w = 0;w <= 32; ++ w) { for(int i = 1;i > w & 1; for(int i = 1;i <= n; ++ i)p1[T + i] = (b[i] + p1[T + i - 1]) % 2; for(int i = 1;i <= n; ++ i)p2[T + i] = p1[T + i] + p2[T + i - 2]; int sum = 0; for(int i = 1;i <= n; ++ i) { int j1 = max(i + 1, l + i - 1), j2 = min(n, r + i - 1); if((j1 - i) % 2 == 0)j1 ++; if((j2 - i) % 2 == 0)j2 --; if(j2 < j1)continue; sum += abs(p2[T + j2] - p2[T + j1 - 2] - p1[T + i - 1] * ((j2 - j1) / 2 + 1)); } ans = (ans + (1ll << w) * sum % p) % p; } cout << ans << '\n'; return 0;}
? 本文由eriktse原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?