A. King Escape
签.
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n, x[3], y[3];
5
6 int f1(int X, int Y)
7 {
8 return X - Y - x[2] + y[2];
9 }
10
11 int f2(int X, int Y)
12 {
13 return x[2] + y[2] - X - Y;
14 }
15
16 bool ok()
17 {
18 //if (f1(x[0], y[0]) * f1(x[1], y[1]) < 0) return false;
19 //if (f2(x[0], y[0]) * f2(x[1], y[1]) < 0) return false;
20 if (x[0] > x[1]) swap(x[0], x[1]);
21 if (y[0] > y[1]) swap(y[0], y[1]);
22 if (y[2] >= y[0] && y[2] <= y[1]) return false;
23 if (x[2] >= x[0] && x[2] <= x[1]) return false;
24 return true;
25 }
26
27 int main()
28 {
29 while (scanf("%d", &n) != EOF)
30 {
31 scanf("%d%d", x + 2, y + 2);
32 for (int i = 0; i < 2; ++i)
33 scanf("%d%d", x + i, y + i);
34 puts(ok() ? "YES" : "NO");
35 }
36 return 0;
37 }
View Code
B. Square Difference
签.
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 int t; ll a, b;
6
7 bool ok(ll x)
8 {
9 ll limit = sqrt(x);
10 for (ll i = 2; i <= limit && i < x; ++i)
11 if (x % i == 0)
12 return false;
13 return true;
14 }
15
16 int main()
17 {
18 scanf("%d", &t);
19 while (t--)
20 {
21 scanf("%lld%lld", &a, &b);
22 if (a - b != 1) puts("NO");
23 else
24 puts(ok(a + b) ? "YES" : "NO");
25 }
26 return 0;
27 }
View Code
C. Permutation Game
Solved.
题意：
$A和B玩游戏，一个人能从i移动到j$
$当且仅当a[i] < a[j] 并且|i - j| \equiv 0 \pmod a[i]$
$判断以每个数为下标作起点,A先手能否必胜$
思路：
我们考虑一个位置什么时候必败
- $它下一步没有可移动的位置$
- $它的下一步状态没有一处是必败态$
倒着处理出每个位置的状态即可
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 100010
5 int n, a[N], ans[N], pos[N];
6
7 int main()
8 {
9 while (scanf("%d", &n) != EOF)
10 {
11 for (int i = 1; i <= n; ++i) scanf("%d", a + i), pos[a[i]] = i;
12 for (int i = n; i >= 1; --i)
13 {
14 int id = pos[i];
15 bool flag = 0;
16 for (int j = id - i; j >= 1; j -= i)
17 if (a[j] > i && ans[a[j]] == 0)
18 {
19 flag = 1;
20 break;
21 }
22 if (flag == 0) for (int j = id + i; j <= n; j += i)
23 if (a[j] > i && ans[a[j]] == 0)
24 {
25 flag = 1;
26 break;
27 }
28 ans[i] = flag;
29 }
30 for (int i = 1; i <= n; ++i)
31 putchar(ans[a[i]] ? 'A' : 'B');
32 puts("");
33 }
34 return 0;
35 }
View Code
D. Divisors
Upsolved.
题意：
给出一些$a_i, 求 \pi a_i 的因子个数$
$保证a_i 有3-5个因数$
思路：
对一个数求因子个数 假设它质因数分解之后是$n = p_1^{t_1} \cdot p_2^{t_2} \cdots p_n^{t_n}$
那么因子个数就是$(t_1 + 1) \cdot (t_2 + 1) \cdots (t_n + 1)$
我们考虑什么样的数有$3-5个因数$
$平方数、立方数、四次方数、n = p \cdot q (p, q 是不同的质数)$
$对于前三类数，可以暴力破出，考虑第四类$
$如果它的p, q在序列中是唯一的，那么我们不需要管它具体是多少$
$直接得到p, q的数量就是这个数的数量$
$否则，拿这个数和别的数作gcd就可以破出p, q$
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 1010
6 const ll MOD = (ll)998244353;
7 int n; ll a[N];
8 map <ll, int> mp, num;
9
10 void work(ll a)
11 {
12 ll limit = pow(a, 1.0 / 4);
13 for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
14 if (i * i * i * i == a)
15 {
16 mp[i] += 4;
17 return;
18 }
19 limit = pow(a, 1.0 / 3);
20 for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
21 if (i * i * i == a)
22 {
23 mp[i] += 3;
24 return;
25 }
26 limit = pow(a, 1.0 / 2);
27 for (ll i = limit + 10; i >= limit - 10 && i >= 1; --i)
28 if (i * i == a)
29 {
30 mp[i] += 2;
31 return;
32 }
33 ++num[a];
34 }
35
36 ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
37
38 int main()
39 {
40 while (scanf("%d", &n) != EOF)
41 {
42 mp.clear(); num.clear();
43 for (int i = 1; i <= n; ++i)
44 {
45 scanf("%lld", a + i);
46 work(a[i]);
47 }
48 ll res = 1;
49 for (auto it : num)
50 {
51 ll tmp;
52 bool flag = true;
53 for (int i = 1; i <= n; ++i)
54 if (a[i] != it.first && (tmp = gcd(it.first, a[i])) != 1)
55 {
56 mp[tmp] += it.second;
57 mp[it.first / tmp] += it.second;
58 flag = false;
59 break;
60 }
61 if (flag) res = (res * (it.second + 1) % MOD * (it.second + 1)) % MOD;
62 }
63 for (auto it : mp)
64 res = (res * (it.second + 1)) % MOD;
65 printf("%lld\n", res);
66 fflush(stdout);
67 }
68 return 0;
69 }
View Code