蓝桥杯模拟赛

First Post:

Last Update:

小郑的蓝桥平衡串

问题描述

平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。

例如，$ababab$ 和 $aababb$ 都是平衡串，因为每种字符各有三个，而 $abaab$ 和 $aaaab$ 都不是平衡串，因为它们的字符数量不相等。

平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。

小郑拿到一个只包含 $L$、$Q$ 的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中 $L$、$Q$ 的数量相等。

输入格式

输入一行字符串，保证字符串中只包含字符 $L$、$Q$。

输出格式

输出一个整数，为输入字符串中最长平衡串的长度。

样例输入

1
LQLL

样例输出

1
2

评测数据规模

对于所有评测数据，输入字符串的长度 $len \le 1000$。

运行限制

语言 最大运行时间 最大运行内存
C++ 1s 256M
C 1s 256M
Java 2s 256M
Python3 3s 256M
PyPy3 3s 256M
Go 3s 256M
JavaScript 3s 256M

解题答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import os
import sys
from itertools import accumulate
def get_presum(a):
  sum=list(accumulate(a))
  return sum
def get_sum(sum,l,r):
  if l==0:
    return sum[r]
  else:
    return sum[r]-sum[l-1]
s=input()
n=len(s)
a=[]
for x in s:
  if x=="L":
    a.append(1)
  else:
    a.append(-1)
sum=get_presum(a)
ans=0
for i in range(n):
  for j in range(i,n):
    if get_sum(sum,i,j)==0:
      ans=max(ans,j-i+1)
print(ans)

区间次方和

问题描述

给定一个长度为 $n$ 的整数数组 $a$ 以及 $m$ 个查询。

每个查询包含三个整数 $l,r,k$ 表示询问 $l \sim r$ 之间所有元素的 $k$ 次方和。

请对每个查询输出一个答案，答案对 $10^9+7$ 取模。

输入格式

第一行输入两个整数 $n,m$ 其含义如上所述。

第二行输入 $n$ 个整数 $a[1],a[2],…,a[n]$。

接下来 $m$ 行，每行输入三个整数 $l,r,k$ 表示一个查询。

输出格式

输出 $m$ 行，每行一个整数，表示查询的答案对 $10^9+7$ 取模的结果。

样例输入

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

样例输出

1
2
3
14
99
12

评测数据规模：

对于 $100$% 的评测数据：$1 \leq n,m \leq 10^5$ ，$1 \leq a[i] \leq 100$ ，$1 \leq l \leq r \leq n$ ，$1 \leq k \leq 5$ 。

运行限制

语言 最大运行时间 最大运行内存
C++ 1s 256M
C 1s 256M
Java 2s 256M
Python3 3s 256M
PyPy3 3s 256M
Go 3s 256M
JavaScript 3s 256M

总通过次数: 1770 | 总提交次数: 2005 | 通过率: 88.3%

难度: 简单 标签: 前缀和

解题答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import os
import sys

from itertools import accumulate
MOD=1000000007
def get_presum(a):
  sum=list(accumulate(a))
  sum=[x % MOD for x in sum]
  return sum
def get_sum(sum,l,r):
  if l==0:
    return sum[r]
  else:
    return (sum[r]-sum[l-1]+MOD)%MOD
n,m=map(int,input().split())
a=list(map(int,input().split()))
sum_list=[]
for i in range(1,6):
  sum_list.append(get_presum([x**i for x in a]))
for i in range(m):
  l,r,k=map(int,input().split())
  print(get_sum(sum_list[k-1],l-1,r-1))

蓝桥17160

问题描述

小 Z 喜欢盖印章。

有一天，小 Z 得到了一个 $n\times m$ 的网格图，与此同时，他的手上有两种印章（分别称为 A，B），如下图所示。

他想将这两种印章盖在这个网格图上。

由于小 Z 是一个有原则的人，他将按照以下规则进行操作。

  1. 每个印章所形成的图案的边必须和网格图边重合。
  2. 对于网格图上的每一个格子，最多只能被一个印章图案覆盖。
  3. 对于每个印章，可以将印章顺时针旋转 $90^{\circ},180^{\circ},270^{\circ}$。
  4. 印章的图案在网格图上必须是完整的。

给定小 Z 所盖完印章的网格图以及两种印章的使用次数 $K$，请你分别求出两种印章的使用次数。可以证明，在这种情况下二者的使用次数是唯一的。

数据保证存在一种方案达到要求。

具体例子可以参考样例。

输入格式

