CF766 ABCDE

A 找最长非公共子序列..如果两串不是完全相同显然就是最长的那个

/** @Date    : 2017-04-15 19:52:34

  * @FileName: 766A.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoundEarlf@gmail.com)

  * @Link    : https://github.com/Lweleth

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int main()

{

	string a, b;

	cin >> a >> b;

	if(a == b)

		printf("-1\n");

	else printf("%d\n", max(a.length(), b.length()));

    return 0;

}

B 给出一些数问里面是否存在三个数能构成三角形排个序遍历一遍即可递增数列下，连续的三个数是最可能满足条件的情况了

/** @Date    : 2017-04-15 20:01:31

  * @FileName: 766B.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoundEarlf@gmail.com)

  * @Link    : https://github.com/Lweleth

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int a[N];

int main()

{

	int n;

	while(cin >> n)

	{

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

			scanf("%d", a + i);

		sort(a, a + n);

		int flag = 0;

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

		{

			if(flag)

				break;

			if(a[i] + a[i - 1] > a[i + 1])

				flag = 1;

		}

		if(flag)

			printf("YES\n");

		else printf("NO\n");

	}

    return 0;

}

题意：给出一字符串，26个字母对应了最大分割长度b['a'~'z']（即分割完长度不超过b[i]），问在里面做分割，满足条件的分割有多少种，并取模1e9+7，以及分割后里面最小的长度。

思路：DP。枚举位置，从该位置向前推，直到不满足条件位置为止，期间不断转移dp[i]+=dp[j - 1],并更新最大数量和最小长度即可

/** @Date    : 2017-04-16 00:27:49

  * @FileName: 766B DP.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoundEarlf@gmail.com)

  * @Link    : https://github.com/Lweleth

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

const int mod = 1e9+7;

char a[1500];

int dp[1500];

int dp2[1500];

int len[50];

int main()

{

	int n;

	while(cin >> n)

	{

		scanf("%s", a + 1);

		for(int i = 0; i < 26; i++)

			scanf("%d", len + i);

		int ma = -1;

		int mi = INF;

		MMF(dp);

		dp[0] = 1;//代表0~i的分割数

		dp2[0] = 0;//代表0~i里的最小分割长度

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

		{

			dp2[i] = INF;

			mi = INF;

			int le = INF;

			for(int j = i; j >= 1; j--)//枚举所有可能分割的位置

			{

				le = min(le, min(len[a[i] - 'a'], len[a[j]-'a']));//满足分割后字母对应 字符串长度的限制

				if(le < i - j + 1)

					break;

				dp[i] = (dp[i] + dp[j - 1]) % mod;//对每个可分割的位置进行转移

				mi = min(mi, dp2[j - 1]);

				ma = max(ma, i - j + 1);

			}

			dp2[i] = mi + 1;

		}

		printf("%d\n%d\n%d\n", dp[n], ma, dp2[n]);

	}

    return 0;

}

题意：给出一些词语间的关系，问里面每个关系是否成立。就是个种类并查集

思路：可以用偏移量写，也可以用秩来写。

/** @Date    : 2017-04-16 16:14:15

  * @FileName: 766D 种类并查集.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoundEarlf@gmail.com)

  * @Link    : https://github.com/Lweleth

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

map<string, int>mir;

int fa[N];

int rk[N];

int n, m, q;

int find(int x)

{

	int df;

	if(fa[x] == x)

		return x;

	df = fa[x];

	fa[x] = find(fa[x]);

	rk[x] = (rk[x] + rk[df]) & 1;

	return fa[x];

}

int join(int x, int y, int f)

{

	int a = find(x);

	int b = find(y);

	//cout << a << "~" << b;

	if(a != b)

	{

		if(f == 3)//判断用

			return 2;

		fa[b] = a;

		rk[b] = (f + rk[x] - rk[y] + 2) % 2;

		return 1;

	}

	else

	{

		int t = (rk[x] - rk[y] + 2) % 2;

		//cout <<"$"<< t << endl;

		if(f == 3)//判断用

			return (t==0);

		if(t == f)

			return 1;

		else

			return 0;

	}

}

int main()

{

	while(cin >> n >> m >> q)

	{

		mir.clear();

		string x, y;

		int t;

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

		{

			fa[i] = i, rk[i] = 0;

			cin >> x;

			mir[x] = i;

		}

		for(int i = 0; i < m; i++)

		{

			scanf("%d", &t);

			t -= 1;

			cin >> x >> y;

			int ans = join(mir[x], mir[y], t);

			printf("%s\n", ans?"YES":"NO");

		}

		for(int i = 0; i < q; i++)

		{

			cin >> x >> y;

			int ans = join(mir[x], mir[y], 3);

			if(ans == 2)

				printf("3\n");

			else

				printf("%d\n", ans?1:2);

		}

	}

    return 0;

}

题意：给出一棵树，求所有节点和其它节点的距离和（距离和定义为异或和）

思路：对所有节点的值按二进制分解（异或和的性质）,枚举所有二进制位，并储存所有节点权值在当前位下1或0,dfs一遍转移所有0和1，最后统计即可。其中dp[i][0]代表以i为根的所有子节点拥有的0个数。那么对于当前节点为now,下一个节点为nextp的异或和为1的情况数为sum += dp[nextp][0]*dp[now][1]+dp[nextp][1]*dp[now][0]，最后答案为对每一位 sum * (1 << i) 求和

/** @Date    : 2017-04-16 20:55:11

  * @FileName: 766E 树形DP.cpp

  * @Platform: Windows

  * @Author  : Lweleth (SoundEarlf@gmail.com)

  * @Link    : https://github.com/Lweleth

  * @Version : $Id$

  */

#include <bits/stdc++.h>

#define LL long long

#define PII pair

#define MP(x, y) make_pair((x),(y))

#define fi first

#define se second

#define PB(x) push_back((x))

#define MMG(x) memset((x), -1,sizeof(x))

#define MMF(x) memset((x),0,sizeof(x))

#define MMI(x) memset((x), INF, sizeof(x))

using namespace std;

const int INF = 0x3f3f3f3f;

const int N = 1e5+20;

const double eps = 1e-8;

int n, x, y;

int a[N];

vectorvt[N];

int bit[N];

int dp[N][2];

LL dfs(int s, int pre)

{

	dp[s][0] = dp[s][1] = 0;

	dp[s][bit[s]]++;

	LL sum = bit[s];

	//ans += a[s];

	for(int i = 0; i < vt[s].size(); i++)

	{

		int np = vt[s][i];

		if(np == pre)

			continue;

		sum += dfs(np, s);

		sum += dp[s][0] * dp[np][1] + dp[s][1] * dp[np][0];

		//cout << sum << endl;

		dp[s][bit[s]] += dp[np][0];

		dp[s][bit[s] ^ 1] += dp[np][1];

	}

	return sum;

}

int main()

{

	while(cin >> n)

	{

		MMF(dp);

		LL ans = 0;

		vt[0].clear();

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

			scanf("%d", a + i), vt[i].clear();

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

		{

			scanf("%d%d", &x, &y);

			vt[x].PB(y);

			vt[y].PB(x);

		}

		for(int i = 0; i < 21; i++)// 对每一位上的1和0进行 统计

		{

			for(int j = 1; j <= n; j++)//对每个节点的数进行分解

			{

				if(a[j] & (1 << i))

					bit[j] = 1;

				else bit[j] = 0;

			}

			ans += dfs(1, 0) * (1 << i);

		}

		printf("%lld\n", ans);

	}

    return 0;

}

巴特西

CF766 ABCDE

最新文章

热门文章