A 마법 문 Trial

크기 비교 문제, 난이도 1성

#include <iostream>
using namespace std;

int main()
{
    int x, y, z, w;
    cin >> x >> y >> z >> w;
    
    if (x < w && y == z)
        cout << "YES";
    else
        cout << "NO";
    return 0;
}

B 약초 채집사

약초를 수집한 후 다중 배낭 DP로 해결 (5. 다중 배낭 문제 II - AcWing 참고), 시간 복잡도 O(n*m), 난이도 3성

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXM = 2010;
const int INF = 1e9 + 7;

int itemCount, capacity, typeCount;
int items[MAXN];
int value[MAXN];
int dp[MAXN];

int calculatePower(int quantity) {
    return static_cast<int>(log(quantity + 1) / log(2));
}

void solve() {
    cin >> itemCount >> capacity >> typeCount;
    
    map<int, int> typeMap;
    for (int i = 1; i <= itemCount; ++i) {
        int type;
        cin >> type;
        typeMap[type]++;
    }
    for (int i = 1; i <= typeCount; ++i)
        cin >> value[i];
    
    for (const auto& pair : typeMap) {
        for (int c = capacity; c >= 0; --c) {
            for (int qty = min(pair.ss, c); qty >= 1; --qty) {
                int power = calculatePower(qty);
                dp[c] = max(dp[c], dp[c - qty] + power * value[pair.ff]);
            }
        }
    }
    cout << dp[capacity] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

C 초기화达人

시뮬레이션 문제. 왼쪽에서 오른쪽으로 1을 덮어쓰면 된다, 난이도 1성

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

int main()
{
    int length;
    cin >> length;
    
    string binaryStr;
    cin >> binaryStr;
    
    int result = 0;
    int position = 0;
    
    while (position < length) {
        if (binaryStr[position] == '1') {
            result++;
            position += 2;
        } else if (binaryStr[position] == '0') {
            position++;
        }
    }
    
    cout << result;
    return 0;
}

G 문자열 최대公约수

같은 알파벳을 출력하면 된다, 난이도 1성

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

int main() {
    string firstStr, secondStr;
    cin >> firstStr >> secondStr;
    
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            if (firstStr[i] == secondStr[j]) {
                cout << firstStr[i];
                break;
            }
        }
    }
    return 0;
}

H 학자의 책갈피

상당한 시뮬레이션, 난이도 2성

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 5e6 + 10;
using int64 = long long;

int total;
queue<int> groupZero, groupOne, groupTwo;
queue<int> altZero, altOne, altTwo;

vector<int> buildSequence(queue<int>& q0, queue<int>& q1, queue<int>& q2, int startGroup) {
    vector<int> result;
    
    if (startGroup == 1 && !q1.empty()) {
        result.pb(q1.front());
        q1.pop();
    } else if (startGroup == 2 && !q2.empty()) {
        result.pb(q2.front());
        q2.pop();
    }
    
    int current = result.empty() ? 1 : startGroup;
    
    for (int i = 2; i <= total; ++i) {
        if (current == 1) {
            if (!q0.empty()) {
                result.pb(q0.front());
                q0.pop();
            } else if (!q1.empty()) {
                result.pb(q1.front());
                q1.pop();
                current = 2;
            } else {
                break;
            }
        } else {
            if (!q0.empty()) {
                result.pb(q0.front());
                q0.pop();
            } else if (!q2.empty()) {
                result.pb(q2.front());
                q2.pop();
                current = 1;
            } else {
                break;
            }
        }
    }
    return result;
}

