Codeforces Round #697 (Div. 3) Codeforces Round #697 (Div. 3) A. Odd Divisor B. New Year's Number C. Ball in Berland D. Cleaning the Phone E. Advertising Agency F. Unusual Matrix G. Strange Beauty
A. Odd Divisor
题意
给你一个n((2leq nleq 10^{14}))问你n是否有奇数因子不包括1但包括它本身。
思路
在质因数分解时只有2是偶数，所以不断对一个数除以2，然后判断最后是不是为1就可以。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
const int N = 2e5 + 10;
void solve() {
int n; cin >> n;
if (n == 2) {
cout << "NO
";
return ;
}
while(n %2 == 0) {
n /= 2;
}
if (n & 1 && n != 1) cout << "YES
";
else cout << "NO
";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
B. New Year's Number
题意
给你一个数n问你n能否被2020，2021相加求和。
思路
直接判断一个数里有多少个2020，然后如果余数少于20020的话就可以将余数给一些2020构成2021
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
const int N = 2e5 + 10;
void solve() {
int n; cin >> n;
int t = n % 2020;
if (n < 2020) {
cout << "NO
";
return ;
}
if (t <= n / 2020) {
cout << "YES
";
return ;
}
cout << "NO
";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
C. Ball in Berland
题意
有a个男的，b个女的，k个配对，问你两两配对且男不重复女也不重复的可能性有多少种
思路
分别计算某个男生某个女生配对的人数有多少种，然后枚举一种情况计算所有可能性
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
const int N = 2e5 + 10;
int a[N], b[N];
int ca[N], cb[N];
void solve() {
int x, y, k; cin >> x >> y >> k;
for (int i = 1; i <= max(x, y); ++i) {
ca[i] = cb[i] = 0;
}
for (int i = 1; i <= k; ++i) {
cin >> a[i];
++ca[a[i]];
}
for (int i = 1; i <= k; ++i) {
cin >> b[i];
++cb[b[i]];
}
int ans = 0;
for (int i = 1; i <= k; ++i) {
ans = ans + k - (ca[a[i]] + cb[b[i]]) + 1;
}
cout << ans / 2 << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
D. Cleaning the Phone
题意
给你n个数，且每个数都有一个b，问你在清理内存大于等于m的情况下b的和最小
思路
以b值分组，分组后求前缀和，然后二分讨论。
需要特别注意若a组一个都没用或者b组一个都没用的情况
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//#define int long long
const int N = 2e5 + 10;
struct NODE {
int a, b;
} d[N];
LL s1[N], s2[N];
void solve() {
int n, m;
cin >> n >> m;
LL tot = 0;
int c1 = 0;
vector<int>v1, v2;
for (int i = 1; i <= n; ++i) {
cin >> d[i].a;
tot += d[i].a;
}
for (int i = 1; i <= n; ++i) {
cin >> d[i].b;
if (d[i].b == 1) {
v1.push_back(d[i].a);
} else v2.push_back(d[i].a);
}
if(tot < m) {
cout << -1 << endl;
return ;
}
sort(v1.begin(), v1.end(), greater<int>());
sort(v2.begin(), v2.end(), greater<int>());
for (int i = 0; i < v1.size(); ++i) {
if (i == 0)s1[i] = v1[i];
else s1[i] = s1[i - 1] + v1[i];
}
for (int i = 0; i < v2.size(); ++i) {
if (i == 0)s2[i] = v2[i];
else s2[i] = s2[i - 1] + v2[i];
}
int ans = 1e9;
for (int i = 0; i < v1.size(); ++i) {
if (s1[i] >= m) {
ans = min(ans, i + 1);
break;
}
int idx = lower_bound(s2, s2 + v2.size(), m - s1[i]) - s2;
if (idx == v2.size()) continue;
ans = min(ans, (i + 1) + (idx + 1) * 2);
}
int idx = lower_bound(s2, s2 + v2.size(), m) - s2;
if (idx != v2.size()) {
ans = min(ans, (idx + 1) * 2);
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
E. Advertising Agency
题意
给你n个数让你找k个数，然后其和最大，问你有多少种可能
思路
显然是把最大的k个数相加，然后看和k个数中最小的数相同的有几个，用了几个。(C_{共计}^{用了})
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int qmi(int a, int k) {
int res = 1;
while(k) {
if(k & 1) res = (LL)res * a % mod;
k >>= 1;
a = (LL)a * a % mod;
}
return res;
}
int fact[N], infact[N];
void init(int n) {
fact[0] = infact[0] = 1;
for(int i = 1; i <= n; i ++) {
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = qmi(fact[i], mod - 2);
}
}
int C(int a, int b) {
if (b > a) return 0;
return (LL)fact[a] * infact[a - b] % mod * infact[b] % mod;
}
int v[1010], a[1010];
void solve() {
int n, k; cin >> n >> k;
for (int i = 1; i <= n; ++i) {
v[i] = 0;
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1,a + 1 +n);
if (n == k) {
cout << 1 << endl;
return ;
}
LL tot = 0;
LL c1 = 0;
LL c2 = 0;
for (int i = n - k + 1; i <= n; ++i) {
if (a[i] == a[n - k + 1]) ++ c2;
}
for (int i = 1; i <= n - k; ++i) {
if (a[i] == a[n - k + 1])++c1;
}
cout << (C(c1 + c2, c2)) << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
init(1000);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
F. Unusual Matrix
题意
给你两个矩阵a,b问你在规则下将a能不能变成b。
规则是每次只能对一行或者一列异或1
思路
如果a,b的相同位置不相同则这个位置需要异或奇数次，如果相同需要异或偶数次，偶数次相当于不异或。
我们先将一行或者一列变为与b相同，然后确定了这一行或一列的异或次数且不能再去改变，然后去枚举其他的情况。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[1005][1005], b[1005][1005];
void solve() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%1d", &a[i][j]);
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%1d", &b[i][j]);
}
}
for (int i = 1; i <= n; ++i) {
if (a[i][1] != b[i][1]) {
for (int j = 1 ; j <= n; ++j) {
a[i][j] ^= 1;
}
}
}
bool ok = true;
for (int i = 2; i <= n; ++i) {
if (a[1][i] != b[1][i]) {
for (int j = 1; j <= n; ++j) {
if (a[j][i] == b[j][i]) ok = false;
}
} else {
for (int j = 1; j <= n; ++j) {
if (a[j][i] != b[j][i]) ok = false;
}
}
}
if (ok) cout << "YES
";
else cout << "NO
";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
}
G. Strange Beauty
题意
给你n个数，问你最少要删除多少个才能使这个数组漂亮
这个数组漂亮：任意两个数都可以作为除数或被除数
思路
挑选倍数,(dp[i])表示最大值为i的情况下这个数列有多少个数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int dp[N], num[N];
void solve() {
int n; cin >> n;
memset(num, 0, sizeof num);
memset(dp, 0, sizeof dp);
for (int i = 1; i <= n; ++i) {
int t; cin >> t;
++num[t];
}
int ans = -1;
for (int i = 1; i < N; ++i) {
dp[i] += num[i];
for (int j = 2 * i; j < N; j += i) {
dp[j] = max(dp[i], dp[j]);
}
ans = max(ans, dp[i]);
}
cout << n - ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}