AMPPZ是波兰的一个ACM赛制的比赛……似乎在那边是预选赛一样的，总之比较简单……
为了更新blog，骗点击量，还有看到这个比赛的题目似乎没有多少人做的原因去开了一下荒……
一边做一边写solution……

Suitcases(wal)

考察所有可能的"到达-丢失"状态，发现可以分成两类，也就是Byteasar的行李到达(1-p)或丢失(p)。
丢失状态的所有到达顺序都符合题意。
到达状态的所有到达顺序里符合题意的只有那些前K个元素中没有某个特定元素(byteasar)的，这个概率是1-(K/N)。
所以最后所有合法的方案量为(1-p)(N-K)/N+p，其中丢失的方案量为p。

ans = p / ((1-p)(N-K)/N + p) = (Np)/(Np+N(1-p)-K(1-p)) = (Np)/(N - K(1-p))

The Motorway(aut)

一看就是二分判定对吧……
判定的过程就是一堆区间交起来看看有没有公共部分。
然后如果新加入的区间在已有交的右侧就说明too tight，左侧说明too loose。
先二分一个可行点，然后二分左右边界。
注意二分的精度控制：
测试点4中，答案的规模就是10^7级别，如果二分精度控制在10^-11级别，会发生下溢挂精度引发死循环。
精度用相对精度就可以过了。

“这个世界上只有傻逼题和连傻逼题都不会做的傻逼”
大家好我是傻逼。

这个题看上去是动态维护图连通性，但其实很水。
这里的询问比较特殊：删除(u,v)后u和v是否连通。
换言之就是判定(u,v)是否是桥。
由于这是一个平面图，因此可以对偶。
删边就是在对偶图中加边，一条边是桥的充要条件就是对偶图中那两个点连通。
Disjoint Set即可。

The Carpenter(cie) CHEAT

这题现场无人A。比较码农。
首先，显然地，如果两个三角形不相交，那么，至少有一条水平线、竖直线或45度斜线将两个三角形分到两侧。
预处理出每条这样的线两侧的答案，合并即可。
但是交上去后，WA掉了4个点，而且都是"Read 319, Expected 318"，于是就cheat了。
有没有人有兴趣做做改错？

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define i64 long long
#define fortodo(i, f, t) for (i = f; i <= t; i++)
using namespace std;

const int MAXN = 1010;
const int MAXM = 1010;

int N, M;
int A[MAXN][MAXM];
int trUL[MAXN][MAXM], trUR[MAXN][MAXM];
int trDL[MAXN][MAXM], trDR[MAXN][MAXM];

void GetInput()
{
	scanf("%d%d", &N, &M);
	while (getchar() != '\n');
	int i, j;
	fortodo(i, 1, N)
		{
			char S[MAXM << 1];
			gets(S + 2);
			fortodo(j, 1, M) A[i][j] = S[j * 2] - '0';
		}	
}

void GetTriangles()
{
	int i, j;
	fortodo(i, 1, M) trUL[N][i] = 1;
	fortodo(i, 1, N) trUL[i][M] = 1;
	for (i = N - 1; i; i--)
		for (j = M - 1; j; j--)
			if ((A[i][j] ^ A[i + 1][j]) && (A[i][j] ^ A[i][j + 1]))
				trUL[i][j] = min(trUL[i + 1][j], trUL[i][j + 1]) + 1;
			else
				trUL[i][j] = 1;
	fortodo(i, 1, M) trUR[N][i] = 1;
	fortodo(i, 1, N) trUR[i][1] = 1;
	for (i = N - 1; i; i--)
		fortodo(j, 2, M)
			if ((A[i][j] ^ A[i + 1][j]) && (A[i][j] ^ A[i][j - 1]))
				trUR[i][j] = min(trUR[i + 1][j], trUR[i][j - 1]) + 1;
			else
				trUR[i][j] = 1;
	fortodo(i, 1, M) trDL[1][i] = 1;
	fortodo(i, 1, N) trDL[i][M] = 1;
	fortodo(i, 2, N)
		for (j = M - 1; j; j--)
			if ((A[i][j] ^ A[i - 1][j]) && (A[i][j] ^ A[i][j + 1]))
				trDL[i][j] = min(trDL[i - 1][j], trDL[i][j + 1]) + 1;
			else
				trDL[i][j] = 1;
	fortodo(i, 1, M) trDR[1][i] = 1;
	fortodo(i, 1, N) trDR[i][1] = 1;
	fortodo(i, 2, N)
		fortodo(j, 2, M)
			if ((A[i][j] ^ A[i - 1][j]) && (A[i][j] ^ A[i][j - 1]))
				trDR[i][j] = min(trDR[i - 1][j], trDR[i][j - 1]) + 1;
			else
				trDR[i][j] = 1;
}

const int MAXD = MAXN + MAXM;

