组合

题目描述

你收集了 nn 张卡片，按照收集的时间顺序编号 11 到 nn 并依次排列，每张卡片上标有一个数值。现在突发奇想，想知道在这些卡片中，若每次挑选两张卡片，会有多少对不同的组合满足两张卡片的数值和恰好为 00，请你计算出符合条件的卡片组合的数量。

输入格式

· 第一行：单个整数表示 nn

· 第二行：nn 个整数表示 a1,a2,a3,…,ana1​,a2​,a3​,…,an​

输出格式

单个整数：表示有多少对卡片数值和为 00。

输入样例

4

2 -2 2 0

输出样例

2

说明提示

· 30%30% 的数据，1≤n≤10001≤n≤1000

· 60%60% 的数据，1≤n≤200001≤n≤20000

· 100%100% 的数据，1≤n≤3000001≤n≤300000

· −1,000,000,000≤ai≤1,000,000,000−1,000,000,000≤ai​≤1,000,000,000

限制

时间限制：1000ms

内存限制：512MiB

选数

题目描述

给定一个正整数 nn，从数字 11 到 nn 中选择若干个数字（所选集合不能为空），且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数，结果对 10000000071000000007 取模。

输入格式

第一行：单个整数 nn。

输出格式

输出一个整数，表示方案数模 10000000071000000007 的结果。

输入样例

3

输出样例

4

说明提示

· 对于 30%30% 的数据，n≤20n≤20；

· 对于 60%60% 的数据，n≤10,000n≤10,000；

· 对于 100%100% 的数据，1≤n≤100,0001≤n≤100,000。

限制

时间限制：1000ms

内存限制：512MiB

图书管理

题目描述

图书馆的书籍分类系统使用二进制标签管理，0 代表儿童读物，1 代表青少年书籍。管理员发现当前的书架排列中不允许出现青少年书籍之后连接儿童读物的情况（即 10 子串）。管理员每次可以交换任意两本书的位置。请计算让书架符合规定所需的最少操作次数。

输入格式

由 0 和 1 组成的字符串，表示当前书架排列。

输出格式

一行一个非负整数，即达到目标所需的最少操作次数。

输入样例#1

1100

输出样例#1

2

输入样例#2

00

输出样例#2

0

输入样例#3

10110100

输出样例#3

3

说明提示

对于全部的输入数据，保证 2≤字符串长度≤2000002≤字符串长度≤200000 ，同时 cici​ 必为1 或 0 中的一个。

限制

时间限制：1000ms

内存限制：512MiB

街道的中心

题目描述

城市商业街主干道是一条笔直的道路，商业街里有 nn 家店铺，现给定 nn 个店铺的位置，请在这条道路上找到一个中心点，使得所有店铺到这个中心点的距离之和最小，并输出这个最小值。

输入格式

第一行：单个正整数 nn。
第二行：nn 个整数表示一个店铺的位置。

输出格式

单个整数：表示商铺到中心点距离之和的最小值。

输入样例

4  

-2  0  2  0  

输出样例

4

说明提示

数据范围：

· −5000≤xi≤5000−5000≤xi​≤5000

· 对于 30%30% 的数据，1≤n≤201≤n≤20

· 对于 60%60% 的数据，1≤n≤20001≤n≤2000

· 对于 100%100% 的数据，1≤n≤1000001≤n≤100000

样例解释：
最优中心设置在坐标 00 处，总距离为：
∣−2−0∣+∣0−0∣+∣2−0∣+∣0−0∣=2+0+2+0=4∣−2−0∣+∣0−0∣+∣2−0∣+∣0−0∣=2+0+2+0=4。

限制

时间限制：1000ms

内存限制：512MiB