Posted 2025-04-14Updated 2025-04-14XCPC26 minutes read (About 3881 words)

使用 proxy-tools 脚本简化 SSH 远程转发

SSH 远程端口转发 (ssh -R) 是一个非常有用的功能，它允许我们将本地机器上的端口暴露给远程服务器访问，从而让远程服务器通过本地代理访问网络。

例如，我们可以使用以下命令将本地的 3128 端口（假设运行着 Squid 代理）转发到远程服务器 user@server_ip 的 3129 端口：

1	ssh -R 3129:localhost:3128 user@server_ip

之后，在远程服务器上访问 127.0.0.1:3129 就相当于访问发起连接的本地机器的 localhost:3128。

然而，直接使用 ssh -R 命令存在一些不便之处：

连接脆弱：网络波动或长时间无活动可能导致 SSH 连接中断，转发随之失效。
手动维护：需要手动保持 SSH 进程在后台运行（例如使用 nohup, screen, tmux），并在中断后手动重连。
不易管理：启动、停止和检查状态不够直观。

为了解决连接稳定性问题，autossh 工具应运而生。它能够监控 SSH 连接，并在断开时自动尝试重新建立。

但这仍然需要用户自行管理 autossh 进程。

proxy-tools：一个管理脚本

为了进一步简化这个过程，proxy-tools 脚本被创建出来。它结合了 autossh 的连接保持能力和 systemd 的服务管理能力，提供了一套更便捷的管理方案。

主要目标：

通过 systemd 服务实现 autossh 隧道的后台稳定运行和自动重启。
提供简单的命令行接口 (proxyon, proxyoff, proxystatus) 来控制隧道的启动、停止和状态查询。
通过交互式脚本简化安装和卸载过程。

工作原理简介

proxy-tools 的核心是利用 systemd 服务来管理 autossh 进程。

安装：脚本会创建一个 systemd 服务模板文件 (autossh-proxy@.service)，该模板定义了如何启动一个 autossh 远程转发实例。同时，它会生成三个辅助脚本 (proxyon.sh, proxyoff.sh, proxystatus.sh) 到用户目录下的 ~/proxy-tools。
**启动 (proxyon)**：当用户执行 proxyon user@server_ip 时，脚本会调用 systemctl 来启动一个基于模板的服务实例（如 autossh-proxy@user@server_ip.service）。systemd 随后根据模板配置，以后台服务的形式运行 autossh，建立并维护到指定服务器的 -R 转发隧道。
**停止 (proxyoff)**：该命令会找到当前活动的服务实例，并使用 systemctl 将其停止并禁用。
**状态 (proxystatus)**：该命令会查询当前活动服务实例的状态信息。

使用准备

在安装和使用 proxy-tools 之前，请确保满足以下条件：

系统环境：运行脚本的本地机器需要是使用 systemd 的 Linux 系统。
软件依赖：已安装 autossh (例如 sudo apt install autossh)。
权限：拥有 sudo 权限，因为需要管理 systemd 服务。
SSH 认证：强烈建议配置好本地机器到目标服务器 (user@server_ip) 的 SSH 密钥免密登录。否则 autossh 可能无法在后台成功连接。
本地服务：确保你想要转发的本地端口（默认为 3128）有服务正在监听。

安装步骤

获取 manage-proxy-tools.sh 脚本（例如通过下载或 Git clone）。

#!/bin/bash

# Exit immediately if a command exits with a non-zero status.
set -e

# --- Configuration ---
INSTALL_DIR="$HOME/proxy-tools"
SERVICE_NAME_BASE="autossh-proxy" # Base name for systemd service template
SYSTEMD_SERVICE_FILE="/etc/systemd/system/${SERVICE_NAME_BASE}@.service"
HELPER_SCRIPTS=("proxyon.sh" "proxyoff.sh" "proxystatus.sh")
TARGET_INFO_FILE="${INSTALL_DIR}/target.info" # Stores the current user@host

# Ports (as per your request)
LOCAL_SQUID_PORT="3128"
REMOTE_FORWARD_PORT="3129"
AUTOSSH_MONITOR_PORT="20000" # Monitor port for autossh (-M)

# Alias configuration
ALIAS_ON="alias proxyon='${INSTALL_DIR}/proxyon.sh'"
ALIAS_OFF="alias proxyoff='${INSTALL_DIR}/proxyoff.sh'"
ALIAS_STATUS="alias proxystatus='${INSTALL_DIR}/proxystatus.sh'"
ALIAS_COMMENT="# Added by proxy-tools"

