Zenefits CodeSprint：Knight or Knave

题意是一堆人，从1到n编号，每个人i说一句话，x。x是正数表示i说x君是个好人，x是负数表示i说x君是坏人。问这个群体中最多能有多少好人，把这种情况用字典序的方式输出(好人用A表示，坏人用B表示)，希望我把题意说清楚了。

又做了一道Hackerrank上一道很好玩的题目，做的时候怎么都想不出来。。。

但看完了题解之后，又发现这个题目。。。

其实这个思路以前做并查集的时候有过，就是每个人就两种可能，即每个点就两种状态，那就对每个点再增加一个点，i增加一个点，i+n。这两个点始终都是对立的关系，如果i是好人，那么i+n一定是坏人。当时也想到dfs了，就是想把这个类的人归到一起去，比方说i是好人，i说j是好人，j说k是好人，那么就会希望i、j、k搞到一起去。这个时候就发挥了增加这个点的作用了，i比如是好人，i说j是坏人，那这个意思也就是i说j+n是坏人，i和j+n要搞到一起去，我靠，和并查集的一些题一样啊。。。。

后面就是查各个集的人数，胜利即是正义，人多即是正义。

官方题解代码：

#pragma warning(disable:4996)

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

using namespace std;

const int mx = 300003;

int n;

int norma(int x)

{

	if (x < 0)

		return abs(x) + n;

	else

		return x;

}

int inv(int x)

{

	x = norma(x);

	if (x > n)

		return x - n;

	else

		return x + n;

}

vector<int>g[2 * mx];

int kc[mx];

int color[mx];

int flag[mx];

void call(int u, int mar)

{

	if (color[u])

		return;

	color[u] = mar;

	if (u <= n)

		kc[mar]++;

	for (int i = 0; i < g[u].size(); i++)

	{

		int v = g[u][i];

		call(v, mar);

	}

}

void addedge(int u, int v)

{

	g[u].push_back(v);

}

int main()

{

	//freopen("i.txt", "r", stdin);

	//freopen("o.txt", "w", stdout);

	int t, u, v, ass;

	int invu, invt;

	cin >> t;

	while (t--)

	{

		memset(kc, 0, sizeof(kc));

		memset(color, 0, sizeof(color));

		cin >> n;

		for (int i = 1; i <= 2 * n + 1; i++)

		{

			g[i].clear();

		}

		for (int i = 1; i <= n; i++)

		{

			u = i;

			cin >> v;

			v = norma(v);

			addedge(u, v);

			addedge(v, u);

			invu = inv(u);

			invt = inv(v);

			addedge(inv(u), inv(v));

			addedge(inv(v), inv(u));

		}

		ass = 0;

		for (int i = 1; i <= n * 2; i++)

		{

			if (!color[i])

			{

				ass++;

				call(i, ass);

			}

		}

		memset(flag, 0, sizeof(flag));

		for (int i = 1; i <= n; i++)

		{

			u = i;

			v = inv(i);

			u = color[u];

			v = color[v];

			if (!flag[u] && !flag[v])

			{

				if (kc[u] >= kc[v])//查数量，贪心，数量多的为好人

				{

					flag[u] = 1;

					flag[v] = 2;

				}

				else

				{

					flag[u] = 2;

					flag[v] = 1;

				}

			}

		}

		for (int i = 1; i <= n; i++)

		{

			if (flag[color[i]] == 1)

				cout << "A";

			else

				cout << "B";

		}

		cout << endl;

	}

	//system("pause");

	return 0;

}

巴特西

Zenefits CodeSprint：Knight or Knave

最新文章

热门文章