Posted 2019-04-16题解29 minutes read (About 4304 words)

ICPC World Finals 2017 题解

在 LOJ 上有翻译题面

一份英文题解

总算搞完了 = =

A. Airport Construction

题意

有一个 $n$ 个顶点的简单多边形，求多边形内部最长线段的长度。

$n\le 200$。

保证相邻两条边不共线。

做法

最长线段一定经过了至少两个顶点，枚举这两个顶点，直接计算这条直线在多边形内部的每个连续段的长度。

具体地，若直线与一条边（不包含端点）相交，则根据方向不同，记交的权值为 $2$ 或 $-2$；若与边的一端点相交，根据方向不同，记权值为 $1$ 或 $-1$。

从多边形外按照顺序枚举每个相交的事件，累加权值如果为 $0$ 则表示当前在多边形外部，否则在内部。

这里涉及到直线求交 = =

假设直线为 $AB$ 和 $CD$，在这里一种比较方便的办法是

\[ k_1\times \overrightarrow{AB}-\overrightarrow{AC}=k_2\times \overrightarrow{CD} \]

由平行，两边叉积为零，可以得到

\[ k_1=\frac{\overrightarrow{AC}\times \overrightarrow{CD}}{\overrightarrow{AB} \times \overrightarrow{CD}} \]

$k_1\times |AB|$ 即 $A$ 到交点的有向距离。