# --- Helper Functions ---
check_dependencies() {
    echo "检查依赖..."
    if ! command -v autossh &> /dev/null; then
        echo "错误: 'autossh' 未安装。请先安装它 (例如: sudo apt install autossh)"
        exit 1
    fi
    if ! command -v systemctl &> /dev/null; then
        echo "错误: 'systemd' (systemctl) 未找到。此脚本需要 systemd。"
        exit 1
    fi
     if [ "$(id -u)" -eq 0 ]; then
        echo "错误：请不要直接使用 root 用户运行此安装脚本。"
        echo "脚本会在需要时使用 'sudo' 请求权限。"
        exit 1
    fi
    echo "依赖检查通过。"
}

check_sudo() {
    if ! sudo -v; then
        echo "错误：无法获取 sudo 权限。请确保你有 sudo 权限并且可以免密或者输入密码。"
        exit 1
    fi
}

add_aliases() {
    local shell_rc
    echo "尝试添加别名到 .bashrc 和 .zshrc..."
    for shell_rc in "$HOME/.bashrc" "$HOME/.zshrc"; do
        if [ -f "$shell_rc" ]; then
            # Check if alias already exists
            if ! grep -qF "$ALIAS_COMMENT" "$shell_rc"; then
                echo "添加别名到 $shell_rc"
                echo "" >> "$shell_rc"
                echo "$ALIAS_COMMENT" >> "$shell_rc"
                echo "$ALIAS_ON" >> "$shell_rc"
                echo "$ALIAS_OFF" >> "$shell_rc"
                echo "$ALIAS_STATUS" >> "$shell_rc"
            else
                echo "别名似乎已存在于 $shell_rc"
            fi
        fi
    done
    echo "完成。请运行 'source ~/.bashrc' 或 'source ~/.zshrc' 或重新打开终端以使别名生效。"
}

remove_aliases() {
    local shell_rc
    echo "尝试从 .bashrc 和 .zshrc 移除别名..."
    for shell_rc in "$HOME/.bashrc" "$HOME/.zshrc"; do
        if [ -f "$shell_rc" ]; then
             # 检查注释标记是否存在
             if grep -qF "$ALIAS_COMMENT" "$shell_rc"; then
                echo "从 $shell_rc 移除别名..."
                # 使用 # 作为 sed 的分隔符，避免与路径中的 / 冲突
                # 同时移除注释标记和其后的别名行
                sed -i -e "#^${ALIAS_COMMENT}$#d" \
                       -e "#^${ALIAS_ON}$#d" \
                       -e "#^${ALIAS_OFF}$#d" \
                       -e "#^${ALIAS_STATUS}$#d" "$shell_rc"
             else
                # 如果找不到注释标记，也尝试直接删除别名（以防万一）
                echo "在 $shell_rc 中未找到注释标记，尝试直接移除别名..."
                sed -i -e "#^${ALIAS_ON}$#d" \
                       -e "#^${ALIAS_OFF}$#d" \
                       -e "#^${ALIAS_STATUS}$#d" "$shell_rc"
             fi
        fi
    done
    echo "完成。"
}

