AtCoder Grand Contest 039

老刷水题也没有意思，难的题又做不出来，只能捡些题来做，果然菜是原罪。

A. Connection and Disconnection

单独考虑全是一种字母的情况。
如果不是，就把每个字符串分成三段，前中后，如果前和后一样，再另行计算。细节较多，慢慢写不难。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 605

using namespace std;

int main()
{
	string s;
	long long k, front, beh, beh_num = 0;
	cin >> s;
	cin >> k;

	front = 0, beh = s.size() - 1;

	for (long long i = 1; i < s.size(); i++)
		if (s[i] != s[i - 1])
		{
			front = i;
			break;
		}

	for (long long i = s.size() - 1; i >= 1; i--)
		if (s[i - 1] != s[i])
		{
			beh_num = s.size() - i;
			beh = i;
			break;
		}

	if (front == 0 || beh_num == 0)
	{
		cout << k*s.size() / 2 << endl;
		return 0;
	}

	long long tot = 0;
	tot += front / 2;
	tot += beh_num / 2;

	long long mid = 0;

	for (long long i = front; i < beh; i++)
	{
		long long num = 1;
		while (1)
		{
			if (s[i] == s[i + num])
				num++;
			else
				break;
		}
		mid += num / 2;
		i = i + num - 1;
	}

	if (s[0] == s[s.size() - 1])
		tot += (k - 1)*((front + beh_num) / 2) + k * mid;
	else
		tot = tot * k + k * mid;

	cout << tot << endl;

	return 0;
}

B. Graph Partition

所有下标为奇数的集合里的点必两两不相邻，偶数同理，故满足条件的无向图必为二分图，所以可用bfs染色的方法判断。之后观察到集合的数量不可能超过图的直径+1，假设直径起点为s，终点为t，把距离s距离为i的放在第i+1个集合，必然满足条件，因此最终的答案就是图的直径+1，跑一遍floyd求最大值就行。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 605

int dis[M][M], color[M];

using namespace std;

bool bfs(int s, int n)
{
	queue<int> q;
	q.push(s);
	color[s] = 1;
	while (!q.empty())
	{
		int from = q.front();
		q.pop();
		for (int i = 1; i <= n; i++)
		{
			if (dis[from][i] != (int)1e9 && color[i] == -1)
			{
				q.push(i);
				color[i] = !color[from];									//染成不同的颜色   
			}
			if (dis[from][i] != (int)1e9 && color[from] == color[i])		//颜色有相同，则不是二分图   
				return false;
		}
	}
	return true;
}

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

	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			if (s[j] == '1')
				dis[i][j + 1] = 1;
			else
				dis[i][j + 1] = (int)1e9;
		}
	}

	memset(color, -1, sizeof(color));

	bool flag = false;
	for (int i = 1; i <= n; i++)
		if (color[i] == -1 && !bfs(i, n))
		{
			cout << -1 << endl;
			return 0;
		}

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

	int maxl = -1;
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
		{
			if (dis[i][j] == 1e9)
			{
				cout << -1 << endl;
				return 0;
			}
			maxl = max(maxl, dis[i][j]);
		}

	cout << maxl + 1 << endl;

	return 0;
}

感觉AGC能做出前两道就不错了，ABC保4争5，AGC保1争2？
剩下的题还没看，听说很难，就这样吧。