A.
题意 :
在之间选择两个不同数,,使得比其它的任意两个数的gcd值都大
题解:
即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); printf("%d\n", n / 2); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.GCD Compression
题意:
给定一个长度为的数组,从中选定个,将它们两两组合相加,形成一个长度为的数组,询问能否使得
题解:
让奇数和奇数组合,偶数和偶数组成,就可以构造出
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); vector<int> v[2]; for (int i = 0, x; i < 2 * n; i++) { scanf("%d", &x); v[x % 2].push_back(i + 1); } int cnt = 0; for (int i = 0; i < 2 && cnt < n - 1; i++) for (int j = 0; j + 1 < (int)v[i].size() && cnt < n - 1; j += 2) { printf("%d %d\n", v[i][j], v[i][j + 1]); cnt++; } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Number Game
题意:
给定一个数,两个人分别进行操作,一共有两张操作。
- 除一个大于的一个的奇数因子
- 减,当
询问最终谁会获胜
题解:
- ,FastestFinger获胜
- ,Ashishgup获胜
- 为奇数,Ashishgup获胜
- 为偶数,当不包含奇数因子时FastestFinger获胜,当包含奇数因子并且除最大的奇数因子的结果不为时,Ashishgup获胜,否则FastestFinger获胜
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); if (n == 1) puts("FastestFinger"); else if (n == 2) puts("Ashishgup"); else if (n % 2) puts("Ashishgup"); else { for (int i = 2; i * i < n; i++) if (n % i == 0) if ((i % 2 && (n / i) != 2) || ((n / i) % 2 && i != 2)) { puts("Ashishgup"); return; } puts("FastestFinger"); } } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Odd-Even Subsequence
题意:
给定一个长度为的数组,要求选出一些元素组成长度为的子序列,这个子序列的花费为。询问最小的花费
题解:
二分答案,分别枚举最小值出现在下标为奇数的和偶数的,如果在奇数,奇数就选取的值,偶数位数值没有要求尽量选取靠左边的值,使得奇数位有更多选取的机会;如果在偶数则相反。
#include <bits/stdc++.h> using namespace std; #define eps 1e-7 typedef long long ll; typedef unsigned long long ull; const int maxn = 1e5 + 5; const ll mod = 998244353; int main() { int n, k; scanf("%d%d", &n, &k); vector<int> a(n + 1); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int l = 1, r = 1e9; while (l < r) { int mid = l + r >> 1; vector<int> cnt(2, 0); for (int i = 1; i <= n; i++) for (int j = 0; j < 2; j++) if (a[i] <= mid || cnt[j] % 2 == j) cnt[j]++; if (max(cnt[0], cnt[1]) >= k) r = mid; else l = mid + 1; } printf("%d\n", l); return 0; }
E. Binary Subsequence Rotation
题意:
给定一个长度为的串和。每次可以选择中的任意一个子序列,对序列中的每个元素向后移一位,询问经过最少多少次操作可以使得和相同
题解:
先判断和中和的数量是否相等,相等则继续判断,否则直接输出。观察可以发现对于一段子序列,中间的实际上是不会改变的,类似情况也成立,因此真正改变的只有或者交替的序列。因此只需遍历一遍,判断该位置是否等于,如果不相等,就判断是否存在以结尾的操作序列,有则加到这个序列尾部,否则就要创建一个新的操作序列,同理
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 1e6 + 5; const ll mod = 998244353; char str1[maxn], str2[maxn]; int main() { int n; int s1 = 0, s2 = 0; scanf("%d %s %s", &n, str1, str2); for (int i = 0; i < n; i++) s1 += str1[i] - '0'; for (int i = 0; i < n; i++) s2 += str2[i] - '0'; if (s1 != s2) puts("-1"); else { int n1 = 0, n2 = 0; for (int i = 0; i < n; i++) if (str1[i] != str2[i]) { if (str1[i] == '0') { if (n1 != 0) n1--; n2++; } else { if (n2 != 0) n2--; n1++; } } printf("%d\n", n1 + n2); } return 0; }