CQTSC2009 Summary

March 4, 2009 — gnarlycow

中位数(median)
简单统计题

?View Code CPP
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

#include <cstdio>
 
const int BASE=100000;
int d[100001],f[100001],h[200002];
 
int main()
{
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	int n,b,s;
	scanf("%d%d",&n,&b);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",d+i);
		if(d[i]==b) s=i;
	}
	h[BASE]=1;
	for(int i=s-1;i;--i)
	{
		if(d[i]>d[s]) f[i]=f[i+1]+1;
		else f[i]=f[i+1]-1;
		++h[BASE+f[i]];
	}
	int ans=h[BASE];
	for(int i=s+1;i<=n;++i)
	{
		if(d[i]>d[s]) f[i]=f[i-1]+1;
		else f[i]=f[i-1]-1;
		ans+=h[BASE-f[i]];
	}
	printf("%d\n",ans);
	return 0;
}

跳舞(dance)
二分答案+网络流
经典的拆点构图模型，这里不加说明地直接给出构图方法：将每个人都拆成两个点，分别表示喜欢和不喜欢。从源向每个男喜欢连一条边，容量为二分枚举的曲子数。每个男孩从喜欢向不喜欢连一条容量为k的边，每个女孩从不喜欢向喜欢连一条容量为k的边。从每个女喜欢向汇连一条为容量为二分枚举的曲子数的边。对于每对相互喜欢的男女，从男喜欢向女喜欢连一条为容量为1的边；对于相互不喜欢的男女，从男不喜欢向女不喜欢连一条为容量为1的边。如果最大流恰为此时枚举的曲子数的n倍则可行。

?View Code CPP
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

#include <iostream>
 
using namespace std;
 
const int MAXNODE=444,MAXEDGE=30000;
struct network
{
	int S,T,len;
	int v[MAXEDGE],capacity[MAXEDGE],flow[MAXEDGE],head[MAXNODE],next[MAXEDGE];
	void initialize();
	void insertEdge(int,int,int);
	bool makeLevelGraph();
	bool changeFlow(int,int);
	void makeMaxFlow();
	int getMaxFlow();
} g;
int q[MAXNODE],h[MAXNODE],cur[MAXNODE],mark[MAXNODE];
bool used[MAXNODE],flag[MAXNODE];
char fancy[55][55];
 
void network::initialize()
{
	len=0;
	memset(head,0,sizeof(head));
	memset(flow,0,sizeof(flow));
	next[0]=0;
}
 
void network::insertEdge(int a,int b,int c)
{
	len++;
	v[len]=b;
	capacity[len]=c;
	next[len]=head[a];
	head[a]=len;
	len++;
	v[len]=a;
	capacity[len]=0;
	next[len]=head[b];
	head[b]=len;
}
 
bool network::makeLevelGraph()
{
	memset(h,0,sizeof(h));
	memset(used,false,sizeof(used));
	used[S]=true;
	q[0]=S;
	for(int headQ=0,tailQ=1;headQ<tailQ;++headQ)
		for(int i=head[q[headQ]];i;i=next[i])
			if(capacity[i]>flow[i]&&!used[v[i]])
			{
				h[v[i]]=h[q[headQ]]+1;
				if(v[i]==T) return true;
				used[v[i]]=true;
				q[tailQ++]=v[i];
			}
	return false;
}
 
inline bool network::changeFlow(int k,int w)
{
	if(k&1) flow[k+1]-=w;
	else flow[k-1]-=w;
	return (flow[k]+=w)==capacity[k];
}
 
void network::makeMaxFlow()
{
	while(makeLevelGraph())
	{
		memcpy(cur,head,sizeof(head));
		memset(used,false,sizeof(used));
		q[0]=cur[S]+1;
		for(int num=0;!used[S];)
			if(v[q[num]]==T)
			{
				int delta=INT_MAX;
				for(int i=1;i<=num;i++) delta<?=capacity[q[i]]-flow[q[i]];
				for(int i=num;i;--i)
					if(changeFlow(q[i],delta))
						num=i-1;
			}
			else
			{
				int &i=cur[v[q[num]]];
				for(;i;i=next[i])
					if(!used[v[i]]&&h[v[i]]==h[v[q[num]]]+1&&capacity[i]>flow[i])
					{
						q[++num]=i;
						break;
					}
				if(!i) used[v[q[num--]]]=true;
			}
	}
}
 
int network::getMaxFlow()
{
	makeMaxFlow();
	int res=0;
	for(int i=head[S];i;i=next[i]) res+=flow[i];
	return res;
}
 
int main()
{
	freopen("dance.in","r",stdin);
	freopen("dance.out","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("\n%s",&fancy[i][1]);
	int L=0,R=n+1;
	while(L+1<R)
	{
		int M=(L+R)>>1;
		g.initialize();
		g.S=0;
		g.T=4*n+1;
		for(int i=1;i<=n;++i)
		{
			g.insertEdge(g.S,i,M);
			g.insertEdge(3*n+i,g.T,M);
			g.insertEdge(i,n+i,k);
			g.insertEdge(2*n+i,3*n+i,k);
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
				if(fancy[i][j]=='Y') g.insertEdge(i,3*n+j,1);
				else g.insertEdge(n+i,2*n+j,1);
		if(g.getMaxFlow()==M*n) L=M;
		else R=M;
	}
	printf("%d\n",L);
	return 0;
}
Posted in 省选. Tags: , , . No Comments »