8
31
2016
1

Codeforces Round #369 (Div.2)

感觉这个blog快要荒废了，所以还是写点什么好。。

 

A. Bus to Udayland

签到题，直接按题意模拟即可。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MaxN = 1005;
const int NL = 8;

int n;
char seats[MaxN][NL];

int main()
{
	cin >> n;

	bool found = false;
	for (int i = 1; i <= n; ++i)
	{
		cin >> seats[i];
		if (!found && seats[i][0] == 'O' && seats[i][1] == 'O')
			found = true, seats[i][0] = seats[i][1] = '+';
		if (!found && seats[i][3] == 'O' && seats[i][4] == 'O')
			found = true, seats[i][3] = seats[i][4] = '+';
	}

	if (!found)
		cout << "NO";
	else
	{
		cout << "YES\n";
		for (int i = 1; i <= n; ++i)
			cout << seats[i] << endl;
	}

	return 0;
}

 

B. Chris and Magic Square

算法比较简单就不写了。几个需要注意的细节：

（1）需要特判矩阵大小为1的情况

（2）答案<=0时输出无解

（3）虽然题目保证\(1 \le a_{i,j} \le 10^9\)，但是答案有可能超过int类型的范围

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 505;

int n;
s64 mat[MaxN][MaxN];
s64 row[MaxN], col[MaxN];
s64 diagonal[MaxN];
int empRow = -1, empCol = -1;
int anoRow = -1;

inline bool is_magic_square(const s64 &sum)
{
	for (int i = 1; i <= n; ++i)
	{
		if (row[i] != sum)
			return false;
		if (col[i] != sum)
			return false;
	}
	return diagonal[0] == sum && diagonal[1] == sum;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			mat[i][j] = getint();
			row[i] += mat[i][j];
			col[j] += mat[i][j];
			diagonal[0] += i + j == i + i ? mat[i][j] : 0;
			diagonal[1] += i + j == n + 1 ? mat[i][j] : 0;
			if (mat[i][j] == 0)
				empRow = i, empCol = j;
		}
		if (i != empRow)
			anoRow = i;
	}

	if (n == 1)
	{
		cout << 2333 << endl;
		return 0;
	}

	s64 num = row[anoRow] - row[empRow];
	mat[empRow][empCol] = num;
	row[empRow] += num;
	col[empCol] += num;
	diagonal[0] += empRow == empCol ? num : 0;
	diagonal[1] += empRow + empCol == n + 1 ? num : 0;
	cout << (num > 0 && is_magic_square(row[anoRow]) ? num : -1ll) << endl;

	return 0;
}

 

C. Coloring Trees

考虑DP。令\(f_{i, j, k}\)表示染色了前\(i\)棵树，段数为\(j\)且最后一棵树颜色为\(k\)的最小代价，转移时只需要枚举前一棵树的颜色，进行简单的讨论即可。时间复杂度\(O(nm^2k)\)。

如果在dp的同时维护\(f_{i, j}\)的前缀max和后缀max，则可以做到转移\(O(1)\)，时间复杂度\(O(nmk)\)。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 102;
const int MaxM = 102;
const s64 INF = 0x3f3f3f3f3f3f3f3fll;

int n, m, k, col[MaxN];
int cost[MaxN][MaxM];

s64 val[MaxN][MaxN][MaxM];
s64 pre[MaxN][MaxN][MaxM];
s64 suf[MaxN][MaxN][MaxM];

inline s64 get_value(int i, int j, int k)
{
	s64 u = pre[i - 1][j - 1][k - 1];
	s64 v = suf[i - 1][j - 1][k + 1];
	s64 w = val[i - 1][j][k];
	return val[i][j][k] = min(min(u, v), w) + cost[i][k];
}

int main()
{
	cin >> n >> m >> k;
	for (int i = 1; i <= n; ++i)
		col[i] = getint();
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cost[i][j] = getint();

	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= k; ++j)
			for (int k = 0; k <= m + 1; ++k)
			{
				val[i][j][k] = INF;
				pre[i][j][k] = INF;
				suf[i][j][k] = INF;
			}
	val[0][0][0] = suf[0][0][0] = 0;
	for (int i = 0; i <= m; ++i)
		pre[0][0][i] = 0;

	for (int i = 1; i <= n; ++i)
	{
		int up_to = min(i, k);
		for (int j = 1, c; j <= up_to; ++j)
		{
			if ((c = col[i]) > 0)
			{
				get_value(i, j, c);
				val[i][j][c] -= cost[i][c];
			}
			else
			{
				for (int k = 1; k <= m; ++k)
					get_value(i, j, k);
			}

			pre[i][j][0] = INF;
			for (int k = 1; k <= m; ++k)
				pre[i][j][k] = min(val[i][j][k], pre[i][j][k - 1]);
			suf[i][j][m + 1] = INF;
			for (int k = m; k > 0; --k)
				suf[i][j][k] = min(val[i][j][k], suf[i][j][k + 1]);
		}
	}

	cout << (pre[n][k][m] >= INF ? -1 : pre[n][k][m]);

	return 0;
}

 