复杂度 $O(n^3\log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 205;
const double eps = 1e-10;
int sgn(long double x){ return x<-eps?-1:(x>eps?1:0);}
struct item{
	long double x, y;
	inline item operator -(const item &r)const{ return (item){x-r.x, y-r.y};}
	inline long double operator ^(const item &r)const{ return x*r.y-y*r.x;}
} p[N];
int n, cnt;
long double ans;
pair<long double,int> f[N];
inline long double dis(item a, item b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline long double dis(item a, item b, item c, item d){ return ((c-a)^(d-c))/((b-a)^(d-c))*dis(a, b);}
int main() {
	scanf("%d", &n);
	for(int i=1; i<=n; ++i) scanf("%Lf%Lf", &p[i].x, &p[i].y);
	for(int a=1; a<=n; ++a) for(int b=a+1; b<=n; ++b){
		item ab=p[b]-p[a];
		cnt=0;
		for(int i=1; i<=n; ++i){
			int sgn1=sgn(ab^(p[i]-p[a])), sgn2=sgn(ab^(p[i%n+1]-p[a]));
			if(sgn1!=sgn2) f[++cnt]=make_pair(dis(p[a], p[b], p[i], p[i%n+1]), sgn(sgn1-sgn2)*(1+(sgn1 && sgn2)));
		}
		sort(f+1, f+cnt+1);
		int now=0;
		long double len=0;
		for(int i=1; i<=cnt; ++i){
			if(now) len+=f[i].first-f[i-1].first;
			else ans=max(ans, len), len=0;
			now+=f[i].second;
		}
		ans=max(ans, len);
	}
	return printf("%.9Lf", ans), 0;
}

B. Get a Clue!

题意

有 $6$ 张写着不同角色的卡， $6$ 张写着不同武器的卡和 $9$ 张写着不同房间的卡。

$4$ 个人玩游戏，三种卡各有一张缺失，$1,2$ 号玩家初始得到 $5$ 张卡，$3,4$ 号玩家得到 $4$ 张。

你是 $1$ 号，你不知道别人手上的卡，你需要确定缺失的三张卡。

游戏进行了 $n$ 轮，从 $1$ 开始，按照 $1 \to 2 \to 3 \to 4 \to 1$ 的顺序轮流发起。

每次发起者提出一种缺失的三张卡的方案，从发起者下一个人开始，按照上述顺序，如果一个人手上存在方案中的卡，那么轮到他时必须提出反对，发起者可以知道这张卡上面的内容，其余人无法知道内容。如果有多张，他可以任意挑一张。

现在给出每轮你能知道的全部信息，求每种卡中是否能确定丢失的是什么，如果可以确定需要输出是什么。

$n\le 50$。

做法

暴力题。

当然也可以有理有据，考虑每个人卡的集合根据已知信息是否合法是独立的（除非两个人的集合冲突）。

处理出每个人的合法集合，暴力子集卷积得到所有可能的缺失方案。

代码

#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 55, M = 1<<16, K = 21;
int n, c1, c2, c3, cnt, cnt1, cnt2, cnt3, id[K], a[N], len[N], pcnt[M];
char c[15], s[N][15];
bool ans[K], f[M], g[M], h[M];
int main() {
	cin>>n, cin.get(), cin.getline(c, 12);
	for(int i=0; i<9; i+=2) id[c[i]-'A']=20;
	for(int i=0; i<21; ++i) if(id[i]<20) id[i]=cnt++;
	for(int i=0; i<n; ++i){
		cin.getline(s[i], 12), len[i]=strlen(s[i]);
		a[i]=(1<<id[s[i][0]-'A'])|(1<<id[s[i][2]-'A'])|(1<<id[s[i][4]-'A']);
	}
	for(int i=1; i<1<<16; ++i){
		pcnt[i]=pcnt[i>>1]+(i&1);
		if(pcnt[i]==5){
			f[i]=1;
			for(int j=0; j<n; ++j){
				int p=4+((81-j)&3)*2;
				if(4<p && p<len[j] && ((s[j][p]=='-' && (i&a[j])) || (s[j][p]=='*' && !(i&a[j])) || (isupper(s[j][p]) && !(i>>id[s[j][p]-'A']&1)))) f[i]=0;
			}
		}
		if(pcnt[i]==4){
			g[i]=h[i]=1;
			for(int j=0; j<n; ++j){
				int p=4+((82-j)&3)*2;
				if(4<p && p<len[j] && ((s[j][p]=='-' && (i&a[j])) || (s[j][p]=='*' && !(i&a[j])) || (isupper(s[j][p]) && !(i>>id[s[j][p]-'A']&1)))) g[i]=0;
				p=4+((83-j)&3)*2;
				if(4<p && p<len[j] && ((s[j][p]=='-' && (i&a[j])) || (s[j][p]=='*' && !(i&a[j])) || (isupper(s[j][p]) && !(i>>id[s[j][p]-'A']&1)))) h[i]=0;
			}
		}
	}
	for(int i=1<<16, j; i--;) if(pcnt[i]==9) for(j=i, f[i]=0; j; j=(j-1)&i) if(f[j] && g[i^j]){ f[i]=1; break;};
	for(int i=1<<16, j; i--;) if(pcnt[i]==13) for(j=i, f[i]=0; j; j=(j-1)&i) if(f[j] && h[i^j]){ f[i]=1; break;};
	for(int i=0; i<6; ++i) for(int j=6; j<12; ++j) for(int k=12; k<21; ++k)
		if(id[i]<20 && id[j]<20 && id[k]<20 && f[(1<<16)-1-(1<<id[i])-(1<<id[j])-(1<<id[k])])
			cnt1+=!ans[i], cnt2+=!ans[j], cnt3+=!ans[k], ans[i]=ans[j]=ans[k]=1, c1=i, c2=j, c3=k;
	printf("%c%c%c", cnt1==1?'A'+c1:'?', cnt2==1?'A'+c2:'?', cnt3==1?'A'+c3:'?');
	return 0;
}

C. Mission Improbable

题意

有一个 $r$ 行 $c$ 列网格，每个格子上堆了若干立方体。

现在要在保证主视图，俯视图，左视图不变的情况下，拿走尽量多的立方体，求一种方案。

即保持每行每列最多的格子堆的立方体高度和每个格子是否存在立方体不变。

注意某一格的高度可以增加。

$r,c\le 100$。

做法

先把所有存在立方体的格子拿到只剩下一个。

接下来要在每行和每列安排一个最大值，尽量使得这些最大值重合。

一个位置可以重合当且仅当其原先存在立方体，且所在行列的最大值相同。

显然是一个二分图匹配问题，考虑到虽然边带权，但是每个联通块内边权相同，因此直接匈牙利即可。

复杂度 $O(rc\times(r+c))$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 102;
int n, m, p[N], a[N], b[N], f[N][N];
bool vis[N];
ll ans;
vector<int> e[N];
bool match(int x){
	for(int i:e[x]) if(!vis[i]){
		vis[i]=1;
		if(!p[i] || match(p[i])) return p[i]=x, 1;
	}
	return 0;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j){
		scanf("%d", f[i]+j);
		if(f[i][j]) ans+=f[i][j]-1, a[i]=max(a[i], f[i][j]), b[j]=max(b[j], f[i][j]);
	}
	for(int i=1; i<=n; ++i) if(a[i]) ans-=a[i]-1;
	for(int i=1; i<=m; ++i) if(b[i]) ans-=b[i]-1;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(f[i][j] && a[i]==b[j])
		e[i].push_back(j);
	for(int i=1; i<=n; ++i) match(i), memset(vis, 0, sizeof vis);
	for(int i=1; i<=m; ++i) if(p[i]) ans+=b[i]-1;
	return printf("%lld", ans), 0;
}

D. Money for Nothing

题意

二维平面上有 $m$ 个一类点和 $n$ 个二类点，求以一个一类点作为左下角，和以一个二类点作为右上角，且边平行于坐标轴的矩形的最大面积。

$n,m\le 5\times 10^5$。

做法

考虑以横坐标排序，只有纵坐标前缀极值的一些点有用，并且按顺序枚举左下角，最优的右上角的是单调的。

每次暴力找到中点的最优匹配点，分治计算即可。

复杂度 $O(n+m\log n)$。

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>

using namespace std;
#define ll long long

const int IN_LEN = 1000000;
char buf[IN_LEN], *s, *t;
inline char read() {
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
inline void read(int &x) {
	static char c;
	while(isspace(c=read()));
	x=c-'0';
	while(isdigit(c=read())) x=x*10+c-'0';
}

#define x first
#define y second
const int N = 500005;
int m, n, nn, mm;
ll ans;
pair<int,int> a[N], b[N];
void solve(int l1, int r1, int l2, int r2){
	int mid=(l1+r1)>>1;
	ll now=0, x=0;
	for(int i=l2; i<=r2 && a[mid].y<=b[i].y; ++i)
		if(a[mid].x<=b[i].x && (ll)(b[i].x-a[mid].x)*(b[i].y-a[mid].y)>=now)
			now=(ll)(b[i].x-a[mid].x)*(b[i].y-a[mid].y), x=i;
	ans=max(ans, now);
	if(l1<mid) solve(l1, mid-1, l2, x);
	if(mid<r1) solve(mid+1, r1, x, r2);
}
int main() {
	read(m), read(n), mm=nn=1;
	for(int i=1; i<=m; ++i) read(a[i].x), read(a[i].y);
	sort(a+1, a+m+1);
	for(int i=2; i<=m; ++i) if(a[i].y<a[mm].y) a[++mm]=a[i];
	for(int i=1; i<=n; ++i) read(b[i].x), read(b[i].y);
	sort(b+1, b+n+1), reverse(b+1, b+n+1);
	for(int i=2; i<=n; ++i) if(b[i].y>b[nn].y) b[++nn]=b[i];
	reverse(b+1, b+nn+1);
	m=0;
	int j=1;
	for(int i=1; i<=mm; ++i){
		while(j<=nn && b[j].x<a[i].x) ++j;
		if(j<=nn && b[j].y>=a[i].y) a[++m]=a[i];
	}
	if(m) solve(1, m, 1, nn);
	return printf("%lld", ans), 0;
}

E. Need for Speed

题意

有 $n$ 段行程，现在已知总用时和每段行程的距离 $d_i$ 和速度 $s_i$ 加上常数 $c$ 后的值。

实数，$n\le 1000$。

做法

二分即可。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1005;
const double eps = 1e-7;
int n, t, mn, d[N], s[N];
int main() {
	scanf("%d%d", &n, &t);
	mn=1000;
	for(int i=1; i<=n; ++i) scanf("%d%d", d+i, s+i), mn=min(mn, s[i]);
	double l=eps-mn, r=2e6;
	while(r-l>=eps){
		double mid=(l+r)/2, ti=0;
		for(int i=1; i<=n; ++i) ti+=d[i]/(s[i]+mid);
		if(ti>t) l=mid; else r=mid;
	}
	return printf("%.7lf", l), 0;
}

F. Posterize

题意

有 $n$ 个数 $r_1,r_2,\dotsc,r_n$，你需要选出 $k$ 个数 $v_1,v_2,\dotsc,v_k$，最小化

\[ \sum_{i=1}^n \min_{1\le j\le k} (r_i-v_j)^2 \]

输出最小值。

$0\le r_i<256$。

数可能很多，按照值和个数给出。

做法

dp 即可，两侧的点特判，复杂度 $O(n^3)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 256;
int n, k, a[N];
ll ans, g[N][N], f[N][N];
int main() {
	scanf("%d%d", &n, &k);
	for(int i=1, x; i<=n; ++i) scanf("%d", &x), scanf("%d", a+x);
	for(int i=0; i<N; ++i) for(int j=i+1; j<N; ++j) for(int t=i+1; t<j; ++t)
		g[i][j]+=(ll)a[t]*min(t-i, j-t)*min(t-i, j-t);
	memset(f, 0x3f, sizeof f), ans=1e18;
	for(int i=0; i<N; ++i){
		f[i][1]=0;
		for(int j=0; j<i; ++j) f[i][1]+=(ll)a[j]*(i-j)*(i-j);
		for(int j=2; j<=k; ++j) for(int t=0; t<i; ++t)
			f[i][j]=min(f[i][j], f[t][j-1]+g[t][i]);
		ll s=f[i][k];
		for(int j=i+1; j<N; ++j) s+=(ll)a[j]*(j-i)*(j-i);
		ans=min(ans, s);
	}
	return printf("%lld", ans), 0;
}

G. Replicate Replicate Rfplicbte

题意

初始有一个无穷大的网格，每个格子是 $0$ 或 $1$，每步每个格子会变成上一步周围 $9$ 个格子的异或和，并且有至多一个格子出现变异，即与上述变化相反。

现在给你大小为 $w\times h$ 的结束状态，问初始的状态最小是多少，最小即最左和最右的 $1$ 相距最近，上下同理。

$w,h\le 300$。

做法

如果没有变异，每个状态有唯一前驱，每次把最左上的 $1$ 消去即可 $O(w \times h)$ 找到前驱

可以发现前驱在四个方向上至少都缩小一格。

考虑有变异的情况，上述消元过程会消出初始边界外，如果先枚举行，那么第一次消出问题的行即变异点所在行，同理我们可以求出所在列。

找出变异点后去掉再消一次，如果仍然出现问题则说明没有前驱。

复杂度 $O(w \times h \times \min\{w,h\} )$。

代码

#include<cstdio>
#include<algorithm>
#include<string.h>

using namespace std;
#define ll long long

const int N = 305;
int n, m;
char s[N];
bool a[N][N], b[N][N], c[N][N];
inline bool undo(){
	memcpy(b, a, sizeof a), memset(c, 0, sizeof c);
	int x=0, y=0;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(b[i][j]){
		if(i>=n-1 || j>=m-1){ x=i; goto f1;}
		else for(int I=i; I<i+3; ++I) for(int J=j; J<j+3; ++J) b[I][J]^=1;
	}
	f1:;
	if(x){
		memcpy(b, a, sizeof a);
		for(int j=1; j<=m; ++j) for(int i=1; i<=n; ++i) if(b[i][j]){
			if(i>=n-1 || j>=m-1){ y=j; goto f2;}
			else for(int I=i; I<i+3; ++I) for(int J=j; J<j+3; ++J) b[I][J]^=1;
		}
		f2:;
		a[x][y]^=1;
	}
	bool f=1;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) f&=!a[i][j];
	if(f) puts("#"), exit(0);
	memcpy(b, a, sizeof a);
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(b[i][j]){
		if(i>=n-1 || j>=m-1) return a[x][y]^=1, 0;
		else{
			c[i+1][j+1]=1;
			for(int I=i; I<i+3; ++I) for(int J=j; J<j+3; ++J) b[I][J]^=1;
		}
	}
	return memcpy(a, c, sizeof a), 1;
}
int main() {
	scanf("%d%d", &m, &n);
	for(int i=1; i<=n; ++i){
		scanf("%s", s+1);
		for(int j=1; j<=m; ++j) a[i][j]=s[j]=='#';
	}
	while(undo());
	int xl=n, xr=1, yl=n, yr=1;
	for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) if(a[i][j])
		xl=min(xl, i), xr=max(xr, i), yl=min(yl, j), yr=max(yr, j);
	for(int i=xl; i<=xr; ++i, puts("")) for(int j=yl; j<=yr; ++j) putchar(a[i][j]?'#':'.');
	return 0;
}

