线性表题解

超，格式怎么这样了，下次再改

妖梦拼木棒

题目背景

上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。

题目描述

有 $n$ 根木棒，现在从中选 $4$ 根，想要组成一个正三角形，问有几种选法？

答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$。

第二行往下 $n$ 行，每行 $1$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。

输出格式

一行一个整数代表答案。

样例 #1

样例输入 #1

1
2
3
4
5
4 
1
1
2
2

样例输出 #1

1
1

提示

数据规模与约定

  • 对于 $30%$ 的数据，保证 $n \le 5 \times 10^3$。
  • 对于 $100%$ 的数据，保证 $1 \leq n \le 10^5$，$1 \le a_i \le 5 \times 10^3$。

一开始想错了，导致后面也被带偏。必须要两只一样长的木棒，剩下两个只需要和跟另外两个一样长就行了。并不需要相等长度，（想错，导致之后改错）其实也并不需要一开始的两只相等长度，比如7 7 2 +5这样。然后就是简单的组合数学

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
#include <bits/stdc++.h>
using namespace std;
vector<int>nums(5001);
const int mod = 1e9 + 7;
long long a = 0, b = 0;
int main()
{
	long long n;
	cin >> n;
	while (n--)
	{
		int x;
		cin >> x;
		nums[x]++;
	}
	long long cnt = 0;
	for (int i = 1; i <= 5000; i++)
	{
		if (nums[i] >= 2)
		{
			a = nums[i] * (nums[i] - 1) / 2 % mod;

			for (int j = 1; j <= i / 2; j++)
			{
				if (j * 2 == i && nums[j] >= 2)cnt += a * (nums[j] * (nums[j] - 1) / 2 % mod) % mod;
				if (j * 2 != i && nums[j] >= 1 && nums[i - j] >= 1)cnt += a * ((nums[j] * nums[i - j]) % mod) % mod;
			}
			cnt %= mod;
		}
	}
	cout << cnt % mod << endl;

}

kkksc03考前临时抱佛脚

题目背景

kkksc03 的大学生活非常的颓废，平时根本不学习。但是，临近期末考试，他必须要开始抱佛脚，以求不挂科。

题目描述

这次期末考试，kkksc03 需要考 $4$ 科。因此要开始刷习题集，每科都有一个习题集，分别有 $s_1,s_2,s_3,s_4$ 道题目，完成每道题目需要一些时间，可能不等（$A_1,A_2,\ldots,A_{s_1}$，$B_1,B_2,\ldots,B_{s_2}$，$C_1,C_2,\ldots,C_{s_3}$，$D_1,D_2,\ldots,D_{s_4}$）。

kkksc03 有一个能力，他的左右两个大脑可以同时计算 $2$ 道不同的题目，但是仅限于同一科。因此，kkksc03 必须一科一科的复习。

由于 kkksc03 还急着去处理洛谷的 bug，因此他希望尽快把事情做完，所以他希望知道能够完成复习的最短时间。

输入格式

本题包含 $5$ 行数据：第 $1$ 行，为四个正整数 $s_1,s_2,s_3,s_4$。

第 $2$ 行，为 $A_1,A_2,\ldots,A_{s_1}$ 共 $s_1$ 个数，表示第一科习题集每道题目所消耗的时间。

第 $3$ 行，为 $B_1,B_2,\ldots,B_{s_2}$ 共 $s_2$ 个数。

第 $4$ 行，为 $C_1,C_2,\ldots,C_{s_3}$ 共 $s_3$ 个数。

第 $5$ 行，为 $D_1,D_2,\ldots,D_{s_4}$ 共 $s_4$ 个数，意思均同上。

输出格式

输出一行,为复习完毕最短时间。

样例 #1

样例输入 #1

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

样例输出 #1

1
20

提示

$1\leq s_1,s_2,s_3,s_4\leq 20$。

$1\leq A_1,A_2,\ldots,A_{s_1},B_1,B_2,\ldots,B_{s_2},C_1,C_2,\ldots,C_{s_3},D_1,D_2,\ldots,D_{s_4}\leq60$。

