P1092 NOIP2004 Senior Division: Alphametic Puzzle

This problem involves solving an alphametic puzzle where letters represent digits in a base-N addition. The solution uses depth-first search with pruning to assign digits to letters efficient.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 30;
char term1[MAX_N], term2[MAX_N], result[MAX_N];
int idx1[MAX_N], idx2[MAX_N], idxRes[MAX_N];
int baseSize;

int mapping[MAX_N];
bool digitUsed[MAX_N];
int searchOrder[MAX_N];
int orderCount;

void validateSolution() {
    int carry = 0;
    for (int pos = baseSize - 1; pos >= 0; pos--) {
        int digit1 = mapping[idx1[pos]];
        int digit2 = mapping[idx2[pos]];
        int digitRes = mapping[idxRes[pos]];
        if ((digit1 + digit2 + carry) % baseSize != digitRes)
            return;
        carry = (digit1 + digit2 + carry) / baseSize;
    }
    for (int i = 0; i < baseSize; i++)
        cout << mapping[i] << ' ';
    exit(0);
}

void backtrack(int assignedCount) {
    if (mapping[idx1[0]] + mapping[idx2[0]] >= baseSize)
        return;
    for (int pos = baseSize - 1; pos >= 0; pos--) {
        int d1 = mapping[idx1[pos]];
        int d2 = mapping[idx2[pos]];
        int dRes = mapping[idxRes[pos]];
        if (d1 == -1 || d2 == -1 || dRes == -1)
            continue;
        if ((d1 + d2) % baseSize != dRes && (d1 + d2 + 1) % baseSize != dRes)
            return;
    }

    if (assignedCount == baseSize) {
        validateSolution();
        return;
    }

    for (int digit = baseSize - 1; digit >= 0; digit--) {
        if (!digitUsed[digit]) {
            mapping[searchOrder[assignedCount]] = digit;
            digitUsed[digit] = true;
            backtrack(assignedCount + 1);
            digitUsed[digit] = false;
            mapping[searchOrder[assignedCount]] = -1;
        }
    }
}

void buildOrder(int letter) {
    if (!digitUsed[letter]) {
        digitUsed[letter] = true;
        searchOrder[orderCount++] = letter;
    }
}

int main() {
    cin >> baseSize;
    scanf("%s%s%s", term1, term2, result);

    for (int i = 0; i < baseSize; i++) {
        idx1[i] = term1[i] - 'A';
        idx2[i] = term2[i] - 'A';
        idxRes[i] = result[i] - 'A';
        mapping[i] = -1;
    }

    for (int pos = baseSize - 1; pos >= 0; pos--) {
        buildOrder(idx1[pos]);
        buildOrder(idx2[pos]);
        buildOrder(idxRes[pos]);
    }

    for (int i = 0; i < baseSize; i++)
        digitUsed[i] = false;

    backtrack(0);
    return 0;
}

P5691 NOI2001: Equation Solutions Count

This problem requires counting the number of integer solutions to a polynomial equation within a given range. The solution employs meet-in-the-middle technique with two depth-first searches.

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_TERMS = 10;
const int MAX_SOLUTIONS = 4000006;
int termCount, maxValue;
int coefficients[MAX_TERMS], exponents[MAX_TERMS];

int leftValues[MAX_SOLUTIONS], rightValues[MAX_SOLUTIONS];

int power(int base, int exp) {
    int result = 1;
    for (; exp; exp >>= 1) {
        if (exp & 1) result *= base;
        base *= base;
    }
    return result;
}

void generateValues(int start, int end, int currentSum, int storage[], int &count) {
    if (start > end) {
        storage[++count] = currentSum;
        return;
    }
    for (int value = 1; value <= maxValue; value++)
        generateValues(start + 1, end, currentSum + coefficients[start] * power(value, exponents[start]), storage, count);
}

int main() {
    cin >> termCount >> maxValue;
    for (int i = 1; i <= termCount; i++)
        cin >> coefficients[i] >> exponents[i];

    int midPoint = (1 + termCount) >> 1;
    int leftCount = 0, rightCount = 0;
    generateValues(1, midPoint, 0, leftValues, leftCount);
    generateValues(midPoint + 1, termCount, 0, rightValues, rightCount);

    sort(leftValues + 1, leftValues + 1 + leftCount);
    sort(rightValues + 1, rightValues + 1 + rightCount);

    int totalSolutions = 0;
    int rightPtr = rightCount;
    for (int leftPtr = 1; leftPtr <= leftCount && rightPtr >= 1; leftPtr++) {
        while (leftValues[leftPtr] + rightValues[rightPtr] > 0)
            rightPtr--;
        int leftDuplicates = 1, rightDuplicates = 0;
        for (int j = rightPtr; leftValues[leftPtr] + rightValues[j] == 0 && j > 0; j--)
            rightDuplicates++;
        while (leftPtr < leftCount && leftValues[leftPtr] == leftValues[leftPtr + 1])
            leftDuplicates++, leftPtr++;
        totalSolutions += leftDuplicates * rightDuplicates;
    }

    cout << totalSolutions;
    return 0;
}

P3956 NOIP2017 Junior Division: Colored Board Game

This problem involves finding the minimum cost to traverse a colored board with specific movement rules. The solution uses a priority queue-based BFS with state tracking.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int BOARD_SIZE = 102;
const int MOVES = 12;
const int dx[MOVES] = {0, 1, 0, -1, 1, 1, -1, -1, 0, 2, 0, -2};
const int dy[MOVES] = {1, 0, -1, 0, 1, -1, 1, -1, 2, 0, -2, 0};
const int baseCost[MOVES] = {0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2};

struct State {
    int row, col, color, cost;
    bool operator<(const State &other) const {
        return cost > other.cost;
    }
};

int board[BOARD_SIZE][BOARD_SIZE];
int boardSize, coloredCells;
int minCost[BOARD_SIZE][BOARD_SIZE];

void findMinimumCost() {
    memset(minCost, 0x3f, sizeof(minCost));
    minCost[1][1] = 0;
    priority_queue<State> pq;
    pq.push({1, 1, board[1][1], 0});

    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();

        if (minCost[current.row][current.col] < current.cost)
            continue;

        for (int move = 0; move < MOVES; move++) {
            State next;
            next.row = current.row + dx[move];
            next.col = current.col + dy[move];
            next.cost = current.cost + baseCost[move];
            if (next.row <= 0 || next.row > boardSize || next.col <= 0 || next.col > boardSize)
                continue;
            next.color = board[next.row][next.col];
            if (next.color == 0)
                continue;
            if (current.color != next.color)
                next.cost++;
            if (minCost[next.row][next.col] > next.cost) {
                minCost[next.row][next.col] = next.cost;
                pq.push(next);
            }
        }
    }
}

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

    cin >> boardSize >> coloredCells;
    for (int i = 1; i <= coloredCells; i++) {
        int x, y, color;
        cin >> x >> y >> color;
        board[x][y] = color + 1;
    }

    findMinimumCost();

    if (board[boardSize][boardSize] == 0) {
        int finalCost = min(minCost[boardSize][boardSize - 1], minCost[boardSize - 1][boardSize]) + 2;
        if (finalCost >= INF)
            cout << "-1";
        else
            cout << finalCost;
    } else {
        if (minCost[boardSize][boardSize] == INF)
            cout << "-1";
        else
            cout << minCost[boardSize][boardSize];
    }
    return 0;
}