이 문서에서는 최소 신장 트리, 배열의 반복 비교, 그리고 비트 연산 기반 그래프 문제를 다룹니다. 각 문제는 별도의 접근 방식과 알고리즘 구현을 필요로 합니다.

문제 1: 최소 신장 트리

배열 p가 주어졌을 때, 이를 바탕으로 n개의 정점을 가진 완전 무방향 그래프를 생성합니다. 두 정점 i와 j 사이의 간선 가중치는 |pi - pj| × |i - j|로 계산됩니다. 이 그래프에서 최소 신장 트리의 총 간선 가중치를 구하는 것이 목표입니다.

해결 방법은 간선 가중치가 n보다 작은 경우에만 의미 있다는 점을 이용합니다. 또한 두 수의 곱이 x 이하라면 적어도 하나의 수는 √x 이하라는 특성을 활용하여 효율적으로 간선을 생성할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int from;
    int to;
    long weight;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> p(n+1);
    for(int i=1;i<=n;i++) cin >> p[i];

    int maxEdge = sqrt(n) + 1;
    vector<Edge> edges;

    for(int i=1;i<=n;i++){
        for(int j=max(1, i-maxEdge);j bool{
        return a.weight < b.weight;
    });

    vector<int> parent(n+1);
    for(int i=1;i<=n;i++) parent[i]=i;

    function<int(int)> find_set=[&](int x) -> int{
        if(parent[x]!=x) parent[x]=find_set(parent[x]);
        return parent[x];
    };

    long long result = 0;
    for(auto &edge : edges){
        int x_root = find_set(edge.from);
        int y_root = find_set(edge.to);
        if(x_root != y_root){
            parent[y_root] = x_root;
            result += edge.weight;
        }
    }
    cout << result;
}

문제 2: 배열 요소 비교

두 개의 배열 a와 b가 주어졌습니다. 배열 a를 m번, 배열 b를 n번 반복하여 길이가 n×m인 새로운 배열 c와 d를 만듭니다. c와 d의 각 요소를 비교하여 c<d, c>d, c=d인 경우의 수를 계산하는 것이 목표입니다.

해결 방법은 배열 a와 b의 요소들이 gcd(n,m) 모듈러 그룹으로 나뉘어지며, 각 그룹 내에서만 비교가 이루어진다는 점을 활용합니다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<int> a(n+1), b(m+1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> b[i];

    int g = __gcd(n, m);
    vector<vector<int>> groupsA(g), groupsB(g);

    for(int i=1;i<=n;i++) groupsA[(i-1)%g].push_back(a[i]);
    for(int i=1;i<=m;i++) groupsB[(i-1)%g].push_back(b[i]);

    long long less=0, greater=0, equal=0;

    for(int i=0;i

#include <bits/stdc++.h>
using namespace std;

struct Graph {
    int dest;
    long weight;
};

long long dijkstra(vector<vector<Graph>> &adj, int start){
    priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
    vector<long> dist(adj.size(), LLONG_MAX);
    pq.push({0, start});
    dist[start] = 0;

    while(!pq.empty()){
        auto [currentDist, node] = pq.top(); pq.pop();
        if(currentDist > dist[node]) continue;
        for(auto &[nextNode, weight] : adj[node]){
            if(dist[nextNode] > dist[node] + weight){
                dist[nextNode] = dist[node] + weight;
                pq.push({dist[nextNode], nextNode});
            }
        }
    }
    return accumulate(dist.begin()+1, dist.end(), 0LL);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, s;
    long k;
    cin >> n >> m >> s >> k;
    vector<Graph> edges(m);
    for(int i=0;i> edges[i].dest >> edges[i].weight;

    if(s ==1 ){
        // AND
    }else if(s ==2){
        // XOR
    }else{
        // OR
    }
}