2017 CCPC 湘潭邀请赛

都tm快一年了我还没补这套题……再不补怕是要留给退役后乐

Problem A

把$n * (n + 1)$的矩阵补成$(n + 1) * (n + 1)$的，然后高斯消元。

Problem B

一看题解：费用流，于是这个题直接交给队友。

Problem C

又是高斯消元……

Problem D

直接输出即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 1e2 + 10;

int c[N][N], f[N][N];

int n, m, a, b;

int main(){

	while (~scanf("%d%d%d%d", &n, &m, &a, &b)){

		rep(i, 1, n){

			rep(j, 1, m) scanf("%1d", c[i] + j);

		}

		rep(i, 1, n * a){

			rep(j, 1, m * b){

				int x = (i - 1) / a + 1;

				int y = (j - 1) / b + 1;

				printf("%d", c[x][y]);

			}

			putchar(10);

		}

	}

	return 0;

}

Problem E

占坑。

Problem F

首先可以肯定的是 $f_{0} + f_{1} + f_{2} + f_{3} = m^{3}$

那么计算出其中的$3$个就可以得到剩余的$1$个。

显然$f_{0}$和$f_{3}$是比较好求的。

所以$f_{1}$和$f_{2}$求出一个，问题就解决了。

大概是……$f_{2}$比较好求？

求$f_{3}$的时候记录一下有哪些三元组是符合这个条件的。

首先枚举两个数，把他们放在$(1, 2)$，$(1, 3)$，$(2, 3)$的位置，然后枚举剩下那个数可以是什么。

首先在$a[]$中没有出现的并且在$[1, m]$中的数肯定可以放，这个直接单独计算。

枚举在$a[]$中出现过的数，得到一个新的三元组，根据题意这个三元组要么计入$f_{2}$要么计入$f_{3}$。

那么看一下是否计入了$f_{3}$，如果不在就计入$f_{2}$

坑点：可能出现$a_{i} > m$的情况。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 2e2 + 10;

const int M = 1e7 + 10;

LL f0, f1, f2, f3;

bitset <M> c, d, f;

int n, nn, m;

int tot;

int a[N], b[N];

void calc_f0(){

	rep(i, 1, n) b[i] = a[i];

	sort(b + 1, b + n + 1);

	int cnt = unique(b + 1, b + n + 1) - b - 1;

	tot = cnt;

	rep(i, 1, n) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;

	f0 = 0ll + m - cnt;

	f0 = 1ll * f0 * f0 * f0;

}

void calc_f1(){

	f1 = 1ll * m * m * m - f0 - f2 - f3;

}

void calc_f2(){

	f2 = 0;

	d.reset();

	f.reset();

	rep(i, 1, n - 1){

		rep(j, i + 1, n){

			int x = a[i] * tot + a[j];

			if (d[x]) continue;

			d.set(x);

			f2 += 0ll + m - tot;

			rep(k, 1, tot){

				int y = a[i] * tot * tot + a[j] * tot + k;

				if (!c[y]) f.set(y);

			}

		}

	}

	d.reset();

	rep(i, 1, n - 1){

		rep(j, i + 1, n){

			int x = a[i] * tot + a[j];

			if (d[x]) continue;

			d.set(x);

			f2 += 0ll + m - tot;

			rep(k, 1, tot){

				int y = k * tot * tot + a[i] * tot + a[j];

				if (!c[y]) f.set(y);

			}

		}

	}

	d.reset();

	rep(i, 1, n - 1){

		rep(j, i + 1, n){

			int x = a[i] * tot + a[j];

			if (d[x]) continue;

			d.set(x);

			f2 += 0ll + m - tot;

			rep(k, 1, tot){

				int y = a[i] * tot * tot + k * tot + a[j];

				if (!c[y]) f.set(y);

			}

		}

	}

	f2 += 0ll + f.count();

}

void calc_f3(){

	int cnt = 0;

	c.reset();

	rep(i, 1, n - 2){

		rep(j, i + 1, n - 1){

			rep(k, j + 1, n){

				int x = a[i] * tot * tot + a[j] * tot + a[k];

				c.set(x);

			}

		}

	}

	f3 = c.count();

}

int main(){

	while (~scanf("%d%d", &n, &m)){

		nn = n;

		n  = 0;

		rep(i, 1, nn){

			int x;

			scanf("%d", &x);

			if (x >= 1 && x <= m) a[++n] = x;

		}

		calc_f0();

		calc_f3();

		calc_f2();

		calc_f1();

		printf("%lld %lld %lld %lld\n", f0, f1, f2, f3);

	}

	return 0;

}

Problem G

Problem H

Problem I

Problem J

巴特西

2017 CCPC 湘潭邀请赛

最新文章

热门文章