盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5143 NPY and arithmetic progression(枚举+想法)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5143

题意

有1,2,3,4四种数字,个数分别为a1,a2,a3,a4。现在要把这些数分成很多组,其中每组都是等差数列,且每组的个数必须大于等于3。问有没有解

思路

观察可以发现等差数列只可能是(1,2,3)(1,2,3,4)(2,3,4)以及3个以上相同的数字。然后三个以上的(1,2,3)可以化为多个(1,1,1)(2,2,2)(3,3,3)和j个(1,2,3)。其中j≤2,其他的相同。所以可以枚举这三种特殊的等差数列的个数,剩下的1,2,3,4的个数≥3或者等于0一定可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define INF 1 << 30
#define fi first
#define se second
#define debug puts("=====================");
using namespace std;
typedef long long ll;
int x;
int main () {
int t;
cin>>t;
while(t--) {
scanf("%d", &x);
int m = 0;
while(x) {
m = m * 2 + x % 2;
x /= 2;
}
printf("%d\n", m);
}
return 0;
}