首页 > 代码库 > HUST 1698 - 电影院 组合数学 + 分类思想
HUST 1698 - 电影院 组合数学 + 分类思想
http://acm.hust.edu.cn/problem/show/1698
题目就是要把一个数n分成4段,其中中间两段一定要是奇数。
问有多少种情况。
分类,
奇数 + 奇数 + 奇数 + 奇数
奇数 + 奇数 + 奇数 + 偶数
偶数 + 奇数 + 奇数 + 奇数
偶数 + 奇数 + 奇数 + 偶数
然后奇数表达成 2 * a - 1这个样子,就能列出方程。
然后就是类似于解a1 + a2 + a3 + a4 = x的问题了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> LL C(LL n, LL m) { if (n < m) return 0; //防止sb地在循环 if (n == m) return 1; //C(0,0)也是1的 LL ans = 1; LL mx = max(n - m, m); //这个也是必要的。能约就约最大 LL mi = n - mx; for (int i = 1; i <= mi; ++i) { ans = ans * (mx + i) / i; } return ans; } void work() { int n; scanf("%d", &n); LL ans = 0; if ((n + 4) % 2 == 0) ans += C((n + 4) / 2 - 1, 3); if ((n + 3) % 2 == 0) ans += C((n + 3) / 2 - 1, 3) * 2; if ((n + 2) % 2 == 0) ans += C((n + 2) / 2 - 1, 3); static int f = 0; printf("Case #%d: %lld\n", ++f, ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
HUST 1698 - 电影院 组合数学 + 分类思想
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。