http://acm.hdu.edu.cn/showproblem.php?pid=5143
题意:
给定数字1,2,3,4.的个数每个数字能且仅能使用一次,组成多个或一个等差数列(长度大于等于3),问能否成功。
思路:
可以发现等差数列只有(123,234,1234和长度>=3的常数列),如果选择非常数数列(123,234,1234)数量大于等于3,
可以变为三个或4个常数列,例如(123,123,123)变为(111,222,333)。所以从0-2枚举选择非常数列的数量,再判断能否用常数列覆盖剩下的(如果数字长度正好为0或≤3就可以)。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 10000+5; 17 18 int a1,a2,a3,a4; 19 20 bool check(int a, int b, int c, int d) 21 { 22 if((a>=3||a==0)&&(b>=3||b==0)&&(c>=3||c==0)&&(d>=3||d==0)) return true; 23 return false; 24 } 25 26 int main() 27 { 28 //freopen("in.txt","r",stdin); 29 int T; 30 scanf("%d",&T); 31 while(T--) 32 { 33 scanf("%d%d%d%d",&a1,&a2,&a3,&a4); 34 bool flag = false; 35 if(check(a1,a2,a3,a4)) flag=true; 36 else 37 for(int i=0;i<=2;i++) 38 { 39 for(int j=0;j<=2;j++) 40 { 41 for(int k=0;k<=2;k++) 42 { 43 if(check(a1-i-k,a2-i-j-k,a3-i-j-k,a4-j-k)) flag=true; 44 } 45 } 46 } 47 if(flag) puts("Yes"); 48 else puts("No"); 49 } 50 return 0; 51 }