题目
题目描述:一个长度为n+m+k包含n个数字1,m个数字2和k个数字4的数组,最多可能有多少个子序列1412?
如果一个序列是数组的子序列,当且仅当这个序列可以由数组删去任意个元素,再将数组中的剩余元素按顺序排列而成。
第一行一个整数t,表示测试用例的组数。
接下来t行每行三个整数n,m,k表示一组测试用例。
对于每组测试用例输出一行一个整数表示答案。
解析
这道题看到题一下就想到了思路,就是一道简单的数学题。
- 但是一定要记得:不要十年longlong一场空了呀。。。开始开了int,我裂开了orz
- 这道题最开始用py过不了,出题人有点不严谨了。
数学思路:
- 因为要满足1412的序列,很简单,1要在4和2前面,4要在2前面。
- 不过这里有两个1,所以1要分配到两个地方。即使靠常识我们也知道1要等分给两边咯(乘法中间最大,可以自己去证明一下)。
- 栗子:11114444444411111222。答案不就是4 * 8 * 5 * 3吗~
打代码:
- 输入。
- 把1分开。
- 计算输出。
- 哈哈哈哈看代码~
AC代码
C++
#include <iostream> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); //代码预处理区 int main() { IOS; // freopen("in.txt", "r", stdin); int T; cin >> T; while (T--) { int a, b, c; cin >> a >> b >> c; int first = a / 2, second = a / 2 + a % 2; cout << 1ll * first * c * second * b << endl; } return 0; } //函数区python
T = int(input()) for _ in range(T): n, m, k = map(int, input().split()) first = n // 2 second = n // 2 + n % 2 print(first * k * second * m)