第一行包含三个正整数 $n ,m, K(2 \le n \times m \le 10^{6}, 0 \le K \le n \times m)$，具体意义如题面所示。

接下来有 $n$ 行长度为 $m$ 的 01 串，其中 1 表示这个位置被印章图案覆盖。否则表示这个位置没有被覆盖。

输出格式

输出两个整数，第一个整数为 A 出现的次数，第二个整数为 B 出现的次数。

样例输入1

1
2
3
4
3 3 3
110
110
110

xxxxxxxxxx15 1import os2import sys3​4# 请在此输入您的代码5n = int(input())6a = list(map(int, input().split()))7a.sort()8b = []9c = []10for i in range(n):11    if a[i] % 2 == 0:12        b.append(a[i])13    else:14        c.append(a[i])15print(“ “.join(map(str, c)),” “.join(map(str,b)))python

1
0 3

样例输入2

1
2
3
4
3 3 2
110
110
110

样例输出2

1
2 0

说明

上述样例如图所示：

运行限制

语言 最大运行时间 最大运行内存
C++ 1s 128M
C 1s 128M
Java 2s 128M
Python3 3s 128M
PyPy3 3s 128M
Go 3s 128M
JavaScript 3s 128M

奇偶排序

问题描述

小蓝所在的王国名为偶数王国，在他们王国中数字的比较通常按以下步骤进行：

  • 如果两个数字的奇偶性不同，那么偶数一定大于奇数。
  • 如果两个数字的奇偶性相同，则比较它们的实际数值大小。

现在给你一个正整数数组 AA，请你输出按照偶数王国规则从小到大排序后的 AA。

输入格式

第一行输入一个整数 N(1≤N≤103)N(1≤N≤103) 表示数组 AA 的长度。

第二行输入 NN 个整数 A1,A2,A3,⋯ ,AN(1≤Ai≤105)A1,A2,A3,⋯,AN(1≤Ai≤105) 表示数组 AA。

输出格式

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

样例输入

1
2
5
1 2 3 4 5

样例输出

1
1 3 5 2 4

解题思路

解法1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import os
import sys

# 请在此输入您的代码

n = input()
str_n = map(int,input().split())
list_a = []
list_b = []
for i in str_n:
    if i%2==0:
        list_b.append(i)
    else:
        list_a.append(i)
list_a.sort()
list_b.sort()
print(" ".join(map(str,list_a))+" "+" ".join(map(str,list_b)))

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import os
import sys

# 请在此输入您的代码
a=input()
b=list(map(int,input().split()))
c=[]
d=[]
for i in range(len(b)):
    if b[i]%2==0 and b[i]!=0:
        c.append(b[i])
    else:
        d.append(b[i])
c.sort()
d.sort()
e=d+c
f=' '.join(map(str,e))
print(f)

解法3：

1
2
3
4
5
6
7
8
9
10
11
12
13
n=int(input())
nums=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
  if nums[i]&1:
    a.append(nums[i])
  else:
    b.append(nums[i])
a.sort()
b.sort()
c=a+b
print(*c)

解法4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import os
import sys

# 请在此输入您的代码
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = []
c = []
for i in range(n):
    if a[i] % 2 == 0:
        b.append(a[i])
    else:
        c.append(a[i])
print(" ".join(map(str, c))," ".join(map(str,b)))

可结合的元素对

问题描述

小蓝和小桥是蓝桥学院中学业成绩最好的两位同学。一天，小蓝向小桥提出了一个问题，希望小桥能够展示她最新学到的知识。问题是这样的：

给定一个长度为 NN 的数组 A，如果一对下标 (i,j) 满足以下规则，那么称它们为可结合的元素对：

  • 1≤i<j≤N。
  • lowbit(ai+aj)=ai+aj ，其中 lowbit(x) 表示 x 的二进制表示中最低位的 1的值。

小蓝希望小桥能够计算出数组 AA 中可结合的元素对的数量，但小桥无法解决这个问题，只能请你帮忙了。

输入格式

第一行输入一个整数 N(2≤N≤105) 表示数组 A 的长度。

第二行输入 NN 个整数 A1,A2,A3,⋯ ,AN(1≤Ai≤109) 表示数组 A。

输出格式

输出一个整数表示答案。

样例输入

1
2
5
2 4 6 7 8

样例输出

1
1

样例说明

只有下标对 (1,3) 符合条件。

运行限制

语言 最大运行时间 最大运行内存
C++ 2s 256M
C 2s 256M
Java 3s 256M
Python3 4s 256M
PyPy3 4s 256M
Go 4s 256M
JavaScript 4s 256M