# --- Installation Function ---
install_proxy_tools() {
    echo "开始安装 proxy-tools..."
    check_dependencies
    check_sudo

    # Create installation directory
    mkdir -p "$INSTALL_DIR"
    echo "安装目录: $INSTALL_DIR"

    # --- Create proxyon.sh ---
    cat << EOF > "${INSTALL_DIR}/proxyon.sh"
#!/bin/bash
set -e

SERVICE_NAME_BASE="${SERVICE_NAME_BASE}"
TARGET_INFO_FILE="${TARGET_INFO_FILE}"

if [ -z "\$1" ]; then
    echo "用法: \$0 <user@server_ip>"
    exit 1
fi

TARGET="\$1"
SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service"

echo "检查当前是否有活动的代理服务..."
if [ -f "\$TARGET_INFO_FILE" ]; then
    CURRENT_TARGET=\$(cat "\$TARGET_INFO_FILE")
    CURRENT_SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${CURRENT_TARGET}.service"
    # Check if the service file exists and is active/enabled
    if systemctl --quiet is-active "\$CURRENT_SERVICE_INSTANCE" || systemctl --quiet is-enabled "\$CURRENT_SERVICE_INSTANCE"; then
       if [ "\$CURRENT_TARGET" != "\$TARGET" ]; then
            echo "错误：似乎已有另一个代理实例 (\$CURRENT_TARGET) 正在运行或已启用。"
            echo "请先使用 'proxyoff' 停止当前服务，然后再启动新的服务。"
            exit 1
       else
            echo "代理服务 (\$TARGET) 似乎已在运行或已启用。"
            echo "尝试重启服务..."
       fi
    fi
fi


echo "正在启动/重启代理服务: \$SERVICE_INSTANCE ..."
# Use --now to enable and start immediately
sudo systemctl enable --now "\$SERVICE_INSTANCE"

if sudo systemctl is-active --quiet "\$SERVICE_INSTANCE"; then
    echo "\$TARGET" > "\$TARGET_INFO_FILE" # Store the target on success
    echo "代理服务已成功启动并启用。"
    echo "远程服务器端口 ${REMOTE_FORWARD_PORT} 已转发到本地 localhost:${LOCAL_SQUID_PORT}"
    echo "请在服务器上配置代理: export http_proxy=\"http://127.0.0.1:${REMOTE_FORWARD_PORT}\" https_proxy=\"http://127.0.0.1:${REMOTE_FORWARD_PORT}\""
else
    echo "错误：启动服务失败。请检查日志：sudo journalctl -u \$SERVICE_INSTANCE -n 50"
    # Clean up target file if start failed
    if [ -f "\$TARGET_INFO_FILE" ] && [ "\$(cat "\$TARGET_INFO_FILE")" == "\$TARGET" ]; then
        rm -f "\$TARGET_INFO_FILE"
    fi
    exit 1
fi
EOF

    # --- Create proxyoff.sh ---
    cat << EOF > "${INSTALL_DIR}/proxyoff.sh"
#!/bin/bash
set -e

SERVICE_NAME_BASE="${SERVICE_NAME_BASE}"
TARGET_INFO_FILE="${TARGET_INFO_FILE}"

if [ ! -f "\$TARGET_INFO_FILE" ]; then
    echo "没有找到活动的代理目标信息 (\$TARGET_INFO_FILE)。"
    echo "尝试查找并停止任何 autossh-proxy@* 服务..."
    ACTIVE_SERVICES=\$(systemctl list-units --type=service --state=active "${SERVICE_NAME_BASE}@*.service" --no-legend | awk '{print \$1}')
    if [ -z "\$ACTIVE_SERVICES" ]; then
        echo "未找到活动的 ${SERVICE_NAME_BASE}@* 服务。"
        exit 0
    else
         echo "警告：找到以下活动服务，将尝试全部停止："
         echo "\$ACTIVE_SERVICES"
         for service in \$ACTIVE_SERVICES; do
             echo "正在停止 \$service..."
             sudo systemctl stop "\$service"
             echo "正在禁用 \$service (防止重启后自启)..."
             sudo systemctl disable "\$service"
         done
         echo "所有找到的 ${SERVICE_NAME_BASE}@* 服务已停止并禁用。"
         exit 0
    fi
fi

TARGET=\$(cat "\$TARGET_INFO_FILE")
SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service"

echo "正在停止代理服务: \$SERVICE_INSTANCE ..."
sudo systemctl stop "\$SERVICE_INSTANCE"

echo "正在禁用代理服务 (防止重启后自启)..."
sudo systemctl disable "\$SERVICE_INSTANCE"

# Clean up target info file after stopping
rm -f "\$TARGET_INFO_FILE"

echo "代理服务已停止并禁用。"
EOF

    # --- Create proxystatus.sh ---
    cat << EOF > "${INSTALL_DIR}/proxystatus.sh"
#!/bin/bash

SERVICE_NAME_BASE="${SERVICE_NAME_BASE}"
TARGET_INFO_FILE="${TARGET_INFO_FILE}"

echo "检查代理服务状态..."

if [ -f "\$TARGET_INFO_FILE" ]; then
    TARGET=\$(cat "\$TARGET_INFO_FILE")
    SERVICE_INSTANCE="\${SERVICE_NAME_BASE}@\${TARGET}.service"
    echo "当前配置的目标: \$TARGET"
    echo "对应的服务单元: \$SERVICE_INSTANCE"
    sudo systemctl status "\$SERVICE_INSTANCE" --no-pager
else
    echo "未找到当前活动的代理目标信息 (\$TARGET_INFO_FILE)。"
    echo "你可以尝试手动检查特定服务: sudo systemctl status ${SERVICE_NAME_BASE}@<user@server_ip>.service"
    echo "或者检查所有可能的实例: systemctl list-units --type=service '${SERVICE_NAME_BASE}@*.service'"
fi
EOF

    # Make helper scripts executable
    chmod +x "${INSTALL_DIR}/proxyon.sh" "${INSTALL_DIR}/proxyoff.sh" "${INSTALL_DIR}/proxystatus.sh"
    echo "辅助脚本已创建并设为可执行。"

    # --- Create systemd service file ---
    # Get the username who invoked sudo, or the current user if not using sudo (fallback)
    INSTALL_USER=${SUDO_USER:-$(whoami)}
    echo "为用户 '$INSTALL_USER' 创建 systemd 服务文件..."

    # Use a heredoc with sudo tee to write the systemd file
    sudo tee "$SYSTEMD_SERVICE_FILE" > /dev/null << EOF
[Unit]
Description=Autossh tunnel for proxy (%I)
After=network.target
# StartLimitIntervalSec=0 # Removed for potentially better restart behavior

[Service]
User=${INSTALL_USER}
Environment="AUTOSSH_GATETIME=0"
Environment="AUTOSSH_POLL=60" # Check connection every 60 seconds
# -M: Monitor port, -N: No remote command, -T: No TTY
# -o options for robustness: keepalive, exit on failure
ExecStart=/usr/bin/autossh -M ${AUTOSSH_MONITOR_PORT} -NT \
    -o "ServerAliveInterval=60" \
    -o "ServerAliveCountMax=3" \
    -o "ExitOnForwardFailure=yes" \
    -o "ConnectTimeout=10" \
    -o "StrictHostKeyChecking=no" \
    -R ${REMOTE_FORWARD_PORT}:localhost:${LOCAL_SQUID_PORT} %i
RestartSec=5
Restart=always # Restart the service if it fails

[Install]
WantedBy=multi-user.target
EOF

    echo "Systemd 服务文件已创建: $SYSTEMD_SERVICE_FILE"

    # Reload systemd daemon
    echo "重新加载 systemd 配置..."
    sudo systemctl daemon-reload

    # Ask about aliases
    read -p "是否要将 proxyon, proxyoff, proxystatus 添加到 shell 别名? (y/N): " add_alias_confirm
    if [[ "$add_alias_confirm" =~ ^[Yy]$ ]]; then
        add_aliases
    else
        echo "跳过添加别名。你可以手动运行脚本:"
        echo "  ${INSTALL_DIR}/proxyon.sh <user@server_ip>"
        echo "  ${INSTALL_DIR}/proxyoff.sh"
        echo "  ${INSTALL_DIR}/proxystatus.sh"
    fi

    echo ""
    echo "--------------------------------------"
    echo "✅ proxy-tools 安装完成!"
    echo "--------------------------------------"
    echo "使用方法:"
    echo "  proxyon user@server_ip   # 启动代理 (如果添加了别名)"
    echo "  proxyoff                # 停止代理 (如果添加了别名)"
    echo "  proxystatus             # 查看状态 (如果添加了别名)"
    echo ""
    echo "或者直接运行脚本:"
    echo "  ${INSTALL_DIR}/proxyon.sh user@server_ip"
    echo "  ${INSTALL_DIR}/proxyoff.sh"
    echo "  ${INSTALL_DIR}/proxystatus.sh"
    echo ""
    echo "重要提示: 确保你的 SSH 密钥已配置好，可以免密登录到 user@server_ip。"
    echo "         否则 autossh 可能无法在后台成功连接。"
    echo "首次连接时，autossh 可能需要手动确认主机密钥。"
    echo "你可能需要手动运行一次 ssh user@server_ip 来添加主机密钥。"
}