void solve() {
    cin >> total;
    
    int64 sum = static_cast<int64>(total) * (total + 1) / 2;
    if (sum % 3 == 0) {
        cout << -1 << endl;
        return;
    }
    
    for (int i = 1; i <= total; ++i) {
        int mod = i % 3;
        if (mod == 0) {
            groupZero.push(i);
            altZero.push(i);
        } else if (mod == 1) {
            groupOne.push(i);
            altOne.push(i);
        } else {
            groupTwo.push(i);
            altTwo.push(i);
        }
    }
    
    vector<int> answer = buildSequence(groupZero, groupOne, groupTwo, 1);
    if (answer.size() == static_cast<size_t>(total)) {
        for (int val : answer)
            cout << val << " ";
        return;
    }
    
    answer = buildSequence(altZero, altOne, altTwo, 2);
    if (answer.size() == static_cast<size_t>(total)) {
        for (int val : answer)
            cout << val << " ";
        return;
    }
    
    cout << -1 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

I 카드 게임 2

결론 추측 + 시뮬레이션, 난이도 2성 교집합이 없으면 양쪽 모두 0, 교집합이 있으면 반드시 한쪽이 총점을 획득. 구체적인 승자는 시뮬레이션으로 결정.

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 1e6 + 10;
using int64 = long long;

int deckSizeA, deckSizeB;
int cardA[MAXN];
int cardB[MAXN];
bool existsA[MAXN];
bool inIntersection[MAXN];

void solve() {
    cin >> deckSizeA >> deckSizeB;
    
    int64 sharedSum = 0;
    for (int i = 1; i <= deckSizeA; ++i) {
        cin >> cardA[i];
        existsA[cardA[i]] = true;
    }
    
    for (int i = 1; i <= deckSizeB; ++i) {
        cin >> cardB[i];
        if (existsA[cardB[i]]) {
            sharedSum += cardB[i];
            inIntersection[cardB[i]] = true;
        }
    }
    
    if (sharedSum == 0) {
        cout << "0 0" << endl;
        return;
    }
    
    queue<int> nonSharedA, sharedA;
    for (int i = 1; i <= deckSizeA; ++i) {
        if (inIntersection[cardA[i]])
            sharedA.push(cardA[i]);
        else
            nonSharedA.push(cardA[i]);
    }
    
    queue<int> nonSharedB, sharedB;
    for (int i = 1; i <= deckSizeB; ++i) {
        if (inIntersection[cardB[i]])
            sharedB.push(cardB[i]);
        else
            nonSharedB.push(cardB[i]);
    }
    
    int turn = 1;
    while (!nonSharedA.empty() || !sharedA.empty()) {
        if (!nonSharedB.empty() || !sharedB.empty()) {
            if (turn == 1) {
                if (nonSharedA.empty()) {
                    cout << 0 << " " << sharedSum << endl;
                    return;
                }
                nonSharedA.pop();
                turn = 2;
            } else {
                if (nonSharedB.empty()) {
                    cout << sharedSum << " " << 0 << endl;
                    return;
                }
                nonSharedB.pop();
                turn = 1;
            }
        } else {
            break;
        }
    }
    
    if (turn == 1)
        cout << 0 << " " << sharedSum << endl;
    else
        cout << sharedSum << " " << 0 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

J 별빛 반딧불

K 문제를 먼저 풀어볼 것!

BFS, 난이도 4성; 연습 문제 P2802 귀가 -洛谷难度 3성

익숙해지면进阶: P8673 [蓝桥杯 2018 国 C] 미로와 함정 -洛谷难度 4성

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 1e6 + 10;
const int MAXM = 2010;
const int INF = 0x3f3f3f3f;

int rowCount, colCount;
int directionX[] = {0, 0, 1, -1};
int directionY[] = {-1, 1, 0, 0};
int nextDir[] = {1, 0, 3, 2};

bool blocked[MAXM][MAXM];
int distanceArray[MAXM][MAXM][4];

struct State {
    int x, y;
    int direction;
    int nextDirection;
    int cost;
    
    bool operator<(const State& other) const {
        return cost > other.cost;
    }
};

void findMinimumPath() {
    priority_queue<State> pq;
    for (int d = 0; d < 4; ++d) {
        pq.push({1, 1, d, nextDir[d], 0});
        distanceArray[1][1][d] = 0;
    }
    
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        
        int cx = current.x;
        int cy = current.y;
        int cd = current.direction;
        
        for (int nd = 0; nd < 4; ++nd) {
            if (nd == current.nextDirection)
                continue;
            
            int nx = cx + directionX[nd];
            int ny = cy + directionY[nd];
            int newCost = current.cost + (nd != cd ? 1 : 0);
            
            if (nx < 1 || nx > rowCount || ny < 1 || ny > colCount || blocked[nx][ny])
                continue;
            
            if (newCost < distanceArray[nx][ny][nd]) {
                distanceArray[nx][ny][nd] = newCost;
                pq.push({nx, ny, nd, nextDir[nd], newCost});
            }
        }
    }
    
    int minDistance = INF;
    for (int d = 0; d < 4; ++d)
        minDistance = min(minDistance, distanceArray[rowCount][colCount][d]);
    
    cout << minDistance << endl;
}

void solve() {
    memset(distanceArray, 0x3f, sizeof(distanceArray));
    cin >> rowCount >> colCount;
    
    for (int i = 1; i <= rowCount; ++i) {
        for (int j = 1; j <= colCount; ++j) {
            cin >> blocked[i][j];
        }
    }
    
    findMinimumPath();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

K 비트 연산 2

BFS, 난이도 2성 강의: AcWing 844. 미로 탐색 - AcWing 연습 문제: P1135 이상한 엘리베이터 -洛谷

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int MAXN = 5e6 + 10;
using int64 = long long;
const int64 MOD = 1e9 + 7;

int startNum, targetNum, referenceNum;
set<int> visitedSet;
queue<int> bfsQueue;

void solve() {
    cin >> startNum >> targetNum >> referenceNum;
    
    bfsQueue.push(startNum);
    visitedSet.insert(startNum);
    
    while (!bfsQueue.empty()) {
        int current = bfsQueue.front();
        bfsQueue.pop();
        
        if (current == referenceNum) {
            cout << "YES" << endl;
            return;
        }
        
        int result = current | targetNum;
        if (visitedSet.find(result) == visitedSet.end()) {
            visitedSet.insert(result);
            bfsQueue.push(result);
        }
        
        result = current & targetNum;
        if (visitedSet.find(result) == visitedSet.end()) {
            visitedSet.insert(result);
            bfsQueue.push(result);
        }
        
        result = current ^ targetNum;
        if (visitedSet.find(result) == visitedSet.end()) {
            visitedSet.insert(result);
            bfsQueue.push(result);
        }
    }
    
    cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

L 최대 평균값

DP, 이전 길이의 값을 상속해야 한다, 난이도 3성

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MAXM = 5010;
using int64 = long long;
const int INF = 1e9 + 7;

int elementCount;
int prefixSum[MAXM];
int dpTable[MAXM][MAXM];

void solve() {
    cin >> elementCount;
    
    for (int i = 1; i <= elementCount; ++i) {
        cin >> prefixSum[i];
        prefixSum[i] += prefixSum[i - 1];
    }
    
    for (int len = 2; len <= elementCount; ++len) {
        for (int start = 1; start + len - 1 <= elementCount; ++start) {
            int end = start + len - 1;
            dpTable[start][end] = max(dpTable[start + 1][end], dpTable[start][end - 1]);
            int segmentSum = prefixSum[end] - prefixSum[start - 1];
            dpTable[start][end] = max(dpTable[start][end], segmentSum / len);
        }
    }
    
    int64 totalResult = 0;
    for (int i = 1; i < elementCount; ++i) {
        for (int j = i + 1; j <= elementCount; ++j) {
            totalResult += dpTable[i][j];
        }
    }
    
    cout << totalResult << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

D 초등학교 1학년 지리

두 개의 배열만 유지하면 된다. 각각 상승 구간 또는 하락 구간의 왼쪽 끝점을 기록하여 판단할 수 있다

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
using int64 = long long;
const int MOD = 100003;
const int NEG_INF = 0x3f3f3f3f;

int queryCount, elementCount;
int arr[MAXN];
int leftAscending[MAXN];
int leftDescending[MAXN];

/*
leftAscending[i]: i번째 수 이전에 상승 추세를 유지하는 가장 낮은 위치
즉, (i번째 수가 속한) 상승 구간의 왼쪽 끝점 위치
*/
// leftDescending[i]: i번째 수 이전에 하락 추세를 유지하는 가장 낮은 위치, leftAscending 배열과 유사

void solve() {
    cin >> elementCount >> queryCount;
    
    for (int i = 1; i <= elementCount; ++i)
        cin >> arr[i];
    
    leftAscending[1] = leftDescending[1] = 1;
    
    for (int i = 2; i <= elementCount; ++i) {
        if (arr[i] < arr[i - 1]) {
            leftDescending[i] = leftDescending[i - 1];
            leftAscending[i] = i;
        } else {
            leftDescending[i] = i;
            leftAscending[i] = leftAscending[i - 1];
        }
    }
    
    while (queryCount--) {
        int l, r;
        cin >> l >> r;
        
        if (leftAscending[l] == leftAscending[r])
            cout << "u" << endl;
        else if (leftDescending[l] == leftDescending[r])
            cout << "d" << endl;
        else if (leftAscending[leftDescending[r]] <= l)
            cout << "t" << endl;
        else if (leftDescending[leftAscending[r]] <= l)
            cout << "v" << endl;
        else
            cout << "?" << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

F 시간은 흐르고, 연회는 영원히

문제는 G를 이진 트리로 취급한다. 즉, 해당 연결 성분에서 s의 차수는 최대 2이다. 이미 선택한 연결 성분 G에서 차수가 3인 노드 s'가 존재한다면, s'의了一条 가장자리를 버리고 연결된 전체 연결 성분을 버리면, s'가 조건을 만족하는 루트 노드가 될 때 답은 버려진 연결 성분上の 한 leaf 노드를 직접 루트 노드로 선택하는 것보다 반드시 나쁘다. 따라서 답의 연결 성분은 숲에서 하나의 완전한 트리를 선택하고, 차수가 3이 아닌 최소 노드를 루트 노드로 선택해야 한다. 전체 그래프를 순회하면 되고, 복잡도 O(n)

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int MAXM = 2010;
using int64 = long long;
const int64 INF64 = 0x3f3f3f3f3f3f3f3f;

int vertexCount, edgeCount;
int nodeValue[MAXN];
int degree[MAXN];
int head[MAXN];
int nextEdge[MAXN];
int toEdge[MAXN];
int edgeIndex;
bool visited[MAXN];

void addEdge(int from, int to) {
    toEdge[edgeIndex] = to;
    nextEdge[edgeIndex] = head[from];
    head[from] = edgeIndex++;
}

int64 evaluateComponent(int start) {
    queue<int> bfsQueue;
    bfsQueue.push(start);
    
    vector<int> component;
    component.pb(start);
    visited[start] = true;
    
    while (!bfsQueue.empty()) {
        int current = bfsQueue.front();
        bfsQueue.pop();
        
        for (int e = head[current]; e != -1; e = nextEdge[e]) {
            int neighbor = toEdge[e];
            if (visited[neighbor])
                continue;
            visited[neighbor] = true;
            bfsQueue.push(neighbor);
            component.pb(neighbor);
        }
    }
    
    int64 minVal = INF64;
    int64 sum = 0;
    
    for (int node : component) {
        sum += nodeValue[node];
        if (degree[node] <= 2)
            minVal = min(minVal, static_cast<int64>(nodeValue[node]));
    }
    
    return 2 * sum - minVal;
}

void solve() {
    memset(head, -1, sizeof(head));
    cin >> vertexCount >> edgeCount;
    
    for (int i = 1; i <= vertexCount; ++i)
        cin >> nodeValue[i];
    
    while (edgeCount--) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
        degree[u]++;
        degree[v]++;
    }
    
    int64 bestResult = 0;
    for (int i = 1; i <= vertexCount; ++i) {
        if (!visited[i])
            bestResult = max(bestResult, evaluateComponent(i));
    }
    
    cout << bestResult << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}