不知不觉成为初三老登了...

但我的水平还停留在初二啊喂 QAQ

QQ 2234970744

能写题解的题目：

AT_abc282_h 笛卡尔树 + 启发式合并做法

CF1361 字典树 + 欧拉回路做法

AT_abc379_g

#include <bits/stdc++.h>
#define Code using
#define by namespace
#define zzx std
Code by zzx;

const int N = 200, mod = 998244353;

int h, w, a[N + 10][N + 10];
vector<int> s[N + 10], dp[N + 10];

void dfs(int j, int la, int state, int i) {
	if(j == w + 1) {
		s[i].push_back(state); dp[i].push_back(-1);
	}
	if(a[i][j] >= 0) {
		if(a[i][j] == la) return;
		dfs(j + 1, a[i][j], state * 3 + a[i][j], i); return;
	}
	for(int x = 0; x < 3; ++x) {
		if(x == la) continue;
		dfs(j + 1, x, state * 3 + x, i);
	}
}

bool check(int u, int v) {
	for(int i = 1; i <= w; ++i) {
		if(u % 3 == v % 3) return false;
		u /= 3; v /= 3;
	}
	return true;
}

int dfs2(int u, int id) {
	if(u == 1) return 1;
	if(dp[u][id] != -1) return dp[u][id];
	int res = 0;
	for(int i = 0; i < (int)s[u - 1].size(); ++i) {
		if(check(s[u][id], s[u - 1][i])) res = (res + dfs2(u - 1, i));
	}
	dp[u][id] = res; return res;
}

int main() {
	cin >> h >> w;
	for(int i = 1; i <= h; ++i) {
		string tmp; cin >> tmp;
		for(int j = 1; j <= w; ++j) {
			int x;
			if(tmp[j - 1] == '1') x = 0;
			else if(tmp[j - 1] == '2') x = 1;
			else if(tmp[j - 1] == '3') x = 2;
			else x = -1;
			if(h >= w) a[i][j] = x;
			else a[j][i] = x;
		}
	}
	if(h < w) swap(h, w);
	for(int i = 1; i <= h; ++i) dfs(1, -1, 0, i);
	int ans = 0;
	for(int i = 0; i < (int)s[h].size(); ++i) ans = (ans + dfs2(h, i));
	cout << ans;
	return 0;
}

P2152 hack

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>

// 高精度数字结构体
struct HighPrecision {
private:
    std::vector<int> digits;  // 存储数字的每一位，低位在前
    bool isNegative;          // 标记是否为负数

    // 移除前导零（优化：一次resize代替多次pop_back）
    void trimLeadingZeros() {
        if (digits.size() <= 1) return;
        
        // 从高位向低位查找第一个非零数字
        auto it = digits.rbegin();
        while (it != digits.rend() && *it == 0) {
            ++it;
        }
        
        // 处理全零情况
        if (it == digits.rend()) {
            digits.resize(1);
            digits[0] = 0;
        } else {
            // 直接调整大小，避免多次pop_back
            digits.resize(it.base() - digits.begin());
        }
    }

    // 两个正数的数字相加（优化：分阶段处理，减少条件判断）
    std::vector<int> addDigits(const std::vector<int>& a, const std::vector<int>& b) const {
        std::vector<int> result;
        // 提前预留最大可能空间，避免多次扩容
        result.reserve(std::max(a.size(), b.size()) + 1);
        int carry = 0;
        size_t minLen = std::min(a.size(), b.size());
        
        // 第一阶段：处理两个数共有的位数
        for (size_t i = 0; i < minLen; ++i) {
            int sum = a[i] + b[i] + carry;
            result.push_back(sum % 10);
            carry = sum / 10;
        }
        
        // 第二阶段：处理a的剩余位数
        for (size_t i = minLen; i < a.size(); ++i) {
            int sum = a[i] + carry;
            result.push_back(sum % 10);
            carry = sum / 10;
        }
        
        // 第三阶段：处理b的剩余位数
        for (size_t i = minLen; i < b.size(); ++i) {
            int sum = b[i] + carry;
            result.push_back(sum % 10);
            carry = sum / 10;
        }
        
        // 处理最后的进位
        if (carry > 0) {
            result.push_back(carry);
        }
        
        return result;
    }

public:
    // 构造函数
    HighPrecision() : isNegative(false), digits({0}) {}
    HighPrecision(const std::string& str) {
        fromString(str);
    }
    
