Codeforces Round #258 (Div. 2)[ABCD]

ACM

题目地址:Codeforces Round #258 (Div. 2)

A - Game With Sticks

题意： 

Akshat and Malvika两人玩一个游戏，横竖n,m根木棒排成#型，每次取走一个交点，交点相关的横竖两条木棒要去掉，Akshat先手，给出n,m问谁赢。

分析： 

水题，非常明显无论拿掉哪个点剩下的都是(n-1,m-1)，最后状态是(0,x)或(x,0)，也就是拿了min(n,m)-1次，推断奇偶就可以。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        A.cpp

*  Create Date: 2014-07-24 23:32:17

*  Descripton:

*/

#include <cstdio>

#include <algorithm>

using namespace std;

const int N = 0;

int a, b;

int main() {

	scanf("%d%d", &a, &b);

	if (min(a, b) % 2) {

		puts("Akshat");

	} else {

		puts("Malvika");

	}

	return 0;

}

---

B - Sort the Array

题意： 

给一个序列，求是否可以通过翻转中间一段数使得整个序列递增，并给翻转区间。

分析： 

数为10^5个，所以直接排序，然后找出区间验证就可以。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        B.cpp

*  Create Date: 2014-07-24 23:49:35

*  Descripton:

*/

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int n, beg, end, flag;

int a[N], b[N];

bool cont;

int main() {

	scanf("%d", &n);

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

		scanf("%d", &a[i]);

		b[i] = a[i];

	}

	sort(b, b + n);

	beg = 0;

	end = n - 1;

	while (beg < n && a[beg] == b[beg])

		beg++;

	while (end >= 0 && a[end] == b[end])

		end--;

	if (beg == n) {

		printf("yes\n");

		printf("1 1\n");

		return 0;

	}

	flag = true;

	for (int i = 0; i <= end - beg; i++) {

//		cout << b[beg + i] << ' ' << a[end - i] << endl;

		if (b[beg + i] != a[end - i]) {

			flag = false;

			break;

		}

	}

	if (flag) {

		printf("yes\n");

		printf("%d %d\n", beg + 1, end + 1);

	} else {

		printf("no\n");

	}

	return 0;

}

---

C - Predict Outcome of the Game

题意： 

三支球队要进行n场足球比赛，已经进行了k场，已知一二两队胜局相差d1，二三两队胜局相差d2，问接下去有没可能出现三队胜局都一样，也就是平局的情况。

分析： 

我们仅仅知道是相差d1,d2，而不知道是那边比較多，所以有四种情况，推断四种情况即可了：

1. 推断已比赛场数的合法性： 推断已经进行的比赛场数s是否已经超过k了，假设没有超过，推断(k-s)能否被3整除
2. 推断剩余场数： 推断剩余场数能否把三队胜局填平，假设能够，看扣掉填平后的剩余场数能否被3整除。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        C.cpp

*  Create Date: 2014-07-25 00:34:20

*  Descripton:

*/

#include <iostream>

using namespace std;

typedef long long ll;

ll t, k, n, d1, d2, md;

bool jg(ll a, ll b, ll c) {

	ll s = a + b + c;

	if (k < s || (k - s) % 3)

		return 0;

	ll  t = n - k - (3 * max(max(a, b), c) - s);

	if (t < 0 || t % 3)

		return 0;

	return 1;

}

int main() {

	cin >> t;

	while (t--) {

		cin >> n >> k >> d1 >> d2;

		md = max(d1, d2);

		if (jg(0, d1, d1 + d2) ||

			jg(d1 + d2, d2, 0) ||

			jg(d1, 0, d2) ||

			jg(md - d1, md, md - d2))

			cout << "yes" << endl;

		else

			cout << "no" << endl;

	}

	return 0;

}

---

D - Count Good Substrings

题意： 

由a和b构成的字符串，假设压缩后变成回文串就是Good字符串。问一个字符串有几个长度为偶数和奇数的Good字串。

分析： 

能够发现，无论怎么样，压缩后的字符串是...ababab...这样的格式的，所以首尾字符同样，那就是Good字符串了。 

我们还要证明下随意good字串的首尾字符串都是一样的，这不难。 

奇偶问题的话，能够发现随意两个奇数位置上的a及中间的字符组成的字符串都是奇数长度的，同理偶数位置和b。奇数位置上的a和偶数位置上的a的字符串是偶数长度的。

代码：

/*

*  Author:      illuz <iilluzen[at]gmail.com>

*  File:        D.cpp

*  Create Date: 2014-07-25 10:49:46

*  Descripton:

*/

#include <iostream>

#include <string>

#define f(a) (a*(a-1)/2)

using namespace std;

string s;

long long r[2][2];

int main() {

	cin >> s;

	for (int i = 0; s[i]; i++)

		r[i&1][s[i]-'a']++;

	cout << r[0][0] * r[1][0] + r[0][1] * r[1][1] << ' '

	  	<< f(r[0][0]) + f(r[0][1]) + f(r[1][0]) + f(r[1][1]) + s.length() << endl;

	return 0;

}

---

总结：Orz帆神AK，E题涉及逆元，回头补上～