目录

• 1. 考试座位
• 2. 小美炒股
• 3. 颜色排序
• 4. 方格染色
• 其他
• 特别鸣谢

1. 考试座位

题目描述：

现在有n个人坐成一排进行上机考试。但他们有的使用C语言，用C表示；而有的使用Java，用J表示。为了防止他们“友好交流”，小美老师要求任意座位相邻的两人之间使用的语言是不同的。小美每次可以交换相邻两人的位置，现在她想知道最少交换多少次可以满足要求？

输入描述：

输入一个整数n（1≤n≤106） ，表示有n个人。
然后输入n个字母c1,c2，… ,cn（ci∈{C,J}）构成的字符串，表示每个人使用的语言。

输出描述：

输出一个整数S，表示最少需要交换S次。若不可能满足要求，则输出-1。

样例输入:

4
CCJJ

样例输出:

1

思路：
刚开始我的想法是双指针从前往后遍历就行，只要出现前后一样的，慢指针停下来，快指针到后面去找跟慢指针指向内容不同的东西，然后将他经过fast减slow次交换到前面就行了。但是这个有个漏洞，就是我每次都是从后往前搬运东西的，这个肯定不是最优的，就比如评论里的JCJCJCJCC，按照之前快慢双指针，就求出结果为9，但实际上只要进行4次就行了。所以我又想了想，或许我们可以采取另一种思路。我就规定第一个人是J，那么最后一个肯定是xx(根据C和J的人数差来决定)。我还是双指针的思路。我两头同时采取贪心的思路，寻找最优满足当前位置的人的移动次数。
是不是有点晕了？看代码，你就能理解了。

代码实现：

