- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
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 <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n;cin >> n;
set<int> st;
for(int i = 1;i <= n / i; ++ i)
if(n % i == 0)st.insert(i), n /= i;
st.insert(n);
cout << st.size() << '\n';
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
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 <bits/stdc++.h>
#define int long long
using 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 <= n; ++ i)cin >> a[i];
a[0] = a[n + 1] = inf;
top = 0;
stk[++ top] = 0;
for(int i = 1;i <= n; ++ i)
{
while(top && a[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] < a[stk[top]])top --;
lmin[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 --;
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 << '\n';
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _;cin >> _;
while(_ --)solve();
return 0;
}
这道题一看有点懵,感觉不是很好处理,但依然是套路题.
看到异或,我们应该想把每一个二进制位拆分开,实际上这里约32位二进制位可以先认为是相互独立的,对于每一位都计算出贡献,然后按照位权重加和即可.
异或题的套路基本都是拆分二进制,整体考虑起来比较复杂,拆分后会简单很多.
先不管 L, R .
假如我们考虑数组 1 2 3 4 5 的第 0 位:
获取第 0 位后得到 b 数组: 1 0 1 0 1 .
因为我们要得到区间内 1 的个数,所以处理一个异或前缀和 p[] 是自然而然的,然后我们枚举每一位作为左端点,看看会得到一个怎样的式子:
我们知道异或其实就是 % 2 的加法,也是 % 2 减法,所以我们将 异或前缀和改为普通前缀和p[] ,以上的柿子可以转化为:
那么我们就可以对 p 再做一个前缀和 p2 ,但是 p2 的步长应为2.
然后上面的柿子就等价于(其中 l, r 为 j 的上下限,需要保证与 i - 1 奇偶性相同, j 的个数为 (r - l + 2) / 2 )
因为这个 p2 存在 p2[-1] 的情况,所以我们做个小小的便宜,方便代码的编写(其实你想要特判也行,只是不太方便,也容易出错).
注意一下其他细节即可.
Code
#include <bits/stdc++.h>
#define int long long
using 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 <= n; ++ i)cin >> a[i];
int ans = 0;
for(int w = 0;w <= 32; ++ w)
{
for(int i = 1;i <= n; ++ i)b[i] = a[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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬 。
最后此篇关于【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学|位运算|前缀和的文章就讲到这里了,如果你想了解更多关于【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学|位运算|前缀和的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我是一名优秀的程序员,十分优秀!