H. Scenery

Tarjan 有论文可以做到 $O(n\log n)$。

题意

有 $n$ 个区间，问是否能选出每个区间的一个长度为 $t$ 的子区间，并且这 $n$ 个子区间不相交（不含端点）。

$n\le 10000$。

做法

考虑一种错误的贪心，从小到大枚举下一次要放的区间的左端点，如果可以放就放，并且让它属于所有未被选择过的区间中，右端点最小的一个。

如图的情况，忽略红色，黄色部分即为正确的方案，但是上述贪心会在第二个区间的开头选择一个子区间，导致第一个区间无法满足。

一般化地，一个区间的集合 $S$，存在一些位置，如果之前选择了其中的某个位置作为一个子区间的左端点，那么 $S$ 就无法被满足。

如果我们可以处理出对于每个集合 $S$ 禁止的位置，不选择其中的位置作为左端点，再进行上述贪心就是正确的，如上图中红色部分即禁止的位置（的一部分）。

设集合 $S$ 中最小的左端点为 $s$，最大的右端点为 $e$，那么把 $[s,e]$ 包含的所有区间都放到 $S$ 中考虑，禁止的限制会严格变强，所以集合 $S$ 只要考虑 $O(n^2)$ 种，即某个区间 $[s,e]$ 包含的区间构成的集合。

