文章目录
正文
总共8道题。
1. MC0355 · 开篇签到
【题目】 MC0355 · 开篇签到
【分析】
输出严格次小值。
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e5 + 10; int a[N];
void solve()
{
int n; cin >> n; for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n); int pos = 0;
for (int i = 0; i < n; i ++) if (a[i] == a[0]) pos ++;
cout << a[pos] << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
2. MC0357 · 移动移动移动
【题目】MC0357 · 移动移动移动
【分析】
考察贪心。
全是1的串直接加，剩余不全为1的串只保留一边连续1长度的最大值。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int cnt1, cnt2, m1, m2, ans;
void solve()
{
int n; cin >> n;
for (int i = 0; i < n; i ++)
{
string s; cin >> s; cnt1 = 0; cnt2 = 0;
for (int i = 0; i < s.length() && s[i] == '1'; i ++) cnt1 ++;
for (int i = s.length() - 1; i >= 0 && s[i] == '1'; i --) cnt2 ++;
if (cnt1 == s.size()) ans += cnt1;
else { m1 = max(cnt1, m1); m2 = max(cnt2, m2); }
}
cout << ans + max(m1, m2) << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
3. MC0357 · 移动移动移动
【题目】MC0357 · 移动移动移动
【分析】
考察：逆元、快速幂、阶乘预处理、逆元求组合数。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
const ll N = 3e5 + 10, mod = 998244353;
ll f[N], inf[N];
ll ksm(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 a) { return ksm(a, mod - 2); }
ll C(ll a, ll b) { return f[a] * inf[b] % mod * inf[a - b] % mod; }
void init()
{
f[0] = inf[0] = 1;
for (ll i = 1; i <= N; i++)
{
f[i] = f[i - 1] * i % mod;
inf[i] = inf[i - 1] * inv(i) % mod;
}
}
void solve()
{
int x1, y1, x2, y2, n, p, q; cin >> x1 >> y1 >> x2 >> y2 >> n >> p >> q;
ll cx = x2 - x1, cy = y2 - y1;
if (cx + cy > n || cx < 0 || cy < 0) return cout << 0 << '\n', void();
ll ans = C(n, cx) * ksm(p * inv(100) % mod, cx) % mod * ksm(q * inv(100) % mod, n - cx) % mod;
cout << ans << '\n';
}
int main()
{
IOS init(); ll t = 1; cin >> t;
while (t --) solve();
return 0;
}
4. MC0358 · 请相信我会做图论
【分析】
考查图论dfs。
【AC_Code】
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using pii = pair<int, int>;
const int N = 1e5 + 10; int w[N], vis[N], ans; vector<int> u[N];
void dfs(int a)
{
if (vis[a]) return ; vis[a] = 1;
for (int i = 0; i < u[a].size(); i ++)
{
int next = u[a][i]; w[next] = min(w[a], w[next]);
dfs(next);
}
}
bool cmp(pii& a, pii& b) { return a.second < b.second; }
void solve()
{
int n, m; cin >> n >> m; pii t[n + 1];
for (int i = 1; i <= n; i ++) cin >> w[i], t[i].first = w[i], t[i].second = i;
while (m --) { int a, b; cin >> a >> b; u[a].push_back(b); }
sort(t + 1, t + n + 1);
for (int i = 0; i < n; i ++) dfs(t[i].second);
for (int i = 1; i <= n; i ++) ans += w[i]; cout << ans << '\n';
for (int i = 1; i <= n; i ++) cout << w[i] << " \n"[i == n];
}
signed main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
5. MC0359 · 我会等差数列
【题目】MC0359 · 我会等差数列
【分析】
前缀和 + 二分查找临界位置 + 处理特殊情况。
【AC_Code】
#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 1e6 + 10; int n, q, a[N], f[N]; long pre[N];
void init()
{
f[1] = 1; f[2] = 2;
for (int i = 3; i <= n; i ++)
{
if (a[i] + a[i - 2] == 2 * a[i - 1]) f[i] = f[i - 1] + 1;
else f[i] = 2;
}
for (int i = 1; i <= n; i ++) pre[i] = pre[i - 1] + f[i];
}
void solve()
{
cin >> n >> q; for (int i = 1; i <= n; i ++) cin >> a[i]; init();
while (q --)
{
int l, r; cin >> l >> r;
if (f[r] >= r - l + 1)
{
cout << long(r - l + 1) * (r - l + 2) / 2 << '\n'; continue;
}
int _l = l, _r = r;
while (_l < _r)
{
int mid = (_l + _r) >> 1;
if (f[mid] < mid - l + 1) _r = mid;
else _l = mid + 1;
}
cout << pre[r] - pre[_l - 1] + long(_l - l) * (_l - l + 1) / 2 << '\n';
}
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
6. MC0360 · 我会修改图
【题目】MC0360 · 我会修改图
【分析】
离线 + 并查集 + 启发式合并。
【AC_Code】
#include <bits/stdc++.h>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e5 + 10, M = 4e5 + 10;
int a[N], s[N], edg[M][2], op[M][3]; bool del[M];
map<int, int> cnt[N]; vector<int> ans;
int find(int u) { return u == s[u] ? u : s[u] = find(s[u]); }
void merge(int u, int v)
{
u = find(u); v = find(v);
if (u == v) return ;
if (cnt[u].size() < cnt[v].size()) swap(u, v);
s[v] = u;
for (const auto& pair : cnt[v])
{
int w = pair.first, c = pair.second; cnt[u][w] += c;
}
}
void solve()
{
int n, m, q; cin >> n >> m >> q;
for (int i = 1; i <= n; i ++) { cin >> a[i]; s[i] = i; cnt[i][a[i]] = 1; }
for (int i = 1; i <= m; i ++) cin >> edg[i][0] >> edg[i][1];
for (int i = 1; i <= q; i ++)
{
cin >> op[i][0] >> op[i][1];
if (op[i][0] == 2) cin >> op[i][2];
else del[op[i][1]] = true;
}
for (int i = 1; i <= m; i ++)
{
if (del[i]) continue;
merge(edg[i][0], edg[i][1]);
}
for (int i = q; i >= 1; i --)
{
if (op[i][0] == 1) { int x = op[i][1]; merge(edg[x][0], edg[x][1]); }
else
{
int x = op[i][1], y = op[i][2], u = find(x), target = y - a[x];
int count = cnt[u].count(target) ? cnt[u][target] : 0;
ans.push_back(count - (a[x] == target ? 1 : 0));
}
}
reverse(ans.begin(), ans.end()); for (int x : ans) cout << x << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
7. MC0361 · 团队能量
【题目】MC0361 · 团队能量
【分析】
【AC_Code】
#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
const int N = 1e6 + 10; ll n, k, a[N], f[N], M = 2e18;
void solve()
{
int n, k; cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 0; i <= n + 1; i ++) f[i] = M;
f[0] = 0; f[2] = a[2] - a[1];
for (int i = 3; i <= n; i ++)
{
f[i] = f[i - 2] + a[i] - a[i - 1];
if (k <= 2) continue;
f[i] = min(f[i], f[i - 3] + a[i] * 2 - a[i - 2] - a[i - 1]);
}
cout << f[n] << '\n';
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
8. MC0362 · 异或
【题目】MC0362 · 异或
【分析】
【AC_Code】
#include <iostream>
#include <vector>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 5e5 + 10, mod = 1e9 + 7;
int n, q, k, a[N], f[N][30][2], ans; vector<int> e[N], path { 0 };
void dfs(int u, int fa)
{
path.push_back(u);
for (int i = 0; i < 30; i ++)
{
f[u][i][a[u] >> i & 1] ++;
f[path[max(0, (int)path.size() - k - 2)]][i][a[u] >> i & 1] --;
}
for (int v : e[u])
{
if (v == fa) continue;
dfs(v, u);
}
path.pop_back();
}
void dfs_sum(int u, int fa)
{
for (int v : e[u])
{
if (v == fa) continue;
dfs_sum(v, u);
for (int i = 0; i < 30; i ++) { f[u][i][0] += f[v][i][0]; f[u][i][1] += f[v][i][1]; }
}
}
void solve()
{
cin >> n >> q >> k; for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = n - 1, u, v; i --; ) { cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
dfs(1, 0); dfs_sum(1, 0);
for (int x; q --; )
{
cin >> x; ans = 0;
for (int i = 0; i < 30; i ++)
{
ans += f[x][i][0] * (1l << i) % mod * f[x][i][1] % mod;
ans %= mod;
}
cout << ans << '\n';
}
}
int main()
{
IOS int _ = 1; // cin >> _;
while (_ --) solve();
return 0;
}
结语
感谢您的阅读！期待您的一键三连！欢迎指正！
