题意 :给出一个包含 n 个元素的序列,将它们满足下列条件的三个集合:
第一个集合里所有元素的乘积小于 0
第二个集合里所有元素的乘积大于 0
第三个集合里所有元素的乘积等于 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 30 31 32 33 #include <bits/stdc++.h> using namespace std ;typedef long long ll;signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int n; cin >> n; int a[100 ] = {}; vector <int > vec; int flag = 0 ; for (int i = 0 ; i < n; ++i) { int x; cin >> x; if (x > 0 && !flag) flag = x; else vec.push_back(x); } sort(vec.begin(), vec.end()); int p = 0 ; cout << 1 << ' ' << vec[p++] << endl ; if (flag) cout << 1 << ' ' << flag << endl ; else cout << 2 << ' ' << vec[p++] << ' ' << vec[p++] << endl ; cout << vec.size() - p; for (; p < vec.size(); ++p) cout << ' ' << vec[p]; cout << endl ; return 0 ; }
B.Coach —带权并查集+思维
题意 :教练有 n 名学生,n 保证能被 3 整除 。他想要将学生们分成三人一组去打 ACM,学生们有 m 个条件,形如学生 i 和学生 j 想要分到一组,求一种满足所有要求的方案,如果不存在输出 -1,否则则每行输出三哥学生的序号代表三人一组
思路 :不难想要肯定要借助并查集先确定条件限制形成的点集的大小,如果存在一个点集的大小大于 3 那么肯定是输出 -1,否则点集的大小都是 1 或者 2。因为还需要输出学生序号所以对于每个点集我们让另开一个容器帮助根节点记录该集合内部的序号成员。对于大小为 3 的点集直接输出,对于大小为 2 的点集跟它在找一个大小为 1的点集,剩余的大小为 1的点集自行组队。但是需要注意如果大小为 2 的点集多余大小为 1 的点集也是不能成功组队的例如 6 被分成 3 个大小为 2 的点集,所以还需要在组队前判断一下
细节多码量也不小,比赛时好像过 C 的比过 B 的要多
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 55 ;int n, m;int fa[maxn];vector <int > se[maxn]; int find (int x) { if (fa[x] < 0 ) return x; fa[x] = find(fa[x]); return fa[x]; } void merge (int x, int y) { int fx = find(x), fy = find(y); if (fx == fy) return ; if (fa[fx] < fa[fy]) { fa[fx] += fa[fy]; fa[fy] = fx; for (int i = 0 ; i < se[fy].size(); ++i) se[fx].push_back(se[fy][i]); se[fy].clear(); } else { fa[fy] += fa[fx]; fa[fx] = fy; for (int i = 0 ; i < se[fx].size(); ++i) se[fy].push_back(se[fx][i]); se[fx].clear(); } } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); while (cin >> n >> m) { for (int i = 1 ; i <= n; ++i) { fa[i] = -1 ; se[i].push_back(i); } while (m--) { int x, y; cin >> x >> y; merge(x, y); } vector <int > vec1, vec2, vec3; for (int i = 1 ; i <= n; ++i) { if (fa[i] < -3 ) { cout << -1 << endl ; return 0 ; } if (fa[i] == -1 ) vec1.push_back(i); else if (fa[i] == -2 ) vec2.push_back(i); else if (fa[i] == -3 ) vec3.push_back(i); } if (vec2.size() > vec1.size()) { cout << -1 << endl ; return 0 ; } for (int i = 0 ; i < vec3.size(); ++i) { for (auto e : se[vec3[i]]) cout << e << ' ' ; cout << endl ; } for (int i = 0 ; i < vec2.size(); ++i) { for (auto e : se[vec1[i]]) cout << e << ' ' ; for (auto e : se[vec2[i]]) cout << e << ' ' ; cout << endl ; } for (int i = vec2.size(); i < vec1.size(); i += 3 ) cout << se[vec1[i]][0 ] << ' ' << se[vec1[i + 1 ]][0 ] << ' ' << se[vec1[i + 2 ]][0 ] << endl ; } return 0 ; }
题意 :给出一个长度为 n 的数 x,如果 x 本身由 a 和 b 两个数构成并且 x 中每个位置上的数的加和还是只由 a 和 b 构成我们就成它为优秀的数,请确定这个 x 是优秀的数有几种构造方法,答案对 1e9+7 取模
思路 :如果 x 中有 cnta 个 a,那么就有 n-cnta 个 b,然后我们判断这样所有的数的加和时候还是只由 a 和 b 构成,是的话 x 就多了 C(n,cnta) 种构造方法,cnta的取值无疑是 [0,n],所以就枚举 a 的个数判断构成的 x 是否为优秀的数,是的话就算上新增加的构造方法,中间环节注意取模
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const ll mod = 1e9 + 7 ;ll a, b, n; ll quick_pow (ll a, ll b) { ll ans = 1 , base = a; while (b) { if (b & 1 ) ans = ans * base % mod; base = base * base % mod; b >>= 1 ; } return ans; } ll factorial (ll n) { ll fc = 1 ; for (int i = 1 ; i <= n; ++i) fc = (fc * i) % mod; return fc % mod; } ll inv (ll a) { return quick_pow(a, mod - 2 ) % mod; } ll combo (ll n, ll m) { ll com = factorial(n) * inv((factorial(m) * factorial(n - m)) % mod) % mod; return com % mod; } bool check (ll x, ll y, ll s) { while (s) { int x = s % 10 ; s /= 10 ; if (x != a && x != b) return 0 ; } return 1 ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); while (cin >> a >> b >> n) { ll ans = 0 ; for (ll cnta = 0 ; cnta <= n; ++cnta) { ll cntb = n - cnta; ll sum = a * cnta + b * cntb; if (check(cnta, cntb, sum)) ans = (ans + combo(n, cnta)) % mod; } cout << ans << endl ; } return 0 ; }