考虑按照左端点从大到小枚举这个区间，记为 $[s,e]$。

由于所有 $>s$ 的位置是否有限制与以 $s$ 为左端点的区间无关，我们现在已经得到了所有 $>s$ 的位置的限制。

只考虑这些限制，忽略 $[s,e]$ 包含的区间各自的特征，只关心其数量，我们要在 $[s,e]$ 中放入数量等同于其包含区间数量的长度为 $t$ 的小区间，并且使这些区间尽可能地靠后。

设这些小区间最小的左端点为 $C$，

如果 $C<s$，那么不存在方案
如果 $C<s+t$，那么把 $(C-t, s)$ 这个区间标记为 forbidden，即不能被选择，否则 $[s,e]$ 包含的所有区间必然无法同时被满足
如果 $C\ge s+t$，那么不会对 $s$ 及更小的位置造成影响

如果做完了仍未出现不合法的情况（上面的 1.），那么存在方案。

考虑证明：

我们可以在限制下跑最初的贪心，必然可以得到一组解。

假设贪心选择的某个子区间超出了原区间的右端点，设这个子区间是从左到右第 $i$ 个，该原区间右端点为 $e$，

若不存在一个更早选择的子区间，对应的原区间的右端点更大，那么 $[-\infty,e]$ 的区间会在上述的过程中判为不合法
若存在，找出一个最靠后的区间，设是第 $j$ 个，那么找出第 $j$ 个到第 $i-1$ 个子区间对应的原区间的左端点的最小值 $s$，$[s,e]$ 会在上述过程中被判为不合法。