# --- Uninstallation Function ---
uninstall_proxy_tools() {
    echo "开始卸载 proxy-tools..."
    check_sudo

    # Stop and disable any running service instance
    echo "尝试停止并禁用所有相关的 systemd 服务..."
    # Find active/enabled instances first
    INSTANCES=$(systemctl list-units --type=service --state=active,enabled --no-legend "${SERVICE_NAME_BASE}@*.service" | awk '{print $1}')
    if [ -n "$INSTANCES" ]; then
        for instance in $INSTANCES; do
            echo "停止服务 $instance ..."
            sudo systemctl stop "$instance" || echo "停止 $instance 失败 (可能已停止)"
            echo "禁用服务 $instance ..."
            sudo systemctl disable "$instance" || echo "禁用 $instance 失败 (可能已禁用)"
        done
    else
        echo "未找到活动的或已启用的 ${SERVICE_NAME_BASE}@* 服务实例。"
    fi

    # Remove the systemd service file
    if [ -f "$SYSTEMD_SERVICE_FILE" ]; then
        echo "移除 systemd 服务文件: $SYSTEMD_SERVICE_FILE"
        sudo rm -f "$SYSTEMD_SERVICE_FILE"
        echo "重新加载 systemd 配置..."
        sudo systemctl daemon-reload
    else
        echo "Systemd 服务文件未找到，跳过移除。"
    fi

    # Remove aliases
    remove_aliases

    # Remove the installation directory
    if [ -d "$INSTALL_DIR" ]; then
        echo "移除安装目录: $INSTALL_DIR"
        rm -rf "$INSTALL_DIR"
    else
        echo "安装目录未找到，跳过移除。"
    fi

    echo ""
    echo "--------------------------------------"
    echo "🗑️ proxy-tools 卸载完成。"
    echo "--------------------------------------"
    echo "你可能需要重新启动你的 shell 或运行 'source ~/.bashrc' / 'source ~/.zshrc' 来完全移除别名。"
}

