代码编织梦想

一、AcWing 4645. 选数异或(中等)

题目描述

给定一个长度为 n 的数列 A1,A2,⋅⋅⋅,An 和一个非负整数 x,给定 m 次查询,每次询问能否从某个区间 [l,r] 中选择两个下标不同的数使得他们的异或等于 x。

输入格式

输入的第一行包含三个整数 n,m,x。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An
接下来 m 行,每行包含两个整数 li,ri 表示询问区间 [li,ri]。

输出格式

对于每个询问,如果该区间内存在两个数的异或为 x 则输出 yes,否则输出 no

数据范围

对于 20% 的评测用例,1 ≤ n,m ≤ 100
对于 40% 的评测用例,1 ≤ n,m ≤ 1000
对于所有评测用例,1 ≤ n,m ≤ 100000,0 ≤ x < 220,1 ≤ li ≤ ri ≤ n,0 ≤ Ai <220

输入样例

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

输出样例

yes
no
yes
no

样例解释

显然整个数列中只有 2,3 的异或为 1。

具体实现

1. 实现思路

  • 我们有 n 个数,然后在 n 个数当中进行 m 次询问(判断),每次询问给一个区间,判断这个区间是否有一对数的异或值等于 x,有的话输出 yes,没有的话输出 no
  • 由于 n,m 的数据范围是100000,因此,我们需要将时间复杂度控制在 O(nlogn)。
  • 首先发现 a ^ b = x -> a ^ x = b -> b ^ x = a,也就是我们只要先把 x 跟每个数的异或值 b 提前算出,如果我们知道的了 b,那么只要 b 在 l ~ r 的范围内就符合题意了。这时输出 Yes 即可。
  • 但是,直接暴力判断的话,要两层 for 循环,时间复杂度时 O(n2),不符合要求。
  • 如果在 l 到 r 当中存在,那么一定在 1 到 r 当中存在(用于缩减询问次数)。
  • 假设,fi 是在 ai 左边,与 ai 配对的最近的一个数,那么 fi 一定是小于 r 的,我们只需要判断 fi 是否大于 l 即可。因此,我们只需要寻找这个 i 。
  • 为了简便,我们可以设定一个数组 g[i] 用于表示 i 左边 fi 的最大值,只需要判断 g® 是否大于等于 l。

2. 实现代码

#include <bits/stdc++.h>

using namespace std;

// 1<<20 表示2的20次方,+10是为了防止溢出
const int N = 100010, M = (1 << 20) + 10; 

int n, m, x;
//last[M]表示每个数最后一次出现的位置
//g[N]表示用于表示 i 左边 f~i~ 的最大值
int last[M], g[N];

int main()
{
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i ++ )
    {
        int a;
        cin >> a;

        //如果一个数字没有出现过,last数组是全局变量,就是0
        //递归
        g[i] = max(g[i - 1], last[a ^ x]);
        //更新last
        last[a] = i;
    }

    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        if (g[r] >= l) 
        {
            puts("yes");
        }
        else
        {
            puts("no");
        }
    }
    
    system("pause");
    return 0;
}

二、AcWing 4644. 求和(简单)

题目描述

给定 n 个整数 a1,a2,⋅⋅⋅,an,求它们两两相乘再相加的和,即
S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+an−1⋅an

输入格式

输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋅⋅⋅,an

输出格式

输出一个整数 S,表示所求的和。
请使用合适的数据类型进行运算。

数据范围

对于 30% 的数据,1 ≤ n ≤ 1000,1 ≤ ai ≤ 100。
对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000。

输入样例

4
1 3 6 9

输出样例

117

具体实现

1. 实现思路

  • 如果直接采取暴力做法两个 for 循环直接会超时,因此,需要进行优化。
  • 可以使用前缀和或者推导公式两种方法,递推公式整体比较复杂,在此不做过多叙述。
  • 前缀和详见博文 基础算法-前缀和

2. 实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n;
int a[N];

int main()
{
    cin >> n;

    long long sum = 0;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        sum += a[i];
    }

    long long res = 0, cnt = 0;   
    for(int i = 1; i <= n; i ++ )
    {
        cnt += a[i];
        res += a[i] * (sum - cnt);
    }

    cout << res << endl;
    system("pause");
    return 0;
}

三、AcWing 4653. 数位排序(简单)

题目描述

小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。
当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。
例如,2022 排在 409 前面,因为 2022 的数位之和是 6,小于 409 的数位之和 13。
又如,6 排在 2022 前面,因为它们的数位之和相同,而 6 小于 2022。
给定正整数 n,m,请问对 1 到 n 采用这种方法排序时,排在第 m 个的元素是多少?

