문제 T1: XOR과 K의 인수
시험 중에는 정해를 생각하지 못하고 브루트포스로 풀었습니다. 브루트포스는 접두사 XOR을 미리 계산한 후, 모든 구간을 순회하며 구간 XOR이 K의 약수인지 확인하는 방식입니다. 복잡도는 높지만 80점을 받을 수 있었습니다.
#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n, k, arr[N], pXor[N], factor[N], ans;
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
pXor[i] = arr[i] ^ pXor[i - 1];
}
for (int i = 1; i <= k; i++)
if (k % i == 0) factor[i] = 1;
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
int val = pXor[i - 1] ^ pXor[j];
if (factor[val]) ans++;
}
cout << ans << endl;
return 0;
}
정해: K의 약수는 √K까지만枚举하면 됩니다. 모든 접두사 XOR을 버킷에 저장한 후, K의 각 약수에 대해 버킷을 이용해 O(N)으로 답을 구합니다. K가 완전 제곱수일 때 중복을 제거해야 합니다.
#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n, k, arr[N], bucket[N], ans;
signed main() {
cin >> n >> k;
bucket[0] = 1;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
arr[i] ^= arr[i - 1];
bucket[arr[i]]++;
}
for (int i = 1; i * i <= k; i++) {
if (k % i != 0) continue;
int res = 0;
for (int j = 0; j <= n; j++)
res += bucket[arr[j] ^ i] + bucket[arr[j] ^ (k / i)];
if (i * i == k) res /= 2;
ans += res;
}
cout << ans / 2 << endl;
return 0;
}
문제 T2: 최대 평균값 구간
시험 중에는 세그먼트 트리로 풀 생각을 못하고 브루트포스로 구간을 모두枚举했습니다. 하지만 시간 초과가 났습니다.
#include <bits/stdc++.h>
#define int long long
#define DB double
#define N 1000100
using namespace std;
int n, m, a[N], sum[N];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
while (m--) {
int op; cin >> op;
if (op == 1) {
int l, r, x; cin >> l >> r >> x;
for (int i = l; i <= r; i++) a[i] += x;
for (int i = l; i <= n; i++) sum[i] = sum[i - 1] + a[i];
} else {
int l, r; cin >> l >> r;
int bestNum = 0, bestDen = 1;
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++) {
int num = sum[j] - sum[i - 1];
int den = j - i + 1;
if ((DB)num / den > (DB)bestNum / bestDen) {
int g = __gcd(num, den);
bestNum = num / g;
bestDen = den / g;
}
}
cout << bestNum << "/" << bestDen << endl;
}
}
return 0;
}
생각해보면, 구간 내 최대 평균은 원소 2개 또는 3개로 구성된 구간에서만 발생합니다. 따라서 두 개의 세그먼트 트리를 사용합니다. 하나는 길이 2 구간, 다른 하나는 길이 3 구간의 최대 합을 저장합니다. 갱신 시에는 경계 처리를 주의해야 합니다.
#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n, m, A[N], B[N];
struct SegTree {
int tree[N << 2], lazy[N << 2];
void pushUp(int x) { tree[x] = max(tree[x << 1], tree[x << 1 | 1]); }
void pushDown(int x) {
if (!lazy[x]) return;
tree[x << 1] += lazy[x];
tree[x << 1 | 1] += lazy[x];
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
lazy[x] = 0;
}
void build(int x, int l, int r) {
if (l == r) { tree[x] = B[l]; return; }
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
pushUp(x);
}
int query(int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[x];
pushDown(x);
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) res = max(res, query(x << 1, l, mid, ql, qr));
if (qr > mid) res = max(res, query(x << 1 | 1, mid + 1, r, ql, qr));
return res;
}
void update(int x, int l, int r, int ul, int ur, int val) {
if (ul <= l && r <= ur) { tree[x] += val; lazy[x] += val; return; }
pushDown(x);
int mid = (l + r) >> 1;
if (ul <= mid) update(x << 1, l, mid, ul, ur, val);
if (ur > mid) update(x << 1 | 1, mid + 1, r, ul, ur, val);
pushUp(x);
}
} seg[2]; // 0: 길이 2, 1: 길이 3
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i <= n; i++) B[i] = A[i] + A[i + 1];
seg[0].build(1, 1, n);
for (int i = 1; i <= n; i++) B[i] += A[i + 2];
seg[1].build(1, 1, n);
while (m--) {
int op, l, r, x; cin >> op >> l >> r;
if (op == 1) {
cin >> x;
if (l <= r - 1) seg[0].update(1, 1, n, l, r - 1, 2 * x);
if (l - 1 >= 1) seg[0].update(1, 1, n, l - 1, l - 1, x);
if (r <= n) seg[0].update(1, 1, n, r, r, x);
if (l <= r - 2) seg[1].update(1, 1, n, l, r - 2, 3 * x);
if (l - 1 >= 1) seg[1].update(1, 1, n, l - 1, l - 1, 2 * x);
if (r - 1 >= 1) seg[1].update(1, 1, n, r - 1, r - 1, 2 * x);
if (l - 2 >= 1) seg[1].update(1, 1, n, l - 2, l - 2, x);
if (r <= n) seg[1].update(1, 1, n, r, r, x);
} else {
if (r - l == 1) {
int ans = seg[0].query(1, 1, n, l, l);
if (ans % 2 == 0) cout << ans / 2 << "/1" << endl;
else cout << ans << "/2" << endl;
} else {
int ans = max(3 * seg[0].query(1, 1, n, l, r - 1), 2 * seg[1].query(1, 1, n, l, r - 2));
int div = 6;
if (ans % 2 == 0) { ans /= 2; div /= 2; }
if (ans % 3 == 0) { ans /= 3; div /= 3; }
cout << ans << "/" << div << endl;
}
}
}
return 0;
}
문제 T3: 특정 값과 같은 구간 쌍
브루트포스로 각 구간 쌍을 직접 검사했습니다. 모든 구간을枚举하고, 두 값이 모두 x인지 확인한 후, 그 사이에 값이 다른 곳이 있는지 세어 답을 구했습니다.
#include <bits/stdc++.h>
#define int long long
#define N 1000100
using namespace std;
int n, m, a[N];
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
while (m--) {
int op, l, r, x; cin >> op >> l >> r >> x;
if (op == 1) a[l] = x;
else {
int ans = 0;
for (int i = l; i <= r; i++)
for (int j = i + 1; j <= r; j++) {
if (a[i] != x || a[j] != x) continue;
for (int k = i; k < j; k++)
if (a[k] != a[k + 1]) ans++;
}
cout << ans << endl;
}
}
return 0;
}
문제 T4: 값 이동 연산
시험 중에는 단순히 각 연산을 수행한 후, 배열 전체를 순회하며 값을 이동시켰습니다. 후속 연산에 영향을 주지 않도록 임시 배열을 사용했습니다.
#include <bits/stdc++.h>
#define N 1000100
using namespace std;
int n, m, a[N], cnt[N], tmp[N], last;
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> m;
while (m--) {
int x; cin >> x;
x ^= last;
cnt[x]++;
cout << cnt[x] << endl;
last = cnt[x];
for (int i = 1; i <= n; i++) tmp[i] = cnt[i];
for (int i = 1; i <= n; i++)
cnt[i] -= tmp[i], cnt[a[i]] += tmp[i];
}
return 0;
}