目录

幸运的袋子

计算日期到天数转换

幸运的袋子

链接:幸运的袋子_牛客题霸_牛客网 (nowcoder.com)

来源:牛客网

描述

一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。
例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1 + 2 + 3 > 1 * 1 * 2 * 3
你可以适当从袋子里移除一些球(可以移除0个,但是别移除完)，要使移除后的袋子是幸运的。现在让你编程计算一下你可以获得的多少种不同的幸运的袋子。

输入描述：

第一行输入一个正整数n(n ≤ 1000) 第二行为n个数正整数xi(xi ≤ 1000)

输出描述：

输出可以产生的幸运的袋子数

示例1

输入：

3
1 1 1

输出：

2

题解: 本题的本质是求符合条件的子集个数

思路:

每次从全集中选择若干元素（小球）组成子集（袋子）。对于任意两个正整数a,b如果满足 a+b>ab，则必有一个数为1.可用数论证明：设a=1+x,b=1+y，则1+x+1+y>(1+x)(1+y)，---> 1>xy，则x，y必有一个为0，即a,b有一个为1.推广到任意k个正整数，假设a1,a2,...ak，如果不满足给定条件，即和sum小于等于积pi。如果此时再选择一个数b,能使其满足sum+b > pib，则，b必然为1，且为必要非充分条件。反之，如果选择的b>1，则sum+b <= pi*b，即a1,a2,...,ak,b不满足给定条件。因此，将球按标号升序排序。每次从小到大选择，当选择到a1,a2,...,ak-1时满足给定条件，而再增加选择ak时不满足条件（ak必然大于等于max(a1,a2,...,ak-1)），继续向后选择更大的数，必然无法满足！此时不必再继续向后搜索。如果有多个1，即当k=1时，sum(1)>pi(1)不满足，但下一个元素仍为1，则可以满足1+1>1*1， 所以要判断当前ak是否等于1，如果等于1，虽然不能满足，组合的个数不能增加，但是继续向后搜索，仍然有满足条件的可能.对于重复数字，组合只能算一个，要去重。

代码: 

#include 
#include 
#include 
using namespace std;

int count_p(vector &x, int n, int pos, int sum, int mul) {
    int count = 0;
    //循环，搜索以位置i开始所有可能的组合
    for (int i = pos; i < n; i++) {
        sum += x[i];
        mul *= x[i];
        //判断幸运与否
        if (sum > mul) {
            //找到符合要求的组合，加1，继续累加后续的值，看是否有符合要求的集合
            count += 1 + count_p(x, n, i + 1, sum, mul);
        }else if (x[i] == 1) {
            //如何不符合要求，且当前元素值为1，则继续向后搜索
            count += count_p(x, n, i + 1, sum, mul);
        }else {
            break;//回溯
            //如何sum大于multi,则后面就没有符合要求的组合了
        }
        //要搜索下一个位置之前，首先恢复sum和multi
        sum -= x[i];
        mul /= x[i];
        //去重
        //数字相同的球，没有什么区别，都只能算一个组合，所以直接跳过
        while (i < n - 1 && x[i] == x[i + 1]) {
            i++;
        }
    }
    return count;
}

int main() {
    int n;
    while (cin >> n) {
        vector x(n);
        for (int i = 0; i < n; ++i) {
            cin >> x[i];
        }
        sort(x.begin(), x.end());
        cout << count_p(x, n, 0, 0, 1) << endl;
    }
    return 0;
}

计算日期到天数转换

链接:计算日期到天数转换_牛客题霸_牛客网 (nowcoder.com)

来源:牛客网

描述

根据输入的日期，计算是这一年的第几天。

保证年份为4位数且日期合法。

进阶：时间复杂度：O(n)O(n) ，空间复杂度：O(1)O(1) 

输入描述：

输入一行，每行空格分割，分别是年，月，日

输出描述：

输出是这一年的第几天

示例1

输入：

2012 12 31

输出：

366

复制

示例2

输入：

1982 3 4

输出：

63

题解 本题考察日期类，我们课堂已经深入讲解过日期类。

解题

用一个数组存放每月的累积天数 输入的日期天数= 当月的天数 + 当月之前的累积天数 如果包含二月，再去判 断是否为闰年，如果是闰年，再加1天即可 代码

#include 
using namespace std;
//判断闰年
int is_year (int year) {
    return  (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}
//根据年和月获取相应月份的天数
int get_month(int year, int month) {
    int d[13] = {29, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    if (month == 2 && is_year(year)) {
        month = 0;
    }
    return d[month];
}
//根据年月日获取相应的这一年的第几天
int is_day(int year, int month, int day) {
    int dat = 0;
    for (int i = 1; i < month; ++i) {
        dat += get_month(year, i);
    }
    dat += day;
    return dat;
}

int main() {
    int year, month, day;
    int m = 0;
    while (cin >> year >> month >> day) {
        m = is_day(year, month, day);
        cout << m <