XVIII Open Cup, Grand Prix of Romania(U of Bucharest Contest)

X

Contest Link:https://official.contest.yandex.ru/opencupXVIII/contest/5012/

A. Balance

容易发现在确定了第一行第一列后整个矩阵便确定了.不妨额外添加第 $0$ 行第 $0$ 列, 则其等价于以下线性规划问题:

$$\begin{split}
\textbf{Minimize}&: \sum_{1 \leq i,j \leq n} \vec{ \mathbf x}_i + \vec{\mathbf y}_j\\
\textbf{Subject to} &:\\
&~
\begin{cases}
\vec{\mathbf x}_i + \vec{\mathbf y}_j \geq a_{i,j} & \forall 0 \leq i,j \leq n\\
\vec{\mathbf x}_0 = 0\\
\vec{\mathbf y}_0 = 0
\end{cases}
\end{split}$$

可以直接求解该线性规划或转对偶后费用流. 注意到其定义与 KM 中的的顶点标号相同,因此可以直接跑 KM 算法,时间复杂度 $\Theta(n^3)$.

#include<bits/stdc++.h>

typedef long long ll;

const int N = 55;
int n, sum, w[N][N], ex[N], ey[N], min[N], cur[N], p[N], ans[N][N];
bool vx[N], vy[N];

bool dfs(int x)
{
	vx[x] = true;
	for (int y = 1; y <= n; ++y)
	{
		if (!vy[y])
		{
			int d = ex[x] + ey[y] - w[x][y];
			if (!d)
			{
				vy[y] = true;
				if (!cur[y] || dfs(cur[y]))
				{
					cur[y] = x;
					return true;
				}
			}
			else min[y] = std::min(min[y], d);
		}
	}
	return false;
}

template <int T>
struct fast_io
{
	char p[T], q[T], *p1, *p2, *q1, *q2;
	fast_io()
	{
		p1 = p, p2 = p, q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char ch)
	{
		if (q1 == q2)
		{
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*q1++ = ch;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1024768> io;

inline int read()
{
	int r = 0;
	char ch; 
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r;
}

inline char rc()
{
	char ch;
	do ch = io.gc(); while (!isalpha(ch));
	return ch;
}

inline void putint(long long x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) putint(x / 10);
	io.pc(48 + x % 10);
}

inline void output(long long x, char ch = ' ')
{
	putint(x);
	io.pc(ch);
}

inline void outputs(const char *s)
{
	while (*s) io.pc(*s++);
	io.pc('\n');
}


int main()
{
	n = read();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			w[i][j] = read();
	for (int x = 1; x <= n; ++x) ex[x] = *std::max_element(w[x] + 1, w[x] + n + 1);
	for (int x = 1; x <= n; ++x)
	{
		memset(min, 0x3f, sizeof min);
		memset(vx, 0, sizeof vx);
		memset(vy, 0, sizeof vy);
		if (!dfs(x))
		{
			while (true)
			{
				int d = 0x3f3f3f3f, t = 0;
				for (int y = 1; y <= n; ++y) if (!vy[y]) d = std::min(d, min[y]);
				for (int x = 1; x <= n; ++x) if (vx[x]) ex[x] -= d;
				for (int y = 1; y <= n; ++y)
					if (vy[y]) ey[y] += d;
					else 
					{
						min[y] -= d;
						if (!min[y]) t = y;
					}
				if (!cur[t]) break;
				int e = cur[t];
				vx[e] = vy[t] = true;
				for (int y = 1; y <= n; ++y) min[y] = std::min(min[y], ex[e] + ey[y] - w[e][y]);
			}
			memset(vx, 0, sizeof vx);
			memset(vy, 0, sizeof vy);
			dfs(x);
		}
	}
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
		{
			ans[i][j] = ex[i] + ey[j];
			sum += ans[i][j];
		}
	output(sum, '\n');
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j)
			output(ans[i][j], " \n"[j == n]);
	return 0;
}

G. Origami

注意到行列是独立的,对一维 hash 后另一维可以直接 Manacher.

#include <bits/stdc++.h>

const int N = 2100000;

char s[N];

template<int mod>
struct Z
{
	int v;
	Z(int v = 0) : v(v) { }
	inline int inc(int x, int y) const { x += y - mod; return x + (x >> 31 & mod); }
	inline int dec(int x, int y) const { x -= y; return x + (x >> 31 & mod); }
	inline int mul(int x, int y) const { return 1ll * x * y % mod; }
	inline Z<mod> operator+(const Z<mod> &rhs) const
	{
		return Z(inc(v, rhs.v));
	}
	inline Z<mod> operator-(const Z<mod> &rhs) const
	{
		return Z(dec(v, rhs.v));
	}
	inline Z<mod> operator*(const Z<mod> &rhs) const
	{
		return Z(mul(v, rhs.v));
	}
	inline Z<mod>& operator+=(const Z<mod> &rhs)
	{
		*this = *this + rhs;
		return *this;
	}
	inline Z<mod>& operator-=(const Z<mod> &rhs)
	{
		*this = *this - rhs;
		return *this;
	}
	inline Z<mod>& operator*=(const Z<mod> &rhs)
	{
		*this = *this * rhs;
		return *this;
	}
	inline bool operator==(const Z<mod> &rhs) const
	{
		return v == rhs.v;
	}
	inline bool operator!=(const Z<mod> &rhs) const
	{
		return v != rhs.v;
	}
};

const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
struct hash_t
{
	Z<mod1> v1; Z<mod2> v2;
	hash_t(int v = 0) : v1(v), v2(v) {}
	hash_t(Z<mod1> v1, Z<mod2> v2) : v1(v1), v2(v2) {}
	inline hash_t operator+(const hash_t &rhs) const
	{
		return hash_t(v1 + rhs.v1, v2 + rhs.v2);
	}
	inline hash_t operator-(const hash_t &rhs) const
	{
		return hash_t(v1 - rhs.v1, v2 - rhs.v2);
	}
	inline hash_t operator*(const hash_t &rhs) const
	{
		return hash_t(v1 * rhs.v1, v2 * rhs.v2);
	}
	inline hash_t& operator+=(const hash_t &rhs)
	{
		*this = *this + rhs;
		return *this;
	}
	inline hash_t& operator-=(const hash_t &rhs)
	{
		*this = *this - rhs;
		return *this;
	}
	inline hash_t& operator*=(const hash_t &rhs)
	{
		*this = *this * rhs;
		return *this;
	}
	