输入格式

输入第一行包含一个正整数 n。
第二行包含一个正整数 m。

输出格式

输出一行包含一个整数,表示答案。

数据范围

对于 30% 的评测用例,1 ≤ m ≤ n ≤ 300。
对于 50% 的评测用例,1 ≤ m ≤ n ≤ 1000。
对于所有评测用例,1 ≤ m ≤ n ≤ 106

输入样例

13
5

输出样例

3

样例解释

1 到 13 的排序为:1,10,2,11,3,12,4,13,5,6,7,8,9。
第 5 个数为 3。

具体实现

1. 实现思路

  • 不可以实时计算每一个数字的数位和,有可能会导致超时。
  • 因此,我们可以使用一个数组,将每个数的数位之和存储进去,然后使用快速排序即可。
  • 快速排序详见 基础算法-快速排序

2. 实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n, m;
int w[N], s[N];

bool cmp(int a, int b)
{
    if (s[a] != s[b]) 
    {
        return s[a] < s[b];
    }
    return a < b;
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
        w[i] = i;
        for (int j = i; j != 0; j /= 10)
        {
            s[i] += j % 10;
        }
    }

    sort(w + 1, w + n + 1, cmp);

    cout << w[m] << endl;
    system("pause");
    return 0;
}

四、AcWing 4655. 重新排序(中等)

题目描述

给定一个数组 A 和一些查询 Li,Ri,求数组中第 Li 至第 Ri 个元素之和。
小蓝觉得这个问题很无聊,于是他想重新排列一下数组,使得最终每个查询结果的和尽可能地大。
小蓝想知道相比原数组,所有查询结果的总和最多可以增加多少?

输入格式

输入第一行包含一个整数 n。
第二行包含 n 个整数 A1,A2,⋅⋅⋅,An,相邻两个整数之间用一个空格分隔。
第三行包含一个整数 m 表示查询的数目。
接下来 m 行,每行包含两个整数 Li、Ri,相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 30% 的评测用例,n,m ≤ 50;
对于 50% 的评测用例,n,m ≤ 500;
对于 70% 的评测用例,n,m ≤ 5000;
对于所有评测用例,1 ≤ n,m ≤ 105,1 ≤ Ai ≤ 106,1 ≤ Li ≤ Ri ≤ n。

输入样例

5
1 2 3 4 5
2
1 3
2 5

输出样例

4

样例解释

原来的和为 6+14=20,重新排列为 (1,4,5,2,3) 后和为 10+14=24,增加了 4。

具体实现

1. 实现思路

  • 首先,我们可以先统计一下每一位数在答案当中会加多少次。
  • 具体方法可以通过差分实现,当 l 到 r 这段区间被求和时,就 将 bl 加上 1,br+1 减去 1 就可以了。具体详见 基础算法-差分
  • 然后,重新排列,使得最大的相互对应,按照顺序去配对。
  • 求和的过程就是前缀和的步骤,具体详见 基础算法-前缀和

2. 实现代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
//w[N]表示原数组
//s[N]表示记录被加次数的数组
int w[N], s[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> w[i];
    }

    cin >> m;
    while (m -- )
    {
        int l, r;
        cin >> l >> r;
        s[l] ++, s[r + 1] -- ;
    }

    //对原数组求前缀和
    for (int i = 1; i <= n; i ++ )
    {
        s[i] += s[i - 1];
    }

    //最初的总和
    LL sum1 = 0;
    for (int i = 1; i <= n; i ++ )
    {
        sum1 += (LL)s[i] * w[i];
    }

    //重新排序后的总和
    LL sum2 = 0;
    sort(s + 1, s + n + 1);
    sort(w + 1, w + n + 1);
    for (int i = 1; i <= n; i ++ )
    {
        sum2 += (LL)s[i] * w[i];
    }

    cout << sum2 - sum1 << endl;
    system("pause");
    return 0;
}

五、AcWing 4652. 纸张尺寸(简单)

题目描述

在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm,将 A0 纸沿长边对折后为 A1 纸,大小为 841mm×594mm,在对折的过程中长度直接取下整(实际裁剪时可能有损耗)。
将 A1 纸沿长边对折后为 A2 纸,依此类推。
输入纸张的名称,请输出纸张的大小。

输入格式

输入一行包含一个字符串表示纸张的名称,该名称一定是 A0、A1、A2、A3、A4、A5、A6、A7、A8、A9 之一。

输出格式

