微软秋季校园招聘编程笔试hihocoder 1399 Shortening Sequence（异或/乱搞）

题目链接分析Java code

题目链接

hihocoder 1399 Shortening Sequence

分析

开始我以为是dp,后来发现没那么难，

首先想到仅与每个数的奇偶性有关。那么我们记偶数为0，奇数为1。

那么对于这个数组来说只要有0和1同时存在我们就可以消除一对。也就是说最终仅能有一种元素存在。所以答案是元素个数多的减去小的。

Java code

import java.io.BufferedInputStream;import java.util.ArrayList;import java.util.Arrays;import java.util.Collection;import java.util.Collections;import java.util.HashMap;import java.util.HashSet;import java.util.PriorityQueue;import java.util.Scanner;public class Main {public static final int INF = 0x3f3f3f3f;public static Scanner in = new Scanner(new BufferedInputStream(System.in));public static void main(String[] args) {int n = in.nextInt();int[] a = new int[n];for(int i=0 ; i<n ; ++i)a[i] = ((in.nextInt()&1)==1?1:-1);System.out.println(new Solution(n, a).solve());}}class Solution {int N;int[] a;int[] dp;int[] last;public Solution(int n, int[] a) {super();N = n;this.a = a;this.dp = new int[N+1];last = new int[N+1];}public int solve() {int ret =0;for(int i=0 ; i<N; ++i)ret +=a[i];return Math.abs(ret);}}