	inline bool operator==(const hash_t &rhs) const
	{
		return v1 == rhs.v1 && v2 == rhs.v2;
	}
	inline bool operator!=(const hash_t &rhs) const
	{
		return v1 != rhs.v1 || v2 != rhs.v2;
	}
};

hash_t str[N];
unsigned long long ansX, ansY;
int n, m, len, rad[N], abL[N];

template <int T>
struct fast_io
{
	char p[T], q[T], *p1, *p2, *q1, *q2;
	fast_io()
	{
		p1 = p, p2 = p, q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char ch)
	{
		if (q1 == q2)
		{
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*q1++ = ch;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1024768> io;

inline int read()
{
	int r = 0;
	char ch; 
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r;
}

inline char rc()
{
	char ch;
	do ch = io.gc(); while (!isalpha(ch));
	return ch;
}

inline void putint(long long x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) putint(x / 10);
	io.pc(48 + x % 10);
}

inline void output(long long x, char ch = ' ')
{
	putint(x);
	io.pc(ch);
}

inline void outputs(const char *s)
{
	while (*s) io.pc(*s++);
	io.pc('\n');
}


int main()
{
	n = read(), m = read();
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			s[(i - 1) * m + j] = rc();
		}
	}
	str[len = 1] = -1;
	for (int i = 1; i <= m; ++i)
	{
		++len;
		for (int j = 1; j <= n; ++j)
			str[len] *= 233, str[len] += s[(j - 1) * m + i];
		str[++len] = -1;
	}
	for (int i = 2, maxR = 0, pos; i <= len; ++i)
	{
		if (i <= maxR) rad[i] = std::min(rad[(pos << 1) - i], maxR - i);
		while (i - rad[i] > 1 && i + rad[i] < len && str[i - rad[i] - 1] == str[i + rad[i] + 1]) ++rad[i];
		if (i + rad[i] > maxR) maxR = i + rad[i], pos = i;
	}
	abL[1] = 1;
	for (int i = 2, lst = 1; i <= m; ++i)
	{
		abL[i] = abL[i - 1];
		if (i - (rad[(i << 1) - 1] >> 1) <= lst)
			++abL[i], lst = i;
	}
	ansX = abL[m];
	for (int i = m - 1, lst = m; i; --i)
		if (i + (rad[(i << 1) + 1] >> 1) >= lst)
			ansX += abL[i], lst = i;
	str[len = 1] = -1;
	for (int i = 1; i <= n; ++i)
	{
		str[++len] = 0;
		for (int j = 1; j <= m; ++j)
			str[len] *= 233, str[len] += s[(i - 1) * m + j];
		str[++len] = -1;
	}
	for (int i = 2, maxR = 0, pos; i <= len; ++i)
	{
		rad[i] = 0;
		if (i <= maxR) rad[i] = std::min(rad[(pos << 1) - i], maxR - i);
		while (i - rad[i] > 1 && i + rad[i] < len && str[i - rad[i] - 1] == str[i + rad[i] + 1]) ++rad[i];
		if (i + rad[i] > maxR) maxR = i + rad[i], pos = i;
	}
	abL[1] = 1;
	for (int i = 2, lst = 1; i <= n; ++i)
	{
		abL[i] = abL[i - 1];
		if (i - (rad[(i << 1) - 1] >> 1) <= lst)
			++abL[i], lst = i;
	}
	ansY = abL[n];
	for (int i = n - 1, lst = n; i; --i)
		if (i + (rad[(i << 1) + 1] >> 1) >= lst)
			ansY += abL[i], lst = i;
	output(ansX * ansY);
	return 0;
}

L. Xormites

设 $S=\bigoplus^n_{i=1} a_i$, 则若 Alice 取得的异或和为 $x$, 那么 Bob 取得的即为 $x \oplus S$. 容易发现平局当且仅当 $S=0$.

对于不平局的情况,设 $S$ 二进制表示的最高非零位为 $k$, 则容易发现 $k$ 这一位直接决定了胜负,因此可将序列转为 0/1 序列.当序列长度是偶数时,将序列黑白染色,则先手一定可以通过操作让自己全部取得黑色或全部取得白色,而这其中一定有一种包含了奇数个1,故此时先手必胜.

当序列长度为偶数时,如果先手取走一个零,那么后手就得到了先手必胜局面.不妨假设先手取走的是1,则此时问题转化成你有一个长度为偶数的序列,里面有偶数个1,问后手(Alice)能不能取得偶数个1. 显然Alice必须复读每次Bob取的内容.即对于Alice必胜局面,当Bob取走一侧时,要么另一侧的值与其相同,要么该侧下一个数与其相同.当某一时刻两侧不同时,若另一侧与结尾不同,那么Bob取该侧Alice就输了.因此,在去除两侧相同的部分后,剩余序列的相邻位置必须相同.因此序列一定可以表示成 $SRS$ 的形式,其中 $S$ 为任意可空0/1串,$R$ 满足 $R_1=R_2,R_3=R_4,\cdots, R_{n-1}=R_n$. 直接判定即可.时间复杂度 $\Theta(n)$.

#include <bits/stdc++.h>

const int N = 1e6 + 50;
int n, a[N];

template <int T>
struct fast_io
{
	char p[T], q[T], *p1, *p2, *q1, *q2;
	fast_io()
	{
		p1 = p, p2 = p, q1 = q, q2 = q + T;
	}
	inline char gc()
	{
		return p1 == p2 && (p2 = (p1 = p) + fread(p, 1, T, stdin), p1 == p2) ? EOF : *p1++;
	}
	inline void pc(char ch)
	{
		if (q1 == q2)
		{
			fwrite(q, 1, T, stdout);
			q1 = q;
		}
		*q1++ = ch;
	}
	~fast_io()
	{
		fwrite(q, 1, q1 - q, stdout);
	}
};
fast_io<1024768> io;

inline int read()
{
	int r = 0;
	char ch; 
	do ch = io.gc(); while (ch < 48 || ch > 57);
	do r = r * 10 + ch - 48, ch = io.gc(); while (ch >= 48 && ch <= 57);
	return r;
}

inline void putint(int x)
{
	if (x < 0) io.pc('-'), x = -x;
	if (x >= 10) putint(x / 10);
	io.pc(48 + x % 10);
}

inline void output(int x, char ch = ' ')
{
	putint(x);
	io.pc(ch);
}

inline void outputs(const char *s)
{
	while (*s) io.pc(*s++);
	io.pc('\n');
}

inline bool go(int l, int r)
{
	int L = l, R = r, sum = 0;
	while (l < r && a[l] == a[r]) ++l, --r;
	for (int i = l; i <= r; i += 2) if (a[i] != a[i + 1]) return false;
	for (int i = L; i <= R; ++i) sum += a[i];
	return (sum & 2) == 0;
}

inline bool solve(int sum)
{
	if (n & 1)
	{
		int k = 30;
		while (!(sum >> k & 1)) --k;
		for (int i = 1; i <= n; ++i)
		{
			a[i] >>= k; a[i] &= 1;
		}
		if (!a[1] && !a[n]) return false;
		return (a[n] && go(1, n - 1)) || (a[1] && go(2, n));
	}
	return true;
}

int main()
{
	int T = read();
	while (T--)
	{
		n = read();
		int sum = 0;
		for (int i = 1; i <= n; ++i) a[i] = read(), sum ^= a[i];
		if (!sum)
		{
			outputs("Draw");
		}
		else
		{
			outputs(solve(sum) ? "First" : "Second");
		}
	}
	return 0;
}

About the author

Qingyu

qwq

Add Comment

By Qingyu

Qingyu

qwq

Follow Me