public class Main {static int res = 0;public static void main(String[] args) {//----------------输入------------------//Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());String str = scanner.nextLine();System.out.println(exChangeTime(str, n));}public static int exChangeTime(String str, int n) {int c = 0;int j = 0;char[] chs = str.toCharArray();for (int i = 0; i < n; i++) {if (chs[i] == 'C') {c++;} else {j++;}}int abs = c - j;if (abs == 0) {//说明两个一样多int pre = start_end(chs, n, 0, n - 1, 'J', 'C');int next = start_end(chs, n, 0, n - 1, 'C', 'J');return pre < next ? pre : next;} else if (abs == 1) {//说明C比J多return start_end(chs, n, 0, n - 1, 'C', 'C');} else if (abs == -1) {return start_end(chs, n, 0, n - 1, 'J', 'J');} else {return -1;}}public static int start_end(char[] chs, int n, int start, int end, char first, char last) {if (end - start <= 1) {return res;}for (int i = start; i <= end; i++) {if (chs[i] == first) {res = res + (i - start);//-----交换-------//char temp = chs[i];chs[i] = chs[start];chs[start] = temp;break;}}if (first == 'C') {first = 'J';} else {first = 'C';}for (int i = end; i >= start; i--) {if (chs[i] == last) {res = res + (end - i);//-----交换-------//char temp = chs[i];chs[i] = chs[end];chs[end] = temp;break;}}if (last == 'C') {last = 'J';} else {last = 'C';}return start_end(chs, n, start + 1, end - 1, first, last);}
}

2. 小美炒股

题目描述：

小美最近在炒股。

小美只关注一支股票，而且她有着预测未来的能力，她提前知道了未来n天的股票价格（第 i 天为ai）。

小美每天只在收盘时的瞬间操作，所以可以认为每天股票价格是不变的。在股市出现剧烈波动时，小美可能赚得过多，为了防止泄露超能力，她决定在总资金超过1e6=1000000之后不再买入（但是卖出时间不定，仍要求卖出时有最大收益）。超过100万后，如果她还想买入，可以捐款一些资金，使自己的资金不超过100万，这样她可以在超过100万前继续买入。（即资金超过100万后，找以100万为本金的单次买卖的最大收益）

现在小美现在有1000元，她想知道如果一直最优抉择，她在n天后拥有多少钱？请你帮帮她。（允许不买任意股票，购入股票数必须为整数）

输入描述:

对于每一组数据，第一行一个正整数n；
第二行n个空格隔开的整数 a1,a2, … ,an
1≤n≤10000 ，1≤ai≤1000

输出描述:

输出一个整数，表示小美最优决策后的金钱。

样例输入:

5
101 102 100 101 103

样例输出:

1039

思路：
原本想着用动态规划dp数组，但是这个玩意儿涉及本金，还涉及手头不能超过100万。着实受不了，所以我直接用回溯法了，如果大家有好的想法，欢迎告诉我呀。秋梨膏=.=

标准版：

public class Main {static int up = 1000000;public static void main(String[] args) {//----------------输入------------------//Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());String str = scanner.nextLine();//----------------整理输入------------------////因为我只会在波峰波谷的地方操作，所以我只记录波峰波谷就行，这么好用的预见未来能里肯定要好好用啊List<Integer> list = new ArrayList<>();int first = Integer.parseInt(str.split(" ")[0]);int mid = Integer.parseInt(str.split(" ")[1]);if (first < mid) {list.add(first);}int flag = mid - first;for (int i = 1; i < n; i++) {int pre = Integer.parseInt(str.split(" ")[i - 1]);int next = Integer.parseInt(str.split(" ")[i]);if (flag * (next - pre) < 0) {list.add(pre);flag = 0 - flag;}}int last = Integer.parseInt(str.split(" ")[n - 1]);if (Integer.parseInt(str.split(" ")[n - 2]) < last) {list.add(last);}//TODOint[] prices = new int[list.size()];for (int i = 0; i < list.size(); i++) {prices[i] = list.get(i);}System.out.println(Math.max(dynamic(prices, 1, 1000 / prices[0], 1000 % prices[0]), 1000));}public static int dynamic(int[] prices, int start, int n, int money) {//prices为操作，start为从什么时候开始操作，n为当前持有的股票数int max = 0;if (start == prices.length - 1) {if (n > 0) {return money + n * prices[start];} else {return money;}}if (n > 0) {//此时可以卖也可以不卖max = Math.max(dynamic(prices, start + 1, n, money), dynamic(prices, start + 1, 0, money + prices[start] * n));} else {//此时可以买也可以不买if (money > up) {max = Math.max(dynamic(prices, start + 1, 0, money), dynamic(prices, start + 1, up / prices[start], up % prices[start]));} else {max = Math.max(dynamic(prices, start + 1, 0, money), dynamic(prices, start + 1, money / prices[start], money % prices[start]));}}return max;}
}

代码是不是看上去好乱，加上回溯，我都不知道到底哪里买入哪里卖出的。没事，我这还有更强的杀招，什么时候买入什么时候卖出。我来告诉你:

详细版：

public class Main {static int up = 1000000;static List<String> outprint = new ArrayList<>();public static void main(String[] args) {//----------------输入------------------//Scanner scanner = new Scanner(System.in);int n = Integer.parseInt(scanner.nextLine());String str = scanner.nextLine();//----------------整理输入------------------//List<Integer> list = new ArrayList<>();int first = Integer.parseInt(str.split(" ")[0]);int mid = Integer.parseInt(str.split(" ")[1]);if (first < mid) {list.add(first);}int flag = mid - first;for (int i = 1; i < n; i++) {int pre = Integer.parseInt(str.split(" ")[i - 1]);int next = Integer.parseInt(str.split(" ")[i]);if (flag * (next - pre) < 0) {list.add(pre);flag = 0 - flag;}}int last = Integer.parseInt(str.split(" ")[n - 1]);if (Integer.parseInt(str.split(" ")[n - 2]) < last) {list.add(last);}//TODOint[] prices = new int[list.size()];for (int i = 0; i < list.size(); i++) {prices[i] = list.get(i);}int dy = dynamic(prices, 1, 1000 / prices[0], 1000 % prices[0]);if (dy > 1000) {outprint.add("在价格为" + prices[0] + "时买入");}Collections.reverse(outprint);outprint.remove(outprint.size() - 1);outprint.add("最终手里有" + dy);System.out.println(outprint);}public static int dynamic(int[] prices, int start, int n, int money) {//prices为操作，start为从什么时候开始操作，n为当前持有的股票数int max = 0;if (start == prices.length - 1) {if (n > 0) {int res = money + n * prices[start];outprint.add("在价格为" + prices[start] + "时卖出");return res;} else {return money;}}if (n > 0) {//此时可以卖也可以不卖int no = dynamic(prices, start + 1, n, money);int yes = dynamic(prices, start + 1, 0, money + prices[start] * n);if (no < yes) {outprint.add("在价格为" + prices[start] + "时卖出");max = yes;} else {max = no;}} else {//此时可以买也可以不买if (money > up) {int no = dynamic(prices, start + 1, 0, money);int yes = dynamic(prices, start + 1, up / prices[start], up % prices[start]);if (yes > no) {outprint.add("在价格为" + prices[start] + "时买入" + "此时因为手头超过100万了，所以我捐了" + (money - up));max = yes;} else {max = no;}} else {int no = dynamic(prices, start + 1, 0, money);int yes = dynamic(prices, start + 1, money / prices[start], money % prices[start]);if (yes > no) {outprint.add("在价格为" + prices[start] + "时买入");max = yes;} else {max = no;}}}return max;}
}

3. 颜色排序

题目描述：

小美得到了一个长度为n的整数序列，并且序列上每个数字都被染上了颜色1~n的其中一种。现在小美想要给这个序列按从小到大排序，但她每次操作只能交换相邻两个数，并且这两个数的颜色要不相同。她想知道进行若干次操作之后能不能给这个序列排好序。

输入描述：

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

对于每一组数据，第一行一个正整数n，表示这个序列的长度；第二行n个正整数ai，表示该序列；第三行n个正整数ci，表示第 i 个数的颜色。

数字间两两有空格隔开

1≤T≤8，1≤n≤104 ，1≤ai,ci≤n

输出描述：

对于每一组数据，如果可以排好序，输出一行Yes；否则，输出一行No。

样例输入：

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

样例输出:

Yes
No

样例解释:

第一组样例可以如下排序：
[3 2 4 1 5] -> [2 3 4 1 5] -> [2 3 1 4 5] -> [2 1 3 4 5] -> [1 2 3 4 5]

思路：同色不能交换的意思也就是说同色的相对顺序不能改变，如此一来我枚举每一种颜色, 如果相同颜色的数字都是有序的，那么就返回Yes，否则返回No。

public class Main {public static void main(String[] args) {//------------------输入--------------------//Scanner scanner = new Scanner(System.in);int T = Integer.parseInt(scanner.nextLine());for (int i = 0; i < T; i++) {int n = Integer.parseInt(scanner.nextLine());int[] nums = new int[n];String str1 = scanner.nextLine();for (int j = 0; j < n; j++) {nums[j] = Integer.parseInt(str1.split(" ")[j]);}int[] colors = new int[n];String st2 = scanner.nextLine();for (int j = 0; j < n; j++) {colors[j] = Integer.parseInt(st2.split(" ")[j]);}//TODOSystem.out.println(colorrank(nums, colors, n));}}public static String colorrank(int[] nums, int[] colors, int n) {//对于某个颜色，必须是有序的Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < n; i++) {if (map.containsKey(colors[i])) {if (map.get(colors[i]) > nums[i]) {return "No";} else {map.put(colors[i], nums[i]);}} else {map.put(colors[i], nums[i]);}}return "Yes";}
}

4. 方格染色

题目描述：

小美从老师那里得到了一张N x M的方格纸（即N行M列），上面每个方格都染上了一种颜色。

老师又给了小美另一张大小一模一样但是没有染色的方格纸，并对于方格纸上的每种颜色，老师给了她一些大小为2 x 2的颜料笔，每次可以选择一个大小恰好为2 x 2的方格染成同一种颜色（对已染色的方格也可以染色，同一种颜料笔可以用多次）。

老师想考考小美：能不能用这些颜料笔对这张未染色的方格纸进行染色，使得其与已染色的这张方格纸一模一样？

输入描述：

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

对于每一组数据，第一行输入两个正整数N，M；

接下来N行，每行M个数，第 i 行第 j 列的数表示为 Cij，表示这个位置的方格的颜色。

数字间两两有空格隔开。

2≤N,M≤200 , 1≤Cij≤NM , 1≤T≤10

输出描述：

对于每一组数据，如果可以染成与已染色的方格纸相同的话，输出一行Yes；否则，输出一行No。

样例输入：

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

样例输出：

Yes
No

思路：
染色的题目一般倒着做, 我最后一次涂抹的地方肯定是一块完整的2*2的同色快。那么我倒着来，我把它擦了（都换成-1）。然后我重新遍历，只要是一个2*2里出现同色块或者没有颜色（-1），那说明我之前在这里涂抹过，我把他们都擦掉。循环往复。最后如果我看整张纸是白纸了，那说明确实我可以画出来。只要还有颜色，直接返回No

代码实现：

public class Main {public static void main(String[] args) {//-------------输入-------------------//Scanner scanner = new Scanner(System.in);int T = Integer.parseInt(scanner.nextLine());for (int i = 0; i < T; i++) {String str1 = scanner.nextLine();int n = Integer.parseInt(str1.split(" ")[0]);int m = Integer.parseInt(str1.split(" ")[1]);int[][] colors = new int[n][m];for (int j = 0; j < n; j++) {String str2 = scanner.nextLine();for (int k = 0; k < m; k++) {colors[j][k] = Integer.parseInt(str2.split(" ")[k]);}}System.out.println(give_it_color_see(colors, n, m));}}public static String give_it_color_see(int[][] colors, int n, int m) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < m - 1; j++) {//将[i,j]作为左上角int color = 0;if (colors[i][j] != -1) {color = colors[i][j];} else if (colors[i + 1][j] != -1) {color = colors[i + 1][j];} else if (colors[i][j + 1] != -1) {color = colors[i][j + 1];} else if (colors[i + 1][j + 1] != -1) {color = colors[i + 1][j + 1];}if (color == 0) {continue;}if ((colors[i][j] == color || colors[i][j] == -1) && (colors[i][j + 1] == color || colors[i][j + 1] == -1) && (colors[i + 1][j] == color || colors[i + 1][j] == -1) && (colors[i + 1][j + 1] == color || colors[i + 1][j + 1] == -1)) {colors[i][j] = -1;colors[i][j + 1] = -1;colors[i + 1][j] = -1;colors[i + 1][j + 1] = -1;i = 0;j = -1;}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (colors[i][j] != -1) {return "No";}}}return "Yes";}
}

其他

Java的二维数组打印方式：
用Arrays.deepToString()

public class Main {public static void main(String[] args) {int[][] array = {{1, 2, 3}, {4, 5, 6}};System.out.println(Arrays.toString(array));//打印的是地址System.out.println(Arrays.deepToString(array));}
}

本人愚笨，上述的代码也不知道是否正确，如果有发现错误或者有更好的方法，请评论，谢谢各位大哥大嫂了

特别鸣谢

• qq_41556048：第一题错了，JCJCJCJCC 这种情况最小应该是4 你的是9 错了