输出两行,每行包含一个整数,依次表示长边和短边的长度。

输入样例 1

A0

输出样例 1

1189
841

输入样例 2

A1

输出样例 2

841
594

具体实现

1. 实现思路

  • 只需要依次递推计算即可,中间需要注意长边和短边的变换。
  • 当 x 小于 y 的时候,下一次就是 y 折半,为了方便,这里直接将 x 与 y 交换即可。

2. 实现代码

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    char s;
    cin >> s >> n;
    int x = 1189, y = 841;
    while (n -- )
    {
        x /= 2;
        if (x < y)
        {
            swap(x, y);
        }
    }

    cout << x << endl << y << endl;
    system("pause");
    return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_45891612/article/details/128731001

AcWing寒假每日一题——Day6剪绳子-爱代码爱编程

680剪绳子 一、题目描述 有 N 根绳子,第 i 根绳子长度为   L i \ L_i

寒假每日一题打卡day6—— AcWing 680. 剪绳子-爱代码爱编程

【题目描述】 AcWing 680. 剪绳子 【思路】 实数二分法 import java.util.Scanner; public class Main{ static int N = 100010; static int a[] = new int[N]; static double n,m; public st

寒假每日一题打卡day10—— AcWing 1208. 翻硬币-爱代码爱编程

【题目描述】: AcWing 1208. 翻硬币 【思路】 题目说一定有解,那只要将原状态往目标状态翻就一定可以达到要求。 import java.util.Scanner; public class Main{ public static void change(char [] c1,int i){ if(c1[i]=='*'

寒假每日一题打卡day16——AcWing 1381. 阶乘-爱代码爱编程

【题目】 AcWing 1381. 阶乘 大整数类硬算 看了数据规模,N最大1k,大整数类硬算。Java选手的福利。 import java.math.BigInteger; import java.util.Scanner; public class Main{ public static void main(String[] args

寒假每日一题打卡day22——ACWing126. 最大的和-爱代码爱编程

【题目描述】 ACWing 126. 最大的和 import java.util.Scanner; class Main{ static int N = 110; public static void main(String args[]){ Scanner reader = new Scanner(System.in

寒假每日一题打卡day23——AcWing 426. 开心的金明-爱代码爱编程

【题目描述】 AcWing 426. 开心的金明 动态规划 【思路】 01背包,二维数组f[i][j], 第一维度表示物品,第二维度表示钱数,f[i][j]表示前i种物品中价格不超过j的最大目标值。 import java.io.*; import java.lang.Math; class Main{ static int N = 300

寒假每日一题打卡day1——ACWing 104. 货仓选址-爱代码爱编程

【题目描述】 ACWing 104. 货仓选址 TLE代码 import java.io.*; import java.lang.Math; class Main{ static int N = 100010; public static void main(String args[])throws Exception{

寒假每日一题打卡day28——AcWing 428. 数列-爱代码爱编程

【题目描述】AcWing 428. 数列 【思路】 N=1 ----> 1 ----> 3^0 N=2----> 10 ----> 3^1 N=3----> 11 ----> 3^0+3^1 N=4----> 100 ----> 3^2 N=5----> 101 ----

寒假每日一题打卡day32—— ACWing 458. 比例简化-爱代码爱编程

【题目描述】【思路】 枚举 欧几里得定理 L在100以内,枚举 A′(a), B′(b)的所有组合,判断: a和b是否互质A / B <= a / b且a/b−A/B的值尽可能小实际上不需要判断互质,因为a,b都是从 1开始枚举的,如果a,b不互质,那么一定存在最大公约数c,也就是说存在比a、b更小的数a/c和b/c满足。所以最后不管如何都不可能取

寒假每日一题打卡day33—— AcWing 441. 数字统计-爱代码爱编程

【题目描述】 AcWing 441. 数字统计 【思路】 枚举 分离数字 import java.io.*; class Main{ public static void main(String args[])throws Exception{ BufferedReader bf = new BufferedReader(ne

寒假每日一题打卡day38——AcWing 3203. 画图-爱代码爱编程

【题目描述】AcWing 3203. 画图 【思路】 模拟 统计出现次数大于等于1的方块个数即可 import java.io.*; public class Main{ static int N = 105; static int a[][] = new int[N][N]; public static void main(S

acwing -爱代码爱编程

文章目录 一、AcWing 4261.孤独的照片(简单)1. 实现思路2. 实现代码 二、AcWing 3400.统计次数(简单)1. 实现思路2. 实现代码 三、AcWing 4366. 上课睡觉