腾讯
1. 打怪兽游戏
小Q在玩一款打怪兽的游戏，他在之前的关卡已经获得了足够多的金币，当前关有n个怪兽，每个怪兽有$C_i$的血量，打死它可以获得$W_i$的金币， 问小Q通过当前关卡最多可以多获得多少金币。
输入：
输入两个数，n,m 。n表示怪兽的数量，m表示一个金币可以购买的血量
接下来n行，每行是一个怪兽的血量和打死它可以获得的金币。
输出：
通过当前关卡最多可以多获得的金币数
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
using namespace std;
const int N = 1010;
int c[N], w[N];
int main() {
int n, m;
while (cin >> n >> m) {
for (int i = 0; i < n; i++) {
cin >> c[i] >> w[i];
}
int cost = 0; // 记录买血花了多少钱
int blood = 0; // 记录自己拥有的血量
int gain = 0; // 记录打怪兽获得的金币
// 遍历每一只怪兽，可以选择打或者不打
for (int i = 0; i < n; i++) {
// 先购买可以打死当前怪兽的血量
int cnt = 0;
while (blood < c[i]) {
cnt++;
blood += m;
}
//如果买血花的金币小于等于打死获得的金币，说明值得打
if (cnt - w[i] <= 0) {
cost += cnt;
blood -= c[i];
gain += w[i];
// 否则选择不打
} else {
blood -= cnt * m;
}
}
cout << gain - cost << endl;
}
return 0;
}
2. 抛物线与直线围成的面积
求抛物线 $y^2 = 2Ax$ 和直线 $y = Bx + C$ 所围成的面积.
输入：A B C
输出：面积
思路：联合两个方程求解交点的y坐标，$y=\frac{A+-\sqrt{A^2-2ABC}}{B}$,
$\int_{y_1}^{y^2} \frac{y-C}{B}-\frac{y^2}{2A} dy $
然后对这个式子进行积分
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int f(int A, int B, int C) {
int delta = pow(A, 2) - 2 * A * B * C;
if (delta < 0) return 0;
double y1 = (A - sqrt(delta)) / B, y2 = (A + sqrt(delta)) / B;
double x2 = pow(y2, 2) / (2 * B) - C / B * y2 - pow(y2, 3) / (6 * A);
double x1 = pow(y1, 2) / (2 * B) - C / B * y1 - pow(y1, 3) / (6 * A);
return x2 - x1;
}
int main() {
int T;
cin >> T;
while (T--) {
int A, B, C;
cin >> A >> B >> C;
double res = f(A, B, C);
cout << res << endl;
}
return 0;
}
3. 牢房冲突
有n个牢房，编号为1~n,每个牢房中都包含一个人，每个人都可以在1~m中选择一个数字，如果有相邻牢房选择的数字相同，则会发生冲突。求发生冲突的情况有多少种？结果取mod100003.
输入： m ，n
输出： 发生冲突的情况数。
思路：数学推导，所有情形数-任意相邻房间数不同的情形，即m^n - m* (m-1)^(n-1)，考察点：快速幂算法：有模板！！！
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
const int mod = 100003;
// 快速幂模板 m^k%p 时间复杂度O(logk)
int qmi(int m, int k, int p) {
int res = 1 % p, t = m;
while (k) {
if (k & 1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
int main() {
LL m, n;
while (cin >> m >> n) {
int x1 = qmi(m, n, mod);
int x2 = m * qmi(m - 1, n - 1, mod);
cout << x1 - x2 << endl;
}
}
4. 完美数
有n个数，每个数有k个属性值，对于任意的两个数$a_i$和$a_j$，如果 $a_{i1}$+$a_{j1} $= $a_{i2}$+$a_{j2}$ = …=$a_{ik}$+$a_{jk}$,则成$a_i$和$a_j$是一对完美数。 求这n个数中总共有多少对完美数.
输入： n, k 。n个数，每个数有k个属性。
接下来n行，每行k个属性
输出：
总共有多少对完美数
思路：记录属性的变化值，让变化值作为键，变化值与当前相反的就是完美数对, 如1,2,3,4 和 4,3,2,1 它们的差值分别是 1,1,1 和 -1,-1,-1. 因为差值相反，所以它们是一对完美数
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int main() {
int n, k;
while (cin >> n >> k) {
int g[n][k];
for (int i = 0; i < n; i++)
for (int j = 0; j < k; j++) cin >> g[i][j];
map<vector<int>, int> hash;
for (int i = 0; i < n; i++) {
vector<int> key;
// 记录属性的差值
for (int j = 0; j < k - 1; j++)
key.push_back(g[i][j + 1] - g[i][j]);
// 更新属性差值的次数
hash[key]++;
}
map<vector<int>, int>::iterator it;
int res = 0;
for (it = hash.begin(); it != hash.end(); it++) {
auto item = *it;
vector<int> tmp = item.first;
int val = item.second;
vector<int> inv;
bool flag = false; // 用来标记差值是否为0
for (int i = 0; i < tmp.size(); i++) {
inv.push_back(-tmp[i]);
if (tmp[i] != 0) flag = true;
}
if (flag) // 不为0，则完美数对数为当前次数与与它差值相反的次数的乘积
res += val * hash[inv];
else // 为0的情况
res += val * (val - 1);
}
// 因为每一对都计算了两次，需要除以2
cout << res / 2 << endl;
// 暴力法
// int res = 0;
// for (int i = 0; i < n - 1; i++) {
// for (int j = i + 1; j < n; j++) {
// int t = 0;
// int sum = g[i][0] + g[j][0];
// for (t = 1; t < k; t++) {
// if (g[i][t] + g[j][t] != sum) break;
// }
// if (t == k) res++;
// }
// }
// cout << res << endl;
}
return 0;
}
5. 最大关系网
有n对关系，比如A和B有关系，B和C有关系，则ABC关系。求这些关系中能构成的最大关系网中的人数。
输入：
n 。n对关系
接下来n行，每行是一对关系
输出：
这些关系中构建出来的最大关系网中的人数
参考代码
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main(){
// 待填
return 0;
}
阿里
1. 翻转01串
给你一串01组成的字符串，可以选择一个位置进行翻转，即0变1,1变0，同时与该位置相邻的位置也要进行翻转 如 11011 在0的位置翻转变为10101，问给定一个这样的串，最少经过多少次翻转可以变成全0串，如果变不成输出NO。
样例：
“01” –> NO
“011” –> 1
思路：每一个位置要么不翻转，要么只翻转一次，翻转两次相当于没翻转,然后深度优先搜索。LeeCode1284
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int reverse(string s) {
if (s == "1") {
return 1;
} else if (s == "0") {
return 0;
}
int count = 0;
if (helper(s, 0, 0)) {
return res;
} else {
return -1;
}
}
private:
int res = 0; // 记录翻转次数
bool helper(string s, int index, int count) {
string temp(s.size(), '0'); // 和s等长的全0串
if (s == temp) { // 如果等于全0串，则记录翻转次数，返回
res = count;
return true;
}
// 如果翻转的位置已经到达s的末尾，则不能翻转成全0串
if (index == s.size()) {
return false;
}
// 递归，要么翻转当前位置，要么不翻转当前位置
// 翻转当前位置 调用reverse函数翻转，计数器count+1，并移动到下一个位置
// 若不翻转，移到下一个位置，
return helper(s, index + 1, count) ||
helper(reverse(s, index), index + 1, count + 1);
}
// 翻转字符串中的每一个位置，注意边界情况
string reverse(string s, int index) {
int n = s.size() - 1;
if (index == 0) {
s[0] = s[0] == '0' ? '1' : '0';
s[1] = s[1] == '0' ? '1' : '0';
} else if (index == n) {
s[n] = s[n] == '0' ? '1' : '0';
s[n - 1] = s[n - 1] == '0' ? '1' : '0';
} else if (index > 0 && index < n) {
s[index - 1] = s[index - 1] == '0' ? '1' : '0';
s[index] = s[index] == '0' ? '1' : '0';
s[index + 1] = s[index + 1] == '0' ? '1' : '0';
}
return s;
}
};
int main() {
Solution solu = Solution();
string str = "011111";
int res = solu.reverse(str);
if (res != -1) {
cout << res << endl;
} else {
cout << "No";
}
return 0;
}
2.射鹿
有n头鹿，m只箭，每头鹿都有一定的血量，每只箭也有相应的伤害值，使用每只箭都有相应的花费，当箭的伤害值大于等于鹿的血量时，可以将其射死，问如果能将所有鹿射死，求需要的最少花费是多少，如果不能全部射死，就输出NO。
样例：
1 // 测试用例的组数
3 3 // n,m
1 2 3 // 鹿的血量
2 3 4 // 箭的伤害值
1 2 3 // 箭的花费
6 // 输出最小花费
思路：将鹿按血量排序，定义一个箭的结构体，包含伤害值和花费两个属性，将箭按照伤害值排序， 然后对每只鹿，用能将其射死且花费最小的箭射它，这儿用到按花费排序的优先队列。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Arrow {
int damage;
int cost;
Arrow(int x, int y) : damage(x), cost(y) {}
};
struct cmp {
bool operator()(Arrow* a1, Arrow* a2) { return a1->cost > a2->cost; }
};
bool static compare(Arrow* a1, Arrow* a2) { return a1->damage < a2->damage; }
int main() {
int T;
cin >> T;
for (int i = 0; i < T; i++) {
int N, M;
cin >> N >> M;
vector<int> nums(N, 0);
vector<Arrow*> arrows;
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
vector<int> damage(M, 0);
for (int i = 0; i < M; i++) {
cin >> damage[i];
}
vector<int> cost(M, 0);
for (int i = 0; i < M; i++) {
cin >> cost[i];
}
for (int i = 0; i < M; i++) {
Arrow* arrow = new Arrow(damage[i], cost[i]);
arrows.push_back(arrow);
}
if (N > M) {
cout << "NO";
} else {
// 定义优先队列 用于按花费大小存储伤害值高于血量的箭
priority_queue<Arrow*, vector<Arrow*>, cmp> q;
int res = 0; // 记录结果
bool can = true; // 能否全部射死
sort(nums.begin(), nums.end()); // 按血量排序
sort(arrows.begin(), arrows.end(), compare); // 按伤害值排序
int j = M - 1;
for (int i = N - 1; i >= 0; i--) {
// 将能射死当前鹿的箭入优先队列
while (j >= 0 && arrows[j]->damage >= nums[i]) {
q.push(arrows[j]);
j--;
}
// 如果没有能射死当前鹿的箭，则不能全部射死
if (q.size() == 0) {
cout << "NO";
can = false;
break;
//否则拿出花费最小的箭射死当前鹿
} else {
Arrow* arrow = q.top();
q.pop();
res += arrow->cost;
}
}
if (can) {
cout << "Total cost: " << res;
}
}
}
}
华为
1. 名字选举
输入一串字符串，表示人名，输出票数最多的人的名字，票数一样多的按名字字典序排序（如：Tom和Lily，Lily在前），字典序一样的，名字短的在前面（比如：Tom和Tommy，Tom在前），其中每个人名只有首字母大写，用逗号隔开。
输入 : Tom Lily Mike Lily Tom
输出：Lily
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef pair<string, int> PII;
vector<PII> names;
map<string, int> m;
bool check(string s) {
if (s.empty()) return false;
if (s[0] < 'A' || s[0] > 'Z') return false;
for (int i = 1; i < s.size(); i++) {
if (s[i] < 'a' || s[i] > 'z') return false;
}
m[s]++;
return true;
}
bool split(string s) {
int len = s.size();
if (!len) return false;
s += ' ';
string cur;
int p = 0;
while (p <= len) {
if (s[p] == ' ') {
bool ok = check(cur);
if (!ok) return false;
cur = "";
} else {
cur += s[p];
}
p++;
}
return true;
}
bool cmp(PII p1, PII p2) {
if (p1.second != p2.second) return p1.second > p2.second;
// if (p1.first.size() == p2.first.size()) return p1.first < p2.first;
// if (p1.first.find(p2.first) != p1.first.npos) return false;
// if (p2.first.find(p1.first) != p2.first.npos) return true;
return p1.first < p2.first;
}
int main() {
string s;
getline(cin, s);
bool isValid = split(s);
if (!isValid) {
cout << "error.0001" << endl;
} else {
for (auto item : m) {
names.push_back({item.first, item.second});
}
sort(names.begin(), names.end(), cmp);
cout << names[0].first << endl;
}
return 0;
}
2. 字符串匹配
输入一串字符串，找出特定字符串后面的特定类型的值，保证’[‘前的字符要和第一个关键词就是read 是一样的，中间也要保证十六进制。
输入：“read read[addr=0x17,mask=0xff,val=0x7], read_his[addr=0xff,mask=0xff,val=0x1], read[addr=0xf0,mask=0xff,val=0x80]“
输出：addr mask val 所对应16进制值
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 需要记录的信息很多时，可以定义一个结构体
struct Info {
string addr;
string mask;
string val;
};
string content, pattern;
vector<Info> res;
bool check16(string s) {
int len = s.size();
if (len < 3) return false;
int idx = 0;
if (s[idx] != '0') return false;
++idx;
if (s[idx] != 'x' && s[idx] != 'X') return false;
++idx;
string num = s.substr(idx);
for (int i = 0; i < num.size(); ++i) {
char ch = num[i];
if (ch >= '0' && ch <= '9') continue;
if (ch >= 'A' && ch <= 'F') continue;
if (ch >= 'a' && ch <= 'f') continue;
return false;
}
return true;
}
void check(string s) {
int len = s.size();
string head = s.substr(0, pattern.size());
if (head != pattern) return;
int idx = pattern.size();
if (idx < len && s[idx] != '[') return;
idx++;
if (s.substr(idx, 5) != "addr=") return;
idx += 5;
int pos = s.find(',', idx);
if (pos == s.npos || !check16(s.substr(idx, pos - idx))) return;
string addr = s.substr(idx, pos - idx);
idx = pos + 1;
if (s.substr(idx, 5) != "mask=") return;
idx += 5;
pos = s.find(',', idx);
if (pos == s.npos || !check16(s.substr(idx, pos - idx))) return;
string mask = s.substr(idx, pos - idx);
idx = pos + 1;
if (s.substr(idx, 4) != "val=") return;
if (!check16(s.substr(idx))) return;
string val = s.substr(idx);
res.push_back({addr, mask, val});
}
void solve(string s) {
int len = s.size();
s += ',';
int idx = 0;
while (idx <= len) {
int pos = s.find("],", idx);
if (pos == s.npos) break;
check(s.substr(idx, pos - idx));
idx = pos + 2;
}
}
int main() {
cin >> pattern >> content;
solve(content);
if (res.size() == 0) {
cout << "FAIL" << endl;
} else {
for (int i = 0; i < res.size(); i++) {
cout << res[i].addr << ' ' << res[i].mask << ' ' << res[i].val
<< endl;
}
}
return 0;
}
3. 最大开销栈
函数a 的空间是30，函数a调用了函数b(空间是60)，函数b调用了函数c(空间是30)，则最大开销栈是30+60+30=120。
输入：第一行n，表示n个函数，编号为1-n, 第二行n个数，表示n个函数每个函数调用的子函数个数，接下来n行分别是每个函数的编号，空间，调用的子函数编号
输出：最大开销
测试例：
6
2 3 1 0 0 0 // 表示每个函数调用多少个子函数
1 20 2 3
2 30 3 4 5
3 50 4
4 60
5 80
6 90
输出：160，解释1-2-3-4
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
vector<int> callnum, fsize;
vector<vector<int>> G;
int ans;
map<string, int> mp;
vector<bool> vis;
bool dfs(int cur, int sum) {
vis[cur] = true;
ans = max(ans, sum);
for (int i = 0; i < G[cur].size(); ++i) {
int nxt = G[cur][i];
if (vis[nxt]) return false;
bool ret = dfs(nxt, sum + fsize[nxt]);
if (!ret) return false;
}
vis[cur] = false;
return true;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
callnum.push_back(num);
}
int id = 0;
for (int i = 0; i < n; ++i) {
string name;
cin >> name;
if (mp.count(name) == 0) {
mp[name] = ++id;
}
int sz;
cin >> sz;
fsize.resize(id + 5);
fsize[mp[name]] = sz;
for (int j = 0; j < callnum[i]; ++j) {
string s;
cin >> s;
if (mp.count(s) == 0) mp[s] = ++id;
G.resize(id + 5);
G[mp[name]].push_back(mp[s]);
}
}
if (id != n) {
cout << "NA" << endl;
return 0;
}
vis.resize(id + 5);
for (auto o : mp) {
int enter = o.second;
for (int i = 1; i <= id; ++i) vis[i] = false;
bool ret = dfs(enter, fsize[enter]);
if (!ret) {
cout << "R" << endl;
return 0;
}
}
cout << ans << endl;
return 0;
}
4. 字符串全排列
给定一个字符串（最多包含8个字符），可能包含重复的字母，返回有多少种不同的排列组合。类似LeeCode47题
输入：字符串
输出：不重复的排列组合数
样例：
输入：abc
输出：6
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
int res = 0;
void dfs(string s, int begin, vector<bool>& used) {
if (begin == s.size()) {
res += 1;
return;
}
for (int i = 0; i < s.size(); i++) {
if (used[i] || (i > 0 && s[i] == s[i - 1] && used[i - 1])) continue;
used[i] = true;
dfs(s, begin + 1, used);
used[i] = false;
}
}
int main() {
string s;
while (getline(cin, s)) {
if (s.size() <= 0 || s.size() >= 8) {
cout << 0 << endl;
continue;
}
int len = s.size();
res = 0;
sort(s.begin(), s.end());
vector<bool> used(s.size(), false);
dfs(s, 0, used);
cout << res << endl;
}
return 0;
}
5. 字符串秘钥
给定一个字符串M和一个整数k，可以删除M中任意k个字符，返回字典序最小的那一个作为秘钥。
输入：字符串M和k值
输出：秘钥
样例：
输入：bacaa 1
输出：acaa
思路：遍历这个字符串，类似于冒泡算法不断比较相邻的字符。如果遇到逆序对就删掉第一个字符，k–，然后继续比较剩余的字符；如果全部逆序对都删除了k仍然大于0，就删掉后面的剩余字符； 如果当前枚举的字符串比当前最优ans要大就不需要比较了，直接返回。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
void dfs(int k, string m, string& res) {
if (k == 0) {
res = min(res, m);
return;
}
int i;
for (i = 0; i < m.size() - 1; i++) {
if (m[i] > m[i + 1]) {
string tmp = m;
m.erase(i, 1);
if (m < res) dfs(k - 1, m, res);
m = tmp;
}
}
if (i == m.size() - 1 && k > 0) dfs(0, m.erase(m.size() - k), res);
}
int main() {
string m;
int k;
while (cin >> m >> k) {
string res = m;
dfs(k, m, res);
cout << res << endl;
}
return 0;
}
6. 最短路径
A要去B的城市找他玩，但是去B的城市有很多路径，A身上的钱也有限，请你帮他找到去B的城市的最短路径，路费也要足够。城市之间有单向的路径，每条路径有一定的路费。这题默认A在1号城市，B在N号城市。输出最短路径。如果钱不够到达B的城市，则输出-1.
输入：k,n,r //分别表示路费，城市数量，边的数量
接下来r行，每行s, d, l, t 分别表示起点，终点，距离，花费
输出：最短路径
样例：输入：
5
6
7
1 2 2 4
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
输出：11 // 1->3->5->4->6
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <climits>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 110, M = 100010, INF = 100000000;
int g[N][N], dist[N];
int cost[N][N], val[N];
bool st[N];
int k, n, r;
void dijkstra() {
for (int i = 1; i <= n; i++) {
dist[i] = INF;
val[i] = INF;
}
dist[1] = 0;
val[1] = 0;
for (int i = 0; i < n; i++) {
int id, mind = INF;
for (int j = 1; j <= n; j++) {
// 这儿需要根据花费来选，选取到起点花费最小的点
if (!st[j] && val[j] < mind) {
id = j;
mind = val[j];
}
}
st[id] = true;
for (int j = 1; j <= n; j++) {
if (val[j] > val[id] + cost[id][j]) {
dist[j] = dist[id] + g[id][j];
val[j] = val[id] + cost[id][j];
} else if (val[j] > val[id] + cost[id][j] &&
dist[j] > dist[id] + g[id][j]) {
dist[j] = dist[id] + g[id][j];
}
}
}
}
int main() {
while (cin >> k >> n >> r) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
g[i][j] = INF;
cost[i][j] = INF;
}
}
for (int i = 0; i < r; i++) {
int s, d, l, t;
cin >> s >> d >> l >> t;
g[s][d] = l;
cost[s][d] = t;
}
dijkstra();
// cout << dist[n] << ' ' << val[n] << endl;
if (dist[n] != INF && val[n] < k) {
cout << dist[n] << endl;
} else {
cout << -1 << endl;
}
}
return 0;
}
快手
美团
1. 优秀学生奖励
给n个学生的m科成绩，如果一个学生的某一科是单科最高，那么这个学生获得奖励，即便该学生有多科最高，也只获得一次奖励。求获得奖励的学生人数。
输入：n, m 表示n个学生m个科目，接下来n行，每行是一个学生的m科成绩
输出：获得奖励的学生数
思路：直接遍历每个科目求最大值就行了，要注意的细节是，可能有很多学生获得该科最高分，此时所有最高分都有奖励。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> data(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int tmp;
cin >> tmp;
data[i].push_back(tmp);
}
}
vector<int> flag(n); // 用于标记获得奖励的学生
for (int j = 0; j < m; ++j) {
int max_value = 0;
vector<int> max_index; // 用来存最大值对应的同学的索引
for (int i = 0; i < n; ++i) {
if (data[i][j] > max_value) {
max_value = data[i][j];
max_index.clear();
max_index.push_back(i);
} else if (data[i][j] == max_value) {
max_index.push_back(i);
}
}
// 将当前科最大值的同学打上标记
for (int i = 0; i < max_index.size(); ++i) {
flag[max_index[i]] = 1;
}
}
int ans = 0;
// 统计结果
for (int i = 0; i < n; ++i) {
ans += flag[i];
}
cout << ans << endl;
return 0;
}
2. 递推式的循环起点
给a,b,x,m四个数，给定递推式 x = (a * x + b ) % m，这个x不停算会循环，问递推第几次起x开始循环。
输入：a,b,x,m
输出：第几次开始循环
思路：因为取模m，x取值最多m种，维护一个m长度的flag数组，见到没见过的x就标记，如果见过了就代表循环了。根据抽屉原理，最多m+1次就一定会开始循环!!!
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>
using namespace std;
typedef long long LL;
int main() {
LL a, b, m, x;
cin >> a >> b >> m >> x;
map<LL, int> mp;
int res = 0;
while (true) {
x = (a * x + b) % m;
if (mp.count(x)) { // 遇到见过的，说明重复了
cout << res << endl;
break;
}
mp[x]++;
res++;
}
return 0;
}
3. 第K大有序数对
给定n个数，这n个数两两结合构成一共$n^2$个有序数对（i， j）（可以自己和自己构成有序数对）。给定k，求第k大的有序数对是哪一个。例如给定1，2，2那么9个有序数对应该是： （1，1）（1，2）（1，2） （2，1）（2，2）（2，2） （2，1）（2，2）（2，2） 这是第5大的应该是（2，1）而不是第二行第二列的（2，2）
输入： n,k 表示n个数，第k大。接下来n个数
输出：第K大的有序对
思路：先排序得到数列data，有序数对中第一个数越小那么有序数对越小。第一想法很容易想到 （data[(k-1)/n], data[(k-1)%n]）是答案，但这样忽略了数列中可能存在相同元素。(这样写答案大概得64%)。这时候先定位第k大所在的有序数对中第一个数是什么，很明显是data[(k-1)/n] 再数这个数重复出现了几次，假如出现了p次。再数比这个数小的有几个，假如有q个。 那么答案就是（data[(k-1)/n], data[(k-n*q-1)/p]）。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
int main() {
int n;
LL k;
vector<int> data;
cin >> n >> k;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
data.push_back(tmp);
}
sort(data.begin(), data.end());
LL a = (k - 1) / n;
LL l = 0, row = 0;
while (data[l] != data[a]) ++l;
while (data[l + row] == data[a]) ++row;
LL aa = (k - 1 - l * n) / row; // 这个索引牛皮！！！
printf("(%d,%d)", data[a], data[aa]);
return 0;
}
4. 伪中位数
给定有序数列伪中位数的定义，m=a[floor((n-1)/2)]，其实就是当n为奇数时就是正常中位数，n是偶数时取中间两个数较小的那个数。给定一个数列，和一个值k，问至少添加几个数，使得该序列的伪中位数等于k。
输入：n个数和k
输出：需要添的数的个数
思路：稍微分析就可以知道，如果需要往数列里加数，不停加k就行了，现在求需要加几个k。先遍历数列，统计出比k小的数small个，跟k一样大的数equal个，比k大的数big个。很容易发现，如果k是伪中位数，就一定有small+equal >= big和big + equal > small两个式子同时成立。第二个式子可以变换成 big + equal >= small+1，最后解出equal满足 equal >= big-small 且 equal >= small-big+1。所以equal比二者较大值大，即equal>=max(big-small, small-big+1)。需要补的k的个数即max(big-small, small-big+1) - equal。注意上式可能为负，跟0再取个最大即可。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int n, k;
int main() {
cin >> n >> k;
int cnt_big = 0, cnt_equal = 0, cnt_small = 0;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
if (t < k)
cnt_small++;
else if (t == k)
cnt_equal++;
else
cnt_big++;
}
int res = max(0, max(cnt_small - cnt_big + 1, cnt_big - cnt_small) - cnt_equal);
cout << res << endl;
return 0;
}
5. 子串和子序列
给两个字符串s,t求s的子串与t的子序列相同的情况有多少种。字串的定义是连续的子字符串。 子序列的定义是不必连续的子序列。abcde的子序列可以是ace。
输入：两个字符串
输出：相同的情况数
思路：动态规划，定义f[i][j]为字符串s到第i个位置为止，且用上了第i个位置的字符；字符串t到第j个位置为止；此时的相同数目。
状态转移方程，分两种情况：
第一种是s串的子串就是s[i]自己，（长度为1的字串）,那么此时种类数是cntj[s[i]]，这个数的意思是字符串t的前j个字符里，有多少个s[i]。这种情况很好理解。
第二种是s串字串长度大于2，且包含s[i]。这种情况下考虑s[i]和t中的哪一个字符配对。事实上总共有cntj[s[i]]种配对方法（这个数的意思详见上面）。假设这些s[i]分别出现在t串的p1,p2,p3,…,pc (c=cntj[s[i]])这些位置那么种类数是f[i-1][p1-1]+f[i-1][p2-1]+...+f[i-1][pc-1]。
综上，f[i][j] = cntj[s[i]] + (f[i-1][p1-1]+f[i-1][p2-1]+...+f[i-1][pc-1])
最终答案为f[1][nt] + f[2][nt] + ... + f[ns][nt] ns和nt为s串和t串的长度。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
const int M = 1000000007;
int f[5001][5001], ns, nt;
string s, t;
int main() {
cin >> s >> t;
ns = s.size();
nt = t.size();
unordered_map<char, int> cnt;
unordered_map<char, vector<int>> value;
for (int j = 1; j <= nt; ++j) {
char tt = t[j - 1];
cnt[tt]++;
if (value.find(tt) == value.end()) {
value[tt].resize(ns + 1);
}
for (int i = 1; i <= ns; ++i) {
char ss = s[i - 1];
f[i][j] = cnt[ss];
if (value.find(ss) != value.end()) {
f[i][j] = (f[i][j] + value[ss][i - 1]) % M;
}
value[tt][i] = (value[tt][i] + f[i][j - 1]) % M;
}
}
int ans = 0;
for (int i = 1; i <= ns; ++i) {
ans = (ans + f[i][nt]) % M;
}
cout << ans;
return 0;
}
拼多多
1. 买三赠一 (4.10)
买商品，买三送一，送价钱最低的，准备买n个商品（编号1-n），其中第i个商品的价格为Ai，现在找到策略，花最少的钱买到所有商品。
输入：
第一行：一个整数n，$1\le n \le 10,000$;第二行：n个整数$A_i$,分别表示n个商品的价格，$1 \le A_i \le 1,000,000$
输出：最少需要花费多少钱？
样例：
输入：
4
100 200 300 400
输出：800 // 解释：买200 300 400省200，再加上100。
思路：先递减排序，然后三个一组计算
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int p[N];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i];
}
sort(p, p + n);
reverse(p, p + n);
int cost = 0;
int count = 0;
int index = 0;
while (index < n) {
cost += p[index];
count++;
if (count == 3) {
cost -= p[index];
count = 0;
}
index++;
}
cout << cost << endl;
}
2. 和谐区 (4.10)
某个小区有1-n棵树，每棵树有个和谐值$A_i$，如果一段连续的树，他们和谐值之和可以被$m$整除，那么这个区间整体就是和谐的。求有多少个这样的区间? LeeCode974
输入：
第一行两个整数 n, m
第二行n个整数，分别表示第i棵树的和谐值，$0\le A_i \le 1,000,000$
输出：满足的区间数量
样例：
输入：
5 2
1 2 3 4 5
输出：6 //解释 [2],[4],[1,2,3],[3,4,5],[1,2,3,4],[2,3,4,5]
思路：前缀和 + 哈希 + 同余定理
如果两个数的差能被K整除，就说明这两个数 mod K得到的结果相同，只要找有多少对 mod k 相同的数就可以组合一下得到结果。
同余定理：如果整数a和整数b满足$a-b$能够被m整除，即$(a-b)/m$是一个整数$(a-b)\%m==0$，则a对m取余与b对m取余相等，即$a\%m==b\%m$。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m;
int va[N];
int main() {
while (cin >> n >> m) {
for (int i = 0; i < n; i++) {
cin >> va[i];
}
unordered_map<int, int> hash;
hash[0] = 1; // 考虑单个元素就可以整除m的情况
for (int i = 0; i < n; i++) {
// 前缀和对m取余
va[i] = ((i == 0 ? 0 : va[i - 1]) + va[i]) % m;
hash[va[i]]++;
}
int res = 0;
for (auto item : hash) {
// 对m取余相同的情况进行组合
res += (item.second * (item.second - 1)) / 2;
}
cout << res << endl;
}
return 0;
}
3. 找靓号 (4.10)
给定字符串长度为N，字符串只会包括’0’-‘9’，要求修改字符串使得至少有一个字符出现K次，修改每个字符的代价为对应数字的变化大小，求最小代价，并输出最小代价下的最小字符串。例如：对于字符串 ‘787855’, K = 5， 则最小代价应该为4， 并且输出最小字符串’777757’（不能是’777775’， 因为不满足最小字符串）牛客原题
输入：第一行包含2个整数 N、K，分别表示手机号码数字个数以及靓号至少有 K 个数字相同。第二行包含 N 个字符，每个字符都是一个数字(‘0’-‘9’)，数字之间没有任何其他空白符。表示小多的手机号码。数据范围：$2 \le K \le N \le 10,000$.
输出：第一行包含一个整数，表示修改成一个靓号，最少需要的金额。第二行包含 N 个数字字符，表示最少花费修改的新手机号。若有多个靓号花费都最少，则输出字典序最小的靓号。
样例：
输入：
6 5
787585
输出：
4
777577 // 说明：花费为4的方案有两种：777577与777775，前者字典序更小。
思路：是一道贪心求解的题。由于一共就10个数字，求每一位数字作为靓号的花费。例如对于787585这个号，n=6，k=5。首先判断设置5个9的情况，再针对设置每个数字到9的花费进行排序。这里利用了一个结构体，包含了当前数的在号码的位置，其初始值，其目标值，以及从初始值转换到目标值所需要的花费。将花费从小到大进行排序，对于花费一致的数，这里需要输出字典序最小的结果，因此当当前数比目标数小，优先处理后面的数。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
// 定义每个数字的结点
struct Node {
int cost; //记录保存当前值转换为目标值的花费
int idx; // 记录当前数字在字符串中的位置
int target; // 记录要转换的目标值
int ori; // 记录原始的数字
};
int nums[N]; // 保存将字符串转为数组
Node nds[N]; // 记录每个数字的信息
int res[N]; // 记录答案
int n, k;
// 先按照花费大小进行排序，如果花费一样，如果当前数比目标数小的，则优先处理后面的数
bool cmp(Node nd1, Node nd2) {
if (nd1.cost != nd2.cost) return nd1.cost < nd2.cost;
if (nd1.idx < nd2.idx) return nd1.target < nd1.ori;
return nd2.target > nd2.ori;
}
int main() {
while (cin >> n >> k) {
string s;
cin >> s;
// 转换成数字
for (int i = 0; i < s.size(); i++) {
nums[i] = s[i] - '0';
}
int cnt = INT_MAX, tmp; // cnt 记录最小花费
// 暴力尝试每一个数字0-9作为相同的数字
for (int i = 0; i <= 9; i++) {
// 遍历所有数字，计算花费
for (int j = 0; j < n; j++) {
nds[j].cost = abs(nums[j] - i);
nds[j].idx = j;
nds[j].target = i;
nds[j].ori = nums[j];
}
// 按照排序规则排序
sort(nds, nds + n, cmp);
tmp = 0;
// 计算当使i作为相同数字时的花费
for (int j = 0; j < k; j++) tmp += nds[j].cost;
// 如果比之前的花费小，则更新花费和答案数组
if (tmp < cnt) {
cnt = tmp;
// 先将原来的数字拷贝一份
for (int j = 0; j < n; j++) res[j] = nums[j];
// 再将需要修改的地方进行修改
for (int j = 0; j < k; j++) res[nds[j].idx] = i;
}
}
for (int i = 0; i < n; i++) {
cout << res[i];
}
cout << endl;
}
return 0;
}
4. 我忘了。。。 (4.10)
题目忘了。。。
输入：
输出：
样例：
思路：
参考代码
1
待填。。。
5. 不同球数的盒子 (5.6)
N个盒子（1~N），盒子$i$中有$A_i$个球，现需使每个盒中球的个数各不相同，盒子里面只能放入不可取出，问题：最少放入多少球，使每个盒子球数各不相同。LeeCode945
输入：第一行盒子个数n,第二行，n个盒子中球的个数
输出：最少放入多少个球。
样例：
输入：
5
2 1 1 2 4
输出：
5
思路：先排序，然后暴力增加。如果当前的数<=前一个数，那么就变成前一个数+1
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N];
int n;
int main() {
while (cin >> n) {
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n); // 排序
LL res = 0;
// 遍历数组，暴力增加
for (int i = 1; i < n; i++) {
// 如果当数小于等于前一个数，则当前数变为前一个数+1,并计算需要添加多少个球
if (a[i] <= a[i - 1]) {
res += 1LL * (a[i - 1] - a[i] + 1);
a[i] = a[i - 1] + 1;
}
}
cout << res << endl;
}
return 0;
}
6. 拼正方形 (5.6)
N个木棍（1~N），第i个木棍长$L_i$，用完所有木棍，拼出正方形，一共T组，有些无解，判断T组是否有解，有YES，无NO。$1\le N\le 20$,$1\le L_i \le 10000$。 LeeCode473
输入：第一行T，表示有T组测试数据，第二行，第一个是n，表示有n个木根，接下来n个数表示木棍的长度。
输出：有解输出YES，否则输出NO
样例：
输入：
2
5 1 1 2 2 2
5 3 3 3 3 4
输出：
YES
NO
思路：深度优先搜索 + 剪枝，时间复杂度有点高($O(4^N)$), 可以使用状态压缩dp。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int nums[N];
bool vis[N];
int n;
// 剪枝更彻底
bool dfs2(int idx, int sum) {
if (sum == 0) return true;
if (idx == n) return false;
for (int i = idx; i < n; i++) {
if (vis[i] || nums[i] > sum) continue;
vis[i] = true;
if (dfs2(i + 1, sum - nums[i])) return true;
vis[i] = false;
}
return false;
}
bool dfs(int idx, int a, int b, int c, int d, int sum) {
if (idx == n) {
if (a == sum && b == sum && c == sum && d == sum)
return true;
else
return false;
}
// 排序就是为了这儿的剪枝
if (a > sum || b > sum || c > sum || d > sum) return false;
return dfs(idx + 1, a + nums[idx], b, c, d, sum) ||
dfs(idx + 1, a, b + nums[idx], c, d, sum) ||
dfs(idx + 1, a, b, c + nums[idx], d, sum) ||
dfs(idx + 1, a, b, c, d + nums[idx], sum);
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 0; i < n; i++) cin >> nums[i];
// 排序是为了更快的剪枝
sort(nums, nums + n), reverse(nums, nums + n);
int sum = 0;
for (int i = 0; i < n; i++) sum += nums[i];
if (sum % 4) return false;
// if (dfs(0, 0, 0, 0, 0, sum / 4))
// cout << "YES" << endl;
// else
// cout << "NO" << endl;
bool can = true;
for (int i = 0; i < 4; i++) {
if (!dfs2(0, sum / 4)) can = false;
}
if (can)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