解题思路：

解法1：

二者之和为2的幂次即为所求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import os
import sys
from collections import Counter

# 请在此输入您的代码
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
pool ={}

rs = 0

for x in a:
  e = 2 ** x.bit_length()-x
  rs += pool.get(e,0)
  if x in pool:
      pool[x] += 1
  else:
      pool[x] = 1

print(rs)

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from math import log
from collections import Counter
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
d = Counter()
for i in range(n):#预处理计数
    d[arr[i]] += 1
ans = 0
for i in range(n - 1, 0, -1):
    d[arr[i]] -= 1 #计数减去当前位置
    cnt = int(log(arr[i], 2)) + 1
    res = 2 ** cnt - arr[i]
    ans += d[res]
    # ans+=arr[0:i].count(res)
print(ans)

解法3：

两个数加起来是2n的都符合条件，用hash表计数。

1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = sorted(map(int,input().split()))
res = []
for i in range(1, 32): res.append(1<<i)
cnt = {}
ans = 0
for i in range(n):
    for j in range(len(res)):
        ans += cnt.get(res[j] - a[i], 0)
    if a[i] not in cnt: cnt[a[i]] = 1
    else: cnt[a[i]] += 1
print(ans)

题目：霓虹

问题描述

晚上，小蓝正无聊的走在大路上，小蓝所在的街区是一个带有赛博朋克风格的街区。

他抬头一看，看到了很多霓虹灯牌。在其中的某一个店铺前，挂着一排的数字灯牌，每一个数字的显示都依靠 77 段 LED 管，亮着的灯管组成数字，具体来说如下图所示：

图片描述

小蓝刚学过数字电路，他知道具体的工作原理如下：

图片描述

在思考的过程中，他发现数字发生了变化。他想要知道，在数字变化的过程中，总共有多少根灯管的状态产生了变化？

例如，从显示数字 00 到显示数字 66，会有一个灯管熄灭，一个灯管点亮，那么总共有两根灯管发生了变化。

具体来说，当前的数字串是 AA，一秒钟之后，数字串变成了 BB，小蓝想知道，在数字跳转的过程中，有多少个灯管的状态发生了变化。

输入格式

输入共两行，包含两个等长字符串。

第一行包含一个字符串 SS（∣S∣≤105∣S∣≤105），代表一开始的数字串。

第二行包含一个字符串 TT（∣T∣≤105∣T∣≤105），代表跳变后的数字串。

输出格式

一个整数，代表跳变过程中变化的灯管数量。

样例输入

1
2
01
56

样例输出

1
9

说明

跳变过程如题干中的图片。

0→50→5 变化了 33 根灯管，1→61→6 变化了 66 根灯管，共变化 99 根灯管。

解题思路

本题考察位运算，具体考察异或运算。

每个数字由 77 个数码管表示，我们可以用 77 个二进制位来表示每个数。

0∼90∼9 可以表示为如下数位：

1
2
int pos[] = {0B1111110, 0B0000110, 0B1011011, 0B1001111, 0B0100111,
             0B1101101, 0B1111101, 0B1000110, 0B1111111, 0B1101111};

0B 是代码语言的二进制前缀，同样的还有 0X 是十六进制前缀，0 是八进制前缀。

对于两个数，比如 11 和 22，我们可以用 pos1⊗pos2pos1⊗pos2，⊗⊗ 为异或，结果为 0B1011101，11 的数量就是不同的数量。

复杂度：O(∣S∣)O(∣S∣)。

如果你愿意统计出 100100 种情况，也是可以的。

AC_Code

  • C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>

using namespace std;
const int N = 1e5+100;

int pos[] = {0B1111110, 0B0000110, 0B1011011, 0B1001111, 0B0100111,
             0B1101101, 0B1111101, 0B1000110, 0B1111111, 0B1101111};

char S[N], T[N];

inline int nu_i(int x) {
    int res = 0;
    while (x) {
        res += (x & 1);
        x >>= 1;
    }
    return res;
}

int main() {
    cin >> S;
    cin >> T;
    int ans = 0;
    for (int i = 0; S[i]; ++i) {
        ans += nu_i(pos[S[i] - '0'] ^ pos[T[i] - '0']);
    }
    cout << ans << '\n';
    return 0;
}
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;

public class std {
    static final int N = 100010;
    static int[] pos = {0B1111110, 0B0000110, 0B1011011, 0B1001111, 0B0100111,
                        0B1101101, 0B1111101, 0B1000110, 0B1111111, 0B1101111};

