Codeforces Round #332 (Div. 2)

水 A - Patrick and Shopping

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

int main(void)	{
	int d1, d2, d3;
	scanf ("%d%d%d", &d1, &d2, &d3);
	printf ("%d
", min (min (2 * (min (d1, d2) + d3), 2 * (d1 + d2)), d1 + d2 + d3));

	return 0;
}

构造(坑) B - Spongebob and Joke

题目不难,但是有坑点:如果可能Ambiguity的话不能直接break,因为可能是Impossible

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

const int N = 1e5 + 5;
int a[N], f[N], b[N];
struct Pos	{
	int cnt, id;
}p[N];

int main(void)	{
	int n, m;	scanf ("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)	{
		scanf ("%d", &f[i]);
		p[f[i]].cnt++;	p[f[i]].id = i;
	}
	for (int i=1; i<=m; ++i)	{
		scanf ("%d", &b[i]);
	}
	int ans = 0;	//-1 Impossible 1 Ambiguity 0 Possible
	for (int i=1; i<=m; ++i)	{
		if (p[b[i]].cnt == 0)	{
			ans = -1;	break;
		}
		else if (p[b[i]].cnt > 1)	{
			ans = 1;	//break;
		}
		else	{
			a[i] = p[b[i]].id;
		}
	}
	if (ans == -1)	puts ("Impossible");
	else if (ans == 1)	puts ("Ambiguity");
	else	{
		puts ("Possible");
		for (int i=1; i<=m; ++i)	{
			printf ("%d%c", a[i], i == m ? '
' : ' ');
		}
	}

	return 0;
}

贪心 C - Day at the Beach

预处理出前缀最大值和后缀最小值

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

const int N = 1e5 + 5;
int a[N];
int pmx[N], pmn[N];

inline int Max(int a, int b)	{
	if (a > b)	return a;
	else	return b;
}

inline int Min(int a, int b)	{
	if (a < b)	return a;
	else	return b;
}

int main(void)	{
	int n;	scanf ("%d", &n);
	for (int i=1; i<=n; ++i)	{
		scanf ("%d", &a[i]);
		pmx[i] = Max (pmx[i-1], a[i]);
		//printf ("i: %d mx: %d
", i, pmx[i]);
	}
	pmn[n+1] = 0x3f3f3f3f;
	for (int i=n; i>=1; --i)	{
		pmn[i] = Min (pmn[i+1], a[i]);
		//printf ("i: %d mx: %d
", i, pmx[i]);
	}
	if (n == 1)	{
		puts ("1");	return 0;
	}
	int ans = 0, i = 1;
	while (i < n)	{
		while (i < n && pmx[i] > pmn[i+1])	{
			i++;
		}
		//printf ("now: %d
", i);
		if (i == n)	{
			ans++;	break;
		}
		else	{
			ans++;	i++;
			if (i == n)	{
				ans++;	break;
			}
		}
	}
	printf ("%d
", ans);

	return 0;
}

找规律+暴力 D - Spongebob and Squares

题意:问有x个不同的正方形的方案数

分析:x = n * m + (n - 1) * (m -1) + ... + 1 * (m - (n-1)) = (-n^3 + 3mn^2 + (3m+1)*n ))/ 6, 可以想象成2 * 2的正方形比1*1的在行上少了1种可能,在列上也少了1种可能,以此类推.然后暴力枚举判断

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

typedef long long ll;

ll get_m(ll x, ll n)	{
	ll ret = (2 * x + (n * n * n - n) / 3) / (n * n + n); 
	return ret;
}

ll cal(ll n, ll m)	{
	ll ret = -n * n * n + 3 * (n * n + n) * m + n;
	ret /= 6;
	return ret;
}

int main(void)	{
	set<pair<ll, ll> > S;
	ll x;	scanf ("%lld", &x);
	for (ll i=1; i<=3000000; ++i)	{
		ll m = get_m (x, i);
		if (m < i)	break;
		if (cal (i, m) == x)	{
			S.insert (make_pair (i, m));
			if (i != m)	{
				S.insert (make_pair (m, i));
			}
		}
	}
	set<pair<ll, ll> >::iterator it;
	printf ("%d
", (int) S.size ());
	for (it=S.begin (); it!=S.end (); ++it)	{
		printf ("%lld %lld
", it->first, it->second);
	}

	return 0;
}

Codeforces Round #332 (Div. 2)

相关推荐