题目限制一览

题目 时间限制 空间限制
1. magician $1000$ MS $128$ MB
2. seq $1000$ MS $128$ MB
3. show $1000$ MS $128$ MB

1. 黑魔法师之门（magician.cpp）

Description

经过了 16 个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与 Violet 星球的战争中，由于 Z 副官的愚蠢，地球的领袖 applepi 被邪恶的黑魔法师 Vani 囚禁在了 Violet 星球。为了重启 Nescafé这一宏伟的科技工程，人类派出了一支由 HQX 1人组成的精英队伍，穿越时空隧道，去往 Violet 星球拯救领袖 applepi。

applepi 被囚禁的地点只有一扇门，当地人称它为“黑魔法师之门”。这扇门上画着一张无向无权图，而打开这扇门的密码就是图中每个点的度数大于零且都是偶数的子图的个数 对 1000000009 取模的值。此处子图 (V, E) 定义为：点集 V和边集 E 都是原图的任意子集， 其中 E 中的边的端点都在 V中。 但是 Vani 认为这样的密码过于简单，因此门上的图是动态的。起初图中只有 N 个顶点 而没有边。Vani 建造的门控系统共操作 M 次，每次往图中添加一条边。你必须在每次操作 后都填写正确的密码，才能够打开黑魔法师的牢狱，去拯救伟大的领袖 applepi。

Input

第一行包含两个整数 N 和 M。 接下来 M 行，每行两个整数 A和 B，代表门控系统添加了一条无向边 (A, B)。

Output

输出一共 M 行，表示每次操作后的密码。

Sample Input

1
2
3
4
5
6
7
8
9
4 8
3 1
3 2
2 1
2 1
1 3
1 4
2 4
2 3

Sample Output

1
2
3
4
5
6
7
8
0 
0
1 
3
7
7
15
31

Hint

第三次添加之后，存在一个满足条件的子图 {1, 2, 3}（其中 1, 2, 3 是数据中边的标号）。

第四次添加之后，存在三个子图 {1, 2, 3}，{1, 2, 4}，{3, 4}。

【数据范围】

对于 30% 的数据，N, M≤10。 对于 100% 的数据，N≤200000，M≤300000。

分析

考试时一看到这个题，脑子里各种统计点的度数还有排列组合搅在一起，感觉过于复杂就果断放弃去做了第三题，考完试才知道这个题是最简单的？

可以发现一个简单环上的所有点都满足度数大于 0 且度数为偶数 2 的条件，所以简单环就可以看作一个符合条件的子图（如果是 2 个点形成简单环则需他们之间连有 2 条无向边）

设某一时刻图中存在 $n$ 个环，则所有符合条件的子图的个数就是从这 $n$ 个环中选，每个环都有选和不选两种状态，又因为不能一个环都不选所以 $ans=2^n-1$

由于题目不断加边的操作，简单环的个数明显是增加或者不变的，用并查集维护点的集合关系，如果要加边的两个点属于同一个集合就环数+1，否则把他们俩合并到一个集合就完了

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 200001
#define mod 1000000009
using namespace std;
typedef long long ll;
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;
}
int f[maxn];int n,m;
int Sfind(int x){
	if(f[x]==x) return x;
	else return f[x]=Sfind(f[x]);
}
ll ans=1;
int main(){
	#ifndef ONLINE_JUDGE
	freopen("magician.in","r",stdin);
	freopen("magician.out","w",stdout);
	#endif
	fcin(n);fcin(m);
	for(int i=1;i<=n;i++) f[i]=i;
	int x,y;int fx,fy;
	for(int i=1;i<=m;i++){
		fcin(x);fcin(y);
		fx=Sfind(x);fy=Sfind(y);
		if(fx==fy) ans=(ans<<1)%mod;
		else f[fx]=fy;
		printf("%lld\n",ans-1);
	}
	return 0;
}

2. 检测序列（seq.cpp）

Description