# --- Main Menu ---
echo "=============================="
echo "  Proxy Tools 管理脚本"
echo "=============================="
echo "请选择操作:"
echo "  1) 安装 proxy-tools"
echo "  2) 卸载 proxy-tools"
echo "  3) 退出"
echo "------------------------------"

read -p "输入选项 [1-3]: " choice

case "$choice" in
    1)
        install_proxy_tools
        ;;
    2)
        uninstall_proxy_tools
        ;;
    3)
        echo "退出。"
        exit 0
        ;;
    *)
        echo "无效选项。"
        exit 1
        ;;
esac

exit 0

赋予执行权限：
1
chmod +x manage-proxy-tools.sh
运行安装脚本（请勿直接使用 sudo 运行）：
1
./manage-proxy-tools.sh
在菜单中选择 1) 安装 proxy-tools。脚本将检查依赖、创建目录和文件、设置 systemd 服务。
脚本会询问是否添加别名到 ~/.bashrc 或 ~/.zshrc。选择 y 可以方便后续使用。
如果添加了别名，需要重新加载 shell 配置或新开一个终端窗口：
1
source ~/.bashrc # 或 source ~/.zshrc

使用方法

启动转发隧道：
1
2
3
4
5
# 如果设置了别名
proxyon <user@server_ip>

# 或者直接运行脚本
~/proxy-tools/proxyon.sh <user@server_ip>
成功后，远程服务器 <server_ip> 上的 127.0.0.1:3129 (默认) 端口将连接到你本地机器的 localhost:3128 (默认) 端口。
在远程服务器上使用转发的端口：
登录到远程服务器 (<server_ip>)，然后配置需要使用此隧道的应用程序。例如，若要将该隧道用作 HTTP/HTTPS 代理：
1
2
3
4
5
export http_proxy="http://127.0.0.1:3129"
export https_proxy="http://127.0.0.1:3129"

# 测试代理是否工作
wget www.google.com

停止转发隧道：

# 如果设置了别名
proxyoff

# 或者直接运行脚本
~/proxy-tools/proxyoff.sh

该命令会停止当前活动的 autossh 服务实例。

检查隧道状态：

# 如果设置了别名
proxystatus

# 或者直接运行脚本
~/proxy-tools/proxystatus.sh

该命令会显示当前活动服务实例的 systemd 状态信息。

配置选项

脚本默认使用以下配置：

本地监听端口 (LOCAL_SQUID_PORT): 3128
远程转发端口 (REMOTE_FORWARD_PORT): 3129 (在远程服务器上监听 127.0.0.1)
autossh 监控端口 (AUTOSSH_MONITOR_PORT): 20000
安装目录: ~/proxy-tools

如需修改这些默认值，可以直接编辑 manage-proxy-tools.sh 脚本顶部的配置变量，然后重新运行安装程序 (选择 1) 以应用更改。

卸载方法

