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.