Codeforces Round #200 (Div. 2) 水题4道～

今晚是第200场，在div2水了几题水题。。。

第三题始终找不到思路，还是赛后做的。。。

嘛，这次总算是做出了三题，还没被hack，感觉还不错，不过这次实在太水了，rating没降实在不错～

姑且贴下代码吧～

A - Magnets

题意：01和10代表一个磁铁的两种摆法，1,0表示正负极，同性相斥异性相吸，问排成一排后会变成几组磁铁。

简单模拟。。。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        A.cpp
*  Create Date: 2013-09-14 23:29:09
*  Descripton:  simulate 
*/

#include <iostream>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
	int n, t, tt, sum = 1;
	cin >> n;
	cin >> t;
	rep(i, n - 1) {
		cin >> tt;
		if (tt == t)
			continue;
		else {
			t = tt;
			sum++;
		}
	}
	cout << sum << endl;
	return 0;
}

B - Simple Molecules

有关化学的背景。。。谷歌翻译了看了好久，最后还是去看原文了。。。

题意：三个原子构成一个分子，原子键的连接规则是一定得全部原子都联通，且不能自己连自己。给出三个原子各连出了几条键，原子间的连键情况。

画下图找下规律就出来了。。。我也说不清怎么推出了，看代码。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        B.cpp
*  Create Date: 2013-09-14 23:50:09
*  Descripton:  greedy 
*/

#include <cstdio>
#include <iostream>
using namespace std;

int main() {
	int a, b, c, sum, M, r[3];
	cin >> a >> b >> c;
	sum = a + b + c;
	M = max(a, max(b, c));
	if (sum - M >= M && ((sum - M) - M) % 2 == 0) {
		int ta = ((sum - M) - M) / 2;
		if (a >= b && a >= c) {
			r[1] = ta;
			r[0] = b - ta;
			r[2] = c - ta;
		}
		else if (b >= a && b >= c) {
			r[2] = ta;
			r[0] = a - ta;
			r[1] = c - ta;
		}
		else {
			r[0] = ta;
			r[1] = b - ta;
			r[2] = a - ta;
		}
		printf("%d %d %d\n", r[0], r[1], r[2]);
	}
	else printf("Impossible\n");
	return 0;
} 

C - Rational Resistance

题意：电阻可以串联并联，然后给出目标电阻a/b，求最少需要几个电阻才能达到目标电阻。

模拟gcd即可，比赛时没想出来，orz各位大神～

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        C.cpp
*  Create Date: 2013-09-15 10:26:31
*  Descripton:  simulate 
*/

#include <iostream>
using namespace std;

int main() {
	long long a, b, t, cnt = 0;
	cin >> a >> b;
	while (b) {
		cnt += a / b;
		t = a % b;
		a = b;
		b = t;
	}
	cout << cnt << endl;
	return 0;
}

D - Alternating Current

比赛时cf由于太卡了，比赛延长了10分钟。

我做到第三题时卡住了，没有思路，于是准备放弃治疗了，去洗了趟澡回来后发现大家都说D太水，于是我稍微看了一下，5分钟敲完过掉了 = =。。。

题意：如题目中图所示，+-线相缠绕，给出每个交叉点在上面是哪条线，问这俩线能不能拉成平行的线。（大概就是这样- -）

在草稿纸上画了一下，发现只有连续的偶数个相同的交叉点才能消掉，如果遍历模拟消掉怕会超时，于是想到了栈，每次把+-放进去时判断和栈顶元素是不是一样，一样就把栈顶弹出，不一样就压入，这样就能保证栈里面肯定没有连续相同的元素，且消掉时是成对消除的，跟括号匹配一样。。。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        D.cpp
*  Create Date: 2013-09-15 01:30:30
*  Descripton:  CF200.2 D
*/

#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

char ch;

int main() {
	stack<char> s;
	while (scanf("%c", &ch) != EOF && ch != '\n') {
		if (s.empty())
			s.push(ch);
		else {
			char t = s.top();
			if (t == ch)
				s.pop();
			else
				s.push(ch);
		}
	}
	if (s.size())
		printf("No\n");
	else
		printf("Yes\n");
	return 0;
}