A 小贪一手
思路：
当然不可能暴力了，暴力是不可能的。
代码：
void solve() { int n, x, y; cin >> x >> y >> n; int now = n / x; int cur; for (int i = now - 1; ; i++) { if(i * x + y > n) break; cur = i * x + y; } cout << cur << endl; }
B A+B Problem (very easy)
简单的小模拟
C Alice and Bob
上取整坑点
代码：
简单的博弈论
f[i]=1：先手胜
f[i]=2：后手胜
int f[1010]; void init() { f[1] = 1; f[2] = 2; f[3] = 1; f[4] = 1; f[5] = 2; for (int i = 6; i <= 1000; i++) { int o = 0; for (int j = 1; j <= i / 2; j++) { if(f[i - j] == 2) o = 1; } f[i] = o ? 1 : 2; } } void solve() { int n; cin >> n; if(f[n] == 1) { cout << "NO" << endl; } else { cout << "YES" << endl; } } signed main() { IOS int _ = 1; init(); cin >> _; while(_--) { solve(); } return 0; }
D 进化
E 防疫物资
简单来说： 加一条边，让快递员送完后回去的路程最短。
思路：
发现加一条边，必然选择最高和次高之间。这样构成的一条路径（走一步）是最长的一个环（根->最深->次深->根）。其它路都要走两步。
答案即为：2∗所有边−最深−次深+1
代码：
int n, ans; vi e[N], v; int height(int u, int f) { int res = 1; int mx = 0; for (auto &x: e[u]) { if(x == f) continue; mx = max(mx, height(x, u)); } return res + mx; } void dfs(int u, int f) { for (auto &x: e[u]) { v.pb(height(x, u)); } sort(rall(v)); } void solve() { cin >> n; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; e[a].pb(b); e[b].pb(a); } dfs(1, -1); if(v.sz > 1) ans = v[0] + v[1]; else ans = v[0]; cout << 2 * (n - 1) - ans + 1 << endl; }
F 有挂
思路：
只需要将模板线段树，简单改改就好了。
原 s u m值维护区间和，改为维护区间内攻击次数即可。
代码：
int n, m, x; int op, l, r, k; #define ls u<<1 #define rs u<<1|1 struct node { int l, r; int add, sum; } tr[N << 2]; int len(int u) { return tr[u].r - tr[u].l + 1; } void pushup(int u) { tr[u].sum = tr[ls].sum + tr[rs].sum; } void pushdown(int u) { if(tr[u].add) { tr[ls].sum += len(ls) * tr[u].add, tr[ls].add += tr[u].add; tr[rs].sum += len(rs) * tr[u].add, tr[rs].add += tr[u].add; tr[u].add = 0; } } void build(int u, int l, int r) { tr[u] = {l, r, 0}; if(l == r) return ; int mid = l + r >> 1; build(ls, l, mid), build(rs, mid + 1, r); } void modify(int u, int l, int r, int k) { if(tr[u].l >= l && tr[u].r <= r) { int fa = (k - 1) / x + 1; tr[u].sum += len(u) * fa; tr[u].add += fa; return ; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) modify(ls, l, r, k); if(r > mid) modify(rs, l, r, k); pushup(u); return ; } int query(int u, int l, int r) { if(tr[u].l >= l && tr[u].r <= r) { return tr[u].sum; } int mid = tr[u].l + tr[u].r >> 1; int v = 0; pushdown(u); if(l <= mid) v = query(ls, l, r); if(r > mid) v += query(rs, l, r); return v; } void solve() { cin >> n >> m >> x; build(1, 1, n); while(m--) { cin >> op >> l >> r; if(op == 1) { cin >> k; modify(1, l, r, k); } else { cout << (query(1, l, r)) << endl; } } }
G 鸡你太美
#include<bits/stdc++.h> #define ll long long #define ri register int #define x first #define y second using namespace std; const int maxN = 1e5 + 5; const ll INF = 0x3f3f3f3f; inline int read() { int ans = 0, f = 0; char ch = getchar(); while (ch < '0' || ch>'9')f ^= (ch == '-'), ch = getchar(); while (ch >= '0' && ch <= '9')ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = getchar(); return f ? -ans : ans; } int n, m; int a[maxN]; int f[maxN][1 << 9]; int count(int x) { int ans = 0; for (int i = 0; i < m; i++)ans += x >> i & 1; return ans; } int main() { n = read(), m = read(); for (int i = 1; i <= n; i++)a[i] = read(); f[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < 1 << m; j++) { int k = j >> 1; if (count(k) + 1 <= m / 2) { f[i][k | 1 << (m - 1)] = max(f[i][k | 1 << (m - 1)], f[i - 1][j] + a[i]); } if (count(k) <= m / 2) { f[i][k] = max(f[i][k], f[i - 1][j]); } } } int ans = 0; for (int i = 0; i < 1 << m; i++)ans = max(ans, f[n][i]); cout << ans; return 0; }
H 爱美之心人皆有之
思路：
区间 max − 区间 min = = k，问这样（以下称为合法）区间的对数？
multiset：可重复元素的 set
s 1 ：维护区间恰好合法，即（==k）。右端下标 l
s 2：维护区间恰好不合法，即（ > k )。右端下标 r
类似前缀和思想？：r−l 即以 i 为起始段的区间合法的对数。
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1000010; int n, k, a[N]; multiset<int> s1, s2; int ret(multiset<int> &s) { if(s.size() == 0) return -1; return *s.rbegin() - *s.begin(); } signed main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; int res = 0; int l = 0, r = 0; for (int i = 1; i <= n; i++) { while(l <= n && ret(s1) < k) s1.insert(a[++l]); while(r <= n && ret(s2) <= k) s2.insert(a[++r]); res += r - l; s1.erase(s1.find(a[i])); s2.erase(s2.find(a[i])); } cout << res << endl; return 0; }
I 签签签到
void solve() { cout << "%d%\\n\"" << endl; }
