目录
玉米大炮
思路：
代码：
逆序对计数
思路：
代码：
旅行
思路：
代码：
神奇数字
编辑
思路：
代码：
玉米大炮
A-玉米大炮_2022河南萌新联赛第（三）场：河南大学 (nowcoder.com)
思路：
我们发现如果花x的时间可以打败僵尸博士，那么花比x更多的时间肯定也可以打败僵尸博士，所以答案具有单调性，可以用二分求解。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int n, m;
int a[N], b[N];bool check(int x) {int res = 0;for (int i = 1; i <= n; i++) {int cnt = x / b[i] + 1;res += cnt * a[i];if (res >= m) return true;}return res >= m;
}
void solve()
{cin >> n >> m;int s = 0;for (int i = 1; i <= n; i++) cin >> a[i] >> b[i], s += a[i];if (s >= m) {cout << 0 << '\n';return;}int l = 0, r = 1e18, ans;while (l <= r) {int mid = l + r >> 1;if (check(mid)) ans = mid, r = mid - 1;else l = mid + 1;}cout << ans << '\n';
}
signed main() {ios;solve();return 0;
}
逆序对计数
B-逆序对计数_2022河南萌新联赛第（三）场：河南大学 (nowcoder.com)
思路：
因为n最大为6000，所以可以用n^2的时间复杂度求解，我们可以定义一个二维数组a[i][j]，代表在i到j的区间内有多少对逆序对，因为每次询问互不影响，所以每次询问可以O（1）求解，区间数组可以动态规划求解。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;int lr[6001][6001];
int n, a[N];
void solve()
{cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];int res = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j < i; j++) lr[j][i] = lr[j][i - 1];int k = 0;for (int j = i-1;j >=1; j--) {if (a[j] > a[i]) k++,res++;lr[j][i] += k;}}int q;cin >> q;while (q--) {int l, r;cin >> l >> r;int cnt = lr[l][r];//这个区间的逆序对int tot = ( (r - l + 1) * (r - l) )/ 2;cout << res + ((tot - cnt)-cnt) << '\n';}}
signed main() {ios; solve();return 0;
}
旅行
I-旅行_2022河南萌新联赛第（三）场：河南大学 (nowcoder.com)
思路：
题目在普通最短路的基础上加上了附加条件，导致经过的城市越多会导致检测的次数变多，所以我们可以发现一下规律，发现我们最优求解必定是检测后，经过一次不检测再检测，所以我们在建边时只需要将检测过的城市与未检测的城市相连即可，我们需要扩充dis数组为n的两倍，最后走一遍迪杰斯特拉。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;int n, m, x, head[N], cnt;
struct node
{int u, v, w;
}e[N];
void add(int u, int v, int w) {e[++cnt] = { v,head[u],w };head[u] = cnt;
}void solve()
{cin >> n >> m >> x;for (int i = 1; i <= m; i++) {int u, v, w; cin >> u >> v >> w;//将缴费和未缴费的建边,未缴费的边为u,缴费的边为u+nadd(u, v + n, w + x);add(u + n, v, w);add(v, u + n, w + x);add(v + n, u, w);}vector<int>dis(2 * n + 1, inf);dis[1] = 0;priority_queue<pll>q;q.emplace(0, 1);while (q.size()) {auto it = q.top(); q.pop();int x = it.second;for (int i = head[x]; i; i = e[i].v) {int now = e[i].u;if (dis[now] > dis[x] + e[i].w) {dis[now] = dis[x] + e[i].w;q.emplace(-dis[now], now);}}}cout << min(dis[n], dis[2 * n]) << '\n';}
signed main() {ios; solve();return 0;
}
神奇数字
J-神奇数字_2022河南萌新联赛第（三）场：河南大学 (nowcoder.com)
思路：
有且仅当三个数相同时才有无穷的答案，否则答案只存在1到三个数中的最大值之间，但是一个循环会超时，看了题解发现这个是个数学问题，答案就是三个数任意两数之间的差值的最大公约数的所有因子。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<algorithm>
#define int long long
#define pb push_back
#define TEST int T; cin >> T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x&(-x)
#define pll pair<int,int>
const int N = 1e6 + 30;
const int M = 1e3 + 10;
const int inf = 512785182741247112;
const int mod = 1e9 + 7;
using namespace std;
int qgcd(int a, int b) {int res;while (b > 0) {res = a % b;a = b;b = res;}return a;
}
void solve()
{int a, b, c;cin >> a >> b >> c;int mx = max({ a,b,c });if (a == b && b == c) {cout << "-1\n";return;}int A = abs(a - b), B = abs(b - c), C = abs(a - c);int ans = qgcd(A, B);ans = qgcd(ans, C);vector<int>res;for (int i = 1; i * i <= ans; i++) {if (ans % i == 0) {res.push_back(i);if (ans / i != i) {res.push_back(ans / i);}}}sort(res.begin(), res.end());for (auto x : res) cout << x << ' ';cout << '\n';}
signed main() {ios; TESTsolve();return 0;
}
