Menu

2014ACM-ICPC亚洲区上海站

发表于 06 Oct 2019 总计 4508字 阅读时间 16分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

Rotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, n, m, ti, L;
ll ans;
char ch[10];
int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		scanf("%d%d%d", &n, &m, &ti);
		vector<vector<ll>> v(n + 9, vector<ll>(m + 9));
		for (int i = 1, nowx = 1, nowy = 1; i <= ti; ++i)
		{
			scanf("%s%d", ch, &L);
			if (ch[0] == 'R')
			{
				++v[nowx][nowy];
				--v[nowx][nowy += L];
			}
			if (ch[0] == 'L')
			{
				++v[nowx][nowy];
				--v[nowx][nowy -= L];
			}
			if (ch[0] == 'D')
				nowx += L;
			if (ch[0] == 'U')
				nowx -= L;
		}
		ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
				ans += v[i][j] * v[i][j];
			}
		printf("Case #%d: %lld\n", t, ans);
	}
}

Room Assignment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a+b<2*M，就不必取模了，取模运算耗时很高
	ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }	  //考虑a和b不在同余系内甚至为负数的情况
	ll mul(ll a, ll b) const { return add(a * b, M); }
	ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数，否则return pow(a, phi(M) - 1);
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		/*
		if (b < 0)
			b = -b, a = inv(a);
		*/
		for (a = add(a, M); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	/*
	ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); } //long double 有效位数16~18位，模数过大时慎用！
	ll mul(ll a, ll b) const //Head算法，无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
	{
		ll c = a / SM, d = b / SM;
		a %= SM, b %= SM;
		ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
		return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
	}
  ll mul(ll a, ll b) const //龟速乘
	{
		ll r = 0;
		for (a %= M; b; b >>= 1, qadd(a, a))
			if (b & 1)
				qadd(r, a);
		return r;
	}
	ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
	{
		ll x, y, d = gcd(a, M, x, y);
		return d == 1 ? add(x, M) : -1;
	}
	vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back(mul((b / d) % (M / d), x));
		for (ll i = 1; i < d; ++i)
			ans.push_back(add(ans.back(), M / d));
		return ans;
	}
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
	*/
};
struct Factorial : Mod
{
	vector<ll> fac, ifac;
	Factorial(int N, ll M) : fac(N, 1), ifac(N, 1), Mod(M)
	{
		for (int i = 2; i < N; ++i)
			fac[i] = mul(fac[i - 1], i), ifac[i] = mul(M - M / i, ifac[M % i]);
		for (int i = 2; i < N; ++i)
			ifac[i] = mul(ifac[i], ifac[i - 1]);
	}
	ll c(int n, int m)
	{
		if (m > n || m < 0 || n < 0)
			return 0;
		return mul(mul(fac[n], ifac[m]), ifac[n - m]);
	}
} F(1e5 + 9, 1e9 + 7);
ll t, n, m, k, kase, c[31], p[31], f[31][127];
int main()
{
	for (scanf("%lld", &t); t--;)
	{
		memset(f, 0, sizeof(f));
		scanf("%lld%lld%lld", &n, &m, &k);
		for (int i = 1; i <= m; ++i)
		{
			scanf("%lld", &c[i]);
			p[i] = p[i - 1] + c[i];
		}
		f[0][k] = 1;
		for (int i = 1; i <= m; ++i)
			for (int j = 0, sum = p[m] - p[i - 1]; j <= k; ++j)
				for (int l = 0; l <= j; ++l)
					F.qadd(f[i][j - l], F.mul(F.mul(f[i - 1][j], F.c(j, l)), F.c(sum - (j - l) * 2 - l, c[i] - l)));
		printf("Case #%lld: %lld\n", ++kase, f[m][0]);
	}
}

Defeat the Enemy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
pair<int, int> p[N], q[N];
int t, n, m, kase;
int main()
{
	for (scanf("%d", &t); t--;)
	{
		scanf("%d%d", &n, &m);
		multiset<int> se;
		for (int i = 0; i < n; ++i)
			scanf("%d%d", &p[i].first, &p[i].second);
		for (int i = 0; i < m; ++i)
			scanf("%d%d", &q[i].second, &q[i].first);
		sort(p, p + n);
		sort(q, q + m);
		for (int j = m - 1, i = n - 1; ~j; --j)
		{
			for (; (~i) && p[i].first >= q[j].first; --i)
				se.insert(p[i].second);
			if (se.empty())
			{
				n = -1;
				break;
			}
			auto it = se.lower_bound(q[j].second);
			if (it == se.end())
				it = se.begin(), --n;
			se.erase(it);
		}
		printf("Case #%d: %d\n", ++kase, n);
	}
}

World Cup

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int T;
LL n, m, a, b, c;

int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++)
	{
		scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c);
		if (c > a)
			swap(a, c);

		printf("Case #%d: %lld %lld\n", t,
			   max(a, b) * (n - m - 1) + max(m / 2 * (a + c) + m % 2 * max(b, c), b * m),
			   min(b, c) * (m - 1) + min((n - m) / 2 * (a + c) + (n - m) % 2 * min(a, b), (n - m) * b));
	}

	return 0;
}