题目大意
$n$人参加信息学竞赛，共有$m$道题。现在比赛已经结束，评分正在进行中，对于已经结束评测的试题，已知每名考生这道题的答案是否正确，对于未结束评测的试题，只知道每名考生是否提交答案。每个题分数固定，提交正确的答案的考生可以得到这一题的分数，分数越高排名越靠前，分数相同编号小的考生排名靠前。这$n$人中，排名最靠前的$s$人将获得入选代表队的资格，而这$s$个中将通过最终的科学委员会面试选出其中的$t$ 个人。输入当前的评测信息（包括是否提交，以及已经评测部分的是否正确）以及每道题的分值，问最终的$t$人代表队共有多少种组队的可能。
题目分析
WC2012讲的一道原题啊~
这道题要是直接想比较复杂，不如换个思路。
计算出每个人可能的最高成绩和最低成绩，按照可能最高成绩排序。
我们设$i$是$t$人代表队中的最后一名。
为什么要按照可能的最高成绩排序？这样就可以保证在$i$前面的人都有可能进入$s$人代表队。
设在$i$前面的人有$tot$个的最低成绩都比$i$高（这$tot$个人必在$s$中）
如图，当$i$为$t$人代表队最后一名，共有$C_{tot}^xC_{i-1-tot}^{t-x-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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=55;
int n,m;
LL a[maxn],C[maxn][maxn],s,t,ans=0;
struct Point {
LL min,max;
int pos;
bool operator < (const Point& b) const {
return (max>b.max)||(max==b.max&&pos<b.pos);
}
} p[maxn];
int main() {
m=Get_Int();
for(int i=1; i<=m; i++)a[i]=Get_Int();
n=Get_Int();
for(int i=1; i<=n; i++) {
p[i].pos=i;
for(int j=1; j<=m; j++) {
char x=' ';
while(x!='Y'&&x!='N')x=getchar();
if(x=='Y') {
p[i].max+=abs(a[j]);
p[i].min+=max(a[j],0ll);
}
}
}
C[0][0]=1;
for(int i=1; i<=n; i++) {
C[i][0]=C[i][i]=1;
for(int j=1; j<i; j++)C[i][j]=C[i-1][j]+C[i-1][j-1];
}
s=Get_Int();
t=Get_Int();
sort(p+1,p+n+1);
for(int i=1; i<=n; i++) {
LL tot=0;
for(int j=1; j<i; j++)
if(p[j].min>p[i].max||p[j].min==p[i].max&&p[j].pos<p[i].pos)tot++;
for(LL x=max(0ll,max(t+tot-i,tot-s+t)); x<=min(tot,t-1); x++)ans+=C[tot][x]*C[i-tot-1][t-x-1];
}
printf("%lld\n",ans);
return 0;
}
|
