C - Bugged
题意
给(n)个数，找其中的一个子集，使得其和最大，且不是(10)的整数倍。
思路
先对(n)个数求和，
- 如果本身即不被(10)整除，则即为答案。
- 否则，如果本身被(10)整除，则找到这(n)个数中最小的不被(10)整除的数，减去它即为答案。
- 如果不存在这样的数，说明所有的数都被(10)整除，所以答案为(0).
回顾上述过程，可以发现，这个子集的(size)要么是(0)，要么是(n-1)，要么是(n).
解题无关部分
结论
满足条件的子集的(size)要么是(0)，要么是(n-1)，要么是(n)
证明
-
(size=0,n)的情况显然
-
对于其余情况，即(10mid sum_{i=1}^{n}a_i)而(exists a_i,10 mid a_i)时
假设存在一个(size=n-k(kgt 1))的子集，那么(10 mid (sum0=sum_{i=1}^{n-k}a_i)而10mid (sum=sum_{i=1}^{n}a_i))，因而(10 mid sum_{i=n-k+1}^{n}a_i)
因为(kgt 1)，所以(sum_{i=n-k+1}^{n}a_i=sum_{i=n-k+1}^{n-1}a_i+a_n=A+B)，因为(10 mid (A+B))，所以(A,B)中至少存在一个不被(10)整除。
(Case 1.) (10mid A, 10
mid B)
则有(10
mid (sum0+A)=sum_{i=1}^{n-1}a_i)，即为一个(size=n-1)的子集
(Case 2.) (10
mid A, 10mid B)
则有(10
mid (sum0+B)=sum_{i=1}^{n-k}a_i+a_n)，即得到一个(size=n-k+1)的子集，变成原问题的子问题，可在此基础上继续操作直至得到一个(size=n-1)的子集。
(Case 3.) (10
mid A, 10
mid B)
在此条件下，必然有(10
mid (sum0+A)且10
mid (sum0+B))
（否则，如果(10mid (sum0+A))，而又有条件(10
mid B)，因而(10
mid (sum0+A+B)=sum)与题设矛盾；
如果(10mid (sum0+B))同理）
因而，可以做出与(Case. 1)中相同的选择，取(10
mid (sum0+A))这个(size=n-1)的子集，即满足要求。
Code
#include <bits/stdc++.h>
#define maxn 110
using namespace std;
typedef long long LL;
int a[maxn];
int main() {
int n;
scanf("%d", &n);
int sum=0;
for (int i = 0; i < n; ++i) scanf("%d", &a[i]), sum += a[i];
sort(a,a+n);
if (sum % 10) printf("%d
", sum);
else {
int i=0;
for (; i < n; ++i) if (a[i] % 10) break;
if (i == n) puts("0");
else printf("%d
", sum-a[i]);
}
return 0;
}
D - Widespread
题意
有(n)个小怪，每个小怪都有血量(h_i). 攻击某一个小怪，可对它造成(A)的伤害，对其他所有小怪造成(B)的伤害((Agt B))。问最少攻击多少次能消灭所有小怪。
思路
假设一共攻击了(k)次，攻击过(p)个小怪（攻击第(i)个小怪(t_i)次），则有$$k=t_1+t_2+...+t_p$$
对第(i)个小怪造成的伤害为$$(k-t_i)B+t_iA=kB+(A-B)t_i$$显见血越厚需要花费的(t_i)就越多。
因此，可以二分攻击次数(k)，(check)的标准是(sum_{}t_i)是否小于等于(k).
Code
#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
typedef long long LL;
int n, A, B;
int a[maxn];
bool check(LL k) {
LL base = k * B, diff = A - B, sum = 0;
for (int i = n-1; i >= 0; --i) {
if (a[i] <= base) continue;
sum += ceil(1.0 * (a[i] - base) / diff);
}
return sum <= k;
}
int main() {
scanf("%d%d%d", &n, &A, &B);
LL ri = 0;
for (int i = 0; i < n; ++i) scanf("%d", &a[i]), ri += a[i]/B+1;
sort(a, a+n);
LL le = 1;
while (ri > le) {
LL mid = le + ri >> 1;
if (check(mid)) ri = mid;
else le = mid + 1;
}
printf("%lld
", le);
return 0;
}
E - Meaningful Mean
题意
给定一个数组(a[ ])与一个数字(k)，问有多少对((l,r))满足$$frac{sum_{i=l}^{r}a[i]}{r-l+1}geq k$$即问有多少子段的平均数(geq k)
思路
转化
将数组中每一个数都减去(k)，则问题转化为有多少段数的和(geq 0)
树状数组
处理出前缀和，再用树状数组进行统计（思想类似逆序对个数）。
(sum[l,r] = Sum[r] - Sum[l-1])，因此前缀和应包括(0)
Code
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
typedef long long LL;
LL c[maxn], a[maxn], b[maxn];
int n, k, tot;
int lowbit(int x) { return x & (-x); }
LL query(int x) { LL ret=0; while (x) ret += c[x], x -= lowbit(x); return ret; }
void add(int x) { while (x <= tot) ++c[x], x += lowbit(x); }
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]), a[i] -= k;
for (int i = 1; i <= n; ++i) b[i] = (a[i] += a[i-1]);
b[n+1] = 0;
sort(b+1, b+2+n);
tot = unique(b+1, b+2+n) - (b+1);
LL ans=0;
a[0] = 0;
for (int i = 0; i <= n; ++i) {
int p = lower_bound(b+1, b+1+tot, a[i]) - b;
ans += query(p);
add(p);
}
printf("%lld
", ans);
return 0;
}