牛客练习赛61【非官方题解】
A、打怪
解题思路
1、先特判输出-1的情况，即一回合秒杀怪物，永远是我先手，所以杀无数只怪物。
2、计算我杀怪物需要多久记作a回合，可以考虑用向上取整ceil函数。同理计算怪物杀我所要回合数，记作b回合。
3、%d输出(b-1) / (a-1)。因为我是先手所以我需要花费的回合 -1，又因为我的血量需要大于等于0，所以怪物杀我回合数也需要 -1。
时间复杂度 O (N) 。
代码
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int main() {
int T = read();
while (T--) {
int n = read(), m = read(), a = read(), b = read();
if (m >= a) {
puts("-1");
continue;
}
int ans = ceil(1.0 * a / m);//杀一只怪
int tmp = ceil(1.0 * n / b);//怪杀了我
printf("%d\n", (tmp - 1) / (ans - 1));
}
return 0;
}B、吃水果
解题思路
因为数据规模小，直接模拟，开一个时间计数器初始化为0。先保证 ，每次做决策，如果
我们这次选择 n*2，否则选择 --n,--m。每次决策时间计数器加一。
时间复杂度 O（N*log(N)）。
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
int main() {
int T = read();
while (T--) {
int n = read(), m = read();
int ans = 0;
if (n > m) swap(n, m);
else if (n == m) {
printf("%d\n", n);
continue;
}
while (n) {
if ((n << 1) <= m) n <<= 1;
else --n, --m;
++ans;
}
printf("%d\n", ans);
}
return 0;
}C、四个选项
解题思路
并查集 + dfs暴搜；先通过并查集处理区域块，绑定的绑定，后面从1，开始向下 dfs ，选A，选B，选C，选D。并且记录选项编号，当达到递归出口，n==13的时候，先判断是否符合题目给的ABCD数量，在判断并查集在一起的方案是否相同。如果都相同，++ans。
时间复杂度 O（
）应该还会更小，题目ABCD有数量限制。
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
#define N 15
ll ans;
int pa[N]; //记录填涂方案
int father[N];
int Find(int root) {
if (father[root] == root) return root;
return father[root] = Find(father[root]);
}
void Merge(int a, int b) { //路径压缩
int fa = Find(a);
int fb = Find(b);
if (fa > fb) swap(fa, fb);
if (fa != fb) {
father[fa] = fb;
}
}
void dfs(int n, int a, int b, int c, int d) {
if (a < 0 || b < 0 || c < 0 || d < 0) return; //可行性剪枝
if (n == 13) {
if (a || b || c || d) return;
for (int i = 1; i <= 12; ++i)
if (pa[i] != pa[father[i]]) return;
++ans;
return;
}
pa[n] = 1, dfs(n + 1, a - 1, b, c, d);
pa[n] = 2, dfs(n + 1, a, b - 1, c, d);
pa[n] = 3, dfs(n + 1, a, b, c - 1, d);
pa[n] = 4, dfs(n + 1, a, b, c, d - 1);
}
int main() {
for (int i = 0; i < N; ++i) father[i] = i;
int a = read(), b = read(), c = read(), d = read(), m = read();
for (int i = 1; i <= m; ++i) {
int x = read(), y = read();
if (x > y) swap(x, y);
Merge(x, y);
}
dfs(1, a, b, c, d);
printf("%lld\n", ans);
return 0;
}D、最短路变短了
解题方法
通过一次dji可以算出 1-n 的最短路，那么如果路径进行翻转呢？我们如果重新去dji一遍重复q次，肯定TLE，而且边权信息不好删除，不好操作所以这种方法Pass。这时候我们画个图，如下：
我们可以发现，如果我们吧2->5这条路径翻转，变成5->2，这时新的最短路径为 1->5 + 5->2 + 2->5；如果写的通常一点就是：i->j翻转；带来的影响之后的最短路径就是：len(1->j) + len(j->i) + len(i->5) 如果这个花费小于原来1->n的最小花费，那么puts("YES")， else puts("NO")。
时间复杂度 O(N + Q)
Code
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 1e5 + 7;
int u[N << 1], v[N << 1], w[N << 1];// 记录边权信息
int n, m;
struct Node {
int v;
ll cost;
friend bool operator<(Node a, Node b) { //自定义priority_queue的less规定，注意false排在前面，给坑了一发。。
return a.cost > b.cost;
}
};
ll d[N], f[N]; //d正向图，f反向图
vector<Node> D[N]; // pair<终点，花费>
vector<Node> F[N];
void dji1(int x) {
priority_queue<Node> pq;
while (pq.size()) pq.pop();
memset(d, 0x3f, sizeof(d));
d[x] = 0;
pq.push({ x,0 });
while (pq.size()) {
Node tmp = pq.top();
pq.pop();
ll v = tmp.v;
if (d[v] < tmp.cost) continue; //原先这个节点花费更少 跳过
for (int i = 0; i < D[v].size(); ++i) {
Node s = D[v][i];
if (d[s.v] > d[v] + s.cost) {
d[s.v] = d[v] + s.cost;
pq.push({ s.v,d[s.v] });
}
}
}
}
void dji2(int x) {
priority_queue<Node> pq;
while (pq.size()) pq.pop();
memset(f, 0x3f, sizeof(f));
f[x] = 0;
pq.push({ x,0 });
while (pq.size()) {
Node tmp = pq.top();
pq.pop();
ll v = tmp.v;
if (f[v] < tmp.cost) continue; //原先这个节点花费更少 跳过
for (int i = 0; i < F[v].size(); ++i) {
Node s = F[v][i];
if (f[s.v] > f[v] + s.cost) {
f[s.v] = f[v] + s.cost;
pq.push({ s.v,f[s.v] });
}
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= m; ++i) {
u[i] = read(), v[i] = read(), w[i] = read();
D[u[i]].push_back({ v[i], w[i] });
F[v[i]].push_back({ u[i], w[i] });
}
dji1(1);
dji2(n);
int T = read();
while (T--) {
int x = read();
ll a = u[x], b = v[x], c = w[x];
ll ans = d[b] + c + f[a];
if (ans < d[n]) puts("YES");
else puts("NO");
}
return 0;
}E、相似的子串
知识点：字符串hash+二分
解题思路
题目要我们找k个位置，最长公共前缀是x，并且x需要最大，那我们就只考虑子串内容为前缀相同部分，保证最大。
通过O(N)的hash预处理字符串，就可以通过O(1)查找到该字符串，散列表的话可以通过STL的unordered_map<>实现，我这里遇到了点小插曲，是因为我使用的编译器是VS2019，因为微软自己的宏__cplusplus一直都没有修改是C++99的版本，就算你改了编译器版本这个宏还是不变，以至于不能再万能头文里面直接用。如果需要修改的小伙伴可以通过VS的项目属性，找到C/C++，在命令行加上 /Zc : __cplusplus这样就可以使用了，回归正题，在这个map里面，键对应的值的内容我们需要使用一个pair去定义，first为子串最后出现的位置，second为子串个数，这样我们通过二分查找去寻找ans，如果当前mid不符合，那么左区间查找，如果mid符合，右区间查找。至于check(mid)函数，从x开始求对应hash表中长度为x的前缀和，如果这个字符串在表中位置减去上次在表中位置大于等于mid，说明子串没有重叠部分，把字符串的最后位置赋值为i，子串个数加1，如果长度为mid的子串存在k个及以上就return true。
时间复杂度 O(N * log(N))
Code
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull; //物理取模
struct Node {
int pos, cnt; //最后一次出现位置，子串中元素个数
};
const int N = 2e5 + 7;
unordered_map<ull, pair<int, int> > mp; // 使用umap建立hash表
int base = 131; // 字符串hash值 一般取131 or 13331
ull po[N], has[N];
int n, k;
char s[N];
bool check(int x) {
mp.clear();
for (int i = x; i <= n; ++i) {
ull tmp = has[i] - has[i - x] * po[x];
if (i - mp[tmp].first >= x) {
mp[tmp].first = i; //最后一次出现位置为结尾位置
++mp[tmp].second; //子串数量+1
}
if (mp[tmp].second >= k) return true;
}
return false;
}
int main() {
scanf("%d %d %s", &n, &k, s + 1);
po[0] = 1;
for (int i = 1; i <= n; ++i) {
has[i] = has[i - 1] * base + s[i] - 'a';
po[i] = po[i - 1] * base;
}
int l = 0, r = n + 1, ans = 0;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid;
}
printf("%d\n", ans);
}F、苹果树
待补
投递小米集团等公司10个岗位 >