题目限制一览
| 题目 |
时间限制 |
空间限制 |
| 1. array |
1000 MS |
128 MB |
| 2. bus |
2000 MS |
128 MB |
| 3. team |
3000 MS |
256 MB |
1. 逆序数对列（array.cpp）
Description
对于一个数列{ai}，如果有iaj，那么我们称ai与aj为一对逆序对数。若对于任意一个由1~n自然数组成的
数列，可以很容易求出有多少个逆序对数。那么逆序对数为k的这样自然数数列到底有多少个？
第一行为两个整数n，k。
Output
写入一个整数，表示符合条件的数列个数，由于这个数可能很大，你只需输出该数对10000求余数后的结果。
Sample Output
Hint
样例说明：
下列3个数列逆序对数都为1；分别是1 2 4 3 ；1 3 2 4 ；2 1 3 4；
100%的数据 n<=1000，k<=1000
分析
- 正统解法
设 $f[i][j]$ 表示 $1\rightarrow i$ 的排列中逆序对数为 $j$ 个的方案数
那么一些边界的情况就可以手算出来了，例如 $f[i][0]=1$，$f[i][1]=i-1$
接下来考虑怎么通过这个式子递推，可以考虑在已经形成的 $i-1$ 个排列中插入当前的数 $i$，这会导致增加一些逆序对数
设 $k$ 为增加的逆序对数，那么 $k\in[0,\;min(j,i-1)]$，即：$f[i][j]=\sum_{k=0}^{min(i-1,j)}f[i-1][j-k]$
再做个变形，$f[i][j]=\sum_{k=max(0,j-i+1)}^jf[i-1][k]$ ，到这一步递推的话，时间复杂度 $O(nk^2)$ ，有超时风险
但是我们发现 $k$ 是从 0 开始循环的，当 $i,j$ 固定时，$k$ 的区间 $[max(0,j-i+1),\;j]$ 也固定了，所以我们可以额外维护前缀和来快速的计算
- 神奇乱搞解法
考试的时候想出来的神奇乱搞解法，对于数据较小的时候，可以直接搜索，然后设 $f[i][j]$ 意义同上，观察表格：
| $f[3][0\rightarrow3]$ |
1 |
2 |
2 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
| $f[4][0\rightarrow6]$ |
1 |
3 |
5 |
6 |
5 |
1 |
|
|
|
|
|
|
|
|
|
|
| $f[5][0\rightarrow10]$ |
1 |
4 |
9 |
15 |
20 |
22 |
20 |
15 |
9 |
4 |
1 |
|
|
|
|
|
| $f[6][0\rightarrow15]$ |
1 |
5 |
14 |
29 |
49 |
71 |
90 |
101 |
101 |
90 |
71 |
49 |
29 |
14 |
5 |
1 |
后面数据太多就不放了，总之可以发现一个规律：
- 当 $j<i$ 时，$f[i][j]=f[i-1][j]+f[i][j-1]$
- 当 $i\leq j \leq \frac{i(i-1)}{4}$ 时，$f[i][j]=f[i-1][j]+f[i][j-1]-x$
- 当 $\frac{i(i-1)}{4} \leq j \leq \frac{i(i-1)}{2}$ 时，$f[i][j]=f[i][\frac{i(i-1)}{2}-j]$
由于 $ 1 \rightarrow i$ 的全排列最多有 $\frac{i(i-1)}{2}$ 对逆序对，所以 $j_{max}=\frac{i(i-1)}{2}$ ，接下来考虑 $x$ 的问题
可以发现，$f[i][j]$ 从 $j=i$ 开始减去的数，恰好是 $f[i-1]$ 的一行从 $j’=0$ 开始的项，随着 $j$ 往后移 $j’$ 也往后移动
于是这样一个神奇的递推式就写好了，时间复杂度 $ O(nk)$
Codes
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 1005
#define lowbit(x) (x&-x)
using namespace std;
typedef long long ll;
const ll mod=10000;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
ll f[maxn][maxn];
int n;int k;
inline void init(){
for(int i=1;i<=n;i++) f[i][0]=1,f[i][1]=i-1;
f[3][2]=2;f[3][3]=1;
for(int i=4;i<=n;i++){
for(int j=2;j<i;j++) f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1])%mod;
int sub=0,lim2=(i*(i-1))>>2,lim1=(i*(i-1))>>1;
for(int j=i;j<=lim2 && j<=k;j++,sub++){
f[i][j]=(f[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][sub])%mod;
while(f[i][j]<0) f[i][j]+=mod;f[i][j]%=mod;
}
for(int j=lim2+1;j<=lim1 && j<=k;j++) f[i][j]=f[i][lim1-j];
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
#endif
fcin(n);fcin(k);
init();printf("%lld",f[n][k]);
return 0;
}
|
{:. copyable}
2. 公交线路（bus.cpp）
Description
某城市的街道形成了一个棋盘网络 – 他们要么是北南走向要么就是西东走向.北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m).
该城市里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.
第一行一个数字 T 表示数据组数；
对于每组数据，
第一行两个数字 N,Q 分别表示 特殊位置数量和询问次数。
接下来 N 行，每行两个数字 Xi,Yi 表示特殊位置坐标；
接下来 Q 行，每行两个数字 S,T 表示询问起点坐标。
Output
一个数表示最多能接到的乘客数量.
1
2
3
4
5
6
7
8
9
10
11
12
| 8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
|
Sample Output
Hint
本题共 5 个测试点，每个测试点 20 分。
对于 20% 的数据，T=1,1≤N,Q≤5000,1≤S,T,Xi,Yi≤1000
对于 40% 的数据，所有数据中 NQ 的总和不超过 5\10^7
对于另外 20% 的数据，T=1,1≤S,T,Xi,Yi≤1000
对于 100% 的数据，N 的总和和 Q 的总和均不超过 10^6 ，1≤S,T,Xi,Yi≤10^9
分析
考试时看到这个题，觉得很像以前做过的二维偏序问题，因为每个车站结点 $(x,\;y)$ 只能由 $(x’,\;y’)(x;\leq x,\;y’\leq y)$ 出发的公交车接客，所以可以用数据结构维护 $(x,\;y)$ 为右下角的矩形中的最大值
于是考场上 45min 敲代码+调试二维线段树结果 build 花了 1.8s+??? 怀疑人生
其实这题只需对$y$ 开一维线段树就可以轻松过了，因为 $x$ 轴的顺序可以直接一遍排序解决。。。
Codes
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 1000005
#define mid ((L+R)>>1)
using namespace std;
template<typename t>inline void fcin(t &x){
int sign=1; x=0; char op=getchar();
while(op<'0'||op>'9'){if(op=='-') sign=-1;op=getchar();}
while(op>='0'&&op<='9'){x=x*10+(op-48);op=getchar();}
x*=sign;
}
struct node{
int x,y,w;
bool operator <(const node &obj)const{
if(x!=obj.x) return x<obj.x;
return y<obj.y;
}
}d[maxn],dat[maxn];
int f[maxn],c[maxn];
int n,m,k;
struct st{
st *lc,*rc;
int val;
st():lc(0x0),rc(0x0),val(0){}
inline void pushup(){
val=max(lc->val,rc->val);
}
void updata(int L,int R,int x,int d){
if(L==R){
val=max(val,d);return;
}
if(x<=mid) lc->updata(L,mid,x,d);
else rc->updata(mid+1,R,x,d);
pushup();
}
int stmax(int L,int R,int x,int y){
if(x<=L && R<=y) return val;
int ans=0;
if(x<=mid) ans=max(ans,lc->stmax(L,mid,x,y));
if(y>mid) ans=max(ans,rc->stmax(mid+1,R,x,y));
return ans;
}
};
void build(st* &p,int L,int R){
p=new st();
if(L==R){
p->val=0;return;
}
build(p->lc,L,mid);
build(p->rc,mid+1,R);
p->pushup();
}
int maxDx,maxDy;
void discret(){
int ed;
for(int i=1;i<=k;i++) c[i]=d[i].x;
sort(c+1,c+k+1);
ed=unique(c+1,c+k+1)-(c+1);
for(int i=1;i<=k;i++)
dat[i].x=lower_bound(c+1,c+ed+1,d[i].x)-c,
maxDx=max(maxDx,dat[i].x);
for(int i=1;i<=k;i++) c[i]=d[i].y;
sort(c+1,c+k+1);
ed=unique(c+1,c+k+1)-(c+1);
for(int i=1;i<=k;i++)
dat[i].y=lower_bound(c+1,c+ed+1,d[i].y)-c,
maxDy=max(maxDy,dat[i].y);
}
int solve_40(){
sort(d+1,d+k+1);
for(int i=1;i<=k;i++) f[i]=d[i].w;
int ans=0;
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
if(i==j) continue;
if(d[j].x<=d[i].x && d[j].y<=d[i].y)
f[i]=max(f[i],f[j]+d[i].w);
}
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}
st *root;
int main(){
#ifndef ONLINE_JUDGE
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
#endif
fcin(n);fcin(m);fcin(k);
for(int i=1;i<=k;i++){
fcin(d[i].x);
fcin(d[i].y);
fcin(d[i].w);
dat[i].w=d[i].w;
}
discret();
n=maxDx;m=maxDy;
build(root,1,m);
sort(dat+1,dat+k+1);
int ans=0,cur=0;
for(int i=1;i<=k;i++){
cur=root->stmax(1,m,1,dat[i].y);
ans=max(ans,cur+dat[i].w);
root->updata(1,m,dat[i].y,cur+dat[i].w);
}
printf("%d",ans);
return 0;
}
|
3. 最佳团体（team.cpp）
Description
茜茜的舞蹈团队一共有N名候选人，这些候选人从1到N编号。方便起见，茜茜的编号是0号。每个候选人都由一位编号比他小的候选人Ri推荐。如果Ri=0则说明这个候选人是茜茜自己看上的。为了保证团队的和谐，茜茜需要保证，如果招募了候选人i，那么候选人Ri也一定需要在团队中。当然了，茜茜自己总是在团队里的。每一个候选人都有一个能力值Pi，也有一个招募费用Si。茜茜希望招募K个候选人（茜茜自己不算），组成一个性价比最高的团队。也就是，这K个被茜茜选择的候选人的总能力值与总招募总费用的比值最大。
输入一行包含两个正整数K和N。
接下来N行，其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用，战斗值和推荐人编号。
Output
输出一行一个实数，表示最佳比值。答案保留三位小数。
Sample Output
Hint
对于100%的数据满足 $1\leq K\leq N \leq 2500,\;0\leq S_i,P_i\leq 10^4,\;0\leq R_i\leq i$
分析
这是一道 $0/1$ 分数规划的题目，但是由于我根本没学过导致只能写爆搜爆0
借着这个题来回顾一下 $0/1$ 分数规划的解题思路吧
首先，题目要求的是一个总战斗力和总费用的比值最大值，设比值为 $k$，战斗力为 $v[i]$，费用为 $w[i]$
那么 $k{max}=\frac{\sum v[i]}{\sum w[i]}$，把这个分式化成整式，得到：$k{max}\sum w[i]=\sum v[i]$ ，移项得到 $\sum v[i]-k_{max}\sum w[i]\geq 0$
那么我们就可以二分 $k_{max}$，然后更新 $v$ 数组，然后树上 DP 看能否满足结果 $\geq 0$
设 $f[i][j]$ 表示以 $i$ 为根的子树里面，选择 $j$ 个得到的最大 $v$ 值（$v$ 值已经减去 $k_{max}w[i]$），对于每个推荐人 $R[i]$ ，将这个推荐人 $R[i]$ 与他推荐的所有人连一条边，$R[i]$ 为父结点，$i$ 为儿子结点，就能符合题目选择的要求了
对于茜茜自己，根据题意设为 $0$ 号结点，由于最终茜茜自己也在团体里面，所以答案为 $f[0][k+1]$
这个 DP 的转移方程也很好写：$f[i][j]=max(f[i][j],\;f[i][k]+f[s][j-k])\;(s\in son[i])$
然后是实数域上的二分精度问题，事实上这个题的树上背包做法是 $O(nk^2)$ 时间复杂度（正解是 DFS 序不想再写了），所以注意控制精度问题，实测 $1e-4$ 足矣，平时使用的 $1e-8$ 甚至 $1e-10$ 都有可能 TLE
Codes
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
| #include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <stack>
#define maxn 2505
#define maxm maxn<<1
#define INF 1e-4
#define mid ((L+R)/2.0)
using namespace std;
int to[maxm],nxt[maxm],head[maxn];
double cost[maxn];
double v[maxn],src[maxn];
int n,k,tot;
double f[maxn][maxn];
int siz[maxn];
double d[maxn];
inline void Eadd(int u,int v){
to[++tot]=v;nxt[tot]=head[u];
head[u]=tot;
}
bool check(int u,int pre){
siz[u]=1; f[u][0]=0.0; f[u][1]=v[u];
for(int i=head[u];i;i=nxt[i]){
if(to[i]==pre) continue;
check(to[i],u);
for(int j=1;j<=siz[u]+siz[to[i]];j++) d[j]=-2147483647.0;
for(int j=1;j<=siz[u];j++)
for(int p=0;p<=siz[to[i]];p++) d[j+p]=max(d[j+p],f[u][j]+f[to[i]][p]);
siz[u]+=siz[to[i]];
for(int j=1;j<=siz[u];j++) f[u][j]=d[j];
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("team.in","r",stdin);
freopen("team.out","w",stdout);
#endif
scanf("%d%d",&k,&n);int x;
for(int i=1;i<=n;i++){
scanf("%lf%lf",&cost[i],&src[i]);
scanf("%d",&x);
Eadd(x,i);Eadd(i,x);
}
double L=0.0,R=10000.0;
while(R-L>=INF){
for(int i=1;i<=n;i++)
v[i]=src[i]-mid*cost[i];
memset(f,-0x3f,sizeof(f));
check(0,0);
if(f[0][k+1]>0) L=mid;
else R=mid;
}
printf("%.3lf",L);
return 0;
}
|
