CSP-J 复赛 模拟题6

1.大小写字母互换：

题目描述

由输入给定一个字符串，你的任务是将原字符串中的大写字母转换成其对应的小写字母，还要将原字符串中的小写字母转换成对应的大写字母，其余字符不变。

输出转换之后得到的新字符串。

输入格式

一行，一个字符串，可能包含空格。

输出格式

一行，表示转换之后的字符串

输入输出样例

输入 #1

How much U wanna risk?

输出 #1

hOW MUCH u WANNA RISK?

说明/提示

对于100%的测试点，保证字符串长度不超过1000.

2.超能力棋盘：

题目描述

公元2069年，Centent公司所经营的围斗寿棋业务突破了下限，他们甚至允许对弈双方在开局时通过充值来提前落子！

我们可以将棋盘视作一个无限大的平面直角坐标系，棋盘的正中心坐标为(0,0)，所有棋子都必须放置在实线的交叉点处(即横坐标纵坐标均为整数的位置)。如下图所示：

小C计划在对局开始前，先在棋盘上放置n个棋子，放置一枚棋子至(x,y)处的代价为∣x∣+∣y∣ 。如果放置了多枚棋子，那么你只需要付出代价最高的那一枚棋子的代价。为了让每一枚棋子都能充分的发挥作用，小C想让任意两枚棋子都不会挨着(即两枚棋子间的距离大于1)。请问为了放置这n枚棋子，小C至少需要付出多少代价？

输入格式

第一行，一个正整数T表示多组数据。

接下来T行，每行一个正整数n表示需要放置的棋子数目。

输出格式

输出共T行，每行一个数，表示放置n枚棋子所需要的最小代价。

输入输出样例

输入 #1

4
1
3
5
975461057789971042

输出 #1

0
1
2
987654321

说明/提示

样例解释：

对于第一组询问，直接将11枚棋子放置于(0,0)(0,0)处，所需代价为00。

对于第二组询问，直可以将33枚棋子放置于(1,0),(−1,0),(0,1)(1,0),(−1,0),(0,1)处，所需代价为11。

对于第三组询问，直可以将55枚棋子放置于(0,0),(1,1),(−1,1),(1,−1),(−1,−1)(0,0),(1,1),(−1,1),(1,−1),(−1,−1)处，所需代价为22。

数据范围：

对于20%的数据，保证n≤10^2.

对于50%的数据，保证n≤10^5.

对于80%的数据，保证T≤10^4,n≤10^8.

对于100%的数据，保T≤10^6,n≤10^18.

3.分糖果

题目描述

现在有 n 包糖果要分给两名小朋友，每一包糖果里有着 1,2,31,2,3 颗糖果。我们当然希望能分给两名小朋友同样多的糖果，请问是否能够办到？可以的话请输出 YES， 否则请输出 NO 。

输入格式

输入第一行，一个正整数 T 表示多组数据。

接下来 T 组数据，每组数据分两行输入：

• 第一行，一个正整数 n 表示有 n 包糖果。

• 第二行，n 个正整数 1,2,...,a1​,a2​,...,an​ 表示每包糖果中的糖果个数。

输出格式

输出共 T 行，每行一个 YES 或 NO 表示结果。

输入输出样例

输入 #1

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

输出 #1

YES
NO
YES

说明/提示

样例解释：

对于第一组样例，分给一名小朋友第 1,3,51,3,5 包糖果，另一名小朋友第 2,42,4 包糖果，两名小朋友所得的糖果个数相同。

对于第二组样例，44 包糖果中的总糖果个数为奇数，无论如何也无法办到。

数据范围：

对于 100% 的数据，保证T≤10^2,n≤10^4,1≤ai​≤3。

4.最少交换次数:

题目背景

Famrer Jnoh闲来无事，开始钻研起了排序算法；

无所不能的Famrer Jnoh每一次能够将序列中的任意两个数字交换位置，但他很着急，想要知道最少交换多少次可以让整个序列完全有序(升序降序都算)。

题目描述

给定n个数1,2,...,a1​,a2​,...,an​，请求出最少经过多少次的交换，可以让n个数按照升序或降序排列。

输入格式

第一行一个整数n;

第二行n个数，表示1,2,...,a1​,a2​,...,an​.

输出格式

一个整数，表示最少经过多少次交换可以使得这n个数有序.

输入输出样例

输入 #1

5
2 3 1 5 4

输出 #1

3

输入 #2

7
6 5 1 7 4 2 3

输出 #2

5

说明/提示

数据范围：

对于10%的数据，保证ai​=i;

对于30%的数据，保证n≤20;

对于60%的数据，保证1,2,...,a1​,a2​,...,an​是1∼n 的一个排列；

对于100%的数据， 保证n≤5⋅105,ai​≤109且对于任意的，i!=j，有ai​!=aj​.