Codeforces Round #373 (Div. 2)

A. Vitya in the Countryside

这回做的好差啊，a想不到被hack的数据，b又没有想到正确的思维 = =

【题目链接】A. Vitya in the Countryside

【题目类型】模拟

&题意：

一个月30天，月亮的大小分别是上面所说的规律，求输入的下一天是变大还是变小

&题解：

我想的是首先n==1的时候，我想的是一定-1，但这样是错的，因为当那一个数是15或0时，那么答案就不是-1了。

最后，只比较最后一个和倒数第二个数就好了，分4种情况。

【时间复杂度】O(n)

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define SI(N) scanf("%d",&(N))

#define rep(i,b) for(ll i=0;i<(b);i++)

int n, pre, x;

void Solve() {

	while (~SI(n)) {

		if (n == 1) {

			SI(x);

			if (x == 15) puts("DOWN");

			else if (x == 0) puts("UP");

			else puts("-1");

			continue;

		}

		rep(i, n) {

			pre = x;

			SI(x);

		}

		if (pre < x) puts(x == 15 ? "DOWN" : "UP");

		else puts(x != 0 ? "DOWN" : "UP");

	}

}

int main() {

	Solve();

	return 0;

}

B. Anatoly and Cockroaches

【题目链接】B. Anatoly and Cockroaches

【题目类型】思维题

&题意：

你要弄出rb交替的字符串，对于每个给出的字符，有2中俄操作：

1、把2个不同的位置交换。

2、把1个位置的染成不同的颜色、

&题解：

标准答案一共2种，r开头和b开头，即s1和s2，就只说s1时，s2同理：

把输入和s1比较，如果不同，要看是r还是b，之后记录不同时他们各个出现的次数，只有不同的位置才需要操作，假设r是6个b是3个，那么一定是3+3，因为要涂3个色，和交换3个。最后取最小值

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define rep(i,b) for(ll i=0;i<(b);i++)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

const int MAXN = 100000 + 5 ;

char s1[MAXN],s2[MAXN],buf[MAXN];

int n;

void Solve()

{

	bool f=0;

	rep(i,MAXN)

	{

		s1[i]=f?'r':'b';

		f=!f;

	}

	f=1;

	rep(i,MAXN)

	{

		s2[i]=f?'r':'b';

		f=!f;

	}

	while(~SI(n)){

		scanf("%s",buf);

		int u=0,v=0;

		int cr=0,cb=0;

		rep(i,n)

		{

			if (s1[i]!=buf[i])

			{

				s1[i]=='b'?cb++:cr++;

			}

		}

		u=max(cr,cb);

		cr=0,cb=0;

		rep(i,n)

		{

			if (s2[i]!=buf[i])

			{

				s2[i]=='b'?cb++:cr++;

			}

		}

		v=max(cr,cb);

		PI(min(u,v))

	}

}

int main()

{

	Solve();

	return 0;

}