|
| 1 | +# Acwing44场周赛 |
| 2 | + |
| 3 | +### T1 |
| 4 | + |
| 5 | +直接用哈希表来查找 |
| 6 | + |
| 7 | +```cpp |
| 8 | +#include <bits/stdc++.h> |
| 9 | +using namespace std; |
| 10 | +void solve(){ |
| 11 | + set <int> s; |
| 12 | + int n; |
| 13 | + cin >> n; |
| 14 | + for(int i = 0; i < n; i++){ |
| 15 | + int j; |
| 16 | + cin >> j; |
| 17 | + if(j) s.insert(j); |
| 18 | + } |
| 19 | + cout << s.size() << endl; |
| 20 | +} |
| 21 | + |
| 22 | +int main(){ |
| 23 | + ios_base::sync_with_stdio(0); |
| 24 | + int t; |
| 25 | + t = 1; |
| 26 | + while(t--){ |
| 27 | + solve(); |
| 28 | + } |
| 29 | + return 0; |
| 30 | +} |
| 31 | +``` |
| 32 | + |
| 33 | + |
| 34 | + |
| 35 | +### T2 |
| 36 | + |
| 37 | +构造，如果想满足该路径是最短路径，必须得确保之前的某个时间节点不能到达该位置，我们可以通过用炸弹填充的方式来”迫使“它是最短的，如果说之前的时间节点与其相邻，那么就说明肯定有矛盾，我们只要验证是否矛盾即可 |
| 38 | + |
| 39 | +```cpp |
| 40 | +#include <bits/stdc++.h> |
| 41 | +using namespace std; |
| 42 | +int dx[5] = {0, 0,-1,1, 0}, dy[5] = {1, -1, 0, 0, 0}; |
| 43 | +void solve(){ |
| 44 | + string s; |
| 45 | + cin >> s; |
| 46 | + int x = 0, y = 0; |
| 47 | + bool o = 1; |
| 48 | + unordered_map<int,unordered_map<int,int>> vis; |
| 49 | + vis[0][0] = 1; |
| 50 | + for(int i = 0; i < s.size(); i++){ |
| 51 | + int prex = x, prey = y; |
| 52 | + if(s[i] == 'U') y++; |
| 53 | + if(s[i] == 'D') y--; |
| 54 | + if(s[i] == 'L') x++; |
| 55 | + if(s[i] == 'R') x--; |
| 56 | + if(vis[x][y]) o = 0; |
| 57 | + for(int j = 0; j < 5; j++){ |
| 58 | + int a = prex + dx[j], b = prey + dy[j]; |
| 59 | + vis[a][b] = 1; |
| 60 | + } |
| 61 | + } |
| 62 | + if(o) cout << "YES" << endl; |
| 63 | + else cout << "NO" << endl; |
| 64 | +} |
| 65 | + |
| 66 | +int main(){ |
| 67 | + ios_base::sync_with_stdio(0); |
| 68 | + int t; |
| 69 | + t = 1; |
| 70 | + while(t--){ |
| 71 | + solve(); |
| 72 | + } |
| 73 | + return 0; |
| 74 | +} |
| 75 | + |
| 76 | + |
| 77 | +``` |
| 78 | + |
| 79 | + |
| 80 | + |
| 81 | +### T3 |
| 82 | + |
| 83 | +> 质数唯一分解定理，构造 |
| 84 | +
|
| 85 | +由质数唯一分解定理，$$N=p1∗p2∗p3∗…∗pn$，任意一个大于1的正整数都可以被分解为若干个质数之积： |
| 86 | +于是我们就只需要去考虑是否存在(i,j)(i,j)对满足a[i]a[i]的质因数种类以及个数与a[j]a[j]的质因数种类相同并且互补就可了。 |
| 87 | + |
| 88 | + |
| 89 | +```cpp |
| 90 | +#include <bits/stdc++.h> |
| 91 | +using namespace std; |
| 92 | +using ll = long long; |
| 93 | +void solve(){ |
| 94 | + int n, k; |
| 95 | + cin >> n >> k; |
| 96 | + vector <int> cnt(100010); |
| 97 | + auto pow = [&](int a, int b)->ll{ //slow pow |
| 98 | + ll ans = 1; |
| 99 | + while(b--) { |
| 100 | + ans *= a; |
| 101 | + if(ans >= 1e5) return 0; |
| 102 | + } |
| 103 | + return ans; |
| 104 | + }; |
| 105 | + //由算数基本定理，一个>1正整数可分解为若干个质数之积 |
| 106 | + ll x, ans = 0; |
| 107 | + for(int i = 0; i < n; i++){ |
| 108 | + cin >> x; |
| 109 | + ll y = 1, z = 1; |
| 110 | + for(int i = 2; i * i <= x; i++){ //分解质因数 |
| 111 | + if(x % i == 0){ |
| 112 | + int s = 0; |
| 113 | + while(x % i == 0) x /= i, s++; |
| 114 | + s %= k; |
| 115 | + if(s) y *= pow(i, s), z *= pow(i, k - s); |
| 116 | + } |
| 117 | + } |
| 118 | + if(x > 1) y *= x, z *= pow(x, k - 1); |
| 119 | + if(z > 100000) ans += cnt[0]; |
| 120 | + else ans += cnt[z]; |
| 121 | + cnt[y]++; |
| 122 | + } |
| 123 | + cout << ans << endl; |
| 124 | + |
| 125 | +} |
| 126 | + |
| 127 | +int main(){ |
| 128 | + ios_base::sync_with_stdio(0); |
| 129 | + cin.tie(0); |
| 130 | + int t; |
| 131 | + t = 1; |
| 132 | + while(t--){ |
| 133 | + solve(); |
| 134 | + } |
| 135 | + return 0; |
| 136 | +} |
| 137 | +``` |
| 138 | + |
| 139 | + |
0 commit comments