因此算法正确性得证。

forbidden 区间的右端点都是一个原区间的左端点，根据这个可以简单地 $O(n^2)$ 实现。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 10005;
int n, t, b[N], f[N], ban[N], now[N];
pair<int,int> a[N];
int main() {
	scanf("%d%d", &n, &t);
	for(int i=1; i<=n; ++i) scanf("%d%d", &a[i].first, &a[i].second), b[i]=a[i].second;
	sort(a+1, a+n+1), sort(b+1, b+n+1);  
	for(int i=1; i<=n; ++i) f[i]=b[i], now[i]=n, ban[i]=a[i].first;
	for(int i=n; i; --i) for(int j=n; b[j]>=a[i].second; --j){
		f[j]-=t;
		while(now[j]>i && f[j]<a[now[j]].first) f[j]=min(f[j], ban[now[j]--]);
		if(f[j]<a[i].first) return puts("no"), 0;
		ban[i]=min(ban[i], f[j]-t);
	}
	return puts("yes"), 0;
}

I. Secret Chamber at Mount Rushmore

题意

有 $m$ 种小写字母间的转化规则，$n$ 次询问两个单词是否可以转化，长度不超过 $50$。

$m\le 500,n\le 50$。

做法

跑 Floyd。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 30, M = 52;
int n, m;
bool a[N][N];
char s[M], t[M];
int main() {
	scanf("%d%d", &m, &n);
	for(int i=1; i<=m; ++i){
		char x, y;
		cin>>x>>y, a[x-'a'][y-'a']=1;
	}
	for(int k=0; k<26; ++k) for(int i=0; i<26; ++i) for(int j=0; j<26; ++j) a[i][j]|=a[i][k] && a[k][j];
	while(n--){
		scanf("%s%s", s, t);
		if(strlen(s)!=strlen(t)){
			puts("no");
			goto nxt;
		}
		for(int i=0; s[i]; ++i) if(s[i]!=t[i] && !a[s[i]-'a'][t[i]-'a']){
			puts("no");
			goto nxt;
		}
		puts("yes");
		nxt:;
	}
	return 0;
}