有M（1≤M≤50,000）个序列（称作检测序列）， 每个序列有mi个不同的数字，且每个数字都属于[1,N]，其中1≤N≤10^5。每个序列描述了数字间的相对位置关系（谁在前谁在后），比如序列2、5、1 描述了2在5的前面，5在1的前面。

求一个字典序最小的1…N的排列，且尽可能多的满足前若干个检测序列描述的相对位置关系。

Input

第一行包含N和M。接下来的M行，每行描述了一个检测序列：第一个数是mi，紧跟同一行后面是mi个整数，表示一个检测序列。所有mi的和至多为200,000。

Output

如题目描述，输出N个空格分隔的整数，给出一个1…N的排列。

Sample Input

1
2
3
4
4 3
3 1 2 3
2 4 2
3 3 4 1

Sample Output

1
1 4 2 3

Hint

无

分析

做法：二分需要满足前 $mid$ 个检测序列，连有向边跑拓扑排序

如题目所说，只需要尽量满足前若干个检测序列，可以二分答案 $mid$ 表示需要满足前 $mid$ 个检测序列，按照序列的数字从前往后连有向边，然后跑拓扑排序，若图中存在环则说明这 $mid$ 个检测序列不能同时满足，否则 $mid$ 可以更大

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
#pragma GCC optimize(3)
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define maxn 100001
#define maxm maxn*2
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;
}
int to[maxm],nxt[maxm],head[maxn];
int tot,out_[maxn],ans[maxn];
int n,m,indeg[maxn];
vector<int> mi[50001];
inline void Eadd(int u,int v){
	to[++tot]=v;nxt[tot]=head[u];
	head[u]=tot;
}
bool topp()
{
	int qh;
	priority_queue< int,vector<int>,greater<int> > wait;
	for(int i=1;i<=n;i++) if(indeg[i]==0) wait.push(i);
	while(!wait.empty()){
		qh=wait.top();
		out_[++out_[0]]=qh;
		wait.pop();
		for(int i=head[qh];i;i=nxt[i])
			if(--indeg[to[i]]==0) wait.push(to[i]);
	}
	return out_[0]==n; 
}
bool check(int k){
	vector<int>::iterator iter;
	out_[0]=0;memset(indeg,0,sizeof(indeg));
	memset(head,0,sizeof(head));tot=0;
	for(int i=1;i<=k;i++)
	for(iter=mi[i].begin();iter+1!=mi[i].end();iter++)
		Eadd(*iter,*(iter+1)),indeg[*(iter+1)]++;
	return topp();
}
inline void solve(){
	int L=1,R=m;
	int mid=(L+R)>>1;
	while(L<R){
		mid=(L+R)>>1;
		if(check(mid)) L=mid+1;
		else R=mid;
	}
	out_[0]=0;memset(indeg,0,sizeof(indeg));
	memset(head,0,sizeof(head));tot=0;
	check(mid);
	for(int i=1;i<=out_[0];i++) printf("%d ",out_[i]);
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	#endif
	int x,y;
	fcin(n);fcin(m);
	for(int i=1;i<=m;i++){
		fcin(x);
		for(int j=1;j<=x;j++)
			fcin(y),mi[i].push_back(y); 
	}
	solve();
	return 0;
}

3. 达牛秀（show.cpp）

Description

编号为1…N的奶牛！第i头奶牛重量为wi，才艺水平为ti，两者都是整数。

在到达时，HQX 就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为W（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且

（二）总才艺值与总重量的比值最大的一组获得胜利。

HQX注意到他的所有奶牛的总重量不小于W，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

Input

输入的第一行包含N（1≤N≤250）和W（1≤W≤1000）。下面N行，每行用两个整数wi（1≤wi≤10^6）和ti（1≤ti≤10^3）描述了一头奶牛。

Output

请求出HQX用一组总重量最少为W的奶牛最大可能达到的总才艺值与总重量的比值。如果你的答案是A，输出1000A向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

Sample Input

1
2
3
4
3 15
20 21
10 11
30 31

Sample Output

1
1066

Hint

