3.24 CodeForces练习

A - Bear and Poker(1400)
题意：给定一堆数，可以对一个数乘以2或者乘以3多次，求是否可以把这些数变成相等的数字。
一个数可以通过分解质因数，化成一堆质数的乘积(2^a * 3^b * 5^c * 7^d...)，
要使得一堆数字乘以2和3之后的乘积相同，意味着我们只能增加2和3的指数，使得它们的幂相等，但是它们其它质因数的乘积无法改变，所有要使得它们的乘积相同，
除2和3以外的质因子的指数都要相等，我们只需要将所有数字除去2和3的质因子，然后判断是否相等即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 100005;
LL a[N];

LL gcd(LL a, LL b)
{
	return b ? gcd(b, a % b) : a;
}

int main()
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);

	while (a[1] % 2 == 0) a[1] /= 2;
	while (a[1] % 3 == 0) a[1] /= 3;

	int last = a[1];

	bool flag = true;
	for (int i = 2; i <= n; ++i)
	{
		while (a[i] % 2 == 0) a[i] /= 2;
		while (a[i] % 3 == 0) a[i] /= 3;
		if (a[i] != last)
		{
			flag = false;
			break;
		}
		else
		{
			last = a[i];
		}
	}

	if (flag)
		puts("YES");
	else
		puts("NO");


	return 0;
}

C. Remove Adjacent(贪心题)(1600)

每次从字母最大的字符开始移除

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;
const int N = 105;
string s;
int res;
bool solve()
{
	for (int i = 25; i >= 0; --i)
	{
		for (int j = 0; j < s.size(); ++j)
		{
			if (s[j] != 'a' + i)
				continue;
			if (s[j] == i + 'a')
			{
				if (j > 0)
				{
					if (s[j - 1] == s[j] - 1)
					{
						s.erase(j, 1);
						return true;
					}
				}
				if (j < s.size() - 1)
				{
					if (s[j + 1] == s[j] - 1)
					{
						s.erase(j, 1);
						return true;
					}
				}
			}
		}
	}
	return false;
}

int main()
{
	int n;
	scanf("%d", &n);
	
	cin >> s;
	while (solve())
		++res;	

	printf("%d
", res);
	return 0;
}

D. Treasure Island(1800)
分析:答案最多3种情况，我们只要堵住了(1, 2)或者(2, 1)，那么就无法到达终点，答案为1的情况是，存在一个点，使得所有能达到终点的路径都通过这个点，我们用一次dfs走到终点，将路径上能通过的点修改为障碍，如果无法走到，就输出0，否则再继续dfs一遍，如果能走，则说明答案为2，否则为1。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
const int N = 1000005;

string g[N];
int n, m;
bool dfs(int x, int y)
{
	if (x == n - 1 && y == m - 1) return true;//到达终点
	if (x >= n || y >= m) return false;//超出范围
	if (g[x][y] == '#') return false;//被堵住
	if (x || y) g[x][y] = '#';//不能堵住起点
	return dfs(x + 1, y) || dfs(x, y + 1);//只要有一条路径可以走
}

int main()
{
	scanf("%d%d", &n, &m);

	//地图
	for (int i = 0; i < n; ++i)
		cin >> g[i];

	bool flag = dfs(0, 0);
	if (!flag) puts("0");
	else
	{
		flag = dfs(0, 0);
		if (flag)
			puts("2");
		else
			puts("1");
	}
	return 0;
}