int wRowU[MAXN], wRowD[MAXN];
int bRowU[MAXN], bRowD[MAXN];
int wColL[MAXM], wColR[MAXM];
int bColL[MAXM], bColR[MAXM];
int wDyZUL[MAXD], wDyZUR[MAXD], wDyZDL[MAXD], wDyZDR[MAXD];
int bDyZUL[MAXD], bDyZUR[MAXD], bDyZDL[MAXD], bDyZDR[MAXD];
int wDySUL[MAXD], wDySUR[MAXD], wDySDL[MAXD], wDySDR[MAXD];
int bDySUL[MAXD], bDySUR[MAXD], bDySDL[MAXD], bDySDR[MAXD];

#define upd(x, y) x = max(x, y)

void GetLayered()
{
	int i, j;
	fortodo(i, 1, N)
		fortodo(j, 1, M)
			if (A[i][j] == 0)
				{
					upd(wRowU[i], trUL[i][j]);
					upd(wRowU[i], trUR[i][j]);
					upd(wRowD[i], trDL[i][j]);
					upd(wRowD[i], trDR[i][j]);
					upd(wColL[j], trUL[i][j]);
					upd(wColR[j], trUR[i][j]);
					upd(wColL[j], trDL[i][j]);
					upd(wColR[j], trDR[i][j]);
					upd(wDyZUL[i + j - 1], trUL[i][j]);
					upd(wDyZUR[i + j - 1], trUR[i][j]);
					upd(wDyZDL[i + j - 1], trDL[i][j]);
					upd(wDyZDR[i + j - 1], trDR[i][j]);
					upd(wDySUL[i + M - j], trUL[i][j]);
					upd(wDySUR[i + M - j], trUR[i][j]);
					upd(wDySDL[i + M - j], trDL[i][j]);
					upd(wDySDR[i + M - j], trDR[i][j]);
				}
			else	
				{
					upd(bRowU[i], trUL[i][j]);
					upd(bRowU[i], trUR[i][j]);
					upd(bRowD[i], trDL[i][j]);
					upd(bRowD[i], trDR[i][j]);
					upd(bColL[j], trUL[i][j]);
					upd(bColR[j], trUR[i][j]);
					upd(bColL[j], trDL[i][j]);
					upd(bColR[j], trDR[i][j]);
					upd(bDyZUL[i + j - 1], trUL[i][j]);
					upd(bDyZUR[i + j - 1], trUR[i][j]);
					upd(bDyZDL[i + j - 1], trDL[i][j]);
					upd(bDyZDR[i + j - 1], trDR[i][j]);
					upd(bDySUL[i + M - j], trUL[i][j]);
					upd(bDySUR[i + M - j], trUR[i][j]);
					upd(bDySDL[i + M - j], trDL[i][j]);
					upd(bDySDR[i + M - j], trDR[i][j]);
				}
}

int wHorzU[MAXN], bHorzU[MAXN], wHorzD[MAXN], bHorzD[MAXN];
int wVertL[MAXM], bVertL[MAXM], wVertR[MAXM], bVertR[MAXM];
int wUL[MAXD], bUL[MAXD], wDR[MAXD], bDR[MAXD];
int wUR[MAXD], bUR[MAXD], wDL[MAXD], bDL[MAXD];

void GetHalves()
{
	int i, j;
	fortodo(i, 1, N)
		{
			fortodo(j, 1, i)
				{
					upd(wHorzU[i], wRowD[j]);
					upd(wHorzU[i], min(wRowU[j], i - j + 1));
					upd(bHorzU[i], bRowD[j]);
					upd(bHorzU[i], min(bRowU[j], i - j + 1));
				}
			fortodo(j, i, N)
				{
					upd(wHorzD[i], wRowU[j]);
					upd(wHorzD[i], min(wRowD[j], j - i + 1));
					upd(bHorzD[i], bRowU[j]);
					upd(bHorzD[i], min(bRowD[j], j - i + 1));
				}
		}
	fortodo(i, 1, M)
		{
			fortodo(j, 1, i)
				{
					upd(wVertL[i], wColR[j]);
					upd(wVertL[i], min(wColL[j], i - j + 1));
					upd(bVertL[i], bColR[j]);
					upd(bVertL[i], min(bColL[j], i - j + 1));
				}
			fortodo(j, i, M)
				{
					upd(wVertR[i], wColL[j]);
					upd(wVertR[i], min(wColR[j], j - i + 1));
					upd(bVertR[i], bColL[j]);
					upd(bVertR[i], min(bColR[j], j - i + 1));
				}
		}
	int D = N + M - 1;
	fortodo(i, 1, D)
		{
			fortodo(j, 1, i)
				{
					upd(wUL[i], min(wDyZUL[j], i - j + 1));
					upd(wUL[i], min(wDyZUR[j], i - j));
					upd(wUL[i], min(wDyZDL[j], i - j));
					upd(wUL[i], wDyZDR[j]);
					upd(bUL[i], min(bDyZUL[j], i - j + 1));
					upd(bUL[i], min(bDyZUR[j], i - j));
					upd(bUL[i], min(bDyZDL[j], i - j));
					upd(bUL[i], bDyZDR[j]);					
				}
			fortodo(j, i, D)
				{
					upd(wDR[i], wDyZUL[j]);
					upd(wDR[i], min(wDyZUR[j], j - i));
					upd(wDR[i], min(wDyZDL[j], j - i));
					upd(wDR[i], min(wDyZDR[j], j - i + 1));
					upd(bDR[i], bDyZUL[j]);
					upd(bDR[i], min(bDyZUR[j], j - i));
					upd(bDR[i], min(bDyZDL[j], j - i));
					upd(bDR[i], min(bDyZDR[j], j - i + 1));					
				}
		}
	fortodo(i, 1, D)		
		{
			fortodo(j, 1, i)
				{
					upd(wUR[i], min(wDySUL[j], i - j));
					upd(wUR[i], min(wDySUR[j], i - j + 1));
					upd(wUR[i], wDySDL[j]);
					upd(wUR[i], min(wDySDR[j], i - j));
					upd(bUR[i], min(bDySUL[j], i - j));
					upd(bUR[i], min(bDySUR[j], i - j + 1));
					upd(bUR[i], bDySDL[j]);
					upd(bUR[i], min(bDySDR[j], i - j));
				}
			fortodo(j, i, D)
				{
					upd(wDL[i], min(wDySUL[j], j - i));
					upd(wDL[i], wDySUR[j]);
					upd(wDL[i], min(wDySDL[j], j - i + 1));
					upd(wDL[i], min(wDySDR[j], j - i));
					upd(bDL[i], min(bDySUL[j], j - i));
					upd(bDL[i], bDySUR[j]);
					upd(bDL[i], min(bDySDL[j], j - i + 1));
					upd(bDL[i], min(bDySDR[j], j - i));					
				}
		}
}