在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛，但是由于我们需要至少15单位的重量，最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值为(11+21)/(10+20) = 32/30 = 1.0666666…，乘以1000向下取整之后得到1066。

分析

做法一：01分数规划 + 背包 DP

看到“才艺与重量的比值最大”就会想起 01 分数规划的思路，要求 $\sum t[i]\div \sum w[i]$ 的最大值，设答案为 $x$ ，原式变形得 $\sum (t[i]-w[i]\times x)$

二分 $x$ ，带入进行背包 DP 即可，注意实数域上的二分精度问题

做法二：DP

设 $f[i][j]$ 表示考虑了第 $i$ 头牛，当前的总重量为 $j$ 的比值的最大值，转移方程为：

  1. 不选择第 $i+1$ 头奶牛：$f[i+1][j]=max(f[i+1][j],\;f[i][j])$
  2. 选择第 $i+1$ 头奶牛：$f[i+1][j+w[i]]=max(f[i+1][j+w[i],\;x)$

其中 $i\in[1,\;n-1]$，$j\in[0,\;W]$

这个 $x$ 就是选择第 $i+1$ 头奶牛后，新的总才艺值和总重量的比值，由于 $x$ 不能直接由 $f[i][j]$ 得到，需要新设 $s[i][j]$ 表示 $f[i][j]$ 对应的总才艺值， $p[i][j]$ 表示 $f[i][j]$ 对应的总重量，于是：

$f[i+1][j+w[i]]=max(f[i+1][j+w[i]],\;(s[i][j]+t[i+1])\div(p[i][j]+w[i+1])$

$s[i][j]$ 和 $p[i][j]$ 在 $f[i][j]$ 发生变化的时候一起更新，但是注意到 $f[i][j]$ 里面 $j$ 是表示重量的，而对应的 $p[i][j]$ 也是表示重量的，看起来是重复表示了重量，实际上是因为避免 MLE，转移方程的 $j$ 只开到了 $W$(1000) ,而题目中奶牛的重量和可能远大于这个值，在 $j>W$ 时可以把它累积到 $j=W$ 也就是 $f[i][W]$ 来转移，但是要对应真实的重量和，所以新设的 $p[i][j]$ 是用来表示 $f[i][j]$ 对应的实际重量和

边界为 $f[1][w[1]]=t[1]\div w[1]$，最后的答案在 $f[1\to n][W]$ 里面取最大值

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define maxn 251
#define maxs 1001
#define v(x) (x>maxw?maxw:x)
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;
}
int n,maxw;
int t[maxn],w[maxn];
int s[maxn][maxs],p[maxn][maxs];
double f[maxn][maxs];
inline void dp(){
	f[1][v(w[1])]=(double)t[1]/(double)w[1];
	s[1][v(w[1])]=t[1];p[1][v(w[1])]=w[1];
	for(int i=1;i<=n-1;i++)
	for(int j=0;j<=maxw;j++){
		if(f[i][j]>f[i+1][j]){
			f[i+1][j]=f[i][j];
			s[i+1][j]=s[i][j];
			p[i+1][j]=p[i][j];
		}
		if((double)(s[i][j]+t[i+1])/(double)(p[i][j]+w[i+1])>f[i+1][v(p[i][j]+w[i+1])]){
			f[i+1][v(p[i][j]+w[i+1])]=(double)(s[i][j]+t[i+1])/(double)(p[i][j]+w[i+1]);
			s[i+1][v(p[i][j]+w[i+1])]=s[i][j]+t[i+1];
			p[i+1][v(p[i][j]+w[i+1])]=p[i][j]+w[i+1];
		}
	}
	double ans=0.0;
	for(int i=1;i<=n;i++) ans=max(ans,f[i][maxw]);
	ans*=1000.0;
	printf("%lld",(long long)ans); 
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("show.in","r",stdin);
	freopen("show.out","w",stdout);
	#endif
	fcin(n);fcin(maxw);
	for(int i=1;i<=n;i++)
		fcin(w[i]),fcin(t[i]);
	dp();
	return 0;
}