本来是贪心+模拟。。但是有几个过不了，大概是情况没考虑全。btw别人想的都是把题目分成尽量平均的两部分啊。（模拟不是下意识就出来了吗，窝好菜

用dp求尽量平均的两部分，即01背包问题，分到左边和分到右边，状态表示为二维，集合为到j的时候的体积，状态计算为给左大脑和给右大脑，此处视左大脑为背包1，右大脑为0，放到让左边为1/2总体积。每道题的时间既是价值，也是体积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
f = [[0]*2000 for _ in range(2000)]
ans = 0
lis = list(map(int, input().split()))


for i in range(4):
    nums = list(map(int, input().split()))
    m = sum(nums)
    n = len(nums)
    t = 0
    for j in range(0,n):
        for k in range(m//2 + 1):
            f[j][k] = f[j - 1][k]
            if k >= nums[j]:
                f[j][k] = max(f[j][k],f[j - 1][k - nums[j]] + nums[j])
            t = max(t,f[j][k])

    ans += max(t, m-t)
print(ans)

一维优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
f = [0] * 100010
ans = 0
lis = list(map(int, input().split()))


for i in range(4):
    nums = list(map(int, input().split()))
    m = sum(nums)
    n = len(nums)
    t = 0
    for j in range(0,n):
        for k in range(m//2, nums[j]-1, -1):
            f[k] = max(f[k],f[k - nums[j]] + nums[j])


    ans += m - f[m//2]
    for i in range(m // 2 + 1):
        f[i] = 0
print(ans)

[COCI2008-2009#2] PERKET

题目描述

Perket 是一种流行的美食。为了做好 Perket，厨师必须谨慎选择食材，以在保持传统风味的同时尽可能获得最全面的味道。你有 $n$ 种可支配的配料。对于每一种配料，我们知道它们各自的酸度 $s$ 和苦度 $b$。当我们添加配料时，总的酸度为每一种配料的酸度总乘积；总的苦度为每一种配料的苦度的总和。

众所周知，美食应该做到口感适中，所以我们希望选取配料，以使得酸度和苦度的绝对差最小。

另外，我们必须添加至少一种配料，因为没有任何食物以水为配料的。

输入格式

第一行一个整数 $n$，表示可供选用的食材种类数。

接下来 $n$ 行，每行 $2$ 个整数 $s_i$ 和 $b_i$，表示第 $i$ 种食材的酸度和苦度。

输出格式

一行一个整数，表示可能的总酸度和总苦度的最小绝对差。

样例 #1

样例输入 #1

1
2
1
3 10

样例输出 #1

1
7

样例 #2

样例输入 #2

1
2
3
2
3 8
5 8

样例输出 #2

1
1

样例 #3

样例输入 #3

1
2
3
4
5
4
1 7
2 6
3 8
4 9

样例输出 #3

1
1

提示

数据规模与约定

对于 $100%$ 的数据，有 $1 \leq n \leq 10$，且将所有可用食材全部使用产生的总酸度和总苦度小于 $1 \times 10^9$，酸度和苦度不同时为 $1$ 和 $0$。

说明

简单dfs 选或不选###的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n = int(input())
nums = [[0]*(n+1) for _ in range(n+1)]
minn = 0x7fffffff
def dfs(u,sor,bit):
    global minn
    if u == n:
        if sor == 1 and bit == 0:
            return
        else:
            minn = min(minn,abs(sor - bit))
            return

    dfs(u + 1,sor,bit)
    dfs(u + 1,sor * nums[u][0], bit + nums[u][1])


for i in range(n):
   nums[i] = list(map(int,input().split()))

dfs(0,1,0)
print(minn)

# [NOIP2016 普及组 海港]([P2058 NOIP2016 普及组] 海港 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目背景

NOIP2016 普及组 T3

题目描述

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 $i$ 艘到达的船，他记录了这艘船到达的时间 $t_i$ (单位：秒)，船上的乘客数 $k_i$，以及每名乘客的国籍 $x_{i,1}, x_{i,2},\dots,x_{i,k}$。

小K统计了 $n$ 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 $24$ 小时（$24$ 小时 $=86400$ 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 $n$ 条信息。对于输出的第 $i$ 条信息，你需要统计满足 $t_i-86400<t_p \le t_i$ 的船只 $p$，在所有的 $x_{p,j}$ 中，总共有多少个不同的数。

输入格式

第一行输入一个正整数 $n$，表示小 K 统计了 $n$ 艘船的信息。

接下来 $n$ 行，每行描述一艘船的信息：前两个整数 $t_i$ 和 $k_i$ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 $k_i$ 个整数 $x_{i,j}$ 表示船上乘客的国籍。

保证输入的 $t_i$ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 $t_i$ 秒到达海港。

保证 $1 \le n \le 10^5$，$\sum{k_i} \le 3\times 10^5 $ ，$1\le x_{i,j} \le 10^5$， $1 \le t_{i-1}\le t_i \le 10^9$。

其中 $\sum{k_i}$ 表示所有的 $k_i$ 的和。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数表示第 $i$ 艘船到达后的统计信息。

样例 #1

样例输入 #1

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

样例输出 #1

1
2
3
3
4
4

样例 #2

样例输入 #2

1
2
3
4
5
4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

样例输出 #2

1
2
3
4
3
3
3
4

提示

【样例解释 1】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $4,1,2,2$，共来自 $3$ 个不同的国家；

第二艘船在第 $2$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4 + 2 = 6$ 个乘客，分别是来自国家 $4,1,2,2,2,3$，共来自 $4$ 个不同的国家；

第三艘船在第 $10$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船、第二艘船和第三艘船，共有 $4+2+1=7$ 个乘客，分别是来自国家 $4,1,2,2,2,3,3$，共来自 $4$ 个不同的国家。

【样例解释 2】

第一艘船在第 $1$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船，共有 $4$ 个乘客，分别是来自国家 $1,2,2,3$，共来自 $3$ 个不同的国家。

第二艘船在第 $3$ 秒到达海港，最近 $24$ 小时到达的船是第一艘船和第二艘船，共有 $4+2=6$ 个乘客，分别是来自国家 $1,2,2,3,2,3$，共来自 $3$ 个不同的国家。

第三艘船在第 $86401$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船和第三艘船，共有 $2+2=4$ 个乘客，分别是来自国家 $2,3,3,4$，共来自 $3$ 个不同的国家。

第四艘船在第 $86402$ 秒到达海港，最近 $24$ 小时到达的船是第二艘船、第三艘船和第四艘船，共有 $2+2+1=5$ 个乘客，分别是来自国家 $2,3,3,4,5$，共来自 $4$个 不同的国家。

【数据范围】

  • 对于 $10%$ 的测试点，$n=1,\sum k_i \leq 10,1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10$。
  • 对于 $20%$ 的测试点，$1 \leq n \leq 10, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 32767$。
  • 对于 $40%$ 的测试点，$1 \leq n \leq 100, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 86400$。
  • 对于 $70%$ 的测试点，$1 \leq n \leq 1000, \sum k_i \leq 3000,1 \leq x_{i,j} \leq 1000,1 \leq t_i \leq 10^9$。
  • 对于 $100%$ 的测试点，$1 \leq n \leq 10^5,\sum k_i \leq 3\times 10^5, 1 \leq x_{i,j} \leq 10^5,1\leq t_i \leq 10^9$。
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
# 主要是python的语法 ship.num = lis[2:]把2和后面的全都赋到num里面，然后就是python的语法，双端队列deque的使用方法，支持[]访问，直接用shiparr[Ship()]*100000，会导致错误，应该是类似于地址出错（所有的数组里面都是同一个值
from collections import deque


class Ship:
    time = 0
    num = []
    numpass = 0


q = deque()
n = int(input())
peo = [0] * 1000000
lis = []
shiparr = []
for i in range(n):
    lis = list(map(int,input().split()))
    ship = Ship()
    ship.time = lis[0]
    ship.numpass = lis[1]
    ship.num = lis[2:]
    shiparr.append(ship)


country = 0
for j in range(n):
    ship = shiparr[j]
    i = 0
    while 1:
        if len(q) == 0:
            break
        if ship.time - q[0].time < 86400:
            break
        for x in q[0].num:
            peo[x] -= 1
            if peo[x] == 0:
                country -= 1
        q.popleft()
        i += 1
    q.append(ship)
    for x in ship.num:
        if peo[x] == 0:
            country += 1
        peo[x] += 1
    print(country)

# [括号序列](P1241 括号序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

题目描述

定义如下规则：

  1. 空串是「平衡括号序列」
  2. 若字符串 $S$ 是「平衡括号序列」，那么 $\texttt{[}S\texttt]$ 和 $\texttt{(}S\texttt)$ 也都是「平衡括号序列」
  3. 若字符串 $A$ 和 $B$ 都是「平衡括号序列」，那么 $AB$（两字符串拼接起来）也是「平衡括号序列」。

例如，下面的字符串都是平衡括号序列：

()，[]，(())，([])，()[]，()[()]

而以下几个则不是：

(，[，]，)(，())，([()

现在，给定一个仅由 (，)，[，]构成的字符串 $s$，请你按照如下的方式给字符串中每个字符配对：

  1. 从左到右扫描整个字符串。
  2. 对于当前的字符，如果它是一个右括号，考察它与它左侧离它最近的未匹配的的左括号。如果该括号与之对应（即小括号匹配小括号，中括号匹配中括号），则将二者配对。如果左侧未匹配的左括号不存在或与之不对应，则其配对失败。

配对结束后，对于 $s$ 中全部未配对的括号，请你在其旁边添加一个字符，使得该括号和新加的括号匹配。

输入格式

输入只有一行一个字符串，表示 $s$。

输出格式

输出一行一个字符串表示你的答案。

样例 #1

样例输入 #1

1
([()

样例输出 #1

1
()[]()

样例 #2

样例输入 #2

1
([)

样例输出 #2

1
()[]()

提示

数据规模与约定

对于全部的测试点，保证 $s$ 的长度不超过 100，且只含 (，)，[，] 四个字符。

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
// 主要是题目，2.的意思是从遇到第一个右括号开始向左寻找第一个未匹配的左括号（其实根本不需要栈）。只需要在找到的地方做个标记表示已匹配即可。最后，输出的时候未匹配的就直接输出同类的完整括号，匹配的就正常输出。
#include <bits/stdc++.h>
using namespace std;
int main()
{
	stack<char>stleft;
	int a[105] = { 0 };
	char ch;
	string str;
	cin >> str;
	for (int j = 0; j < str.size(); j++)
	{
		ch = str[j];
		if (ch == ')')
		{
			for (int i = j - 1; i >= 0; i--)
			{
				if (str[i] == '(' && a[i] == 0)
				{
					a[i] = a[j] = 1;
					break;
				}
				else if (str[i] == '[' && a[i] == 0)
					break;
			}
		}
		else if (ch == ']')
		{
			for (int i = j - 1; i >= 0; i--)
			{
				if (str[i] == '[' && a[i] == 0)
				{
					a[i] = a[j] = 1;
					break;
				}
				else if (str[i] == '(' && a[i] == 0)
					break;
			}
		}
	}
	for (int i = 0; i < str.size(); i++)
	{
		if (a[i] == 0 && (str[i] == '(' || str[i] == ')'))cout << "()";
		else if (a[i] == 0 && (str[i] == '['||str[i] == ']')) cout << "[]";
		else cout << str[i];
	}

}
algorithm
#Ans
线性表题解
https://brtulien.github.io/2023/07/31/线性表题解/
作者
Brtulien
发布于
2023年7月31日
更新于
2024年7月1日
许可协议