J. Son of Pipe Stream

题意

给定一个 $n$ 个点的无向管道网络，每条边有一个容量 $c_i$。

一种液体 Flubber 从 $1$ 号点流向 $3$ 号点，水从 $2$ 号点流向 $3$ 号点。

一条管道 $i$ 中 Flubber 和水要保证同向，设其流量分别为 $f$ 和 $w$，需要满足 $v\cdot f+w\le c_i$，其中 $v$ 是一个给定的实数。

点要保持 Flubber 和水的流量守恒。

设 $3$ 号点 Flubber 和水的总流量为 $F$ 和 $W$，最大化 $F^a W^{1-a}$，其中 $a$ 是一个给定的实数，要求输出每条边的方向及 Flubber 和水的流量。

$n\le 200, c_i\le 10, 1\le v\le 10,0.01\le a\le 0.99$

做法

首先 $v$ 是没有用的，在最后除以 $v^a$ 即可。

记 $1$ 到 $3$ 的最大流为 $F_{\max}$，$2$ 到 $3$ 的最大流为 $W_{\max}$。

建超级源向 $1,2$ 连无穷边，最大流为 $Z$。

则 Flubber 流量 $F$ 的范围在 $[Z-W_{\max},F_{\max}]$ 中，简单求导可以知道取 $a\cdot Z$ 为最优，令 $F^*$ 表示范围内最接近 $a\cdot F$ 的值，水的流量 $W^*=Z-F^*$。

~~题解说~~事实上这里必然能取到这两个值，考虑构造一组解。

用超级源限制 Flubber 和水的流量恰好分别为 $F^*$ 和 $W^*$，跑一遍最大流，~~题解说~~事实上存在解，可以考虑两种极端情况。

用这组解给每条边定向并定容。

从 $1$ 开始限制最大流量为 $F^*$ 在新图上跑最大流，可以得到 Flubber 每条边的流量，剩余部分即为水的流量。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 205, M = 20005, inf = 1e9;
const double eps = 1e-9;
double V, A;
int n, m, cur[N], d[N], cnt[N], id1[M], id2[M], a[M], b[M], c[M];
bool rev[M];
struct edge{ int v, id; double f;};
vector<edge> e[N];
inline void add(int x, int y, double z, bool t=0){
	e[x].push_back((edge){y, (int)e[y].size(), z});
	e[y].push_back((edge){x, (int)e[x].size()-1, t*z});
}
double sap(int u, double flow){
	if(flow<eps || u==3) return flow;
	double now=0;
	for(unsigned i=cur[u]; i<e[u].size(); ++i){
		edge &p=e[u][i];
		if(d[p.v]+1==d[u]){
			double tmp=sap(p.v, min(flow-now, p.f));
			p.f-=tmp, now+=tmp, e[p.v][p.id].f+=tmp;
			if(flow-now<eps) return flow;
		}
		cur[u]=i;
	}
	cur[u]=0;
	if(!--cnt[d[u]]) d[3]=n+1;
	++cnt[++d[u]];
	return now;
}
inline void clear(){
	memset(cur, 0, sizeof cur), memset(d, 0, sizeof d), memset(cnt, 0, sizeof cnt), cnt[0]=n+1;
	for(auto i:e[0]) i.f=inf, e[i.v][i.id].f=0;
	for(int i=1; i<=m; ++i) e[a[i]][id1[i]].f=e[b[i]][id2[i]].f=c[i];
}
inline double SAP(int S, bool t=1){
	if(t) clear();
	double ans=0;
	while(d[3]!=n+1) ans+=sap(S, inf);
	return ans;
}
int main() {
	scanf("%d%d%lf%lf", &n, &m, &V, &A);
	for(int i=1; i<=m; ++i){
		scanf("%d%d%d", a+i, b+i, c+i);
		id1[i]=e[a[i]].size(), id2[i]=e[b[i]].size(), add(a[i], b[i], c[i], 1);
	}
	add(0, 1, inf), add(0, 2, inf);
	int f=SAP(1), w=SAP(2), s=SAP(0);
	double ff=max(min(A*s, (double)f), (double)s-w), ww=s-ff, ans=pow(ff/V, A)*pow(ww, 1-A);
	clear(), e[0][0].f=ff, e[0][1].f=ww, SAP(0, 0);
	for(int i=1; i<=m; ++i){
		if(e[a[i]][id1[i]].f<c[i]) e[a[i]][id1[i]].f=c[i]-e[a[i]][id1[i]].f, e[b[i]][id2[i]].f=0;
		else e[a[i]][id1[i]].f=0, e[b[i]][id2[i]].f=c[i]-e[b[i]][id2[i]].f, rev[i]=1;
	}
	memset(cur, 0, sizeof cur), memset(d, 0, sizeof d), memset(cnt, 0, sizeof cnt), cnt[0]=n+1;
	e[0][0].f=ff, e[1][e[0][0].id].f=e[0][1].f=e[2][e[0][1].id].f=0, SAP(0, 0);
	for(int i=1; i<=m; ++i){
		if(rev[i]) printf("%.9lf %.9lf\n", -e[a[i]][id1[i]].f/V, -e[b[i]][id2[i]].f);
		else printf("%.9lf %.9lf\n", e[b[i]][id2[i]].f/V, e[a[i]][id1[i]].f);
	}
	printf("%.9lf", ans);
	return 0;
}

