https://codeforces.com/contest/1370
C. Number Game
题意：给定一个数n，两个人轮流操作，每次操作可以n-1或n除以它的一个奇数因子。先变为1的人赢。
显然如果n是奇数或2，先手必胜。
如果n没有奇数因子，即n是除2以外的2的幂次，则先手必败。
如果n是2和一个奇质数的乘积，则先手必败。
所以，如果n不是2的幂次，且有多个2，则先手必胜。如果n只有1个2，且有多个奇质数，则先手必胜。
其他情况先手必败。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int T;
int prime[N];
bool is_prime[N];
int vis[N];
int euler_sieve(int n) {
int cnt = 0;
memset(vis, 0, sizeof(vis));
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++) {
if (!vis[i]) { vis[i] = i; prime[cnt++] = i; is_prime[i] = true; }
for (int j = 0; j < cnt; j++) {
if (i*prime[j] > n) break;
vis[i*prime[j]] = prime[j];
if (i%prime[j] == 0)
break;
}
}
return cnt;
}
int main() {
int t = euler_sieve(100000);
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
if (n == 1)puts("FastestFinger");
else if (n == 2)puts("Ashishgup");
else if (n & 1)puts("Ashishgup");
else {
int cnt = 0, cnt2 = 0;
for (int i = 0; 1ll*prime[i]*prime[i] <= n; i++) {
if (n%prime[i] == 0) {
while (n%prime[i] == 0) {
if (prime[i] & 1)cnt++;
else cnt2++;
n /= prime[i];
}
}
}
if (n != 1)cnt++;
if (cnt == 0)puts("FastestFinger");
else {
if (cnt2 > 1)puts("Ashishgup");
else {
if (cnt>1)puts("Ashishgup");
else puts("FastestFinger");
}
}
}
}
return 0;
}
|
D. Odd-Even Subsequence
题意：给定一个数组，要求找出一个长度为k的子序列，要求最小化子序列奇数位置和偶数位置分别的最大值的最小值。
二分+dp
一个数可以作为答案，说明存在一个子序列，满足奇数位置上的所有数都小于等于它，或者偶数位置上的所有数都小于等于它。
如果存在 ⌈k/2⌉ 个不相邻的数满足都小于等于x，则一定可以构造出这样一个序列。
可以dp求出最多的不相邻的小于等于x的数。
而如果只有 ⌊k/2⌋ 个，那么还要考虑如果在两边，那么可能无法构造出，所以要把两边都排除之后再求一次。
奇偶不同情况也要考虑。
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
63
64
65
66
67
68
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, k;
int a[N], dp[N][2];
bool ck(int x) {
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + (a[i] <= x);
}
int t = max(dp[n][0], dp[n][1]);
if (k & 1) {
if (t >= (k + 1) / 2)return true;
if (t < k / 2)return false;
int p = a[1], q = a[n];
a[1] = a[n] = 2 * INF;
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + (a[i] <= x);
}
t = max(dp[n][0], dp[n][1]);
a[1] = p, a[n] = q;
if (t >= k / 2)return true;
return false;
}
else {
if (t >= k / 2 + 1)return true;
if (t < k / 2)return false;
int p = a[1]; a[1] = INF;
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + (a[i] <= x);
}
t = max(dp[n][0], dp[n][1]);
a[1] = p;
if (t >= k / 2)return true;
p = a[n]; a[n] = INF;
dp[0][0] = dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + (a[i] <= x);
}
t = max(dp[n][0], dp[n][1]);
a[n] = p;
if (t >= k / 2)return true;
return false;
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
ck(1);
int L = 1, R = INF;
while (L < R) {
int mid = (L + R) / 2;
if (ck(mid))R = mid;
else L = mid + 1;
}
printf("%d\n", L);
return 0;
}
|
E. Binary Subsequence Rotation
题意：给定两个等长的01串，每次操作对第一个串选一个子序列，环形向右平移一个字符，问最少多少次操作后变成第二个串。
贪心+模拟
显然对应相等的位置可以不用动了，所以只考虑不等的。
每次都是移动01010101这样的序列，因为像10001这样的，移动后实际上等同于只移动了最右边的01。
然后就是贪心选择最长的0101或101010串，最终有几个这样的串，就要操作几次。
但是实际上对于01010这样首和尾相同的串，平移一次后并不能使所有位置都对齐，而是会剩下一位。但是这样并不会影响结果，因此对于每个01010，一定会有一个10101对应，还是可以通过两次操作把这两个串都对齐。
实现方式还是要注意的，遍历每一位，同时记录是否有以0结尾或1结尾的0101串，如果当前位是0，则接在1后，并使1串变为0串，如果没有1串，则新建一个0串。如果当前位为1也类似。至于不用考虑010这样的串的原因就是上一段。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 1e6 + 10;
int n;
char s[N], t[N];
int cn[2];
int c0, c1;
int main() {
scanf("%d", &n);
scanf("%s%s", s + 1, t + 1);
for (int i = 1; i <= n; i++) {
if (s[i] == t[i])continue;
if (s[i] == '0') {
if (c1 > 0)c1--;
c0++;
cn[0]++;
}
else {
if (c0 > 0)c0--;
c1++;
cn[1]++;
}
}
if (cn[0] != cn[1])puts("-1");
else printf("%d\n", c0 + c1);
return 0;
}
|
