【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.cnblogs.com/eriktse/p/17335906.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【ACM算法竞赛日常训练】DAY16【奇♂妙拆分】【区区区间间间】【小AA的数列】数学 | 位运算 | 前缀和 - Python技术站

(0)
上一篇 2023年4月20日
下一篇 2023年4月20日

相关文章

  • 简介二分查找算法与相关的Python实现示例

    下面是详细讲解“简介二分查找算法与相关的Python实现示例”的完整攻略。 二分查找算法 二分查找算法(Binary Search Algorithm)是一种常用的查找算法,用于在有序数组中查找指定元素。该算法的核心思想是将数组分成两份,判断目标元素在哪一部分中然后继续在该部分中查找,直到找到目标元素或者确定标元素不存在。 二分查找算法的时间复杂度为O(lo…

    python 2023年5月14日
    00
  • C语言线性表的顺序表示与实现实例详解

    C语言线性表的顺序表示与实现实例详解 1. 线性表的定义 线性表是一种线性结构,它是由n个数据元素(n≥0)组成的有限序列。当n=0时,我们称为一个空表。 在C语言中,我们可以通过数组来实现线性表的顺序表示,每个数据元素都存在数组的一个位置中,数组下标可以看作是该数据元素的位置。 2. 线性表的基本操作 一个线性表的基本操作有以下几种: 2.1 初始化线性表…

    数据结构 2023年5月17日
    00
  • Python实现的拉格朗日插值法示例

    下面是详细讲解“Python实现的拉格朗日插值法示例”的完整攻略。 1. 什么是拉格朗日插值法 拉格朗日插值法是一种通过已知数据点来估计未知数据点的方法。它基于拉格朗日多项式,通过构造一个多项式函数来逼近原始数据,从而实现插值。 2. 拉格朗日插值法原理 假设有n数据点$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$,其中$x_i$互不…

    python 2023年5月14日
    00
  • python3实现单目标粒子群算法

    下面是详细讲解“Python3实现单目标粒子群算法”的完整攻略,包括算法原理、Python实现和两个示例。 算法原理 粒子群算法是一种基于群体智能的优化算法,其主要思想是通过模拟鸟群或鱼群等群体的行为,寻找最优解。在单目标粒子群算法中,每个个体用一个向量表示,通过不断更新速度和位置,寻找最优解。 单目标粒子群算法的实现过程如下: 初始化粒子群,包括每个粒子的…

    python 2023年5月14日
    00
  • python中超简单的字符分割算法记录(车牌识别、仪表识别等)

    Python中超简单的字符分割算法记录 字符分割是图像处理中的一个重要问题,它的主要作用是将一张图像中的字符分割出来,以便进行后续的识别和处理。本文将介绍Python中超简单的字符分割算法,以及两个示例说明。 算法原理 Python中超简单的字符分割算法的基本思想是通过对图像进行二值化处理,然后对二值化后的图像进行连通域分析,最后根据连通域的位置和大小将字符…

    python 2023年5月14日
    00
  • EM算法的python实现的方法步骤

    以下是关于“EM算法的Python实现的方法步骤”的完整攻略: 简介 EM算法是一种常用的统计学习算法,用于估计含有隐变量的概率模型参数。在本教程中,我们将介绍如何使用Python实现EM算法,并提供两个示例。 方法步骤 EM算法的Python实现方法步骤如下: 初始化模型参数,包括隐变量的初始值和模型参数的初始值。 E步骤:根据当前模型参数和观测数据,计算…

    python 2023年5月14日
    00
  • 多维度深入分析Redis的5种基本数据结构

    多维度深入分析Redis的5种基本数据结构 Redis是一种高性能、内存数据存储系统,它支持多种数据结构,包括字符串、哈希表、列表、集合和有序集合。其中,每种数据结构都具有不同的特性和用途,本文将对这五种基本数据结构进行深入分析。 1. 字符串(string) 字符串是最基本的数据结构,一个字符串可以存储任意二进制数据,例如一个jpg图片或者一个序列化的对象…

    数据结构 2023年5月17日
    00
  • python动态规划算法实例详解

    下面是关于“Python动态规划算法实例详解”的完整攻略。 1. 动态规划算法简介 动规划算法是一种用于解决最优化的算法,它将问题分解为子问题,并使用递推的方式求解子问题的最优解,最终得到原问题的最优解。在Python中,我们可以使用动态规划算法来解决一些复杂的问题,例如背包问题、最长公共子序列问题等。 2. Python实现动态规划算法 2.1 背包问题 …

    python 2023年5月13日
    00
合作推广
合作推广
分享本页
返回顶部