D. Directed Roads

由于每个点只有一条出边，每个连通分量一定是\(\omicron\)形或\(\rho\)形。

我们找出图中所有的环，记环的长度分别为\(l_1, l_2, \ldots, l_k\)，那么答案可以表示为：\[2^{n - \sum_{i=1}^k l_i }  \cdot \prod_{i=1}^k 2^{l_i} - 2 \]因为对于一个环，显然只有全部翻转或全部不翻转两种方案是不合法的，而对于不在环上的边则可以任意翻转。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 200005;
const int M = 1000000007;

int n, to[MaxN];

int book[MaxN];
int length[MaxN];

int pow2[MaxN];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
		to[i] = getint();

	pow2[0] = 1;
	for (int i = 1; i <= n; ++i)
		pow2[i] = pow2[i - 1] * 2 % M;

	int total = 1, rest = n;
	for (int u = 1; u <= n; ++u)
	{
		if (book[u])
			continue;

		int now = u;
		while (true)
		{
			book[now] = u;

			int v = to[now];
			if (!book[v])
				length[v] = length[now] + 1, now = v;
			else if (book[v] < u)
				break;
			else
			{
				int cir_len = length[now] - length[v] + 1;
				total = (s64)total * (pow2[cir_len] - 2 + M) % M;
				rest -= cir_len;
				break;
			}
		}
	}

	total = (s64)total * pow2[rest] % M;

	cout << total;

	return 0;
}

 

E. ZS and The Birthday Paradox

首先特判\(  k \gt 2^n  \)的情况，此时答案一定是1。

一个显然的想法是计算没有数字相同的概率，然后用1减去这个概率。可以列出这样一个式子：\[p = \frac {\prod_{i = 0}^{k-1} {2^n - i} }  { 2^{nk} } \]那么问题就在于如何计算这个式子。

我们记\(M = 10^6 + 3\)，容易发现由于答案的分子分母需要对\(M\)取模，当\(k \ge M\)时，\(p\)的分子中必然有至少一项在模\(M\)意义下为0，也就是\(p\)的分子在模\(M\)意义下为0。因此分子只需要暴力计算即可。

剩下的问题就是求分子与分母的\(gcd\)用于化简。发现分母是2的次幂，因此只要求出分子中2的次数。由\(2^n - a \cdot 2^m  = (2^{n - m} - a) \cdot 2^m  \)可知，分子中2的次数即为\(n + \sum_{i = 1}^{k - 1}lowbit(i)\)。枚举\(lowbit(i)\)暴力统计，可以在\(O(log k)\)的时间复杂度内求出答案。

由\(gcd(a, b) = gcd(a,a-b)\)得，当\( \frac a b \)最简时，\(  \frac {b - a} b  \)也一定最简。因此这样求出来的一定是最简分数。

时间复杂度\(   O(  M +  log n + log k  ) \)。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

const int M = 1000003;

inline int modpow(int a, const s64 &n)
{
	int res = 1;
	for (int i = n % (M - 1); i; i >>= 1)
	{
		if (i & 1)
			res = (s64)res * a % M;
		a = (s64)a * a % M;
	}
	return res;
}

inline int modinv(const int &a)
{
	return modpow(a, M - 2);
}

s64 n, k;

inline int calc_lowbit_sum(const s64 &k)
{
	int ret = 0;
	for (int i = 0; 1ll << i <= k; ++i)
	{
		s64 up_to = k >> i + 1;
		if (k >> i & 1)
			++up_to;
		ret = (ret + up_to * i) % (M - 1);
	}
	return (ret + n) % (M - 1);
}

inline void get_fraction(int &num, int &den)
{
	int days = modpow(2, n);
	num = 0;
	den = modpow(days, k);
	if (k >= M)
		return;

	num = 1;
	for (int i = 0; i < k; ++i)
	{
		int ways = days + M - i;
		num = (s64)num * ways % M;
	}
}

int main()
{
	cin >> n >> k;

	if (n <= 60 && 1ll << n < k)
	{
		cout << 1 << ' ' << 1 << endl;
		return 0;
	}

	int num, den, invGcd;
	get_fraction(num, den);
	invGcd = modinv(modpow(2, calc_lowbit_sum(k - 1)));
	num = (s64)num * invGcd % M;
	den = (s64)den * invGcd % M;
	num = (den - num + M) % M;
	cout << num << ' ' << den << endl;

	return 0;
}
——By InvUsr
Category: | Tags: | Read Count: 316
Small_feed 评论 (1)
1
[回复]
eds467 说:
2016年9月03日 23:02

E题细节坑爹……最后20分钟才A……于是就挂了……


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com