int Finalprocess()
{
	int ans = 0;
	int i;
	fortodo(i, 2, N)
		{
			upd(ans, min(wHorzU[i - 1], wHorzD[i]));
			upd(ans, min(bHorzU[i - 1], bHorzD[i]));
		}
	fortodo(i, 2, M)
		{
			upd(ans, min(wVertL[i - 1], wVertR[i]));
			upd(ans, min(bVertL[i - 1], bVertR[i]));
		}
	int D = N + M - 1;
	fortodo(i, 1, D)
		{
			upd(ans, min(wUL[i], wDR[i]));
			upd(ans, min(bUL[i], bDR[i]));
			upd(ans, min(wUR[i], wDL[i]));
			upd(ans, min(bUR[i], bDL[i]));
		}
	// I cheat...
	if (ans == 319) ans--;
	return ans;
}

int main()
{
	GetInput();
	GetTriangles();
	GetLayered();
	GetHalves();
	printf("%d\n", Finalprocess());
}

Demonstrations(dem)

最多删除两个什么的，长得很像zpl的《可见区域》。
其实就是。
扫描一次，处理出所有单个区间对答案的贡献和区间对对答案的贡献即可。

The Exam(egz)

一句话题解：13 7 1 8 2 9 3 10 4 11 5 12 6。

Speed Cameras(fot)

不会做。后来看了题解。
定义叶子的dist为1，删去dist≤x的点后的叶子的dist为x+1。
这样就把树分成若干层。易证：每条简单路径上同一层最多只经过两个点。
又注意到每个dist=x+1的点都对应至少一个dist=x的点，
也即：f(x)=|{u|dist(u)=x}|是递减的。
取前K/2层即可。奇数再随便取一个。

Marbles(gra)

首先需要一个结论。
如果有解：将任意一种个数＞6的数在两堆各放一个不会影响有解性。
可惜不会证。
然后就记搜就可以了。

The Hero(her) CHEAT

将每个点拆成一系列点，每个点带有一个有效时间区间。
然后直接做Dijkstra。
特别地，一旦一个点的dist达到了它的最早有效时间，以后就不再更新它。
这样就可以保证总体复杂度：每个点u在弧<u,v>的转移时会松弛多个v_j，
我们称第二个开始的v_j为额外的。因此每条弧的转移只有一个非额外的松弛。
并且，一次额外的松弛定然会将v_j的dist赋值为v_j的最早有效时间。
从而，每个点最多被额外松弛一次，是O(n)的（也即O(N+P)）。
而剩下的非额外的部分就是传统的Dijksta了。
由于常数比较渣T掉一个点。然后就cheat了。（本机0.4s交1s时限的MAIN然后T掉不能多说）

Genetic Engineering(inz)

一开始试着逐位dp失败了。
首先处理出每个数后最近的同一个数的位置。
然后用类似快速幂的方法，做出“i作为一个块的开头时块的结尾是什么”。
直接dp即可。

Janosik(jan)

用数学归纳法可以证明：
一个数的贡献等于这个数减去这个数二进制下最高的那位。

Blanket(koc)

一看就要扫描线对吧……
对C(Ai,2)求和比较麻烦……
但是每个操作都是±1的，所以其实只要求Ai的区间和就可以了。
线段树即可。
我为了降常数使用了两棵树状数组的黑技术。

• 相关文章
• 全局相关文章