//
问题 G: 4-adjacent
时间限制: 1.000 Sec 内存限制: 128 MB题目描述
We have a sequence of length N, a=(a1,a2,…,aN). Each ai is a positive integer.
Snuke's objective is to permute the element in a so that the following condition is satisfied:
For each 1≤i≤N?1, the product of ai and ai+1 is a multiple of 4.
Determine whether Snuke can achieve his objective.Constraints
2≤N≤10e5
ai is an integer.
1≤ai≤10e9
输入
Input is given from Standard Input in the following format:
N
a1 a2 … aN
输出
If Snuke can achieve his objective, print Yes; otherwise, print No.
样例输入 Copy
3
1 10 100
样例输出 Copy
Yes
提示
One solution is (1,100,10).
//
#include<bits/stdc++.h>
using namespace std;int main()
{int n,a,cnt_1,cnt_2,cnt_4;while( ~scanf("%d",&n) ){cnt_1=cnt_2=cnt_4=0; // 初始化while( n-- ){scanf("%d",&a);if( a%4==0 ) cnt_4++;else if( a%2==0 ) cnt_2++;else cnt_1++;}if( cnt_4+1<cnt_1 || ( cnt_4+1==cnt_1 && cnt_2 ) ) printf("No\n");else printf("Yes\n");}return 0;
}
//
find:
01 思维题 相邻两项的乘积为 4 的倍数 即存在因子 1*4=4 2*2=4
02 找到特殊数据 ( 不止一种 )01: 1 4 1 4 1 恰好 cnt_4+1 == cnt_1 时 (Yes) —— cnt_4+1 < cnt_1 (No)02: 1 2 2 4 1 易知 因子 2 只能挨着 因子 4 —— cnt_4+1 == cnt_1 && cnt_2 != 0 (No)补集思想 列举完反例 剩下的都是正确的