1.A. 找良好数组

题目描述
给你一个数组 a，下标从 0 开始。
如果数组中的每个奇数下标为奇数，且每个偶数下标为偶数，则称其为“好数组”，否则为“坏数组”。
你可以任意交换两个元素（可以不相邻）。
请你判断是否可以通过最少交换变为好数组，并输出最小交换次数；若无法变成好数组，输出 -1。

输入

  • 第一行一个整数 t（1 ≤ t ≤ 1000）表示测试用例组数。
  • 每组测试用例：
    • 第一行一个整数 n（1 ≤ n ≤ 40）表示数组长度。
    • 第二行 n 个整数 a0, a1, ..., an−1（0 ≤ ai ≤ 1000）。

输出
每组数据输出一个整数：能变为好数组的最小交换次数，或 -1 表示无法实现。

样例输入

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

样例输出

1
2
3
4
2
1
-1
0

2.B. B 进制加法

题目描述
给定一个进制 B（2 ≤ B ≤ 36），以及两个 B 进制的正整数，求它们的和（结果仍为 B 进制）。

输入

1
2
3
第1行：进制 B
第2行：第一个 B 进制正整数
第3行：第二个 B 进制正整数

输出
一个 B 进制的数，表示两个输入数的和。

样例输入

1
2
3
4
123
321

样例输出

1
1110

3.C. 高精度五则运算

题目描述
输入两个大整数 A 和 B（A, B > 0，长度不超过 10^4），求它们的：和、差、积、商（整除）、余。

输入

1
2
A
B

输出
五行，依次输出：和、差、积、商、余。

样例输入

1
2
1
1

样例输出

1
2
3
4
5
2
0
1
1
0

4.D. 栈操作

题目描述
三种操作：

  • p x：将数字 x 压入栈中
  • t：输出栈顶元素（若栈为空输出 no）
  • d：删除栈顶元素（若栈为空不操作）

输入

1
2
第一行一个整数 N（1 < N < 200）
接下来的 N 行是操作指令

输出
每次 t 操作输出栈顶元素或 no

样例输入

1
2
3
4
5
6
5
p 2
p 1
t
d
t

样例输出

1
2
1
2

5.E. 队列操作

题目描述
三种操作：

  • p x：将数字 x 入队
  • t：输出队首元素（若为空输出 no）
  • d：删除队首元素（若为空不操作）

输入

1
2
第一行一个整数 N（1 < N < 200）
接下来的 N 行是操作指令

输出
每次 t 操作输出队首元素或 no

样例输入

1
2
3
4
5
6
7
8
7
p 1
p 2
t
d
d
d
t

样例输出

1
2
1
no

6.F. 采药（完全背包）

题目描述
有 n 株草药，每株采集需要 Ti 时间，价值 Vi，总共时间为 m，求最大价值。

输入

1
2
3
4
第一行 t 表示测试组数
每组：
  一行两个整数 n m
  接下来 n 行每行两个整数 Ti Vi

输出
每组输出一个整数，表示最大价值

样例输入

1
2
3
4
5
1
3 70
71 100
69 1
1 2

样例输出

1
3

7.G. 射击游戏（前缀和）

题目描述
有 n 个靶子，每个靶子需要 ai 发子弹，m 次查询，每次给定区间 [L,R]，求其总子弹数。

输入

1
2
3
4
第一行 n（1 < n < 1e5）
第二行 n 个整数 ai
第三行 m（1 < m < 1e5）
接下来 m 行，每行两个数 L R（1-based）

输出
m 行，每行一个整数，表示每次所需子弹数

样例输入

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

样例输出

1
2
3
3
15
12

8.H. 二分查找

题目描述
长度为 n 的非降序列，进行 m 次查询，每次查询给出一个整数 q，输出其首次出现的位置（1-based），否则输出 -1。

输入

1
2
3
第一行 n m
第二行 n 个非降整数 ai
第三行 m 个整数 q

输出
一行，m 个整数，用空格分隔，表示每个查询结果

样例输入

1
2
3
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出

1
1 2 -1

9.I. 神奇的四次方数（DP）

题目描述
将整数 m 分解为若干个四次方数之和，要求最少项数。

输入

1
一行，一个整数 m（1 ≤ m ≤ 100000）

输出

1
最少项数 n

样例输入

1
706

样例输出

1
2

10.J. 栈合法序列个数（卡特兰数）

题目描述
求长度为 2n 的合法出栈序列个数，等价于卡特兰数 C_n。

输入

1
一行一个整数 n（1 ≤ n ≤ 18）

输出

1
合法序列个数

样例输入

1
3

样例输出

1
5

11.K. FBI 树（分治 + 后序遍历）

题目描述
给定一个长度为 2^n 的“01”字符串，构建 FBI 树并输出其后序遍历。

  • 若全是 0，则为 B；
  • 若全是 1，则为 I；
  • 否则为 F，其左右子树分别对应前一半和后一半。

输入

1
2
第一行一个整数 n（1 ≤ n ≤ 10）
第二行一个长度为 2^n 的 01 字符串

输出

1
后序遍历字符串

样例输入

1
2
3
10001011

样例输出

1
IBFBBBFIBFIIIFF