牛客练习赛61
比赛地址:
前言：这场比赛感觉自己脑袋不太清醒,导致了罚时爆表A题把continue写成了retrurn居然一直都没发现,C也不明原因WA了好多次,好在最后一下连过三题苟了个四题尾总算没有掉分。(我真是个憨憨)
A. 打怪
基本思路：
- 由于勇士是先手,所以勇士的攻击如果大于怪物的血量,一定能无限秒杀怪物输出-1;
- 否则我们看下在打一只怪的时候勇士会被攻击到几次,就能算出打一只怪勇士血量的损失(注意先后手);
- 然后用勇士的血量去除打一只怪的血量损失理论上就是答案了,但是注意如果刚好整除的话,由于勇士每次是给与怪物最后一击的,所以如果整除说明最后一次怪物先把勇士打死了,所以这个时候减个一;
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
int a,b,c,d;
signed main() {
IO;
int t;
cin >> t;
while (t-- > 0) {
cin >> a >> b >> c >> d;
if (b >= c) { // 能秒杀怪,无损失;
cout << -1 << '\n';
continue;
}
int k1 = c % b == 0 ? c / b - 1 : c / b;//整除的话,由于先手要减一;
int z = d * k1;//杀一只怪勇士血量的损失;
if (a % z == 0) cout << a / z - 1;//整除要减一;
else cout << a / z;
cout << '\n';
}
return 0;
}B. 吃水果
基本思路：
这题应该很简单贪心的策略,我们要想办法将苹果和香蕉的数量凑到相同再一起吃完，所以我们将苹果和香蕉里较小的那个先最快的加到一样多,然后再一天天吃就是了。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
int n,m;
signed main() {
IO;
int t;
cin >> t;
while (t-- > 0) {
cin >> n >> m;
int cnt = 0;
if(n > m) swap(n,m); // 令n是小的那个;
int ans = m;
while (n < m) { //加到两者数目一样多;
n += n;
cnt++;
}
ans += cnt;
cout << ans << endl;
}
return 0;
}C. 四个选项
基本思路：
因为只有12道题,而且限制条件很多,明显的dfs+剪枝就能过,基本上就是一个裸的dfs再根据每种选项的数量和那m个额外条件剪枝就是了,就是出了一个莫名其妙的问题让我WA了好久,具体实现可以参考代码。
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
int na,nb,nc,nd,m;
int ans = 0;
map<int,vector<int>> memo;
void dfs(int s,string str,int a,int b,int c,int d) {
if (a > na || b > nb || c > nc || d > nd) return; // 数量超过了就return;
if (s == 12) {
if (a == na && b == nb && c == nc && d == nd) ans++;
return;
}
for (int i = 0; i < 4; i++) {
char ct = (char) ('A' + i);
bool v = true;
if (memo.count(s)) { // 要满足和这些都相同;
for (auto it : memo[s]) {
if (it < s && ct != str[it]) {
v = false;
break;
}
}
}
if (!v) continue;
dfs(s + 1, str + ct, i == 0 ? a + 1 : a, i == 1 ? b + 1 : b, i == 2 ? c + 1 : c, i == 3 ? d + 1 : d);
}
}
signed main() {
IO;
cin >> na >> nb >> nc >> nd >> m;
memo.clear();
ans = 0;
rep(i, 1, m) {
int x, y;
cin >> x >> y;
x--, y--;
if (y > x) swap(x, y);
memo[x].push_back(y);
memo[y].push_back(x);//不加这个就WA了,虽然我感觉只往前找没问题...;
}
dfs(0, "", 0, 0, 0, 0);
cout << ans << '\n';
return 0;
}D. 最短路变短了
基本思路：
- 这题其实比较套路这种将边反向啊,或者两个点再多连一条边和原先最短路比的,都差不多是这么做;
- 我们先跑一遍dijkstra算出起点到所有节点的最短路,记录在数组dis1中,然后再反向建边算出终点到所有节点的最短路记录在数组dis2中;
- 我们将边反向后经过这条反向边(原)(u,v)的最短路就应该为 = dis1[v] + dis2[u] + w,将这条经过反向边的最短路和原先的最短路比,就能知道新最短路是否变短了;
参考代码：
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define mp(a, b) make_pair(a, b)
#define INF 1e18
inline int read() {
int x = 0, neg = 1; char op = getchar();
while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
return neg * x;
}
inline void print(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e5 + 10;
const int maxm = 2e5 + 10;
struct Edge{
int to,next,val;
}edge1[maxm],edge2[maxm];
int n,m;
int head1[maxn],head2[maxn];
int cnt1 = 0, cnt2 = 0;
void add_edge1(int u,int v,int w) {
edge1[++cnt1] = {v, head1[u], w};
head1[u] = cnt1;
}
void add_edge2(int u,int v,int w) {
edge2[++cnt2] = {u, head2[v], w};//反向加的边;
head2[v] = cnt2;
}
int dis1[maxn],dis2[maxn];
bool vis[maxn];
void dijkstra1(int k) {//正向dijkstra;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
while (!q.empty()) q.pop();
for (int i = 1; i <= n; i++) dis1[i] = INF;
mset(vis,false);
dis1[k] = 0;
q.push(make_pair(0, k));
while (!q.empty()) {
int s = q.top().second;
q.pop();
if (vis[s]) continue;
vis[s] = true;
for (int i = head1[s]; i != -1; i = edge1[i].next) {
if (dis1[edge1[i].to] > dis1[s] + edge1[i].val) {
dis1[edge1[i].to] = dis1[s] + edge1[i].val;
q.push(make_pair(dis1[edge1[i].to], edge1[i].to));
}
}
}
}
void dijkstra2(int k) {//反向dijkstra;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
while (!q.empty()) q.pop();
for (int i = 1; i <= n; i++) dis2[i] = INF;
mset(vis, false);
dis2[k] = 0;
q.push(make_pair(0, k));
while (!q.empty()) {
int s = q.top().second;
q.pop();
if (vis[s]) continue;
vis[s] = true;
for (int i = head2[s]; i != -1; i = edge2[i].next) {
if (dis2[edge2[i].to] > dis2[s] + edge2[i].val) {
dis2[edge2[i].to] = dis2[s] + edge2[i].val;
q.push(make_pair(dis2[edge2[i].to], edge2[i].to));
}
}
}
}
vector<int> memo[maxm];//记录一下边;
signed main() {
IO;
n = read(),m = read();
cnt1 = 0, cnt2 = 0;
mset(head1, -1);
mset(head2, -1);
rep(i, 1, m) {
int u, v, w;
u = read(),v = read(),w = read();
memo[i] = {u, v, w};
add_edge1(u, v, w);
add_edge2(u, v, w);
}
dijkstra1(1);
dijkstra2(n);
int temp = dis1[n];
int q;
q = read();
while (q-- > 0) {
int x;
x = read();
int u = memo[x][0], v = memo[x][1], w = memo[x][2];
if (dis1[v] + dis2[u] + w < temp) { // 记得v,和u要相反;
cout << "YES" << '\n';
} else cout << "NO" << '\n';
}
return 0;
}
京公网安备 11010502036488号