K. Tarot Sham Boast

题意

有 $s$ 个长度相同的字符集大小为 $3$ 的字符串，要求按照其在长度为 $n$ 的随机串中的出现概率排序，概率相同按照输入顺序输出。

$n\le 10^6, s\le 10$。

串长不超过 $10^5$。

做法

计算概率可以容斥。

设串为 $X,|X|=l$，要计算 $X$ 的出现概率

\[ \sum_{I\subseteq [n-l+1],I\ne \varnothing} (-1)^{|I|+1} P(\text{$X$ 在 $I$ 中的每个位置都出现了}) \]

当 $|I|=1$ 时，概率为 $\frac{n-l+1}{3^l}$，与 $X$ 无关
当 $|I|=2$ 且 $I$ 中的两个位置相距不小于 $l$，也与 $X$ 无关
当 $|I|=2$ 且两个串有交，概率为若干形如 $-3^k$ 的数的和，且 $k$ 两两不同
当 $|I|>2$，~~根据题解，可以不考虑~~ 证明在这里

考虑相距为 $t(t<l)$ 的两个位置可以同时出现，当且仅当 $X$ 有长度为 $l-t$ 的 border，也即有周期 $t$。

由于贡献为 $\frac{n-l-t+1}{3^{l+t}}$，相差极大，可以直接用字典序来比较大小。

注意太大的 $t$ 使得 $l+t>n$ 应该被忽略。

复杂度 $O(l\cdot s\log s)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1000005, M = 100005;
int n, d, m, f[11], nxt[N], a[11][M];
char *t, s[N], T[11][M];
bool cmp(int x, int y){
	for(int i=0; i<m; ++i) if(a[x][i]!=a[y][i]) return a[x][i]<a[y][i];
	return 0;
}
int main() {
	scanf("%d%d", &n, &d);
	for(int i=1; i<=d; ++i){
		scanf("%s", (t=T[i])+1), m=strlen(t+1), f[i]=i;
		for(int j=2, k=0; j<=m; ++j){
			while(k && t[k+1]!=t[j]) k=nxt[k];
			nxt[j]=k+=(t[k+1]==t[j]);
		}
		for(int j=m, cnt=0; j && j>=2*m-n; j=nxt[j]) a[i][cnt++]=j;
	}
	sort(f+1, f+d+1, cmp);
	for(int i=1; i<=d; ++i) puts(T[f[i]]+1);
	return 0;
}

L. Visual Python++

题意

有一类点和二类点各 $n$ 个，问是否存在一种匹配方案，使得以对应的一类点为左上角，二类点为右下角，能构成矩形且矩形两两不交（包括顶点和边），如果有解需要输出方案。

$n\le 10^5$。

做法

枚举一维坐标，可行的匹配是至多只有一种的。

匹配完后离线扫描线判定即可。

