A、完全数
分解一个数的因子,直接 判断即可,符合时间要求。
void solve() { ll n = read(); ll m = 1; for (ll i = 2; i * i <= n; ++i) { if (n % i == 0) { if (i * i == n) m += i; else m += i, m += n / i; } } if (m == n) puts("Pure"); else if (m > n) puts("Late"); else puts("Early"); }
B、移动撤销
涉及回退操作,考虑栈的数据结构。
其他的模拟步伐就行了,把步伐放入栈中即可。
const int N = 1e6 + 7; int n, m; char s[N]; void solve() { n = read(); scanf("%s", s + 1); unordered_map<char, pai> mp; mp['A'] = { -1,0 }; mp['W'] = { 0,1 }; mp['S'] = { 0,-1 }; mp['D'] = { 1,0 }; pai st[N]; st[0] = { 0,0 }; int top = 0; for (int i = 1; i <= n; ++i) { if (s[i] != 'Z') { pai pre = st[top]; pre.first += mp[s[i]].first; pre.second += mp[s[i]].second; st[++top] = pre; } else { if (top) --top; } } printf("%d %d\n", st[top].first, st[top].second); }
C、石头剪刀布
需要求解最大分数,那么也就是能赢的一定要赢,不能赢的全去平局即可,剩下的就只能输了,但是输了也不扣分。
分三步模拟即可。
struct Node { int a, b, c; }x, y; void solve() { int n = read(); x.a = read(), x.b = read(), x.c = read(); y.a = read(), y.b = read(), y.c = read(); ll ans = 0; int mini = min(x.a, y.b); ans += 2 * mini; x.a -= mini, y.b -= mini; mini = min(x.b, y.c); ans += 2 * mini; x.b -= mini, y.c -= mini; mini = min(x.c, y.a); ans += 2 * mini; x.c -= mini, y.a -= mini; ans += min(x.a, y.a); ans += min(x.b, y.b); ans += min(x.c, y.c); print(ans); }
D、夹缝中求和
首先考虑50分的做法,如果数据规模在
这样就可以直接通过枚举每个数字,通过树状数组查询前面出现过几个在合理区间中的数。
现在考虑100分做法,现在数据规模到了不能直接开下这么大的树状数组。
所以就需要考虑离散做法了。
离散全部的数据拿到全部数据的编号,每次查询在对应编号区间中的数字即可。
const int N = 1e5 + 7; int n, x, y; int a[N], b[N]; // a 原数组 b 离散数组 int c[N]; // c 树状数组 int lowbit(int x) { return x & (-x); } void add(int i, int z) { for (; i < N; i += lowbit(i)) c[i] += z; } int query(int i) { if (i < 0) return 0; int res = 0; for (; i; i -= lowbit(i)) res += c[i]; return res; } void solve() { n = read(), x = read(), y = read(); for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i]; sort(b + 1, b + 1 + n); for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b; ll ans = 0; for (int i = 1; i <= n; ++i) { int now = b[a[i]]; if (now < y) { int l = max(x - now, 0), r = y - now; int posl = lower_bound(b + 1, b + 1 + n, l) - b; int posr = upper_bound(b + 1, b + 1 + n, r) - b - 1; if (posr >= posl) ans += query(posr) - query(posl - 1); } add(a[i], 1); } print(ans); }