A-小红的字符移动
签到题
代码
#include <iostream>using namespace std;int main()
{string s;cin >> s;swap(s[0], s[1]);cout << s;
}
B-小红的数轴移动
一道模拟题吧，按题意要求进行操作。
代码
#include <iostream>using namespace std;typedef long long ll;const int N = 1e5 + 10;int a[N];int main()
{int n, x;cin >> n >> x;ll res = 0;while (n --){if (x == 0) break;ll k;cin >> k;if (x > 0) x -= k;else x += k;res += k;}cout << res;return 0;
}
C-小红的圆移动
题目看太快看歪了，赛时解法对的，但做了一堆无效操作。
思路
题意要求包含原点的圆不超过k个，所以枚举每个圆，通过圆心到原点的距离和半径比较，判断是否包含圆心。记录包含圆心的圆的个数设为cnt，cnt <= k则直接输出0，不需要进行移动；cnt > k需要移动cnt - k个圆，移动代价是距离乘圆的面积，可以在枚举圆的时候，将包含原点的圆移动的代价存下来，进行排序，将代价较小的圆优先移动。
代码
#include <iostream>
#include <algorithm>
#include <cmath>#define fi first
#define se secondusing namespace std;typedef long long ll;const double pi = acos(-1);
const int N = 1e5 + 10;pair<double, ll> a[N];
double b[N];double S(ll r)
{return pi * r * r;
}double p(double x, ll r)
{return fabs(x) * S(r);
}int main()
{int n, k;cin >> n >> k;int cnt = 0;for (int i = 0; i < n; i ++){ll x, y, r;cin >> x >> y >> r;double d = sqrt(x * x + y * y);if (d - r < 0) b[cnt ++] = p(d - r, r);}if (cnt <= k) {cout << 0;}else {sort(b, b + cnt);double res = 0;for (int i = 0; i < cnt - k; i ++)res += b[i];printf("%.12lf", res);}return 0;
}
D-小红的树上移动
思路
注意题目说当前节点的邻点中不存在白色节点，则停止移动，根据树的定义，容易知道，停下移动的节点就是叶子节点，且移动过程必然是从根节点一路走到叶子节点。则当前路径的红色节点数量的期望就等于路径节点数量*选择走这条路径的概率，概率求法就是每个分叉点的概率之积。最终答案就是将所有叶子节点的期望求和。
代码
赛时bfs写法
#include <iostream>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int N = 1e5 + 10;int n;
vector<int> g[N];
ll sz[N];
ll p[N];
bool st[N];ll qmi(ll a, ll b)
{ll res = 1;while (b){if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}ll inv(ll x)
{return qmi(x, mod - 2);
}void bfs()
{queue<int> q;q.push(1);sz[1] = 1;while (!q.empty()){int t = q.front();q.pop();st[t] = 1;for (int i : g[t]){if (st[i]) continue;sz[i] = sz[t] + 1;p[i] = p[t] * (g[t].size() - (t != 1)) % mod;q.push(i);}}
}int main()
{cin >> n;for (int i = 1; i <= n; i ++) p[i] = 1; for (int i = 1; i < n; i ++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}bfs();ll res = 0;for (int i = 2; i <= n; i ++)if (g[i].size() == 1)res = (res + sz[i] * inv(p[i]) % mod) % mod;cout << res;return 0;
}
dfs代码
#include <iostream>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int N = 1e5 + 10;int n;
vector<int> g[N];
ll sz[N];
ll p[N];
bool st[N];ll qmi(ll a, ll b)
{ll res = 1;while (b){if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}ll inv(ll x)
{return qmi(x, mod - 2);
}int dfs(int u, int fa)
{int cnt = 0, sum = 0;for (int i : g[u]){if (i == fa) continue;cnt ++;sum = (sum + dfs(i, u)) % mod;}return (1 + sum * inv(cnt) % mod) % mod;
}int main()
{cin >> n; for (int i = 1; i < n; i ++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}cout << dfs(1, 0);return 0;
}
EF-小红的中位数查询
一道主席树的板子题吧。看下官方的题解吧，讲的太好了。
当然也可以用划分树。。。
代码
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 1e5 + 10;int n, m;
int a[N];
vector<int> nums;struct node {int l, r;int cnt;
} tr[N * 4 + N * 17];int root[N], idx;int find(int x)
{return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}int build(int l, int r)
{int p = ++ idx;if (l == r) return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}int insert(int p, int l, int r, int x)
{int q = ++ idx;tr[q] = tr[p];if (l == r) {tr[q].cnt ++;return q;}int mid = l + r >> 1;if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);else tr[q].r = insert(tr[p].r, mid + 1, r, x);tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;return q;
}int query(int q, int p, int l, int r, int k)
{if (l == r) return r;int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;int mid = l + r >> 1;if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i ++){cin >> a[i];nums.push_back(a[i]);}sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());root[0] = build(0, nums.size() - 1);for (int i = 1; i <= n; i ++)root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));while (m --){int l, r, k;cin >> l >> r;k = (r - l + 2) / 2;cout << nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)] << '\n';}return 0;
}
G-小红的数轴移动（二）
01背包。做法和蓝桥的砝码称重有点像，这里改求选择最少操作到达目标值，多一个求选择的先后序。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>using namespace std;const int M = 10000;
const int N = 1e5 + 10;int a[N], dp[110][M * 2];
vector<int> hp[M];
int n, k;
set<int> v;int main()
{cin >> n >> k;int sum = 0;for (int i = 1; i <= n; i ++){cin >> a[i];sum += a[i];hp[a[i]].push_back(i);v.insert(i);}memset(dp, 0x3f, sizeof dp);dp[0][M + k] = 0;for (int i = 1; i <= n; i ++){for (int j = -M; j <= M; j ++) dp[i][M + j] = dp[i - 1][M + j];for (int j = -M; j <= M; j ++){if (j + a[i] <= M) dp[i][j + M + a[i]] = min(dp[i][j + M + a[i]], dp[i - 1][j + M] + a[i]);if (j - a[i] >= -M) dp[i][j + M - a[i]] = min(dp[i][j + M - a[i]], dp[i - 1][j + M] + a[i]);}}if (dp[n][M] == 0x3f3f3f3f) {cout << sum << '\n';for (int i = 1; i <= n; i ++) cout << i << ' ';return 0;}vector<int> l, r, ans;int res = dp[n][M], j = 0;cout << res << '\n';for (int i = n; i; i --){if (dp[i][j + M] == dp[i - 1][j + M]) continue;if (j + a[i] <= M && dp[i][j + M] == dp[i - 1][j + M + a[i]] + a[i]) {l.push_back(hp[a[i]].back());v.erase(hp[a[i]].back());hp[a[i]].pop_back();j += a[i];res -= a[i];}if (j - a[i] >= -M && dp[i][j + M] == dp[i - 1][j + M - a[i]] + a[i]) {r.push_back(hp[a[i]].back());v.erase(hp[a[i]].back());hp[a[i]].pop_back();j -= a[i];res -= a[i];}}while (k != 0){if (k < 0) {k += a[r.back()];ans.push_back(r.back());r.pop_back();}else {k -= a[l.back()];ans.push_back(l.back());l.pop_back();}}for (int i : ans) cout << i << ' ';for (int j : v) cout << j << ' ';return 0;
}
另一个做法，图论。
将区间偏移100，考虑（100, 200]内每个点i是由i-a[i]的点转移过来的，边权是a[i]，[0, 100）内每个点i是由i+a[i]的点转移过来的，边权是a[i]。然后以x+100作为起点，做dijkstra求最短路。注意跑当前路径的时候，每个点只能选一遍，同时将前驱节点记录下来。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;const ll INF = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;struct node {ll v, w, id;
};struct edge {ll v, w, id;vector<bool> vis;bool operator < (const edge& a) const {return w > a.w;}
};int n, x;
ll a[N], dist[N], pre[N], pred[N];
bool st[N], vst[N];
vector<node> g[N];void dijkstra()
{memset(dist, 0x3f, sizeof dist);priority_queue<edge> pq;dist[x + 100] = 0;vector<bool> vis(n + 1, 0);pq.push({x + 100, 0, 0, vis});while (!pq.empty()){auto [u, w, fa, vv] = pq.top();pq.pop();if (vst[u]) continue;vst[u] = 1;for (auto [v, c, id] : g[u]){if (dist[v] > w + c && !vv[id]){dist[v] = w + c;pre[v] = u;pred[v] = id;vector<bool> vs = vv;vs[id] = 1;pq.push({v, w + c, id, vs});}}}
}int main()
{cin >> n >> x;ll sum = 0;for (int i = 1; i <= n; i ++){cin >> a[i];sum += a[i];for (int j = 0; j <= 200; j ++)if (j > 100) g[j].push_back({j - a[i], a[i], i});else if (j < 100) g[j].push_back({j + a[i], a[i], i});}dijkstra();if (dist[100] == INF) {cout << sum << '\n';for (int i = 1; i <= n; i ++) cout << i << ' ';return 0;}cout << dist[100] << '\n';int ne = 100;vector<int> ans;if (pre[ne]) {while (ne != x + 100){ans.push_back(pred[ne]);st[pred[ne]] = 1;ne = pre[ne];}}reverse(ans.begin(), ans.end());for (int i = 1; i <= n; i ++)if (!st[i]) ans.push_back(i);for (int i : ans) cout << i << ' ';return 0;
}
