【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和

这篇具有很好参考价值的文章主要介绍了【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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;
}

小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, rj的上下限,需要保证与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 <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原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞👍、收藏⭐、留言💬文章来源地址https://www.toymoban.com/news/detail-419201.html

到了这里,关于【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Day 36 贪心算法 part05 : 435. 无重叠区间 763.划分字母区间 56. 合并区间

    56. 合并区间 以数组  intervals  表示若干个区间的集合,其中单个区间为  intervals[i] = [starti, endi]  。请你合并所有重叠的区间,并返回  一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间  。 示例 1: 示例 2: 提示: 1 = intervals.length = 104 intervals[i].length == 2 0 =

    2024年02月09日
    浏览(50)
  • 每日算法打卡:连号区间数 day 18

    1210. 连号区间数 题目难度:简单 题目来源:第四届蓝桥杯省赛C++ B组,第四届蓝桥杯省赛Java B组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1 ∼ N 1 sim N 1 ∼ N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [ L , R ] [L, R] [ L , R ] 里的

    2024年01月19日
    浏览(57)
  • 【LeetCode题目详解】第八章 贪心算法 part05 435. 无重叠区间 763.划分字母区间 56. 合并区间 (day36补)

    给定一个区间的集合  intervals  ,其中 intervals[i] = [starti, endi]  。返回 需要移除区间的最小数量,使剩余区间互不重叠  。 示例 1: 示例 2: 示例 3: 提示: 1 = intervals.length = 105 intervals[i].length == 2 -5 * 104 = starti  endi = 5 * 104 相信很多同学看到这道题目都冥冥之中感觉要排序,但

    2024年02月11日
    浏览(49)
  • 算法训练第四十一天|343. 整数拆分 、96.不同的二叉搜索树

    题目链接:343. 整数拆分 参考:https://programmercarl.com/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.html 题目描述 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。 示例 1: 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 示例 2: 输入:

    2023年04月24日
    浏览(41)
  • day31贪心算法 用最少数量的箭引爆气球 和无重叠区间

    题目描述 题目分析: x轴向上射箭,12一支,重叠的需要一支,3-8一支,7-16一支 返回2; 就是让重叠的气球尽量在一起,局部最优;用一支弓箭,全局最优就是最少弓箭; 如何去寻找重叠的气球?和记录弓箭数? 1.对所有气球排序;(左边界排序如上图); 2. if 如果第i个气

    2024年02月16日
    浏览(46)
  • 算法竞赛备赛之贪心算法训练提升,贪心算法基础掌握

    905.区间选点 给定N个闭区间[ai, bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量,位于区间端点上的点也算作是区间内。 将每个按区间的右端点从小到大排序 从前往后依次枚举每个区间 如果当前区间中已经包含点,则直

    2024年02月08日
    浏览(35)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(47)
  • 算法竞赛备赛之经典基础算法训练提升,暑期集训营培训

      目录 1.排序 1.1.快速排序 1.2.归并排序 2.二分 2.1.整数 2.2.浮点数 3.高精度 3.1.高精度加法 3.2.高精度减法 3.3.高精度乘法 3.4.高精度除法 4.前缀和 5.差分 6.双指针算法 7.位运算 8.离散化 8.1.unique函数实现 9.区间合并 快速排序的基本思想来自于分治。 首先,确定分界点的方法:

    2024年02月15日
    浏览(46)
  • 算法 DAY45 动态规划07 70. 爬楼梯 322. 零钱兑换 279. 完全平方数 139. 单词拆分 多重背包

    和377. 组合总和 Ⅳ (opens new window)基本就是一道题了。 本题代码不长,题目也很普通,但稍稍一进阶就可以考察完全背包 动态规划五部曲 1、确定dp[j]的含义 dp[j] 凑成 j 的最少硬币的个数 2、确定递推公式 比如想凑成3, 如果手里有1,那么最小个数就是dp[2]+1 如果手里有2,那

    2024年02月02日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包