复杂度 $O(n\log n)$。

代码

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<string.h>
#include<cmath>
#include<vector>
#include<set>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
	if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
	*ooh++=c;
}
template<class T>
inline void print(T x) {
	static int buf[30], cnt;
	if (x==0) print('0');
	else {
		if (x<0) print('-'), x=-x;
		for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
		while(cnt) print((char)buf[cnt--]);
	}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 200005;
ll ans;
int n, cnt, c[N], e[N], w[N<<1];
pair<int,int> p[N<<1];
vector<int> d[N<<1];
vector<pair<int,int>> q[N<<1];
struct point{
	int x, y, id;
	inline bool operator <(const point &rhs)const{ return x<rhs.x;}
} a[N], b[N];
set<pair<int,int>> s;
inline void modify(int x, int y){ while(x<=n<<1) w[x]+=y, x+=x&-x;}
inline int query(int x){
	int ans=0;
	while(x) ans+=w[x], x^=x&-x;
	return ans;
}
int main() {
	read(n);
	for(int i=1; i<=n; ++i) read(a[i].x), read(a[i].y), a[i].id=i;
	for(int i=1; i<=n; ++i) read(b[i].x), read(b[i].y), b[i].id=i;
	for(int i=1; i<=n; ++i) p[++cnt]=make_pair(a[i].x, i), p[++cnt]=make_pair(b[i].x, i+n);
	sort(p+1, p+cnt+1);
	for(int i=1, now=0; i<=cnt; ++i)
		(p[i].second<=n?a[p[i].second].x:b[p[i].second-n].x)=(p[i].first==p[i-1].first?now:++now);
	cnt=0;
	for(int i=1; i<=n; ++i) p[++cnt]=make_pair(a[i].y, i), p[++cnt]=make_pair(b[i].y, i+n);
	sort(p+1, p+cnt+1);
	for(int i=1, now=0; i<=cnt; ++i)
		(p[i].second<=n?a[p[i].second].y:b[p[i].second-n].y)=(p[i].first==p[i-1].first?now:++now);
	
	sort(a+1, a+n+1), sort(b+1, b+n+1);
	int j=1;
	for(int i=1; i<=n; ++i){
		while(j<=n && a[j].x<=b[i].x) s.insert(make_pair(a[j].y, j)), ++j;
		auto it=s.upper_bound(make_pair(b[i].y, n));
		if(it==s.begin()) return puts("syntax error"), 0;
		c[i]=(--it)->second;
		s.erase(it);
	}
	for(int i=1; i<=n; ++i)
		d[a[c[i]].x].push_back(b[i].y), d[b[i].x+1].push_back(-b[i].y),
		d[a[c[i]].x].push_back(a[c[i]].y), d[b[i].x+1].push_back(-a[c[i]].y),
		q[a[c[i]].x].push_back(make_pair(a[c[i]].y, b[i].y)),
		q[b[i].x].push_back(make_pair(a[c[i]].y, b[i].y));
	for(int i=1; i<=n<<1; ++i){
		for(int j:d[i]) if(j<0) modify(-j, -1); else modify(j, 1);
		for(auto j:q[i]) ans+=query(j.second)-query(j.first-1);
	}
	if(ans==n<<2){
		for(int i=1; i<=n; ++i) e[a[c[i]].id]=b[i].id;
		for(int i=1; i<=n; ++i) print(e[i]), print('\n');
	}
	else puts("syntax error");
	return flush(), 0;
}

ICPC World Finals 2017 题解

https://cekavis.github.io/icpc-world-finals-2017/

Author

Cekavis

Posted on

2019-04-16

Updated on

2022-06-16

ICPC World Finals 2017 题解

A. Airport Construction

题意

做法

代码

B. Get a Clue!

题意

做法

代码

C. Mission Improbable

题意

做法

代码

D. Money for Nothing

题意

做法

代码

E. Need for Speed

题意

做法

代码

F. Posterize

题意

做法

代码

G. Replicate Replicate Rfplicbte

题意

做法

代码

H. Scenery

题意

做法

代码

I. Secret Chamber at Mount Rushmore

题意

做法

代码

J. Son of Pipe Stream

题意

做法

代码

K. Tarot Sham Boast

题意

做法

代码

L. Visual Python++

题意

做法

代码

Author

Posted on

Updated on

Licensed under

Comments

Catalogue