如果不再需要 proxy-tools，可以运行管理脚本进行清理：

1	./manage-proxy-tools.sh

选择 2) 卸载 proxy-tools。脚本会自动停止相关服务、删除 systemd 配置文件、移除 ~/proxy-tools 目录，并尝试清理添加的 shell 别名。

总结

proxy-tools 通过结合 autossh 和 systemd，为管理 SSH 远程转发隧道提供了一套相对简单和可靠的方案。它通过封装底层命令和利用系统服务管理，降低了使用门槛，提高了隧道的稳定性。对于需要频繁或长期使用 SSH 远程转发的用户来说，这可以是一个方便的管理工具。

注意事项

本地服务安全：转发本地端口意味着远程服务器可以访问该端口。确保本地服务（如 Squid）配置了适当的访问控制，防止未授权访问。脚本示例中提到的 Squid 配置 http_access allow all 通常是不安全的，应根据实际需要限制来源 IP。
SSH 主机密钥：systemd 服务配置中可能包含 StrictHostKeyChecking=no 选项，以避免因目标主机密钥未知导致 autossh 启动失败。了解此选项的安全含义（连接时不会验证远程主机的身份）。在安全要求高的场景下，建议首次手动连接目标服务器以接受其主机密钥，然后考虑从服务配置中移除此选项。

Posted 2024-05-06Updated 2024-05-10XCPC8 minutes read (About 1259 words)

GDCPC集训D1补题

这套题是2024湖北icpc省赛题，五月一号集训没时间写，现在慢慢补。

Posted 2024-03-31Updated 2024-03-31XCPCa minute read (About 157 words)

vector如何释放内存

关于vector释放内存

考个csp认证被这个鬼问题卡了，真是服了。

1 2	vector<int> vec; vec.clear(); // 不会释放内存，仅仅长度为0。

释放内存：

将要释放内存的vector与一个空vector进行交换，然后将空vector释放掉。

1	vector<int>().swap(vec);

在调用clear()之后再调用shrink_to_fit()，将vector的容量减小到与其大小相等，从而释放多余的内存空间。

1 2	vec.clear(); vec.shrink_to_fit();

使用resize()方法重新分配vector的大小，从而释放多余的内存空间。

1	vec.resize(n);

Posted 2024-03-28Updated 2024-03-28XCPC2 minutes read (About 334 words)

CF1943D1

CF1943D1 - Counting Is Fun (Easy Version)

题意：定义好数组为：一个由$m$个非负整数组成的数组$b$中，若$b$中所有元素可以通过以下操作使其为$0$。选择一个区间$(l, r)(1\le l< r\le m), \forall{i}, \ i\in(l, r),b_i$减去$1$。询问长度为$n$的数组，每个元素最大为$k$时，好数组个数。

可以证明，一个三元组$(a, b, c)$，当$a+c\ge b$时可以将其减为$0$。

于是设$dp[i][a][b]$为前i个数，第i-1个是a，第i个是b时的方案数。那么转移方程则为$dp[i][b][c] = \sum\limits_{a=b-c}^{k}{dp[i-1][a][b]}$。

对于求和用前缀和维护则可做到$O(n^3)$。

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

const int N = 410;

void work() {
    int n, k, p;
    cin >> n >> k >> p;
    vector<vector<int>> dp(k + 1, vector<int>(k + 1, 0));
    dp[0][0] = 1;
    for (int i = 1; i <= n + 2; i++) { // n + 2, 0, 0 will be the ans.
        vector<vector<int>> sum(k + 1, vector<int>(k + 1, 0));
        for (int b = 0; b <= k; b++) {
            sum[b][0] = dp[0][b];
            for (int a = 1; a <= k; a++)
                sum[b][a] = (dp[a][b] + sum[b][a - 1]) % p;
        }
        for (int b = 0; b <= k; b++) {
            for (int c = 0; c <= k; c++) {
                if (b - c > 0) dp[b][c] = (sum[b][k] - sum[b][b - c - 1] + p) % p; // a > b - c is ok
                else dp[b][c] = sum[b][k]; // any a is ok
            }
        }
    }
    cout << dp[0][0] << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

Posted 2024-03-27Updated 2024-03-28XCPC3 minutes read (About 400 words)

树的直径

CF1944E - Tree Compass

题意：给定一棵树，最初所有结点为白色。你可以进行操作：选定一个节点v和距离k，使树上与v的简单路径距离为k的所有点染色为黑色。构造操作序列，使操作次数最小化。

不难发现，影响操作次数的是树中最长的一条路径，即树的直径。所以我们只要找出树的直径并选定最中间的点（奇数长度则一个，偶数则两个），然后再使距离包含整条直径即可。

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

const int N = 2010;

int n, fa[N];
vector<int> e[N];

void add(int x, int y) {
    e[x].emplace_back(y);
    e[y].emplace_back(x);
}
// 两次bfs找树的直径
int find(int x) {
    queue<int> q;
    vector<int> dep(n + 10, -1);
    dep[x] = 0;
    fa[x] = -1;
    q.push(x);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (auto nxt: e[now]) {
            if (dep[nxt] != -1) continue;
            fa[nxt] = now;
            dep[nxt] = dep[now] + 1;
            q.push(nxt);
        }
    }
    int ans = -1, ansid = 0;
    for (int i = 1; i <= n; i++) {
        if (dep[i] > ans) {
            ansid = i;
            ans = dep[i];
        }
    }
    return ansid;
}

