A 吝啬的拒绝
p个顶点，m条边的无向带权图，给出n个点（可重复）， 求这n个点到图中某个顶点的距离和的最小值。
由于 ，我们可以使用
求任意点之间的最短距离，时间复杂度
。
然后我们枚举每个顶点，计算距离和求 即可。总时间复杂度
。
更新： 理论上复杂度是不够的，所以改用
来求任意点之间的最短距离。总时间复杂度
。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int dist[805];
bool vis[805];
int f[805][805];
vector<pair<int, int>> adj[805];
int p;
void dilkstra(int s) {
fill(dist, dist + p + 1, 0x7fffffff);
fill(vis, vis + p + 1, false);
dist[s] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
que.emplace(0, s);
while (!que.empty()) {
int u = que.top().second;
que.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &[to, w] : adj[u]) {
if (dist[to] > dist[u] + w) {
dist[to] = dist[u] + w;
que.emplace(dist[to], to);
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, c;
cin >> n >> p >> c;
vector<int> a(n);
for (int i = 0 ; i < n ; i++) {
cin >> a[i];
}
for (int i = 1 ; i <= p ; i++) {
for (int j = 1 ; j <= p ; j++) {
f[i][j] = 1000000;
}
}
for (int i = 0 ; i < c ; i++) {
int u, v, w;
cin >> u >> v >> w;
f[u][v] = min(f[u][v], w);
f[v][u] = min(f[v][u], w);
}
for (int i = 1 ; i <= p ; i++) {
for (int j = 1 ; j < i ; j++) {
int k = f[i][j];
if (k != 1000000) {
adj[i].emplace_back(j, k);
adj[j].emplace_back(i, k);
}
}
}
int ans = 0x7fffffff;
for (int i = 1 ; i <= p ; i++) {
dilkstra(i);
int res = 0;
for (int j = 0 ; j < n ; j++) {
res += dist[a[j]];
}
ans = min(ans, res);
}
cout << ans;
return 0;
}
C 数列排序
因为题目中数列是不重复的，所以只需要将数列排序，并重新赋值，这样只需要 即可，重新赋值后，形成了若干个环，那么只需要一直
即可求出操作次数。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n), idx;
for (int i = 0 ; i < n ; i++) {
cin >> a[i];
idx.push_back(a[i]);
}
sort(begin(idx), end(idx));
for (int i = 0 ; i < n ; i++) {
a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
}
int ans = 0;
for (int i = 0 ; i < n ; i++) {
while (a[i] != i) {
int k = a[i];
swap(a[i], a[a[i]]);
ans++;
}
}
cout << ans << "\n";
return 0;
}
D 一种很新的阶乘
，由此可知时间复杂度大概在
以内。
普通的质因数分解不符合要求。
我们通过题目中给的定义可以 求出
中
的指数。
因为质因数分解一定会使被分解数变小，令 代表
中
的指数。
假设 ，那么可以得到转移方程
所以我们从 到
，依次分解即可。
那么问题来了，怎么得到一个质因数，这里可以使用欧拉筛预处理。
总时间复杂度为
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
long long cnt[10000001];
void print(int a, long long b) {
cout << a;
if (b > 1) {
cout << "^" << b;
}
}
vector<int> prime;
int vis[10000001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x;
cin >> x;
for (int i = 2 ; i <= x ; i++) {
if (vis[i] == 0) {
vis[i] = i;
prime.emplace_back(i);
}
for (int j = 0 ; j < int(prime.size()) && 1LL * i * prime[j] <= x ; j++) {
vis[i * prime[j]] = prime[j];
if (i % prime[j] == 0) {
break;
}
}
}
for (int i = 1 ; i < x ; i++) {
int k = x - i + 1;
cnt[k] += i;
if (vis[k] == k) continue;
int z1 = vis[k], z2 = k / vis[k];
cnt[z1] += cnt[k];
cnt[z2] += cnt[k];
cnt[k] = 0;
}
cout << "f(" << x << ")=";
bool flag = false;
for (int i = 1 ; i <= x ; i++) {
if (cnt[i] != 0) {
if (flag) {
cout << "*";
}
print(i, cnt[i]);
flag = true;
}
}
return 0;
}
E 自由还是爱情 这是个问题
01背包模型，分别对 自由 和 爱情 做一次01背包。然后求符合条件的最大价值，比较再输出即可。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int dp[2][2005];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for (int i = 0 ; i <= 2000 ; i++) {
dp[0][i] = dp[1][i] = 20000;
}
dp[0][0] = dp[1][0] = 0;
for (int i = 1 ; i <= n ; i++) {
int x, y, z;
cin >> x >> y >> z;
for (int j = 2000 ; j >= z ; j--) {
dp[x][j] = min(dp[x][j], dp[x][j - z] + y);
}
}
int mx[2] = {};
for (int i = 2000 ; i >= 0 ; i--) {
if (dp[0][i] <= k) {
mx[0] = max(mx[0], i);
}
if (dp[1][i] <= k) {
mx[1] = max(mx[1], i);
}
}
if (mx[0] >= mx[1]) {
cout << mx[0] << " " << 0;
} else {
cout << mx[1] << " " << 1;
}
return 0;
}
F 基本操作
模拟题，数据范围较小，根据题目暴力模拟即可，具体详细见代码。
注意：理论上来说一直复制粘贴可以使字符串很长很长，但是会使得题目不可做，本题应该是有一个最长长度限制。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
void solve() {
int n, m;
cin >> n >> m;
string str;
cin >> str;
str = " " + str;
string cx = "";
for (int i = 0 ; i < m ; i++) {
string s;
cin >> s;
if (s == "cc") {
int L, R;
cin >> L >> R;
cx = str.substr(L, R - L + 1);
} else if (s == "cv") {
int pos;
cin >> pos;
if (cx != "") {
str.insert(pos + 1, cx);
}
} else {
int L, R;
cin >> L >> R;
cx = str.substr(L, R - L + 1);
str.erase(begin(str) + L, begin(str) + R + 1);
}
}
cout << str.substr(1) << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
G 夜雷の史莱姆农场
根据题意， 天后一共有
个史莱姆，但是题目说每个畜栏都有
的容量，也就是说 大于
将被清空，这转化成了
，使用快速幂即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
long long qpow(long long a, long long b, long long p) {
long long res = 1;
while (b) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
void solve() {
long long a, b, p;
cin >> a >> b >> p;
cout << qpow(a, b, p) << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
H 小黑屋的救赎
的迷宫，
点体力，
钥匙。
由于数据范围极小，本题使用最短路搜索即可。
令 为 在
点时，使用了
把钥匙的最少体力花费。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int n, m, p, k;
char g[11][11];
int sx, sy, ex, ey;
int dist[11][11][101];
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> p >> k;
for (int i = 1 ; i <= n ; i++) {
for (int j = 1 ; j <= m ; j++) {
cin >> g[i][j];
if (g[i][j] == 's') {
sx = i;
sy = j;
}
if (g[i][j] == 'e') {
ex = i;
ey = j;
}
for (int z = 0 ; z <= k ; z++) {
dist[i][j][z] = 1000;
}
}
}
queue<pair<int, int>> que;
que.emplace(sx, sy);
dist[sx][sy][k] = 0;
int temp = 0;
while (!que.empty()) {
temp++;
auto [x, y] = que.front();
que.pop();
for (int i = 0 ; i < 4 ; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > n || yy < 1 || yy > m) {
continue;
}
if (g[xx][yy] == 'w') continue;
bool flag = false;
for (int j = 0 ; j <= k ; j++) {
if (j - (g[xx][yy] == 'd') >= 0 && dist[xx][yy][j - (g[xx][yy] == 'd')] > dist[x][y][j] + 1) {
dist[xx][yy][j - (g[xx][yy] == 'd')] = dist[x][y][j] + 1;
flag = true;
}
}
if (flag) {
que.emplace(xx, yy);
}
}
}
for (int i = 0 ; i <= k ; i++) {
if (dist[ex][ey][i] <= p) {
cout << "YES";
return 0;
}
}
cout << "NO";
return 0;
}
I 大写数字
大模拟，本题限制整数部分最多 位，所以可以直接把整数部分扩充到
位，然后 前
位二进制枚举
，后
位同理，小数部分最多
位，二进制枚举
即可。有其他更好做法。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
string num[] = {
"零",
"壹",
"贰",
"叁",
"肆",
"伍",
"陆",
"柒",
"捌",
"玖",
"拾"
};
int printF1(string str) {
// 0000
if (str == "0000") {
return -1;
}
// 0001
if (str[0] == '0' && str[1] == '0' && str[2] == '0') {
cout << num[str[3] - '0'] << "万";
return 1;
}
// 0010
if (str[0] == '0' && str[1] == '0' && str[3] == '0') {
cout << num[str[2] - '0'] << "拾万";
return 1;
}
// 0100
if (str[0] == '0' && str[2] == '0' && str[3] == '0') {
cout << num[str[1] - '0'] << "佰万";
return 1;
}
// 1000
if (str[1] == '0' && str[2] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟万";
return 1;
}
// 0011
if (str[0] == '0' && str[1] == '0') {
cout << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "万";
return 1;
}
// 0101
if (str[0] == '0' && str[2] == '0') {
cout << num[str[1] - '0'] << "佰零" << num[str[3] - '0'] << "万";
return 1;
}
// 1001
if (str[1] == '0' && str[2] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[3] - '0'] << "万";
return 1;
}
// 0110
if (str[0] == '0' && str[3] == '0') {
cout << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾万";
return 1;
}
// 1010
if (str[1] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[2] - '0'] << "拾万";
return 1;
}
// 1100
if (str[2] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰万";
return 1;
}
// 0111
if (str[0] == '0') {
cout << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "万";
return 1;
}
// 1011
if (str[1] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "万";
return 1;
}
// 1101
if (str[2] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰零" << num[str[3] - '0'] << "万";
return 1;
}
// 1110
if (str[3] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾万";
return 1;
}
// 1111
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "万";
return 1;
}
void printF(string str) {
while (str.size() < 8) {
str = "0" + str;
}
int cnt = printF1(str.substr(0, 4));
str = str.substr(4);
if (str == "0000") {
cout << "元";
return;
}
// 0001
if (str[0] == '0' && str[1] == '0' && str[2] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[3] - '0'] << "元";
return;
}
// 0010
if (str[0] == '0' && str[1] == '0' && str[3] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[2] - '0'] << "拾元";
return;
}
// 0100
if (str[0] == '0' && str[2] == '0' && str[3] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[1] - '0'] << "佰元";
return;
}
// 1000
if (str[1] == '0' && str[2] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟元";
return;
}
// 0011
if (str[0] == '0' && str[1] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "元";
return;
}
// 0101
if (str[0] == '0' && str[2] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[1] - '0'] << "佰零" << num[str[3] - '0'] << "元";
return;
}
// 1001
if (str[1] == '0' && str[2] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[3] - '0'] << "元";
return;
}
// 0110
if (str[0] == '0' && str[3] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾元";
return;
}
// 1010
if (str[1] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[2] - '0'] << "拾元";
return;
}
// 1100
if (str[2] == '0' && str[3] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰元";
return;
}
// 0111
if (str[0] == '0') {
if (cnt != -1) {
cout << "零";
}
cout << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "元";
return;
}
// 1011
if (str[1] == '0') {
cout << num[str[0] - '0'] << "仟零" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "元";
return;
}
// 1101
if (str[2] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰零" << num[str[3] - '0'] << "元";
return;
}
// 1110
if (str[3] == '0') {
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾元";
return;
}
// 1111
cout << num[str[0] - '0'] << "仟" << num[str[1] - '0'] << "佰" << num[str[2] - '0'] << "拾" << num[str[3] - '0'] << "元";
}
void printB(string str) {
while (str.size() < 2) {
str += "0";
}
if (str == "00") {
cout << "整";
return;
}
if (str[0] == '0') {
cout << "零" << num[str[1] - '0'] << "分";
return;
}
if (str[1] == '0') {
cout << num[str[0] - '0'] << "角";
return;
}
cout << num[str[0] - '0'] << "角" << num[str[1] - '0'] << "分";
}
void solve() {
string str;
while (cin >> str) {
string f, b = "";
{
int k = str.find(".");
if (k != -1) {
f = str.substr(0, k);
b = str.substr(k + 1);
} else {
f = str;
}
}
printF(f);
printB(b);
cout << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
J 兔子不会种树
易知第 秒新增
，第
秒新增
，...，第
秒新增
。那么
。
我们只需要提前处理等比数列的前 项，然后用二分或者直接循环查找即可知道
是第几秒生长出来的。
总时间复杂度
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, n;
cin >> k >> n;
vector<__int128> ans;
__int128 r = 1, sum = r;
while (k != 1 && sum <= 1000000000000000000LL) {
ans.emplace_back(sum);
r *= k;
sum += r;
}
for (int i = 1 ; i <= n ; i++) {
long long x;
cin >> x;
if (k == 1) cout << x - 1 << "\n";
else cout << (lower_bound(begin(ans), end(ans), x) - begin(ans)) << "\n";
}
return 0;
}
K 淘金币
变
，
变
。
易知 个
和
个
连接起来，可以得到
块钱。
个
和
个
连接起来，也可以得到
块钱。
那么就看 和 左边还是右边的
结合了。这里可以用dp来计算哪个更优。
令 为前
个字符能得到的最多钱数。
那么我们预处理所有可能的结合情况如 ，
，我们记录它们的左右端点。
对于 ，有
我们只需要对左端点进行排序就好了。
总时间复杂度
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
vector<int> adj[200005];
int dp[200005];
void solve() {
string str;
cin >> str;
int n = str.size();
str = " " + str;
for (int i = 0 ; i <= n ; i++) {
adj[i].resize(0);
dp[i] = 0;
}
int cnt = 0;
vector<pair<int, int>> res;
for (int i = 1 ; i <= n ; i++) {
if (str[i] == 'A') {
cnt++;
} else {
if (cnt > 0) {
res.emplace_back(i - cnt, i);
}
cnt = 0;
}
}
if (cnt > 0) {
res.emplace_back(n - cnt, n);
}
cnt = 0;
for (int i = n ; i >= 1 ; i--) {
if (str[i] == 'A') {
cnt++;
} else {
if (cnt > 0) {
res.emplace_back(i, i + cnt);
}
cnt = 0;
}
}
if (cnt > 0) {
res.emplace_back(1, 1 + cnt);
}
for (auto &[L, R] : res) {
adj[L].emplace_back(R);
}
for (int i = 1 ; i <= n ; i++) {
dp[i] = max(dp[i], dp[i - 1]);
for (auto &r : adj[i]) {
dp[r] = max(dp[r], dp[i - 1] + r - i);
}
}
cout << dp[n] << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
L 兔子饼干
结论题。
只有 先手才必输。
证明：
当 只要 阿兔 第一步选择
，那么只会剩下
，
，这是一个以
对称的形状，此时是 夜雷 的回合，那么 夜雷 操作什么，阿兔 就跟着操作什么，（nim游戏），这样子可以做到 夜雷 一定吃到 特制饼干。
当 时，阿兔必定吃到 特制饼干。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
while (cin >> n) {
if (n == 1) {
cout << "就这？就这？\n";
} else {
cout << "哼！哼！啊啊啊啊啊啊！\n";
}
}
return 0;
}
M arkdaytime
根据题意大模拟。可以使用各种技巧来优化代码量。
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
struct Node {
int hp, atk, def;
int sdef, type, pos;
int cnt;
friend Node operator-(Node lhs, Node rhs) {
// lhs 守方
// rhs 攻方
if (rhs.type == 1) {
lhs.hp -= rhs.atk - lhs.def;
} else {
lhs.hp -= (rhs.atk * (100 - lhs.sdef) + 99) / 100;
}
// 返回 守方
return lhs;
}
};
vector<Node> x;
array<vector<Node>, 2> fri;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1 ; i <= n ; i++) {
int a, b, c, d, e, f, g;
cin >> a >> b >> c >> d >> e >> f >> g;
f--;
x.push_back({a, b, c, d, e, f, g});
}
reverse(begin(x), end(x));
for (int i = 1 ; i <= m ; i++) {
int a, b, c, d, e, f;
cin >> a >> b >> c >> d >> e >> f;
f--;
fri[f].push_back({a, b, c, d, e, f, 0});
}
int huihe = 0;
while (!x.empty()) {
huihe++;
auto di = x.back();
x.pop_back();
auto r = fri;
int k = di.cnt;
for (int i = int(r[di.pos].size()) - 1 ; k > 0 && i >= 0 ; k--, i--) {
r[di.pos][i] = r[di.pos][i] - di;
}
for (int i = int(r[di.pos ^ 1].size()) - 1 ; k > 0 && i >= 0 ; k--, i--) {
r[di.pos ^ 1][i] = r[di.pos ^ 1][i] - di;
}
fri[0].resize(0);
fri[1].resize(0);
for (int i = 0 ; i < int(r[0].size()) ; i++) {
if (r[0][i].hp > 0) {
fri[0].push_back(r[0][i]);
}
}
if (fri[0].empty()) {
if (di.hp > 0) {
x.push_back(di);
}
cout << "No\n" << x.size();
return 0;
}
for (int i = 0 ; i < int(r[1].size()) ; i++) {
if (r[1][i].hp > 0) {
fri[1].push_back(r[1][i]);
di = di - fri[1].back();
}
}
if (!fri[0].empty()) {
di = di - fri[0].back();
}
if (di.hp > 0) {
x.push_back(di);
}
}
cout << "Yes\n" << fri[0].size() + fri[1].size();
return 0;
}
京公网安备 11010502036488号