题意 :请判断一个数是否存在一个大于 1 的奇数因子
思路 :正向不好想就反过来想:如果一个数不存在任意一个大于 1 的奇数因子,那么它的任意一个因子自身肯定偶数并且也没有任意一个大于 1 的奇数因子,例如 12 的因子 6 存在 3 奇因子所以 12 也就存在 3 这个奇因子了,所以这个数只有是 2 的幂数的时候无大于 1 的奇数因子
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll; signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; map <ll, bool > mp; ll p = 2 ; mp[p] = 1 ; while (p < 1e14 ) { p *= 2 ; mp[p] = 1 ; } while (t--) { ll a; cin >> a; if (mp[a] == 1 ) cout << "NO" << endl ; else cout << "YES" << endl ; } return 0 ; }
题意 :判断一个整数 n,是否可以由若干个 2020和若干个 2021组成
思路 :先尽可能把 2020 减去,最后会发现一些多余的数,这个时候对多余的数特判——看是否可以从之前减去的 2020 中拿出一部分和余出来的数凑 2021
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <bits/stdc++.h> using namespace std ;typedef long long ll;signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { int n; cin >> n; int x = n / 2020 , y = n - 2020 * x; if (y > x) cout << "YES" << endl ; else cout << "NO" << endl ; } return 0 ; }
题意 :有 a 个男生,b 个女生,并给出 k 种男女组合 (男编号,女编号)
,从中选出两个组合使组合的两种组合的男生编号不相同,女生编号也不相同,请问有多少种选法
思路 :就是询问有多少对 (e,f)
(g,h)
使得 e!=g
并且 f!=h
,首先可以肯定的是这 k 中组合中要么不重合,要么有一个位置重合,不存在完全重合,所以根据容斥原理假设 i 可以与前面的 (i−1) 都组合,然后减去不符合要求的,开两个 map 分别存一下男编号出现的组合次数和女编号出现的组合次数
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 <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 2e5 + 100 ;int x[maxn], y[maxn]; signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int a, b, k; int t; cin >> t; while (t--) { cin >> a >> b >> k; map <int , int > vec1, vec2; for (int i = 1 ; i <= k; ++i) cin >> x[i]; for (int i = 1 ; i <= k; ++i) cin >> y[i]; ll ans = 0 ; for (int i = 1 ; i <= k; ++i) { if (i != 1 ) ans += i - 1 - vec1[x[i]] - vec2[y[i]]; vec1[x[i]] += 1 , vec2[y[i]] += 1 ; } cout << ans << endl ; } return 0 ; }
题意 :手机有 n 个应用,每个应用占用一定内存并且带来 1 或者 2 愉悦值,现在需要腾出至少 k 个内存空间,请找到满足要求并且失去的愉悦值最小的选法,输出这个选法会失去的最小愉悦值
思路 :我们假设选择删除 a 个愉悦值为 1 的应用和 b 个愉悦值为 2 的应用,同时为了内存减少的最多肯定贪心的选择删除内存占用大的。所以我们先将应用分组并用前缀和维护删除之前应用所腾空内存,然后枚举 a 并用二分查找满足条件的 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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 2e5 + 100 ;ll suff[maxn]; struct node { int x, y; } p[maxn]; bool cmp (node a, node b) { if (a.y != b.y) return a.y < b.y; else return a.x > b.x; } void solve () { int n, m; cin >> n >> m; for (int i = 1 ; i <= n; ++i) cin >> p[i].x; for (int i = 1 ; i <= n; ++i) cin >> p[i].y; sort(p + 1 , p + 1 + n, cmp); int last = 0 ; for (int i = 1 ; i <= n; ++i) { suff[i] = suff[i - 1 ] + p[i].x; if (p[i].y == 1 ) last = i; } if (suff[n] < m) { cout << -1 << endl ; return ; } ll ans = LLONG_MAX; for (int i = 0 ; i <= last; ++i) { int l = last, r = n; int tmp = -1 ; while (l <= r) { int mid = l + r >> 1 ; if (suff[mid] - suff[last] + suff[i] >= m) { tmp = mid; r = mid - 1 ; } else l = mid + 1 ; } if (tmp != -1 ) ans = min(ans, i * 1 + (tmp - last) * 2l l); } cout << ans << endl ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { solve(); } return 0 ; }
题意 :给出一个包含 n 个元素的数组,选在需要选出 k 个数,请问选出 k 个数和最大的选法有几种,答案对 1e9+7 取模
思路 :对数组先排序肯定是取前 k 个数,那么会导致选法不唯一的可能就是选取的最小的数在数组中存在多个并且选不完,对这部分求一个组合数就可以了和上一篇文章 C 题雷同
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const ll mod = 1e9 + 7 ;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; } void solve () { map <int , int > mp; int n, k; cin >> n >> k; for (int i = 1 ; i <= n; ++i) { int x; cin >> x; ++mp[x]; } for (auto it = mp.rbegin(); it != mp.rend(); ++it) { if (it->second < k) k -= it->second; else if (it->second == k) { cout << 1 << endl ; return ; } else { cout << combo(it->second, k) << endl ; return ; } } } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { solve(); } return 0 ; }
题意 :给出两个 n*n 的由 0 1 两个数组成的方阵 a 和 b,可以对 a 的某一行或者某一列的数进行多次整体取反,判断能够通过上述操作使 a 变成 b
思路 :如果可以那么无论采取何种方式最终肯定可以使 a 变成 b,所以我们先用列变换让 a 的第一行和 b 的第一行对应相同,然后判断 2~n 行是否可以仅通过行变换相同(列变换会导致第一行又不相同了),如果不能就输出 NO,否则输出 YES
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 1005 ;int n;char a[maxn][maxn], b[maxn][maxn];bool check (int p) { bool yes = 0 , no = 0 ; for (int i = 1 ; i <= n; ++i) { if (a[p][i] == b[p][i]) yes = 1 ; else no = 1 ; if (yes && no) return 0 ; } return 1 ; } void solve () { cin >> n; for (int i = 1 ; i <= n; ++i) { for (int j = 1 ; j <= n; ++j) cin >> a[i][j]; } for (int i = 1 ; i <= n; ++i) { for (int j = 1 ; j <= n; ++j) cin >> b[i][j]; } for (int i = 1 ; i <= n; ++i) { if (a[1 ][i] != b[1 ][i]) { for (int j = 1 ; j <= n; ++j) { if (a[j][i] == '0' ) a[j][i] = '1' ; else a[j][i] = '0' ; } } } for (int i = 2 ; i <= n; ++i) { if (check(i) == 0 ) { cout << "NO" << endl ; return ; } } cout << "YES" << endl ; } signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { solve(); } return 0 ; }
题意 :给出一个由 n 个元素的数组,请求出至少删去几个数能使得数列中的所有数两两之间能被一方整除
思路 :我们在输入数据时先统计出每个数字出现的次数 cnt[i]
,用数组 dp[i]
表示以数字 i
为最大值的数列中的数字个数,则对应转移方程为:dp[i]=cnt[i]+max(dp[a1],dp[a2],dp[a3],...,dp[ak])
,其中 i%aj==0(1<=j<=k)
,从数字 1 开始枚举到 200000,中途将 i
的所有倍数 j
的 dp[j]
值都与 dp[i]
取最大值递推更新
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 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 2e5 + 100 ;int a[maxn], dp[maxn], cnt[maxn]; signed main () { ios::sync_with_stdio(false ), cin .tie(0 ); int t; cin >> t; while (t--) { int n; cin >> n; int ans = 0 ; memset (cnt, 0 , sizeof cnt); memset (dp, 0 , sizeof dp); for (int i = 1 ; i <= n; ++i) { int x; cin >> x; ++cnt[x]; } for (int i = 1 ; i <= 2e5 ; ++i) { dp[i] += cnt[i]; for (int j = 2 * i; j <= 2e5 ; j += i) dp[j] = max(dp[j], dp[i]); } for (int i = 1 ; i <= 2e5 ; ++i) ans = max(ans, dp[i]); cout << n - ans << endl ; } return 0 ; }