    static int nu_i(int x) {
        int res = 0;
        while (x != 0) {
            res += (x & 1);
            x >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        char[] S = scanner.next().toCharArray();
        char[] T = scanner.next().toCharArray();

        int ans = 0;
        for (int i = 0; i < S.length; i++) {
            ans += nu_i(pos[S[i] - '0'] ^ pos[T[i] - '0']);
        }
        System.out.println(ans);
        scanner.close();
    }
}
  • Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def nu_i(x):
    res = 0
    while x:
        res += (x & 1)
        x >>= 1
    return res

if __name__ == "__main__":
    pos = [0B1111110, 0B0000110, 0B1011011, 0B1001111, 0B0100111,
           0B1101101, 0B1111101, 0B1000110, 0B1111111, 0B1101111]

    S = input()
    T = input()

    ans = 0
    for i in range(len(S)):
        ans += nu_i(pos[int(S[i])] ^ pos[int(T[i])])
    print(ans)

其他解法：

解法1：

1
2
3
4
5
6
7
8
li=[[1,0,1,1,0,1,1,1,1,1],[1,0,0,0,1,1,1,0,1,1],[1,1,1,1,1,0,0,1,1,1],[0,0,1,1,1,1,1,0,1,1],[1,0,1,0,0,0,1,0,1,0],[1,1,0,1,1,1,1,1,1,1],[1,0,1,1,0,1,1,0,1,1]]
num1=list(map(int,input()))
num2=list(map(int,input()))
add=0
for i in range(len(num1)):
  for j in li:
    add+=j[num1[i]]^j[num2[i]]
print(add)

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import os
import sys

# 请在此输入您的代码

def dd(a,b):
  z = ''
  for i in a:
    if i not in b:
      z+=i
  for i in b:
    if i not in a:
      z+=i
  return z

f1 = input(' ')
f2 = input(' ')
sz = {
    '0':'abcdef',
    '1':'bc',
    '2':'abged',
    '3':'abgcd',
    '4':'fgbc',
    '5':'afgcd',
    '6':'afedcg',
    '7':'abc',
    '8':'abcdefg',
    '9':'abcdfg'
}
t = ''
for i,j in enumerate(f1):
    t+=dd(sz[j],sz[f2[i]])
print(len(t))

解法3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import os
import sys

num = [[1, 1, 1, 1, 0, 1, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 1, 1, 1, 0, 1], [0, 1, 1, 0, 1, 1, 1],
       [1, 0, 1, 0, 1, 1, 0], [1, 1, 0, 0, 1, 1, 1], [1, 1, 0, 1, 1, 1, 1], [0, 1, 1, 0, 0, 1, 0],
       [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1]]

start_num = input()
end_num = input()
count = 0
for i in range(len(start_num)):
    for j in range(7):
        if num[int(start_num[i])][j] != num[int(end_num[i])][j]:
            count += 1
print(count)

解法4：

1
2
3
4
5
6
7
8
9
10
11
12
13
S = input()
T = input()
n = len(S)
ans = 0
res = {0: "1111110", 1: "0011000", 2: "0110111", 3: "0111101", 4: "1011001", 5: "1101101",
       6: "1101111", 7: "0111000", 8: "1111111", 9: "1111101"}
for i in range(n):
    a = res[int(S[i])]
    b = res[int(T[i])]
    for j in range(len(a)):
        if a[j] != b[j]:
            ans += 1
print(ans)

矩阵X

问题描述

小蓝面对一个 n×m 的矩形D，其中每个位置 (i,j) 上都有一个元素 xi,j。

我们定义两个函数 f(D)、g(D)，f(D) 的值为矩阵 D 的所有元素的和值，g(D) 为矩阵 D 的极差，即矩阵中的最大值减去最小值。

他需要在这个矩形中选择一个 n′×m′n′×m′ 的连续子矩阵，记为矩阵 D′，他希望选择的连续子矩阵 D′ 能够使得 f(D′)×g(D′) 最大化。

小蓝知道你很聪明，于是他把问题交给了你，希望你回答他最大化的值是多少。

连续子矩阵：是在原矩阵选取部分连续行、连续列所组成的新矩阵。

输入格式

第一行包含四个整数 n,m,n′,m′（n×m≤106,1≤n′≤n,1≤m′≤m），表示矩形的行数和列数，以及你需要选择的子矩阵的行数和列数。

接下来 n 行，每行包含 m 个整数，表示矩形中每个位置的元素值 xi,j（1≤xi,j≤106）。

输入量较大，建议采用较快的输入输出方式。

输出格式

一个整数，代表最大化的值。

样例输入

1
2
3
4
5
4 4 2 2
1 2 3 3
2 3 4 5
1 1 3 5
1 7 2 4

样例输出

1
78

说明

选择的连续子矩阵如下图黄色部分所示：

f(D′)=13,g(D′)=6f(D′)=13,g(D′)=6。

图片描述

运行限制

语言 最大运行时间 最大运行内存
C++ 4s 256M
C 4s 256M
Java 5s 256M
Python3 10s 256M
PyPy3 10s 256M
Go 10s 256M
JavaScript 10s 256M

解题思路

本题考察单调队列，优先队列，思维，二维前缀和。

首先第一个问题是存储问题，由于 n×m≤106n×m≤106，但是不知道 n,mn,m 的具体范围，所以，我们可以用一维数组模拟二维，或者二维 vectorvector，这样便就可以解决二维存储问题。

第二个问题，矩阵求和，我们可以用简单的二维前缀和解决这个问题。

第三个问题，求子矩阵的最值，我们有两个解法：

