10.5 考试总结
T1 考试
有 \(n\) 个人来参加考试，每个人有一个分数 \(a_i\) ，老师不想让任意两个人分数相同，所以只会给同学加分，问你同学的分数总和最少是多少。
这道题做法有很多，考试的时候机房也有很多人切了。
我当时的做法就是先对每个人的分数离散化一下，开个桶存每个分数出现的次数，如果有一个数多次出现，就往他的后面插数，这到满足所有情况为止。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e5+10;
const int inf = 2147483647;
int n,ans,a[N],b[N],tong[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
signed main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++)
{
b[i] = a[i] = read();
}
sort(b+1,b+n+1);
int num = unique(b+1,b+n+1)-b-1;
for(int i = 1; i <= n; i++)
{
a[i] = lower_bound(b+1,b+num+1,a[i])-b;
tong[a[i]]++;
}
b[num+1] = inf;
int last = 1;
for(int i = 1; i <= num; i++)
{
for(int j = b[i]; j <= b[i+1]-1; j++)
{
while(tong[last] == 0 && last <= i) last++;
if(last > i) break;
tong[last]--;
ans += j;
}
}
printf("%lld\n",ans);
// fclose(stdin); fclose(stdout);
return 0;
}
T2 游戏
一个坐标抽上有 \(n\) 个石子，（\(n\) 为偶数），Alice 和 Bob 两个人轮流取石子,Alice 先取，Alice想让最后剩下的棋子之间距离尽可能的小，
Bob 想让这两个棋子的距离尽可能·的大，问你最后两个棋子的距离可能是多少。
一道人类智慧题。
假设剩下的两枚棋子为 \(x,y\) 那么 Alice会一直取 \(x,y\) 之外的棋子，但 Bob 后手，处于被动状态，他只能取中间的棋子。
所以到最后剩下的两枚棋子之间会相差 \({n\over 2 }-1\) 个旗子。
又因为 Alice 占据主动权，所以他可以在第一次任选留下的两枚棋子使这两个棋子间的距离尽可能的小，所以最后我们要求的是 \(min(a[x+{n\over 2}] - a[x])\)
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e5+10;
int n,ans,a[N];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int main()
{
// freopen("game.in","r",stdin);
// freopen("game.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
sort(a+1,a+n+1);
int ans = 1e10;
for(int i = 1; i <= n/2; i++)
{
ans = min(ans,a[i+n/2] - a[i]);
}
printf("%d\n",ans);
fclose(stdin); fclose(stdout);
return 0;
}
T3 方差
一个 \(n\) 的序列他的平均数 \(x\) 为 \(\displaystyle\sum a_i \over n\)，方差 就为 \(\displaystyle\sum (a_i - x) ^ 2\over n\) ,现在想让你求出 \(A\) 的所有非空子集的方差对 \(1e9+7\) 取模的结果。
对于 30% 的数据 \(n\leq 20\), 对于 100% 的数据 \(n\leq 10^6\)
考试的时候，这打了第一档的暴力，状压一下水了 \(30\) 分。
正解是个颓柿子的 \(O(n)\) 做法。
啥也不说先颓柿子。
先化简一下分母。
\[\displaystyle\sum（a_i - x) ^ 2 = \sum {a_i}^2 - \sum{a_i} \times x + n\times x^2 = \sum {a_i}^2 -2\times \sum a_i \times x +{{{(\sum a_i})^2} \over n} \]再把 \(x\) 拆成 \(\displaystyle\sum a_i \over n\) 变为
\(\sum{a_i^2} - 2 \times {(\sum a_i)^2 \over n} + {(\sum a_i) ^ 2 \over n}\)
化简之后可得：
\(\sum a_i ^ 2 - {(\sum a_i)^2 \over n}\)
再把分母弄上去变成 \({\sum a_i ^ 2 \over n} - {(\sum a_i)^2 \over n^2}\)
我们从大到小枚举一下 \(n\)
上面的柿子就可以写成：
\(\displaystyle\sum_{k=1}^{n} {1\over k} \times C_{n-1}^{k-1} \times \sum_{i=1}^{n} a_i ^ 2\)
解释一下，我们 \(a_i\) 这个数对答案的贡献，相当于我们确定了 \(a_i\) 这个数一定要选，剩下的 \(k-1\) 个数随便选即 \(C_{n-1}^{k-1}\) ，也就是说 \(a_i ^ 2\) 这个数会出现在 \(C_{n-1}^{k-1}\) 个子集
中被算到。
后面那坨也一样：
\(\displaystyle\sum_{k=1}^{n} {1\over k^2} \times C_{n-1}^{k-1} \times \sum_{i=1}^{n} a_i \times a_i\)
\(\displaystyle\sum_{k=1}^{n} {1\over k^2} \times C_{n-2}^{k-2} \rtimes \sum_{i=1}^{n} \sum_{j=1, i\neq j} ^{n} a_i \times a_j\)
这个就是考虑了 \(i\) 和 \(j\) 相等的情况。
令 \(\displaystyle\ sum1 = \sum_{i=1}^{n} a_i \times a_i\)
那么 \(\displaystyle sum2 =\sum_{i=1}^{n}\sum_{j=1}^{n} a_i \times a_j = (\sum_{i=1}^{n} a_i) ^2 - \sum_{i=1}^{n} a_i\times a_i\)
\(sum1,sum2\) 可以预处理出来，剩下的就可以 \(O(n)\) 来求了。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 5, p = 1e9 + 7;
int n,a[N],ans1,ans2,sum1,sum2,sum3,jz[N];
inline int read()
{
int s = 0, w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
void YYCH() {
jz[0] = 1;
for(int i = 1; i <= N-5; i++) jz[i] = jz[i - 1] * i % p;
}
int ksm(int a,int b)
{
int res = 1;
for(; b; b >>= 1)
{
if(b & 1) res = res * a % p;
a = a * a % p;
}
return res;
}
int C(int n, int m) {
if (n < m) return 0;
return jz[n] * ksm(jz[m],p-2) % p * ksm(jz[n-m],p-2) % p;
}
signed main() {
n = read(); YYCH();
for (int i = 1; i <= n; i++) a[i] = read();
for (int i = 1; i <= n; i++)
{
sum1 = (sum1 + a[i] * a[i]) % p;
sum2 = (sum2 + a[i]) % p;
}
sum3 = (sum2 * sum2 % p - sum1 + p) % p;
for (int k = 1; k <= n; k++) {
ans1 = (ans1 + ksm(k,p-2) * C(n - 1, k - 1) % p * sum1 % p) % p;
ans2 = (ans2 + ksm(k * k % p,p-2) * C(n - 1, k - 1) % p * sum1 % p) % p;
if (k != 1)
{
ans2 = (ans2 + ksm((k * k % p),p-2) * C(n - 2, k - 2) % p * sum3 % p) % p;
}
}
printf("%lld",(ans1 - ans2 + p) % p);
fclose(stdin); fclose(stdout);
return 0;
}