CF1611A Make Even 题解

题目大意

给出一个数字, 可以进行反转的操作(选择一个区间 \([1, l]\) 并颠倒这个区间的顺序)。

询问最少多少次操作才可以让原数变成一个偶数。

解题思路

很明显的分类讨论。

偶数

如果原数是偶数就不需要反转了。

奇数

如果是奇数呢?

可以发现, 颠倒一个区间 \([1, l]\) 的顺序可以理解将 \(a_l\) 一道最前面去。

概括这个操作:

  • 把任意的一个数字转换到这个数的第一位

  • 把第一位的数字转换到第 \(l\) 位。

那问题转化为:第一位是一个偶数需要操作多少次?

可以很容易的想到在做一次区间为 \([1, n]\) (其中 \(n\) 为这个数字的长度)的操作, 第一位的偶数字就到了最后一位, 这个数不就是一个偶数了吗?

Code 实现

// the code is from zxy
#include <bits/stdc++.h>
int a[100], ai, n, f;
inline void solve() {
	scanf("%d", &n); memset(a, 0, sizeof a); ai = 0, f = 0;
	if (n % 2 == 0) {printf("0\n");return;}
	while (n)  {
		a[++ai] = n % 10;
		n /= 10;
	}
	if (a[1] % 2 == 0) {printf("0\n");return;}
	if (a[ai] % 2 == 0) {printf("1\n");return;}
	for (int i = 2; i < ai; i++) if ((a[i]) % 2 == 0) {f = 1; break;}
	if (!f) {printf("-1\n"); return;}
	printf("2\n");
	return;
}
int main() {
	int T; scanf("%d", &T);
	while (T--) solve();
	return 0;
}
上一篇:2020 ICPC Shanghai Site


下一篇:Java奇偶链表