문제 1: 간단한 문자열 처리 첫 번째 문제는 매우 straightforward합니다. 각 행의 문자를 추출하여 정렬한 후 최소 문자열을 만들고, 역순으로 배치하여 최대 문자열을 만들면 됩니다.

코드 확인하기

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

using ll = long long;
template<typename T>
void processRange(T* start, T* end, function<void(T*)> op) {
    for (T* p = start; p <= end; ++p) op(p);
}

int rowCount, colCount;
const int MAX = 3005;
char data[MAX][MAX];
char minStr[MAX][MAX];
char maxStr[MAX][MAX];
char buffer[MAX];
int elementCount;

bool compareSequences(char first[], char second[]) {
    for (int i = 1; i <= colCount; ++i) {
        if (first[i] < second[i]) return true;
        if (first[i] > second[i]) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> rowCount >> colCount;
    
    for (int i = 1; i <= rowCount; ++i) {
        cin >> (data[i] + 1);
    }
    
    for (int i = 1; i <= rowCount; ++i) {
        elementCount = 0;
        for (int j = 1; j <= colCount; ++j) {
            buffer[++elementCount] = data[i][j];
        }
        
        sort(buffer + 1, buffer + elementCount + 1);
        for (int j = 1; j <= elementCount; ++j) {
            minStr[i][j] = buffer[j];
        }
        
        reverse(buffer + 1, buffer + elementCount + 1);
        for (int j = 1; j <= elementCount; ++j) {
            maxStr[i][j] = buffer[j];
        }
    }
    
    for (int i = 1; i <= rowCount; ++i) {
        bool hasConflict = false;
        for (int j = 1; j <= rowCount; ++j) {
            if (j == i) continue;
            if (compareSequences(maxStr[j], minStr[i])) {
                hasConflict = true;
                cout << 0;
                break;
            }
        }
        if (!hasConflict) cout << 1;
    }
    
    return 0;
}

문제 2: 변수 상태 추적 이 문제는 변수에最后一次 할당된 값을 추적하는 것으로, 여러 상황을 나누어讨论해야 합니다.

Case 1: 특정 변수에 대한 이전 연산이 없는 경우

• 奇数번否定 연산이 수행됨 → U 상태
• 그렇지 않으면 U가 아님

Case 2: 이전에 v 클래스 할당이 존재하는 경우

• 否定 후元の値와 다름 → U 상태
• 그렇지 않으면 U가 아님

Case 3: 이전에 x_j 클래스 할당이 존재하는 경우 그래프를 구축합니다. x_j → x_i 방향의 간선을 만들고, 마지막 할당은 하나뿐이므로 각 노드는 하나의 부모만 가집니다. 최종적으로 트리가 형성되거나 순환이 발생할 수 있습니다. 간선 가중치는 할당 후 논리NOT 연산 횟수의奇偶性을 사용하고, 경로상의 가중치를 XOR로 계산합니다.

Case 3에서 U가 발생하는 조건은 다음과 같습니다: 실험 결과, 순환에 홀수 개의 1이 참여하면 순환상의 각 노드가 한 바퀴 돌고 나서 자신의 반대인 결론을導出합니다. 이 경우 순환상의 모든 노드가 U여야 하며, U에서導出된 자식 노드들도 U가 됩니다 (연산 특성에 의해 명확함).

훌륭한 대체 구현으로는 Union-Find를 사용하는 방법이 있습니다.

코드 확인하기

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

using int64 = long long;
const int MAXN = 100005;
const int TRUE_VAL = 100001;
const int FALSE_VAL = -100001;
const int UNKNOWN = 0;

int nodeCount, operationCount;
int parent[MAXN];
bool visited[3 * MAXN];

int findRoot(int x) {
    int result;
    
    if (x == TRUE_VAL || x == FALSE_VAL) {
        result = x;
    }
    else if (visited[nodeCount - x] || x == UNKNOWN) {
        result = UNKNOWN;
    }
    else if (visited[x + nodeCount]) {
        result = TRUE_VAL;
    }
    else if (x < 0) {
        if (x == -parent[-x]) {
            result = x;
        }
        else {
            visited[x + nodeCount] = true;
            result = findRoot(-parent[-x]);
            visited[x + nodeCount] = false;
        }
    }
    else {
        if (x == parent[x]) {
            result = x;
        }
        else {
            visited[x + nodeCount] = true;
            parent[x] = findRoot(parent[x]);
            result = parent[x];
            visited[x + nodeCount] = false;
        }
    }
    
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int testCase, queryCount;
    cin >> testCase >> queryCount;
    
    while (queryCount--) {
        cin >> nodeCount >> operationCount;
        
        for (int i = 1; i <= nodeCount; ++i) {
            parent[i] = i;
        }
        
        for (int i = 1; i <= operationCount; ++i) {
            char operation;
            int a, b;
            
            cin >> operation;
            
            if (operation == 'T') {
                cin >> a;
                parent[a] = TRUE_VAL;
            }
            else if (operation == 'F') {
                cin >> a;
                parent[a] = FALSE_VAL;
            }
            else if (operation == 'U') {
                cin >> a;
                parent[a] = UNKNOWN;
            }
            else {
                cin >> a >> b;
                if (operation == '+') {
                    parent[a] = parent[b];
                }
                else {
                    parent[a] = -parent[b];
                }
            }
        }
        
        int answer = 0;
        for (int i = 1; i <= nodeCount; ++i) {
            if (findRoot(i) == UNKNOWN) {
                answer++;
            }
        }
        
        cout << answer << "\n";
    }
    
    return 0;
}

문제 3: 주의력이 필요한 구현 세 번째 문제는 상당한 집중력이 필요합니다. 작성자는 O(T × n × m) 복잡도의 솔루션만 구현할 수 있었습니다.