A - Last Two Digits
단순 문자열 문제입니다.
B - Practical Computing
문제에서 주어진 대로 구현하면 됩니다.
C - K Swap
관찰하면 인덱스 \(i\)가 \(k\)로 나눈 나머지 끼리의 위치끼를 서로 swap을 해줄 수 있습니다. 그러므로 같은 나머지끼리 묶인 그룹들은 무조건 오름차순으로 정렬할 수 있습니다.
나눈 그룹들을 전체로 합친 다음 오름차순의 결과와 같은 지 확인해주면 됩니다.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
//https://github.com/egod1537/cfLibrary
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
#define rev(x) reverse(x.begin(), x.end())
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p) {
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt) {
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
void solve() {
int n, k; cin >> n >> k;
vector<int> arr(n);
for (int& w : arr) cin >> w;
vector<vector<int>> vec(k, vector<int>());
for (int i = 0; i < n; i++) {
vec[i % k].push_back(arr[i]);
}
for (int i = 0; i < k; i++)
sort(all(vec[i]));
sort(all(arr));
int idx = 0, now = 0;
for (int i = 0; i < n; i++) {
if (vec[now][idx] != arr[i]) {
cout << "No";
return;
}
now++;
if (now == k) now = 0, idx++;
}
cout << "Yes";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
D - Together Square
제곱수를 다르게 정의하자면, 소인수 분해를 했을 때, 각 소인수의 지수가 모두 짝수여야 됩니다. \((i, j)\) 에서 \(i\)를 고정해놓고 볼 때, \(i\)의 소인수 중 지수가 홀수 인 것들만 곱한 수를 \(k\)라고 정의합니다.
그렇다면 \(j\)는 \(k*p^2\)가 되야 되며 \(k*p^2 \le N\)을 만족하는 \(p\)의 개수를 세주면 됩니다. 시간 복잡도는 \(O(N\sqrt{N})\)입니다.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
//https://github.com/egod1537/cfLibrary
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
#define rev(x) reverse(x.begin(), x.end())
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p) {
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt) {
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
vector<int> f(int x) {
vector<int> ans;
for (int i = 2; i * i <= x; i++) {
int cnt = 0;
while (x % i == 0) {
x /= i, cnt++;
}
if (cnt) {
cnt %= 2;
if (cnt) ans.push_back(i);
}
}
if (x > 1) ans.push_back(x);
return ans;
}
void solve() {
int n; cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
vector<int> v = f(i);
ll p = 1;
for (int& w : v) p *= w;
for (ll j = 1; j <= n && j * j * p <= n; j++)
ans++;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
E - Small d and k
쿼리마다 거리가 \(K\)이하인 모든 정점을 순회하면 됩니다. 왜냐하면 \(K\)가 \(3\)이하라는 조건이 있지만, 자식이 많은 경우 TLE가 날 수 있습니다.
하지만 이 문제에서 모든 정점의 차수는 \(3\)이하이므로 각 쿼리가 가장 많이 순회할려면 대략적으로 완전이진트리의 형태를 가져야 된다는 사실을 알 수 있고, 기껏해봐야 순회해하는 정점의 개수는 \(logN\)이하일 것 입니다.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
//https://github.com/egod1537/cfLibrary
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
#define rev(x) reverse(x.begin(), x.end())
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p) {
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt) {
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
vector<int> V[200002];
bool vit[222222];
void solve() {
int n, m; cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
}
int q; cin >> q;
while (q--) {
int x, k; cin >> x >> k;
vector<int> vec;
queue<pi> q;
q.push({x, 0}); vit[x] = true;
ll ans = 0;
while (q.size()) {
pi top = q.front(); q.pop();
ans += top.first;
vec.push_back(top.first);
for (int w : V[top.first]) {
if (vit[w]) continue;
int d = top.second + 1;
if (d <= k) {
vit[w] = true;
q.push({w, d});
}
}
}
cout << ans << "\n";
for (int w : vec) vit[w] = false;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
F - Rectangle GCD
gcd의 성질을 잘 활용하면 해결할 수 있는 문제입니다. 먼저 예저 1번의 \((1,1) ~ (3, 3)\) 쿼리를 한번 봅시다.
\(gcd(A1+B1, A1+B2, A1+B3, A2+B1, A2+B2, A2+B3, A3+B1, A3+B2, A3+B3)\)
으로 나타낼 수 있고, gcd에서 성질을 잘 활용하면
\(gcd(B1-B2, B2-B3, A1+B3, B1-B2, B2-B3, A2+B3, B1-B2, B2-B3, A3+B3)\)
\(B\)값의 차이만큼끼리 gcd를 해주는 걸로 볼 수 있고, 또 \(A\)에 대해 성질을 적용하면
\(gcd(B1-B2, B2-B3, A1-A2, B1-B2, B2-B3, A2-A3, B1-B2, B2-B3, A3+B3)\)
\(gcd(B1-B2, B2-B3, A1-A2, A2-A3, A3+B3)\)
이런식으로 처리할 수 있습니다. \(A\)의 범위중 차이에 대한 gcd와 \(B\)도 동일하게 적용하여 gcd를 구하고 마지막으로 \(AW+BH\)와 gcd를 해줄 수 있습니다. 구간의 gcd는 세그먼트 트리로 빠르게 처리할 수 있습니다.
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
#pragma GCC target("avx,avx2,fma")
//https://github.com/egod1537/cfLibrary
#include <bits/stdc++.h>
#include <unordered_map>
#include <random>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define debug(x) cout << (#x) << " " << x << "\n";
#define compress(x) sort(all(x)); x.erase(unique(all(x)), x.end());
#define rev(x) reverse(x.begin(), x.end())
typedef long double ld;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
#define fi first
#define se second
int dx4[4] = { 1, 0, -1, 0 };
int dy4[4] = { 0, 1, 0, -1 };
int dx8[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy8[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
typedef complex<double> base;
const double PI = acos(-1);
template<typename T>
pair<T, T> operator+(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi + b.fi, a.se + b.se); }
template<typename T>
pair<T, T> operator-(const pair<T, T>& a, const pair<T, T>& b) { return pi(a.fi - b.fi, a.se - b.se); }
template<typename T>
pair<T, T> operator*(const pair<T, T>& a, ll b) { return pi(a.fi * b, a.se * b); }
template<typename T>
ostream& operator<<(ostream& os, pair<T, T> p) {
os << "(" << p.fi << ", " << p.second << ")";
return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
for (T w : vec) os << w << " ";
return os;
}
ll ccw(pi a, pi b, pi c) { return (b.fi - a.fi) * (c.se - a.se) - (c.fi - a.fi) * (b.se - a.se); }
ll gcd(ll a, ll b) { return (!b ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll mypow(ll x, ll cnt) {
if (!cnt) return 1;
ll mid = mypow(x, cnt / 2);
return mid * mid * (cnt % 2 ? x : 1);
}
struct Seg {
int n;
vector<int> seg;
void init(int _n) {
n = _n;
seg.resize(4*n);
}
int update(int num, int s, int e, int idx, int p) {
if (idx < s || e < idx) return seg[num];
if (s == e) return seg[num] = p;
int mid = s + e >> 1;
return seg[num] = gcd(update(2 * num, s, mid, idx, p), update(2 * num + 1, mid + 1, e, idx, p));
}
void update(int idx, int p) { update(1, 0, n-1, idx, p); }
int query(int num, int s, int e, int l, int r) {
if (r < s || e < l) return 0;
if (l <= s && e <= r) return seg[num];
int mid = s + e >> 1;
return gcd(query(2 * num, s, mid, l, r), query(2 * num + 1, mid + 1, e, l, r));
}
int query(int l, int r) { return query(1, 0, n-1, l, r); }
};
void solve() {
int n, q; cin >> n >> q;
vector<int> A(n + 1), B(n + 1);
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i <= n; i++) cin >> B[i];
Seg aseg, bseg;
aseg.init(n+1); bseg.init(n + 1);
for (int i = 1; i < n; i++) aseg.update(i, abs(A[i]-A[i+1]));
for (int i = 1; i < n; i++) bseg.update(i, abs(B[i]-B[i+1]));
while (q--) {
int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
int a = x1, b = y1, c = x2, d = y2;
int ans = aseg.query(a, c - 1);
ans = gcd(ans, bseg.query(b, d - 1));
ans = gcd(ans, A[c] + B[d]);
cout << ans << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int tc = 1;
while (tc--) solve();
return 0;
}
|
cs |
'PS > Codeforces' 카테고리의 다른 글
AtCoder Beginner Contest 243 (0) | 2022.03.15 |
---|---|
Codeforces Round #777 (Div. 2) (0) | 2022.03.14 |
Codeforces Round #725 (Div. 3) (0) | 2021.12.01 |
Codeforces Round #702 (Div. 3) (0) | 2021.12.01 |
[Codeforce] Educational Codeforces Round 104 (Rated for Div. 2) (0) | 2021.12.01 |