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);
}

京公网安备 11010502036488号