  1. 我们记录一下每一行的连续 m′m′ 个元素的最值，具体用优先队列，或者单调队列实现吗，然后我们枚举每个子矩阵，并且暴力扫描这个子矩阵的所有行，由于行数可能很大，我们可以调换一下行列，因为 min⁡(n′,m′)≤106min(n′,m′)≤1

06，所以整体的复杂度为 O(nmnm)O(nmnm

  1. )，四秒可以通过。
  2. 我们不需要暴力扫描子矩阵的所有行，我们仍然可以通过单调队列完成扫描每一行，然后记录下连续 n′n′ 的最值即可。复杂度为 O(nm)O(nm)。

AC_Code

  • C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

int n, m, n1, m1;

const int N = 1e6+100;
using ll = long long;

int a[N];
ll t[N];
int Mx[N], Mn[N];

inline int getidx(int a, int b) {
    return a * m + b;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> n1 >> m1;
    for (int i = 0; i < n * m; ++i) {
        cin >> t[i];
        a[i] = t[i];
    }
    if (n1 > m1) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                a[j * n + i] = t[i * m + j];
            }
        }
        swap(n1, m1);
        swap(n, m);
    }
    for (int i = 0; i < n; ++i) {
        t[getidx(i, 0)] = a[getidx(i, 0)];
        for (int j = 1; j < m; ++j) {
            t[getidx(i, j)] = a[getidx(i, j)] + t[getidx(i, j - 1)];
        }
    }  
    using Pair = pair<int, int>;
    priority_queue<Pair> qx, qn;

    for (int i = 0; i < n; ++i) {
        while (!qx.empty()) qx.pop();
        while (!qn.empty()) qn.pop();
        for (int j = 0; j < m1 - 1; ++j) {
            qx.push({a[getidx(i, j)], j});
            qn.push({-a[getidx(i, j)], j});
        }   
        for (int j = m1 - 1; j < m; ++j) {
            while (!qx.empty() && qx.top().second <= j - m1) qx.pop();
            while (!qn.empty() && qn.top().second <= j - m1) qn.pop();
            qx.push({a[getidx(i, j)], j});
            qn.push({-a[getidx(i, j)], j});
            Mx[getidx(i, j)] = qx.top().first;
            Mn[getidx(i, j)] = -qn.top().first;
        }
    }  
    ll ans = 0;
    for (int i = n1 - 1; i < n; ++i) {
        for (int j = m1 - 1; j < m; ++j) {
            ll sum = 0;
            int tx = -1e9, tn = 1e9;
            for (int k = 0; k < n1; ++k) {
                tx = max(tx, Mx[getidx(i - k, j)]);
                tn = min(tn, Mn[getidx(i - k, j)]);
                if (j == m1 - 1) sum += t[getidx(i - k, j)];
                else sum += t[getidx(i - k, j)] - t[getidx(i - k, j - m1)];
            }
            ans = max(ans, sum * (tx - tn));
        }
    }
    cout << ans << '\n';
    return 0;
}
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.PriorityQueue;
import java.util.Scanner;

public class std {
    static int n, m, n1, m1;
    static int[] a, Mx, Mn;
    static long[] t;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        n1 = scanner.nextInt();
        m1 = scanner.nextInt();
        
        a = new int[n * m];
        t = new long[n * m];
        Mx = new int[n * m];
        Mn = new int[n * m];
        
