题面：https://codeforces.com/contest/810/problems
A. Straight «A»
题意
给定$n$和$k$，分别表示现有的成绩个数和满分。问现在最少还需要多少个成绩才能使平均分四舍五入后等于满分。
解法
数据范围小，不停的加满分。随便模拟一下就好了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, sum = 0, cnt = 0;
cin >> n >> k;
for(int i = 1; i <= n; i++)
{
int t;
cin >> t;
sum += t;
}
while(2 * sum < (2 * k - 1) * n)
{
sum += k;
n++;
cnt++;
}
return 0;
}
B. Summer sell-off
题意
商店卖商品，知道每天有多少顾客来买和每天的商品个数。店主决定选$f$天sell-out，这一天商品个数会加倍。问怎么选能够卖出最多的商品。
解法
贪心就好了呀。
排个序，按照加倍前后多卖出的商品个数，然后取一取就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
const int maxn = 1e5 + 10;
struct node{
ll l, r;
};
node a[maxn];
bool cmp(const node & pa, const node & pb)
{
ll a = min(2 * pa.l, pa.r) - min(pa.l, pa.r);
ll b = min(2 * pb.l, pb.r) - min(pb.l, pb.r);
return a > b;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll n, f, ans = 0;
cin >> n >> f;
for(int i = 0; i < n; i++)
cin >> a[i].l >> a[i].r;
sort(a, a + n, cmp);
for(int i = 0; i < f; i++)
ans += min(2 * a[i].l, a[i].r);
for(int i = f; i < n; i++)
ans += min(a[i].l, a[i].r);
cout << ans << endl;
return 0;
}
C. Do you want a date?
题意
给定一个$n(n < 3 \cdot 10^5)$个数的集合，设$a$为这个集合的子集,令$F(a)=max|a_i-a_j|(i, j \in a)$。求所有子集的$F$值和。
解法
看到这题，首先会想到是排个序。然后枚举最大和最小的两个数，中间的数可以取或不取算一下排列数再累加。但这样的话复杂度是$n^2$的显然不能通过测评。
所以考虑优化，用前缀和来做。
分别考虑每个加$2^0, 2^1, 2^2…., 2^n-2$的数
比如$2^0$: $a_2-a_1, a_3-a_2,….a_n-a_{n-1}$然后加起来发现是$s_n-s_{n-1}-a_1$
得到结论对于$2^i$为$s_n-s_{i+1}-s_{n-i-1}$
记录一下2的幂取模的结果就好了。
当然还可以找规律开始找规律
考虑5个数的子集
要加的内容为：
- $a_2-a_1, (a_3-a_1)\cdot2, (a_4-a_1) \cdot 2^2, (a_5-a_1) \cdot 2^3$
- $a_3-a_2, (a_4-a_2)\cdot2, (a_5-a_2)\cdot2^2$
- $a_4-a_3, (a_5-a_3)\cdot2$
- $a_5-a_4$
把上面这一堆加起来后会得到：
$F(a) =15a_5+6a_4-6a_4-15a_1\\=(1-16)a_5+(8-2)a_4+(4-4)a_3+(2-8)a_4+(1-15)a_1$
喜闻乐见找规律1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
ll a[maxn], bit[maxn];
ll sum[maxn], ans;
void solve1(int n)
{
for(int i = 1; i <= n; i++)
{
ans += (bit[i - 1] + mod - bit[n - i]) % mod * a[i];
ans %= mod;
}
cout << ans << endl;
}
void solve2(int n)
{
for(int i = 1; i <= n; i++)
{
sum[i] = sum[i - 1] + a[i];
sum[i] %= mod;
}
for(int i = 0; i <= n - 1; i++)
{
ll add = sum[n] + 2 * mod - sum[n - i - 1] - sum[i + 1];
add %= mod;
add *= bit[i];
add %= mod;
ans += add;
ans %= mod;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
bit[0] = 1;
for(int i = 1; i <= n; i++)
bit[i] = bit[i - 1] * 2 % mod;
solve1(n);
//solve2(n);
return 0;
}