void work() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        e[i].clear();
    for (int i = 1, x, y; i < n; ++i) {
        cin >> x >> y;
        add(x, y);
    }
    int x = find(1); // begin
    int y = find(x); // end
    vector<int> a;
    for (int i = y; i != -1; i = fa[i]) {
        a.emplace_back(i);
    } // fa[x] = -1
    int len = a.size();
    vector<pair<int, int>> ans;
    if (len & 1) {
        int p = a[len >> 1];
        for (int i = 0; i <= (len >> 1); ++i) {
            ans.emplace_back(p, i);
        }
    } else {
        int p1 = a[(len >> 1) - 1], p2 = a[len >> 1];
        for (int i = 1; i <= (len >> 1); i += 2){
            ans.emplace_back(p1, i);
            ans.emplace_back(p2, i);
        }
    }
    cout << ans.size() << '\n';
    for (auto [x, y]: ans) {
        cout << x << ' ' << y << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

Posted 2024-03-25Updated 2024-03-28XCPC4 minutes read (About 585 words)

双Hash

CF1944D - Non-Palindromic Substring

题意：称一个字符串为$k$-good字符串，当该字符串至少有一个长度为$k$的子串不是回文串。给定一个字符串，询问$[l, r]$子串的$\sum{k}$

通过模拟可以发现对于一个字符串：

不是回文串，则$k$可以取$2 \sim len$中的每一个值。
每个字符都相同，则答案为$0$。
是交错型的字符串，则$k$可以取$2 \sim len$中的每一个偶数。
只是回文串，则$k$可以取$2 \sim {len - 1}$中的每一个值。

判断回文串使用了双Hash（好久没用过了，写一个规范点的出来用）

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

const int N = 200010;
namespace RAND {
    unsigned int SEED() {
        auto now = chrono::system_clock::now();
        auto timestamp = chrono::duration_cast<chrono::milliseconds>(now.time_since_epoch());
        return static_cast<unsigned int>(timestamp.count());
    }
    mt19937 R(SEED());
} // namespace RAND

unsigned long long mod1 = RAND::R(), mod2 = RAND::R();
class HASH {
    typedef unsigned long long ull;
    typedef pair<ull, ull> pULL;
public:
    ull base, pow1[N], pow2[N];
    vector<ull> hash1, hash2;
    HASH() {
        base = 27;
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i < N; ++i) {
            pow1[i] = (pow1[i - 1] * base) % mod1;
            pow2[i] = (pow2[i - 1] * base) % mod2;
        }
    }
    // 默认字符串从1开始
    void init(string s) {
        int len = s.size() - 1;
        hash1.reserve(s.size()), hash2.reserve(s.size());
        hash1[0] = hash2[0] = 0;
        for (int i = 1; i <= len; ++i) {
            hash1[i] = (hash1[i - 1] * base + s[i] - 'a') % mod1;
            hash2[i] = (hash2[i - 1] * base + s[i] - 'a') % mod2;
        }
    }
    pULL subHash(int l, int r) {
        if (l == 1) return make_pair(hash1[r], hash2[r]);
        pULL tmp;
        tmp.first = (hash1[r] - hash1[l - 1] * pow1[r - l + 1] % mod1 + mod1) % mod1;
        tmp.second = (hash2[r] - hash2[l - 1] * pow2[r - l + 1] % mod2 + mod2) % mod2;
        return tmp;
    }
} hashFront, hashBack;

