动态规划 | 线段树 | 0/1分数规划 | 图论 | 201901031考试:解题报告

题目限制一览

题目 时间限制 空间限制
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的这样自然数数列到底有多少个?

Input

第一行为两个整数n,k。

Output

写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对10000求余数后的结果。

Sample Input

4 1

Sample Output

3

Hint

样例说明:

下列3个数列逆序对数都为1;分别是1 2 4 3 ;1 3 2 4 ;2 1 3 4;

100%的数据 n<=1000,k<=1000

分析

  1. 正统解法

设 $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]$ 也固定了,所以我们可以额外维护前缀和来快速的计算

  1. 神奇乱搞解法

考试的时候想出来的神奇乱搞解法,对于数据较小的时候,可以直接搜索,然后设 $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

后面数据太多就不放了,总之可以发现一个规律:

  1. 当 $j<i$ 时,$f[i][j]=f[i-1][j]+f[i][j-1]$
  2. 当 $i\leq j \leq \frac{i(i-1)}{4}$ 时,$f[i][j]=f[i-1][j]+f[i][j-1]-x$
  3. 当 $\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

#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;
}

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

一个数表示最多能接到的乘客数量.

Sample Input

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

11

Hint

本题共 5 个测试点,每个测试点 20 分。

对于 20% 的数据,T=1,1≤N,Q≤5000,1≤S,T,Xi,Yi≤1000

对于 40% 的数据,所有数据中 N*Q 的总和不超过 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

#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;
	}
	//if(k<=10000) return solve_40();
	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个被茜茜选择的候选人的总能力值与总招募总费用的比值最大。

Input

输入一行包含两个正整数K和N。

接下来N行,其中第i行包含3个整数Si,Pi,Ri表示候选人i的招募费用,战斗值和推荐人编号。

Output

输出一行一个实数,表示最佳比值。答案保留三位小数。

Sample Input

1 2
1000 1 0
1 1000 1

Sample Output

0.001

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

#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;
}