        for (int i = 0; i < n * m; ++i) {
            t[i] = scanner.nextLong();
            a[i] = (int) t[i];
        }

        if (n1 > m1) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    a[j * n + i] = (int) t[i * m + j];
                }
            }
            int temp = n1;
            n1 = m1;
            m1 = temp;
            temp = n;
            n = m;
            m = temp;
        }

        for (int i = 0; i < n; ++i) {
            t[getidx(i, 0)] = a[getidx(i, 0)];
            for (int j = 1; j < m; ++j) {
                t[getidx(i, j)] = a[getidx(i, j)] + t[getidx(i, j - 1)];
            }
        }

        PriorityQueue<Pair> qx = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.first, p1.first));
        PriorityQueue<Pair> qn = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.first, p1.first));

        for (int i = 0; i < n; ++i) {
            while (!qx.isEmpty()) qx.poll();
            while (!qn.isEmpty()) qn.poll();
            
            for (int j = 0; j < m1 - 1; ++j) {
                qx.offer(new Pair(a[getidx(i, j)], j));
                qn.offer(new Pair(-a[getidx(i, j)], j));
            }
            for (int j = m1 - 1; j < m; ++j) {
                while (!qx.isEmpty() && qx.peek().second <= j - m1) qx.poll();
                while (!qn.isEmpty() && qn.peek().second <= j - m1) qn.poll();
                qx.offer(new Pair(a[getidx(i, j)], j));
                qn.offer(new Pair(-a[getidx(i, j)], j));
                Mx[getidx(i, j)] = qx.peek().first;
                Mn[getidx(i, j)] = -qn.peek().first;
            }
        }

        long ans = 0;
        for (int i = n1 - 1; i < n; ++i) {
            for (int j = m1 - 1; j < m; ++j) {
                long sum = 0;
                int tx = Integer.MIN_VALUE, tn = Integer.MAX_VALUE;
                for (int k = 0; k < n1; ++k) {
                    tx = Math.max(tx, Mx[getidx(i - k, j)]);
                    tn = Math.min(tn, Mn[getidx(i - k, j)]);
                    if (j == m1 - 1) sum += t[getidx(i - k, j)];
                    else sum += t[getidx(i - k, j)] - t[getidx(i - k, j - m1)];
                }
                ans = Math.max(ans, sum * (tx - tn));
            }
        }
        System.out.println(ans);
        scanner.close();
    }

    static int getidx(int a, int b) {
        return a * m + b;
    }

    static class Pair {
        int first;
        int second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}
  • Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import heapq

n, m, n1, m1 = map(int, input().split())
a = []
t = []

for _ in range(n):
    xx = list(map(int, input().split()))
    for num in xx:
        # print(num)
        t.append(num)
        a.append(num)

if n1 > m1:
    a = [t[i * m + j] for j in range(m) for i in range(n)]
    n1, m1 = m1, n1
    n, m = m, n

for i in range(n):
    for j in range(m):
        if j == 0:
            t[i * m + j] = a[i * m + j]
        else:
            t[i * m + j] = a[i * m + j] + t[i * m + j - 1]

Mx = [0] * (n * m)
Mn = [0] * (n * m)

for i in range(n):
    qx = []
    qn = []
    for j in range(m1 - 1):
        heapq.heappush(qx, (-a[i * m + j], j))
        heapq.heappush(qn, (a[i * m + j], j))
    for j in range(m1 - 1, m):
        while qx and qx[0][1] <= j - m1:
            heapq.heappop(qx)
        while qn and qn[0][1] <= j - m1:
            heapq.heappop(qn)
        heapq.heappush(qx, (-a[i * m + j], j))
        heapq.heappush(qn, (a[i * m + j], j))
        Mx[i * m + j] = -qx[0][0]
        Mn[i * m + j] = qn[0][0]

ans = 0
for i in range(n1 - 1, n):
    for j in range(m1 - 1, m):
        sum_val = 0
        tx = float('-inf')
        tn = float('inf')
        for k in range(n1):
            tx = max(tx, Mx[(i - k) * m + j])
            tn = min(tn, Mn[(i - k) * m + j])
            if j == m1 - 1:
                sum_val += t[(i - k) * m + j]
            else:
                sum_val += t[(i - k) * m + j] - t[(i - k) * m + j - m1]
        ans = max(ans, sum_val * (tx - tn))

print(ans)

解题思路2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
import os
import sys
from collections import deque
input = sys.stdin.readline
# 请在此输入您的代码
n, m, n1, m1 = map(int, input().split())