int n, q;
string s;
void work() {
    cin >> n >> q;
    cin >> s;
    hashFront.init(" " + s);
    reverse(s.begin(), s.end());
    hashBack.init(" " + s);
    reverse(s.begin(), s.end());
    int len = s.size();
    s = " " + s;
    unsigned long long ans, L;
    vector<int> id(n + 1); // 判断交错
    id[1] = 1, id[2] = 2;
    for (int i = 3; i <= len; i++) {
        if (s[i] == s[i - 2]) id[i] = id[i - 2];
        else id[i] = i;
    }
    vector<int> con(n + 1); // 判断连续
    con[1] = 1;
    for (int i = 2; i <= len; i++) {
        if (s[i] == s[i - 1]) con[i] = con[i - 1];
        else con[i] = i;
    }
    for (int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r;
        L = (r - l + 1);
        if (L == 1) {
            cout << "0\n";
            continue;
        }
        if (L == 2) {
            if (s[l] == s[r]) cout << "0\n";
            else cout << "2\n";
            continue;
        }
        auto x1 = hashFront.subHash(l, r);
        auto x2 = hashBack.subHash(len - r + 1, len - l + 1);
        if (x1 == x2) {
            bool flag = 1;
            if (con[r] == con[l]) {
                cout << 0 << '\n';
                continue;
            }
            if (id[l] == id[r] && id[l + 1] == id[r - 1]) {
                unsigned long long tmp = (L / 2) * 2;
                ans = (2 + tmp) * (L / 2) / 2;
            } else {
                ans = (1 + L - 1) * (L - 1) / 2 - 1;
            }
        } else {
            if (id[l] == id[r - 1] && id[l + 1] == id[r]) {
                ans = (2 + L) * L / 4;
            } else ans = (2 + L) * (L - 1) / 2;
        }
        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

Posted 2024-03-23Updated 2024-03-25XCPC11 minutes read (About 1623 words)

CF1946

A - Median of an Array

题意：加多少次1可以改变中位数大小。

显然比中位数位置大的与中位数相同的数有多少个就加多少次

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

int a[100000];
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int k = (n + 1) / 2, ans = 0;
        for (int i = k; i <= n; i++) {
            if (a[i] == a[k])
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

B - Maximum Sum

题意：一个长度为$n$的数组$a$，你可以进行k次操作，每一次操作选一个子段和添加到数组的任意位置，最大化数组总和。

当最大子段和小于$0$时显然不进行操作，当最大子段和大于$0$时不断加入$k$次目前最大子段和。

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007ll;

long long T, a[200010], SUM;
void work() {
    int n, k;
    SUM = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i], SUM += a[i], SUM %= mod;
    long long ans = 0, sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        if (sum > ans) {
            ans = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }
    sum = 0;
    for (int i = 1; i <= k; ++i) {
        sum = (sum + ans) % mod;
        ans = (ans + ans) % mod;
    }
    cout << (SUM + sum + 2ll * mod) % mod << endl;
}

int main() {
    cin >> T;
    while (T--)
        work();
    return 0;
}

Posted 2023-12-28Updated 2023-12-30数学3 minutes read (About 422 words)

各种积分

$Guass$积分

$$\int_{0}^{+\infty}e^{-x^{2}}dx$$

设$I(t)={(\int_{0}^{t} e^{-x^{2}}dx)}^2$, 则求

$$\sqrt{\lim\limits_{t \to +\infty}I(t)}$$

$$I^{‘}(t) = 2(\int_{0}^{t}e^{-x^{2}}dx)e^{-t^2} = 2\int_{0}^{t}e^{-x^2-t^2}dx = 2\int_{0}^{1}2te^{(y^2+1)t^2}dy$$

$$\frac{dI(t)}{dt} = \frac{\int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}dy}{dt}$$

$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+C$$

$$I(0)=\int_0^1\frac{-1}{y^2+1}dy+C = -\frac{\pi}{4} + C=0,C=\frac{\pi}{4}$$

$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+\frac{\pi}{4}$$

$$\lim\limits_{t \to +\infty}I(t)=0+\frac{\pi}{4} = \frac{\pi}{4}$$

$$\therefore\int_{0}^{+\infty}e^{-x^{2}}dx=\frac{\sqrt{\pi}}{2}$$