    // 移动构造函数（减少复制开销）
    HighPrecision(HighPrecision&& other) noexcept
        : digits(std::move(other.digits)), isNegative(other.isNegative) {}
    
    // 移动赋值运算符（减少复制开销）
    HighPrecision& operator=(HighPrecision&& other) noexcept {
        if (this != &other) {
            digits = std::move(other.digits);
            isNegative = other.isNegative;
        }
        return *this;
    }

    // 字符串转为高精度数字（优化：提前预留空间）
    void fromString(const std::string& str) {
        digits.clear();
        isNegative = false;
        size_t start = 0;
        
        // 处理负号
        if (!str.empty() && str[0] == '-') {
            isNegative = true;
            start = 1;
        }
        
        // 提前预留空间，避免多次内存分配
        digits.reserve(str.size() - start);
        
        // 从字符串读取数字，逆序存储（低位在前）
        for (int i = str.size() - 1; i >= static_cast<int>(start); --i) {
            if (isdigit(str[i])) {
                digits.push_back(str[i] - '0');
            } else {
                // 如果包含非数字字符，视为0
                digits.clear();
                isNegative = false;
                digits.push_back(0);
                return;
            }
        }
        
        // 处理空字符串或全是符号的情况
        if (digits.empty()) {
            digits.push_back(0);
        }
        
        trimLeadingZeros();
    }

    // 加法运算
    HighPrecision add(const HighPrecision& other) const {
        HighPrecision result;
        
        if (!isNegative && !other.isNegative) {
            // 两个正数相加
            result.isNegative = false;
            result.digits = addDigits(digits, other.digits);
        } else if (isNegative && other.isNegative) {
            // 两个负数相加
            result.isNegative = true;
            result.digits = addDigits(digits, other.digits);
        } else {
            // 暂不实现正负混合加法，仅处理同号加法
            result.digits = {0};
            result.isNegative = false;
        }
        
        result.trimLeadingZeros();
        return result;
    }

    // 获取数字位数
    size_t getDigitCount() const {
        return digits.size();
    }

    // 输出数字（优化：使用下标访问代替reverse_iterator）
    void print() const {
        if (isNegative && !(digits.size() == 1 && digits[0] == 0)) {
            std::cout << "-";
        }
        // 从高位到低位输出
        for (int i = digits.size() - 1; i >= 0; --i) {
            std::cout << digits[i];
        }
    }

    // 转换为字符串（优化：提前预留空间，使用下标访问）
    std::string toString() const {
        std::string str;
        // 提前预留空间
        str.reserve(digits.size() + (isNegative ? 1 : 0));
        
        if (isNegative && !(digits.size() == 1 && digits[0] == 0)) {
            str += "-";
        }
        
        // 从高位到低位添加
        for (int i = digits.size() - 1; i >= 0; --i) {
            str += char('0' + digits[i]);
        }
        return str;
    }
} a, b, c;

// 重载加法运算符
HighPrecision operator+(const HighPrecision& a, const HighPrecision& b) {
    return a.add(b);
}

// 重载输出运算符
std::ostream& operator<<(std::ostream& os, const HighPrecision& hp) {
    os << hp.toString();
    return os;
}

int main() {
    a.fromString("1"); 
    b.fromString("1");
    
    while(true) {
        c = a + b;
        if(c.getDigitCount() >= 100000) {
        	freopen("hack.in", "w", stdout);
            a.print(); 
            putchar('\n');
            b.print(); 
            return 0;
        }
        // 使用移动语义，避免不必要的深拷贝
        a = std::move(b);
        b = std::move(c);
        if(b.getDigitCount() % 100 == 0) std::cout << b.getDigitCount() << '\n';
    }
    
    return 0;
}