# 京东2019春招编程题参考代码

## 数内排序

### 时间复杂度

O(len(x)*log(len(x)))

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

int main() {
string x;
cin >> x;
sort(x.begin(), x.end());
reverse(x.begin(), x.end());
cout << x << endl;
return 0;
}```

## 幸运时刻

O(n)

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

int n;
int main() {
cin >> n;
string s;
int cnt = 0;
int flag;
for(int i = 0; i < n; i++) {
cin >> s;
flag = 0;
if(s[0] == s[3] && s[1] == s[4]) flag = 1;
if(s[0] == s[1] && s[3] == s[4]) flag = 1;
if(s[0] == s[4] && s[1] == s[3]) flag = 1;
if(flag) cnt++;
}
cout << cnt << endl;
}```

## 有趣的硬币

O(n)

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
cin >> s;
s = s[0] + s;
s = s + s[s.size() - 1];
int cnt = 0;
for(int i = 1; i < s.size() - 1; i++) {
if(s[i] != s[i - 1] || s[i] != s[i + 1]) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}```

## 整除

O(n*sqrt(n))

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;
int tmp[maxn];
int n;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
int k = i;
for(int j = 2; j * j <= n; j++) {
int s = 0;
while(k % j == 0) {
s++;
k /= j;
}
tmp[j] = max(tmp[j], s);
}
if(k > 1) tmp[k] = max(tmp[k], 1);
}
long long res = 1;
for(int i = 1; i <= 100000; i++) {
for(int j = 0; j < tmp[i]; j++) {
res = res * i % 987654321;
}
}
cout << res << endl;
return 0;
}```

## 牛牛下象棋

### 分析

dp[i][a][b]表示i次移动后，马位于坐标(a，b)的情况数。

dp[i+1][a1][b1] += dp[i][a][b]
dp[i+1][a2][b2] += dp[i][a][b]
...
dp[i+1][a8][b8] += dp[i][a][b]

O(81*K)

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

long long dp[100005][10][10];
int d[10][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int main() {
int k, X, Y, tx, ty;
scanf("%d%d%d", &k, &X, &Y);
dp[0][0][0] = 1;
for(int i = 0; i < k; i++) {
for(int x = 0; x <= 8; x++) {
for(int y = 0; y <= 8; y++) {
for(int j = 0; j < 8; j++) {
tx = x + d[j][0];
ty = y + d[j][1];
if(0 <= tx && tx <= 8 && 0 <= ty && ty <= 8)
dp[i+1][tx][ty] = (dp[i + 1][tx][ty] + dp[i][x][y]) % 1000000007;
}
}
}
}
printf("%lld\n", dp[k][X][Y]);
return 0;
}```

## 牛牛的括号匹配

### 分析

1. 如果整个字串没有被处理完，那么肯定是"No".
2. 如果flag=0, 那么要求没有'('剩下.
3. 如果flag=1, 那么结果栈中的'('只能是两个. "((" -> "()".

O(len(s))

### 参考代码

```#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

char str[maxn];
stack<char> s;

int main() {
int t;
cin >> t;
while(t--) {
while(!s.empty()) s.pop();
scanf("%s", str);
int n = strlen(str);
if(n == 2) {
if(str[0] == '(' && str[1] == ')') {
puts("No");
continue;
}
}
int i;
int flag1 = 0;
for(i = 0; i < n; i++) {
if(str[i] == '(') {
s.push('(');
} else {
if(!s.empty()) s.pop();
else {
if(flag1) break;
flag1 = 1;
s.push('(');
}
}
}
if(i == n) {
if(!flag1) {
if(s.empty()) puts("Yes");
else puts("No");
}
else {
if(s.size() != 2) puts("No");
else puts("Yes");
}
}
else puts("No");
}
return 0;
}```

## 分解整数

O(跑得过)

### 参考代码

```#include <bits/stdc++.h>

int main() {
int t;
long long n, x, y;
scanf("%d", &t);
while(t--) {
scanf("%lld", &n);
if(n & 1)
printf("No\n");
else {
for(y = 2; y <= n; y += 2) {
if(n % y == 0 && ((n / y) & 1)) {
x = n / y;
break;
}
}
printf("%lld %lld\n", x, y);
}
}
return 0;
}```

## 生成回文串

### 分析

dp[l][r]表示区间 [l, r] 内的回文串数目。

O(n^2)

### 参考代码

```#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 50 + 5;
LL dp[maxn][maxn];
char s[maxn];
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
memset (dp, 0, sizeof(dp));
for(int i = 1; i <= len; i++) {
for(int l = 1; l + i - 1 <= len; l++) {
int r = l + i - 1;
dp[l][r] += dp[l + 1][r];
dp[l][r] += dp[l][r - 1];
if (s[l] == s[r]) dp[l][r] += 1;
else dp[l][r] -= dp[l + 1][r - 1];
}
}
printf ("%lld\n", dp[1][len]);
return 0;
}```
#春招#

666

console.log("大佬6666666");

import sys n = int(sys.stdin.readline().strip()) ans = 0 nums = [] for i in range(n): line = sys.stdin.readline().strip() nums.append(int(line)) res =[] for n in nums: if (n%2 == 1): print("No") else: a = n / 2 while(a % 2 == 0 ): a = a / 2 b = n / a c = n / b print c, b