A.Odd Divisor—规律+签到

题意:请判断一个数是否存在一个大于 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;
}
// system("pause");
return 0;
}

B.New Year’s Number—思维

题意:判断一个整数 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;
}
// system("pause");
return 0;
}

C.Ball in Berland—容斥+思维

题意:有 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;
}
// system("pause");
return 0;
}

D.Cleaning the Phone—枚举+二分

题意:手机有 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) { //应用分为1,2两个内存降序序列
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; //记录p中类型为1的最后一个应用的索引值
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) { //全部删除都不足返回-1
cout << -1 << endl;
return;
}
ll ans = LLONG_MAX;
for (int i = 0; i <= last; ++i) { //枚举选多少个类型为1的
int l = last, r = n; //枚举类型为2的位置,注意一定是从last开始因为可能类型2的应用一个不选
int tmp = -1;
while (l <= r) {
int mid = l + r >> 1;
if (suff[mid] - suff[last] + suff[i] >= m) { //判断是否符合要求
tmp = mid; //标记顺带记录当前选择的类型为2的最后一个应用索引值
r = mid - 1;
} else
l = mid + 1;
}
if (tmp != -1) ans = min(ans, i * 1 + (tmp - last) * 2ll); //最终找到的就是最小的
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
// system("pause");
return 0;
}

E.Advertising Agency—组合数+快速幂+逆元+思维

题意:给出一个包含 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();
}
// system("pause");
return 0;
}

F.Unusual Matrix—模拟+思维

题意:给出两个 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];
}
//将a的第一行通过列变换为何b第一行一样
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();
}
// system("pause");
return 0;
}

G.Strange Beauty—枚举+DP

题意:给出一个由 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 的所有倍数 jdp[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]; //dp[i]表示本身作为数组中最大边界时数组的最大容量
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]; //当前dp再算上本身
for (int j = 2 * i; j <= 2e5; j += i)
dp[j] = max(dp[j], dp[i]); //后面dp先算上除数
}
for (int i = 1; i <= 2e5; ++i) ans = max(ans, dp[i]);
cout << n - ans << endl;
}
// system("pause");
return 0;
}