100， 100， 20， 86 后两题有大佬有思路吗
1、族谱
某家族子孙众多，每个人只保留了部分的家族族谱，现在想知道该家族的第一代人是谁和第N代人的数量
现在给出N组数据，每组数据分别代表某一个人保留的部分族谱信息，如：[A B C]，表示当前C的父亲是B，B的父亲是A。
输入描述：
第1行输入为数值，代表有多少子族谱，数值范围在1-100
第2-n行输入为N组字符串数组，每组数组相当于一个家族关系的子链表，N<100
第n+1行输入表示要计算第n代人的数量，数值范围在1-100
输出描述：
第一行为字符串，家族第一代人的名称字符串
第二行为数值，第n代人的数量
input:
2
A B C
B C D
4
output:
A
1
2、数列
双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。
给定一个长度为n的数列a0,a1,a2,a3,.…an-1,以及一个数k
求a数列有多少个满足以下条件的长度为k+1的子串
(2^0)*a_{i} < (2^1)*a_{i+1} < (2^2)*a_{i+2} < ... < (2^k)*a_{i+k}
这下喵喵不会做了，你可以帮帮它么？
输入描述：
会有多组询问
首先输入一个数字t(1<=t<=5)
接下来首先有两个数n，k，具体含义如题意所示。（3<=n<=1e5，0<k<n）
接下来有n个数表示数列a的n个数（0<ai<=1e8）
输出描述：
对于每个询问，输出a数列满足条件的长度为k+1的子串的个数
input:
6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12
output:
2
3
2
3
1
0
3、AB实验
AB实验同学每天都很苦恼如何可以更好的进行AB实验，每一步的流程很重要，我们目标为了缩
短所需的步数。
我们假设每一步对应到每一个位置。从一个整数位置x走到另外一个整数位置y，每一步的长度是正整数，每步的值等于上一步的值-1，+0，+1。
求x到y最少走几步。并且第一步必须是1，最后一步必须是1，从×到y最少需要多少步。
样例说明：
整数位置×为12，另外一个整数位置y为6，我们需要从×走到y，最小的步数为：1，2，2，1，所以我们需要走4步。
整数位置x为34，另外一个整数位置y为45，我们需要从x走到y，最小的步数为：1，2，3，2，2,1，所以我们需要走6步。
整数位置x为50，另外一个整数位置y为30，我们需要从x走到y，最小的步数为：1，2，3，，4,3，2，1,所以我们需要走6步。
输入描述：
输入第一行包含一个整数n（1<=n<=1000），表示测试数组的组数，
以下每一行为一组数据。包含2个整数×，y。（0<=×<=y<2^31）
输出描述：
对于每一组数据，输出一行，仅包含一个整数，从x到y所需最小步数。
input：
3
12 6
34 45
50 30
output:
4
6
8
4、吃狗粮
题目描述
小明最近养了一只小狗，并且买了一袋狗粮，一共有M克。小狗每天可能会吃a_1,a_2,…,a_n 克，当剩余狗粮不足a_1,a_2,….,a_n中的最小值时,也算做一天。
小狗后一天吃的不会比前一天多，小明想知道这袋狗粮小狗吃完的情况有多少种
输入描述：
第一行：空格分割的小狗每天的食量，所有值都为正数并且不重复，最多10个
第二行：狗粮一共有多少克
输出描述：
一个数字，表示这袋狗粮小狗吃完的情况有多少种
input:
1 2 5
5
output:
4
第一题ac代码, 先把节点关系理清楚，然后遍历一遍，看看谁没有父亲节点，这个就是祖宗，然后（多叉树）层序遍历计算第k层的节点数量
第一题AC代码
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node *parent;
unordered_set<Node *> child;
string val;
Node(string v) : parent(nullptr), val(v) {}
};
Node *dummyNode = new Node("0");
void slove(vector<vector<string>> &v, int n, int k) {
unordered_map<string, Node *> mp;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < v[i].size(); ++j) {
if (mp.find(v[i][j]) != mp.end()) {
// 找到了
if (j != 0) {
mp[v[i][j - 1]]->child.insert(mp[v[i][j]]);
mp[v[i][j]]->parent = mp[v[i][j - 1]];
}
} else {
// 没找到
Node *node = new Node(v[i][j]);
if (j != 0) {
mp[v[i][j - 1]]->child.insert(node);
node->parent = mp[v[i][j - 1]];
}
mp[v[i][j]] = node;
}
}
}
Node *root = nullptr;
for (auto &m: mp) {
if (m.second->parent == nullptr) {
cout << m.first << endl;
root = m.second;
break;
}
}
// 求第n层的数量
queue<Node *> que;
que.push(root);
int count = 1, res = 0;
while (!que.empty()) {
int size = que.size();
if (count == k) {
res = size;
break;
}
for (int i = 0; i < size; ++i) {
Node *node = que.front();
que.pop();
for (auto &s: node->child) {
que.push(s);
}
}
++count;
}
cout << res << endl;
return;
}
int main() {
int n;
cin >> n;
vector<vector<string>> v(n);
for (int i = 0; i < n; ++i) {
string ch;
while (cin >> ch) {
v[i].push_back(ch);
if (cin.get() == '\n') {
break;
}
}
}
int k;
cin >> k;
slove(v, n, k);
return 0;
}
第二题AC代码,最开始用的动归思想预处理，发现有点问题，直接暴力，结果a了
#include <bits/stdc++.h>
using namespace std;
long long slove(vector<long long> &a, long long n, long long k) {
if (a.empty()) {
return 0;
}
long long res = 0;
for (long long i = 0; i < n - k + 1; ++i) {
for (long long j = 1; j < k; ++j) {
if (!(a[i + j] * pow(2, j) > a[i + j - 1] * pow(2, j - 1))) {
break;
}
if (j == k - 1 && a[i + j] * pow(2, j) > a[i + j - 1] * pow(2, j - 1)) {
++res;
}
}
}
return res;
}
int main() {
long long t;
cin >> t;
vector<long long> res;
for (long long i = 0; i < t; ++i) {
long long n, k;
cin >> n >> k;
vector<long long> a(n, 0);
for (long long j = 0; j < n; ++j) {
cin >> a[j];
}
res.push_back(slove(a, n, k + 1));
}
for (auto &r: res) {
cout << r << endl;
}
return 0;
} 第三题只有20%
#include <bits/stdc++.h>
using namespace std;
long long slove(long long x, long long y) {
if (x > y) {
swap(x, y);
}
// x 是较小的
int dis = y - x;
if (dis <= 2) {
return dis;
}
bool flag = true; // true 代表xy之间距离是偶数
if (dis % 2 == 1) {
flag = false;
}
if (flag) {
int count = 1;
while (dis > 0) {
dis -= 2 * count;
++count;
}
return count * 2 - 2;
} else {
// 距离为奇数
int count = 1;
while (count * 2 <= dis) {
dis -= 2 * count;
++count;
}
return count * 2;
}
}
int main() {
long long n;
cin >> n;
vector<long long> res;
for (long long i = 0; i < n; ++i) {
long long x, y;
cin >> x >> y;
res.push_back(slove(x, y));
}
for (auto &r: res) {
cout << r << endl;
}
return 0;
} 第四题只有80%多，使用回溯的思想，其中index后来没用到，忽略就行，
#include <bits/stdc++.h>
using namespace std;
long long res = 0;
void __slove(vector<long long> &v, long long sum, long long index, long long min_num, long long last_num) {
if (sum < 0) {
return;
}
if (sum < min_num || sum == 0) {
++res;
return;
}
for (long long i = 0; i < v.size(); ++i) {
if (last_num == -1 || last_num >= v[i])
__slove(v, sum - v[i], i, min_num, v[i]);
}
}
long long slove(vector<long long> &v, long long sum, long long min_num) {
__slove(v, sum, 0, min_num, -1);
return res;
}
int main() {
vector<long long> v;
long long num, min_num = LONG_LONG_MAX;
while (cin >> num) {
min_num = min(num, min_num);
v.push_back(num);
}
long long sum = v.back();
v.pop_back();
cout << slove(v, sum, min_num) << endl;
return 0;
} #字节笔试#
海康威视公司福利 1144人发布
