Petrozavodsk Winter Training Camp 2016: Moscow SU Trinity Contest

#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 << " ";
}

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;
        }
    }
}

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;
}