Codeforces Round #868 (Div. 2) (题解)
作者:
ღSupperღ
,
2023-04-28 22:49:19
,
所有人可见
,
阅读 253
Codeforces Round #868 (Div. 2) (题解)
题意:给定k,询问是否能够构造出k对符合1 <= i < j <= n 且 ai * aj = 1
思路:n个数有n * (n - 1)对,由于题目范围小,直接暴力枚举1和-1的对数判断是否等于k即可
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, k;
std::cin >> n >> k;
for (int i = 1; i <= n; i ++) {
int j = n - i;
if (i * (i - 1) / 2 + j * (j - 1) / 2 == k) {
yes
for (int k = 1; k <= i; k ++) {
std::cout << 1 << " ";
}
for (int k = 1; k <= j; k++) {
std::cout << -1 << " ";
}
std::cout << "\n";
return ;
}
}
no
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
题意:是否可以通过不超过1次初始交换,使得最后序列是上升的
思路:首先对于i,每相隔k的数组成的序列(ai,ai+k,ai+2k....)一定可以做到是上升的。由于给定的序列是n的排列,所以最后符合i % k == ai % k.(1,2,3,4).记录不相等的对数,讨论
- cnt == 0,即所有的i都满足 i % k == ai % k.则不需要初始交换,答案为0
- cnt == 2, 即只有1对不满足,则我们交换1次,答案为1
- 除去上述情况,说明有很多对不满足,那么交换1次显然不能满足要求,答案为-1
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n, k;
std::cin >> n >> k;
std::vector<int> a(n + 1);
int cnt = 0;
for (int i = 1; i <= n; i ++) {
std::cin >> a[i];
cnt += (a[i] % k != i % k);
}
if (cnt == 0) {
std::cout << "0\n";
} else if (cnt == 2) {
std::cout << "1\n";
} else {
std::cout << "-1\n";
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
题意:找到最大的k,使其满足题目要求
思路:对序列进行分解质因数,即D = p1^d1 * p2^d2 * ..... (p1为质因子,d1为个数),那么约数为所有(di + 1)相加。令质因子个位为m,约数个数为D,则合数t = D - m - 1,减一是去掉1(既不是质数,也不是合数),m <= D - m - 1,即 2m + 1 <= D.由于di >= 1,则di + 1 >= 2, => D >= 2^m.分类讨论
- 当m = 1时,要时2m + 1 <= D满足,即 d1 >= 2,质因子的个数最少为2
- 当m = 2时, 要时2m + 1 <= D满足,即 d1,d2有一个 >= 2即可,即max(d1,d2) >= 2;
- 当m >= 3时, 2m + 1 <= D(D >= 2^m) 恒成立
最小原则,我们只需让每个数的质因子>= 2即可满足1,2.使每个数都是强合数。那么我们枚举每个质因子,两个两个的捆绑在一起,如果有多余的,超过三个就可以多组成一个新的数(满足3),使k增大.
#include <bits/stdc++.h>
using i64 = long long;
using PII = std::pair<i64,i64>;
#define int i64
#define yes std::cout << "YES\n";
#define no std::cout << "NO\n";
void solve() {
int n;
std::cin >> n;
std::map<int,int> mp;
for (int i = 0; i < n; i ++) {
int x;
std::cin >> x;
for (int j = 2; j <= x / j; j ++) {
while (x % j == 0) {
x /= j;
mp[j]++;
}
}
if (x != 1) {
mp[x]++;
}
}
int ans = 0,cnt = 0;
for (auto [k,v] : mp) {
ans += v / 2;
cnt += v % 2;
}
std::cout << ans + cnt / 3 << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while (T -- ) {
solve();
}
return 0;
}
待更