20230907 携程笔试AK
先mark一下，笔试结束后发题解
===========分割线================
t1
题目：找到n个数中相邻的两位之和不是素数的个数。
/**
* 先找出所有的素数对，然后dfs
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
LinkedList<Integer>[] next = new LinkedList[n];
for (int i = 1; i <= n; ++i) {
next[i - 1] = new LinkedList<>();
for (int j = 1; j <= n; ++j) {
if (i != j && checkPrime(i + j)) {
next[i - 1].add(j - 1);
}
}
}
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += dfs(n - 1, i, next, new boolean[n]);
}
System.out.println(sum);
}
static int dfs(int cnt, int cur, LinkedList<Integer>[] next, boolean[] vis) {
if (cnt == 0) {
return 1;
}
int sum = 0;
vis[cur] = true;
for (int num : next[cur]) {
if (!vis[num]) {
sum += dfs(cnt - 1, num, next, vis);
}
}
vis[cur] = false;
return sum;
}
static boolean checkPrime(int n) {
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return true;
}
return false;
}
t2.这题写复杂了，不用分成四个象限
题目：找到以you为三个点组成的直角三角形
/**
* 对于每个点，如果属于'you'中的一个字符，比如说是'y'，以它为直角，然后再找到它左边‘o’，上边的点'u'的个数相乘+左边'u'与上边'o'的个数相乘的个数
* 同样的，需要找到其余三个象限（左边+下边，右边+上边，右边+下边）相加即可
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int[][][] dp = new int[n + 1][m + 1][3];
char[] c = new char[]{'y', 'o', 'u'};
//构造
for (int i = 0; i < n; ++i) {
String s = in.next();
for (int j = 0; j < s.length(); ++j) {
for (int k = 0; k < 3; ++k) {
dp[i + 1][j + 1][k] = dp[i + 1][j][k] + dp[i][j + 1][k] - dp[i][j][k] + (c[k] == s.charAt(j) ? 1 : 0);
}
}
}
long sum = 0;
int[][] dir = new int[4][3];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int target = isTargetChar(dp, i, j);
if (target == -1) continue;
for (int k = 0; k < 3; ++k) {
dir[0][k] = dp[i][j - 1][k] - dp[i - 1][j - 1][k];//左边k字符的个数
dir[1][k] = dp[i - 1][j][k] - dp[i - 1][j - 1][k];//上边k字符的个数
dir[2][k] = dp[n][j][k] - dp[i][j][k] - dp[n][j - 1][k] + dp[i][j - 1][k];//下边k字符的个数
dir[3][k] = dp[i][m][k] - dp[i][j][k] - dp[i - 1][m][k] + dp[i - 1][j][k];//右边k字符的个数
}
//lu
sum += (long) dir[0][(target + 1) % 3] * dir[1][(target + 2) % 3] + (long) dir[1][(target + 1) % 3] * dir[0][(target + 2) % 3];
//ld
sum += (long) dir[0][(target + 1) % 3] * dir[2][(target + 2) % 3] + (long) dir[2][(target + 1) % 3] * dir[0][(target + 2) % 3];
//ru
sum += (long) dir[3][(target + 1) % 3] * dir[1][(target + 2) % 3] + (long) dir[1][(target + 1) % 3] * dir[3][(target + 2) % 3];
//rd
sum += (long) dir[3][(target + 1) % 3] * dir[2][(target + 2) % 3] + (long) dir[2][(target + 1) % 3] * dir[3][(target + 2) % 3];
}
}
System.out.println(sum);
}
static int isTargetChar(int[][][] dp, int x, int y) {
for (int i = 0; i < 3; ++i) {
int cnt = dp[x][y][i] + dp[x - 1][y - 1][i] - dp[x - 1][y][i] - dp[x][y - 1][i];
if (cnt != 0) return i;
}
return -1;
}
t3：
可以对一个数+1，但是同时需要对一个数-1，计算将所有数移到到[l,r]的代价
/**
* 就是需要将不在[l,r]范围内的数移到[l,r]范围内，所以首先需要计算，平均数在不在[l,r]范围内，
* 然后只需要计算需要将超过r的数移到r，和小于l的数移动到l的最大步数即可。
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int i = 0; i < t; ++i) {
int n = in.nextInt();
//不加long 只能过85%
long l = in.nextInt();
long r = in.nextInt();
long[] arr = new long[n];
long sum = 0;
long high = 0;
long low = 0;
for (int j = 0; j < n; ++j) {
arr[j] = in.nextInt();
sum += arr[j];
if (arr[j] < l) {
low += l - arr[j];
} else if (arr[j] > r) {
high += arr[j] - r;
}
}
if (sum > r * n || sum < l * n) {
System.out.println(-1);
} else {
System.out.println(Math.max(low, high));
}
}
}
t4
题目：给一个0和1组成的字符串，求子串中有多少“好串”。
对“好串”的定义是：所有的前缀子串中，0的数量全部严格大于1的数量
计算好串的个数
/**
* 找规律
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
int cnt0 = 0;
long sum = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '0') {
cnt0++;
sum += cnt0;
} else {
cnt0--;
if (cnt0 > 0) {
sum += cnt0;
} else {
cnt0 = 0;
}
}
}
System.out.println(sum);
}
新环境公司福利 12人发布