美团CodeM复赛 02,03-程序员宅基地

02 城市网络
比赛时候写的是单调栈，真的是让人见笑了，基本思路就是dfs时候动态处理单调栈(带回溯)，然后离线处理答案。题解是用了倍增的，效率高很多

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define lson l,m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;

int A[N];
struct Node{
    int to, nx;
}E[N * 2];
int Deep[N];
int head[N], tot;
void add(int fr, int to) {
    E[tot].to = to; E[tot].nx = head[fr]; head[fr] = tot ++;
}
struct Pode{
    int po, val, an;
    Pode(int a=0, int b=0, int c=0):po(a), val(b), an(c){}
};
vector<Pode> ask[N];
int ans[N];

int SA[N]; int SB[N]; int cnt;
int search(int x, int ty) {
    int l = 1; int r = cnt;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(ty) {
          if(SA[mid] >= x) r = mid - 1;
            else l = mid + 1;
        }else {
            if(-SB[mid] >= -x) r = mid-1;
            else l = mid + 1;
        }
    }
    return l;
}
void dfs(int x, int pre, int dep) {
    Deep[x] = dep;
    vector<pair<int, int> > tmp;
    if(cnt == 0) SA[++cnt] = dep, SB[cnt] = A[x];
    else {
        int pos = 0;
        for(int i = cnt; i >= 1; --i) {
            if(SB[i] > A[x]) {
                pos = i;
                SA[i + 1] = dep; SB[i + 1] = A[x]; cnt = i+1;
                break;
            }else {
                tmp.push_back(MP(SA[i], SB[i]));
            }
        }
        if(pos == 0) SA[1] = dep, SB[1] = A[x], cnt = 1;
    }
//  printf("%d: ", x); for(int i = 1; i <= cnt; ++i) printf("%d:%d ", SA[i], SB[i]); printf("\n");

    for(int i = 0; i < ask[x].size(); ++i) {
        int po = ask[x][i].po; int val = ask[x][i].val; int an = ask[x][i].an;
        int pos1 = search(Deep[po], 1); int pos2 = search(val, 0);
        ans[an] = max(pos2 - pos1, 0);
    }


    for(int i = head[x]; ~i; i = E[i].nx) {
        int to = E[i].to; if(to == pre) continue;
        dfs(to, x, dep + 1);
    }
    cnt --;
    for(int i = tmp.size() - 1; i >= 0; --i) {
        int t1 = tmp[i].first; int t2 = tmp[i].second;
        SA[++cnt] = t1; SB[cnt] = t2; 
    }
    tmp.clear();
}
int main() {
    int n, q;
    while(~scanf("%d %d", &n, &q)) {
        cnt = 0;
        memset(head, -1, sizeof(head)); tot = 0;

        for(int i = 1; i <= n; ++i) ask[i].clear();
        for(int i = 1; i <= n; ++i) scanf("%d", &A[i]);
        for(int i = 1; i < n; ++i) {
            int a, b; scanf("%d %d", &a, &b);
            add(a, b); add(b, a);
        }

        for(int i = 0; i < q; ++i) {
            int a, b, c; scanf("%d %d %d", &a, &b, &c);
            ask[a].push_back(Pode(b, c, i));
        }
        dfs(1, 1, 1);
    //  for(int i = 1; i <= n; ++i) printf("%d ", Deep[i]); printf("\n");
        for(int i = 0; i < q; ++i) printf("%d\n", ans[i]);
    }
    return 0;
}

03 神秘代码
比赛最后10分钟我才想到这就是一个环套树，然后就没有然后了= =，如果能A的话还是很有希望进前50的，我之前认为这题看起来像数论，又那么像拓展欧几里得，不会不会，还不如多试试05。确实弱233

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
#define MP(x, y) make_pair(x, y)
#define lson l,m, rt<<1
#define rson m+1, r, rt<<1|1
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
int MOD;

struct Node{
    int fr, to, nx, a, b, c;
}E[N << 1];
int head[N]; int tot;
int vis[N]; int Pre[N];
int suc;
int ans[N];
void add(int fr, int to, int a, int b, int c) {
    E[tot].to = to; E[tot].a = a; E[tot].b = b; E[tot].c = c; E[tot].fr = fr;
    E[tot].nx = head[fr]; head[fr] = tot ++;
}
long long inv(long long a) {
    if(a == 1) return 1;
    return inv(MOD%a)*(MOD-MOD/a)% MOD; 
}
void bfs(int x) {
    queue<int> Q;
    Q.push(x);
    vis[x] = 2;
    while(!Q.empty()) {
        int po = Q.front(); Q.pop();
    //  printf("%d: %d\n", po, ans[po]);
        for(int i = head[po]; ~i; i = E[i].nx) {
            int y = E[i].to; int a = E[i].a; int b = E[i].b; int c = E[i].c;
            if(vis[y] != 2) {
                vis[y] = 2;
                ll tt = inv(b);
                ans[y] = (1ll*c*tt %MOD - 1ll*a*ans[po]%MOD * tt %MOD + MOD) %MOD;
                Q.push(y);
            }
        }
    }
}


void Find(int x, int tar, int B, int C) {
    int Next = E[Pre[x]].fr; int a = E[Pre[x]].b; int b = E[Pre[x]].a; int c = E[Pre[x]].c;
    ll tmp = inv(a);

    //  printf("a:%d b:%d c:%d Next:%d now:%d %lld %d %d\n", a,b,c, Next, x, tmp, B, C);
    b = 1ll* (-b+MOD) * tmp %MOD;
    c = 1ll* c * tmp %MOD;
    C = (1ll*C + 1ll*B*c) % MOD;
    B = 1ll* B*b %MOD;
    if(Next == tar) {
        ans[tar] = 1ll* C*inv( (1-B+MOD)%MOD ) % MOD;
        //  printf("tar: %d\n", ans[tar]);
        bfs(tar);
        return; 
    }
    Find(Next, tar, B, C);
}
void dfs(int x, int pre) {
    if(suc) return;
    for(int i = head[x]; ~i; i = E[i].nx) {
        int to = E[i].to; if(to == pre) continue;
        if(suc) return;
        if(!vis[to]) { vis[to] = 1; Pre[to] = i; dfs(to, x); }
        else {
            Pre[to] = i;
            Find(to, to, 1, 0);
            suc = 1; 
            break;
        }
    }
}


int main() {
    int n;
    while(~scanf("%d %d", &n, &MOD)) {
        memset(head, -1, sizeof(head));
        tot = 0;

        for(int i = 0; i < n; ++i) {
            int u, v, a, b, c;
            scanf("%d %d %d %d %d", &u, &v, &a, &b, &c);
            add(u, v, a, b, c);
            add(v, u, b, a, c);
        }

        for(int i = 1; i <= n; ++i) {
            if(!vis[i]) {
                suc = 0;
                vis[i] = 1; dfs(i, i);
            }
        }
        for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    }   
    return 0;
}