hdu 5143 NPY and arithmetic progression（暴力+思维）

NPY and arithmetic progression Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 864 Accepted Submission(s): 281

Problem Description NPY is learning arithmetic progression in his math class. In mathematics, an arithmetic progression (AP) is a sequence of numbers such that the difference between the consecutive terms is constant.(from wikipedia) He thinks it's easy to understand,and he found a challenging problem from his talented math teacher: You're given four integers, , which are the numbers of 1,2,3,4 you have.Can you divide these numbers into some Arithmetic Progressions,whose lengths are equal to or greater than 3?(i.e.The number of AP can be one) Attention: You must use every number exactly once. Can you solve this problem?

Input The first line contains a integer T — the number of test cases (). The next T lines,each contains 4 integers .

Output For each test case,print "Yes"(without quotes) if the numbers can be divided properly,otherwise print "No"(without quotes).

Sample Input 3

1 2 2 1

1 0 0 0

3 0 0 0

Sample Output Yes No Yes Hint In the first case,the numbers can be divided into {1,2,3} and {2,3,4}. In the second case,the numbers can't be divided properly. In the third case,the numbers can be divided into {1,1,1}.

题意：一个数组里只有1 2 3 4四种元素，问能不能构成长度大于3等差数列（可能不止一个）且没有剩余

思路：不难发现只有四种情况

1 2 3

2 3 4

1 2 3 4

111 222 333 444

对于1 2 3 4任何一个数，例如1

它被用到只有1 2 3 /1 2 3 4/1 1 1这三种情况

对于前两者的任何一个，如果数量大于等于3，就可以构成111的等差数列，所以只需考虑前两者数量为0 1 2的情况

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
	char ch = getchar(); ll s = 0, w = 1;
	while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
	while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
	return s * w;
}
inline void write(ll x)
{
	if (x < 0)putchar('-'), x = -x;
	if (x > 9)write(x / 10);
	putchar(x % 10 + 48);
}
ll t=read();
inline bool judge(ll a,ll b,ll c,ll d)
{
    // 1 2 3  2 3 4  1 2 3 4
    for(rg i=0;i<3;i++)
    {
        for(rg j=0;j<3;j++)
        {
            for(rg k=0;k<3;k++)
            {
                if(((!(a-i-k))||(a-i-k)>=3)&&((!(b-i-j-k))||(b-i-k-j)>=3)&&((!(c-i-j-k))||(c-i-k-j)>=3)&&((!(d-j-k))||(d-k-j)>=3))
                {
                    return 1;
                }
            }
        }
    }
    return 0;
}
int main()
{
	while(t--)
    {
    ll a=read(),b=read(),c=read(),d=read();
    judge(a,b,c,d)?cout<<"Yes"<<endl:cout<<"No"<<endl;
    }
	return 0;
}