其实就是求矩阵的秩，但是会被卡精度（被卡了好几发），直接抄个矩阵求秩的板子就AC了

#define CLR(x) memset(x,0,sizeof(x))//定义宏

using namespace std;

double mat[300][300];//定义矩阵

int r,c;

int cmp(double x,double y){

    double v = x - y;

    if(v > 1e-1) return 1;//1e-1表示10^-1

    if(v < -1e-1) return -1;

    return 0;

}

//乘相应值

void subrow(int r1 , int r2,double temp){

    for(int i = 1 ; i <= c ; i++){

        mat[r1][i] -= mat[r2][i]*temp;

    }

}

//交换数值

void swaprow(int r1 , int r2){

    for(int i = 1 ; i <= c ; i++){

        swap(mat[r1][i],mat[r2][i]);

    }

}

//判断秩（主要判定函数）

void solve() {

    for (int i = 1; i <= r; i++) {

        for (int cal = i; cal <= c; cal++) { //对这 i 行的每一列来找，要是这列本身和之下的列全是0，则找 i 行下一列。

            bool flag = true;

            if (cmp(mat[i][cal], 0) == 0) {

                flag = false;  //如果第 i 行 cal 列这个位置是 0 ，那找找这列下面的行有没有

                for (int j = i + 1; j <= r; j++) {   //一个不为 0 的数 , 要是有 ， 就将它与 i 行交换。

                    int tmp = cmp(mat[j][cal], 0);

                    if (tmp == 1 || tmp == -1) {

                        flag = true;

                        swaprow(j, i);

                        break;

                    }

                }

            }

            if (!flag) continue;//如果这列全是 0 ， 到下一列。

            int v = i;                                 //如果发现这列有值不为 0 并把它跟 i 行交换后，

            int maxn = mat[i][cal];                     //就再找这列有没有比 i 行 这个位置的值更大的值，如果有，将那一行

            for (int j = i + 1; j <= r; j++) {            //跟i行交换。（听说是为了减小误差）

                if (cmp(mat[j][cal], mat[i][cal]) == 1) {

                    v = j;

                    maxn = mat[j][cal];

                }

            }

            if (v != i) {

                swaprow(i, v);

            }

            for (int j = 1; j <= r; j++) {

                if (j == i) continue;

                if (cmp(mat[i][cal], 0) == 0) continue;

                double tmp = mat[j][cal] / mat[i][cal];

                subrow(j, i, tmp);

            }

            break;

        }

    }

}

int main() {

    CLR(mat);

    scanf("%d %d", &r, &c);

    for (int i = 1; i <= r; i++) {

        for (int j = 1; j <= c; j++) {

            scanf("%lf", &mat[i][j]);

        }

    }

    solve();

    bool f = false;

    int ans = 0;

    for (int i = r; i >= 1; i--) {

        for (int j = 1; j <= c; j++) {

            int tmp = cmp(mat[i][j], 0);

            if (tmp == 1 || tmp == -1) {

                f = true;

                break;

            }

        }

        if (f) {

            ans = i;

            break;

        }

    }

    printf("%d\n", ans);//输出秩

    return 0;

}

阅读理解题

int main() {

    int a, b;

    cin >> a >> b;

    if (a > b) swap(a, b);

    if (a == 1) {

        cout << -1;

        return 0;

    }

    set stt;

    int now = a;

    while (now) {

        stt.insert(now);

        now /= 2;

    }

    now = b;

    int lca;

    while (now) {

        if (stt.find(now) != stt.end()) {

            if (now == a) {

                cout << -1;

                return 0;

            }

            lca = now;

            break;

        }

        now /= 2;

    }

    now = b;

    vector ans;

    while (now / 2 != lca) {

        if (now % 2) ans.push_back(now / 2 * 2);

        else ans.push_back(now / 2 * 2 + 1);

        now /= 2;

    }

    now = a;

    while (now / 2 != lca) {

        if (now % 2) ans.push_back(now / 2 * 2);

        else ans.push_back(now / 2 * 2 + 1);

        now /= 2;

    }

    now = lca;

    while (now != 1) {

        if (now % 2) ans.push_back(now / 2 * 2);

        else ans.push_back(now / 2 * 2 + 1);

        now /= 2;

    }

    ans.push_back(a), ans.push_back(b);

    sort(ans.begin(), ans.end());

    for (int i: ans) 	cout << i << " ";

}

题解：仿样例，凑出来的，神奇的AC姿势

void solve() {

    int k;

    cin >> k;

    cout<< 2*k << endl;

    for (int i = 1; i <= k; ++i) {

        for (int j = 1; j <= k; ++j) {

            cout << i << " " << i + j<< endl;

        }

        for (int j = k+1 ; j <= 2 * k-1 ; ++j) {

            cout << i + k << " " << (i + j-1)%(2*k)+1 << endl;

        }

    }

}

思路:
​ 树形dp维护以某个节点为根的子树中，以根为路径的一个端点，可以在$S$ 中匹配的最长前缀和后缀。当某棵子树的前后缀已经覆盖了$S$，并且前后缀的路径不重复，就是合法路径。保证不重复的方法详见代码。

int n, m, idx;

string s;

int head[maxn];

pii st[maxn], ed[maxn], ans;

struct Edge {

    int to, nxt; char c;

} edge[maxn * 2];

void addedge(int u, int v, char c) {

    edge[idx] = {v, head[u], c};

    head[u] = idx ++;

    edge[idx] = {u, head[v], c};

    head[v] = idx ++;

}

void dfs(int u, int fa) {

    st[u] = ed[u] = {0, u};

    for(int i = head[u]; ~i; i = edge[i].nxt) {

        int v = edge[i].to; char c = edge[i].c;

        if(v == fa) continue;

        dfs(v, u);

        if(c == s[st[v].x + 1] && st[v].x < m) st[v].x ++;

        if(c == s[m - ed[v].x] && ed[v].x < m) ed[v].x ++;

        // 路径不重复

        if(st[u].x + ed[v].x >= m) ans = {st[u].y, ed[v].y};

        if(ed[u].x + st[v].x >= m) ans = {st[v].y, ed[u].y};

        st[u] = max(st[u], st[v]);

        ed[u] = max(ed[u], ed[v]);

    }

}

int main() {

    ios;

    cin >> n >> m;

    for(int i = 1; i <= n; i ++) head[i] = -1;

    for(int i = 1; i < n; i ++) {

        int u, v; char c;

        cin >> u >> v >> c;

        addedge(u, v, c);

    }

    cin >> s;

    s = "?" + s;

    ans = {-1, -1};

    dfs(1, 0);

    cout << ans.x << " " << ans.y;

}