一、附加题
描述
存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；
输入描述：
第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。
输出描述：
输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。
示例1
输入：
2 1 2
输出：
4
说明：
开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。
题解：
/** * { 0 i=1 * dp[i] = { dp[i-1]+2 i>1,pi[i-1]=i-1 * { dp[i-1]+(dp[i-1]-dp[pi[i-1]])+2 i>1,pi[i-1]<i-1 */ import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 1-n int[] pi = new int[n + 1]; // 1-(n+1) long[] dp = new long[n + 2]; // 1-n for(int i = 1; i <= n; ++i){ pi[i] = sc.nextInt(); } sc.close(); long mod = (long)(1e9+7); // 2-(n+1) for(int i = 2; i <= n + 1; ++i){ if(pi[i - 1] == i - 1){ dp[i] = (dp[i - 1] + 2) % mod; }else{ dp[i] = (dp[i - 1] + (dp[i - 1] - dp[pi[i - 1]]) + 2) % mod; } } // System.out.println(Arrays.toString(dp)); System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]); } }
二、编程题1
描述
有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛，有没有可能三只球队的分数打平。
输入描述：
第一行包含一个数字 t (1 <= t <= 10)
接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)
输出描述：
每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”
示例1
输入：
2 3 3 0 0 3 3 3 3
输出：
yes no
说明：
case1: 球队1和球队2 差0分，球队2 和球队3也差0分，所以可能的赛得分是三只球队各得1分 case2: 球队1和球队2差3分，球队2和球队3差3分，所以可能的得分是 球队1得0分，球队2得3分, 球队3 得0分，比赛已经全部结束因此最终不能打平。
题解：
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = Integer.parseInt(sc.nextLine()); for(int i=0;i<t;i++){ String s = sc.nextLine(); String[] ss = s.split(" "); long n = Long.parseLong(ss[0]); long k = Long.parseLong(ss[1]); long d1 = Long.parseLong(ss[2]); long d2 = Long.parseLong(ss[3]); // 利用剩余比赛场次解决 String res = solve2(n,k,d1,d2); System.out.println(res); } } private static String solve2(long n, long k, long d1, long d2) { long m1 = k + 2*d1 + d2; //情况1 if(m1 >= 0 && m1 % 3 == 0){ //m有解是大前提 long left = (n - k) - (2*d1 + d2); //需要2d1+d2才能让两个较低的追上最高的达到平局， if(left >= 0 && left % 3 == 0){ //那么剩下的场次要继续能被3整除才能继续保持平局。 return "yes"; } } long m2 = k + 2*d1 - d2;//情况2 if(m2 >= 0 && m2 % 3 == 0){ long left; if(d1 >= d2){ left = (n - k) - (2*d1 - d2); }else{ left = (n - k) - (2*d2 - d1); } if(left >= 0 && left % 3 == 0){ return "yes"; } } long m3 = k - 2*d1 + d2; //情况3 if(m3 >= 0 && m3 % 3 == 0){ long left = (n - k) - (d1 + d2); if(left >= 0 && left % 3 == 0){ return "yes"; } } long m4 = k - 2* d1 - d2; //情况4 if(m4 >= 0 && m4 % 3 == 0){ long left = (n - k) - (d1 + 2*d2 ); if(left >= 0 && left % 3 == 0){ return "yes"; } } return "no"; } }
三、 编程题2
描述
有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。
输入描述：
第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。
输出描述：
输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。
示例1
输入：
8 1 aabaabaa
输出：
5
说明：
把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。
题解：
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int len = sc.nextInt(); int oper = sc.nextInt(); String str = sc.next(); System.out.println(Math.max(arraySolve(len, oper, str, 'a'), arraySolve(len, oper, str, 'b'))); } public static int arraySolve(int n, int m, String s, char c) { int res = 0; List<Integer> indexes = new ArrayList<>(); // 用来存储a/b的所有下标位置 for (int i = 0; i < n; i++) { if (s.charAt(i) == c) { //用c来替换其他字符，将c所在下标位置加入 indexes.add(i); } } // 如果要替换的字符个数小于可替换个数，那么直接全部替换即可 if (indexes.size() <= m) { return n; } // 注意端点位置的处理 indexes.add(s.length()); res = indexes.get(m); for (int i = m + 1; i < indexes.size(); i++) { res = Math.max(res, indexes.get(i) - indexes.get(i - m - 1) - 1); } return res; }