matrix = [[0] * (m + 1)]
for _ in range(n):
    matrix.append([0] + list(map(int, input().split())))

# 二维前缀和
prefix = [[0] * (m + 1) for _ in range(n + 1)]



for i in range(1, n + 1):
    for j in range(1, m + 1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + matrix[i][j]


def shift_window(a, n, k, f, l):
    b = []
    de = deque()
    for i in range(n):
        while de and f(a[i], a[de[-1]], l):
            de.pop()
        de.append(i)
        if i >= de[0] + k:
            de.popleft()
        if i >= k - 1:
            b.append(a[de[0]])
    return b


def f(x, y, l):
    if l:
        return x >= y
    return x <= y


bb_mx = []
bb_mn = []
for i in range(1, n + 1):
    bb_mx.append(shift_window(matrix[i][1:], m, m1, f, 1))
    bb_mn.append(shift_window(matrix[i][1:], m, m1, f, 0))

cc_mx = []
cc_mn = []
for j in range(len(bb_mx[0])):
    temp1 = []
    temp2 = []
    for i in range(n):
        temp1.append(bb_mx[i][j])
        temp2.append(bb_mn[i][j])
    cc_mx.extend(shift_window(temp1, n, n1, f, 1))
    cc_mn.extend(shift_window(temp2, n, n1, f, 0))

gap = [0] * len(cc_mn)
for i in range(len(cc_mn)):
    gap[i] = cc_mx[i] - cc_mn[i]
cnt = 0
ans = -1
for j in range(1, m - m1 + 2):
    for i in range(1, n - n1 + 2):
        ii, jj = i + n1 - 1, j + m1 - 1
        pre_sum = prefix[ii][jj] - prefix[ii-n1][jj] - prefix[ii][jj-m1] + prefix[ii-n1][jj-m1]
        ans = max(ans, pre_sum * gap[cnt])
        cnt += 1


print(ans)

兽之泪

问题描述

图片描述

在蓝桥王国，流传着一个古老的传说：在怪兽谷，有一笔由神圣骑士留下的宝藏。

小蓝是一位年轻而勇敢的冒险家，他决定去寻找宝藏。根据远古卷轴的提示，如果要找到宝藏，那么需要集齐 nn 滴兽之泪，同时卷轴中也记载了，每击败一次怪物，就能够收集一滴兽之泪。

小蓝知道，这些怪物并非泛泛之辈，每一只都拥有强大的力量和狡猾的技巧。每一只怪物都有它独特的弱点和对策，小蓝必须谨慎选择战斗的策略和使用的能量。

在怪兽谷中，有 k 只怪兽。对于第 ii 只怪兽，第一次击败他需要 xixi 点能量，后续再击败他需要 yi点能量，由于怪兽吃了亏，所以有所准备，可以得到 yi≥xi。在挑战过程中，前 k−1 只怪兽可以随意挑战，但是第 kk 只怪兽是怪兽之王，如果要挑战第 k只怪兽，那么对于前 k−1 只怪兽都要击败至少一次。

小蓝想知道，如果要集齐 n 滴兽之泪，那么至少需要多少能量。

输入格式

第一行包含两个整数 kk 和 nn（2≤k≤105,1≤n≤2×105），表示怪物的数量和需要收集的兽之泪的数量。

接下来 kk 行，每行包含两个整数 xi 和 yi（1≤xi≤yi≤109），表示第 ii 只怪物第一次和后续击败所需的能量。

输出格式

输出一个整数，表示小蓝至少需要多少点能量才能收集完成。

样例输入

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

样例输出

1
8

说明

一种可行的方案是：

  1. 第一次选择 1 号怪物，消耗能量 2。
  2. 第二次选择 2 号怪物，消耗能量 4。
  3. 由于 1,2都已经击败一次，所以可以选择 33 号，第三次选择 3 号怪物，消耗能量 1。
  4. 第四次选择 3 号怪物，消耗能量 1。

运行限制

语言 最大运行时间 最大运行内存
C++ 1s 256M
C 1s 256M
Java 2s 256M
Python3 3s 256M
PyPy3 3s 256M
Go 3s 256M
JavaScript 3s 256M

解题思路

解题思路

考察分情况讨论与优先队列。

  1. 攻击最后一只怪兽。
  2. 不攻击最后一只怪兽。

如果攻击最后一只怪兽，那么每只怪兽都要攻击至少一次，然后还剩下 n−kn−k 次，只需要选择最小的一个攻击 n−kn−k 次即可。

如果不攻击最后一只怪兽，那么只能攻击前 k−1k−1 只怪兽，考虑优先队列，我们首先将前 k−1k−1 只怪兽都入队，然后每次选择最小的那个，当他攻击过后，我们将第二次攻击的能量入队，持续 nn 次即可。

时间复杂度：O(nlog⁡k)O(nlogk)。

AC_Code

  • C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <queue>

using namespace std;
int n, k;
const int N = 1e5+100;
int a[N], b[N];
using ll = long long;
using Pair = pair<int, int>;

int main() {
    cin >> k >> n;
    for (int i = 1; i <= k; ++i) {
        cin >> a[i] >> b[i];
    }
    ll ans1 = 0, ans2 = 1e18;

// ------- 不挑战最后一个怪兽
    priority_queue<Pair> q;
    for (int i = 1; i < k; ++i) {
        q.push({-a[i], i});
    }
    int tmp = n;
    while (tmp) {
        auto x = q.top(); q.pop();
        ans1 += -x.first;
        q.push({-b[x.second], x.second});
        tmp --;
    }
    
// ------- 挑战最后一个怪兽
    if (n >= k) {
        ans2 = 0;
        while (!q.empty()) q.pop();
        for (int i = 1; i <= k; ++i) {
            ans2 += a[i];
            q.push({-b[i], i});
        }
        n -= k;
        while (n) {
            auto x = q.top(); q.pop();
            ans2 += -x.first;
            q.push({-b[x.second], x.second});
            n --;
        }
    }
    cout << min(ans1, ans2) << endl;
    return 0;
}
  • Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.util.PriorityQueue;
import java.util.Scanner;

public class std {
    static class Pair implements Comparable<Pair> {
        int first;
        int second;

        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public int compareTo(Pair other) {
            return Integer.compare(this.first, other.first);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int k = scanner.nextInt();
        int n = scanner.nextInt();
        int[] a = new int[k + 1];
        int[] b = new int[k + 1];

        for (int i = 1; i <= k; ++i) {
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
        }

        long ans1 = 0, ans2 = Long.MAX_VALUE;

        // ------- 不挑战最后一个怪兽
        PriorityQueue<Pair> q = new PriorityQueue<>();
        for (int i = 1; i < k; ++i) {
            q.offer(new Pair(a[i], i));
        }
        int tmp = n;
        while (tmp > 0) {
            Pair x = q.poll();
            ans1 += x.first;
            q.offer(new Pair(b[x.second], x.second));
            tmp--;
        }

        // ------- 挑战最后一个怪兽
        if (n >= k) {
            ans2 = 0;
            q.clear();
            for (int i = 1; i <= k; ++i) {
                ans2 += a[i];
                q.offer(new Pair(b[i], i));
            }
            n -= k;
            while (n > 0) {
                Pair x = q.poll();
                ans2 += x.first;
                q.offer(new Pair(b[x.second], x.second));
                n--;
            }
        }
        System.out.println(Math.min(ans1, ans2));
        scanner.close();
    }
}
  • Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import heapq

k, n = map(int, input().split())
a = [0] * (k + 1)
b = [0] * (k + 1)

for i in range(1, k + 1):
    a[i], b[i] = map(int, input().split())

ans1, ans2 = 0, float('inf')

# ------- 不挑战最后一个怪兽
q = []
for i in range(1, k):
    heapq.heappush(q, (a[i], i))

tmp = n
while tmp:
    x = heapq.heappop(q)
    ans1 += x[0]
    heapq.heappush(q, (b[x[1]], x[1]))
    tmp -= 1

# ------- 挑战最后一个怪兽
if n >= k:
    ans2 = 0
    q = []
    for i in range(1, k + 1):
        ans2 += a[i]
        heapq.heappush(q, (b[i], i))
    n -= k
    while n:
        x = heapq.heappop(q)
        ans2 += x[0]
        heapq.heappush(q, (b[x[1]], x[1]))
        n -= 1

print(min(ans1, ans2))

解题思路2

解法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import os
import sys

import heapq

a = []
b = []

n,k = map(int,input().split())

for _ in range(n):
  x,y = map(int,input().split())
  a.append(x)
  b.append(y)


q = []

for i in range(n-1):
  heapq.heappush(q,(a[i],i))


t = k

ans = 0

while t > 0:
  w,i = heapq.heappop(q)

  heapq.heappush(q,(b[i],i))
  ans += w
  t -= 1


ans2 = 0
if k >= n:
  ans2 += sum(a) + (k-n) * min(b)


if k >= n:
  print(min(ans,ans2))
else:
  print(ans)
≡