Atcoder Beginner 246 EFG

E - Max Min

题意：给出一个序列，问有多少个子区间满足 \(max=X\) 且 \(min=Y\)

我的解法（下面还有另一种神仙解法：

枚举区间的左端点，然后二分区间的右端点，二分两次，分别找第一个使得区间max>X或min<Y的右端点，和第一个使得区间max>=X且min<=Y的右端点。简单来说就是找第一个达到要求的位置和第一个超出要求范围的位置。这两个位置相减即可得到合法右端点的数量。

求区间max和min自然是用st表

int n, X, Y;
int mx[maxn][32], mi[maxn][32];

pair<int, int> get(int l, int r){
    if(r > n) return make_pair(1e9, -1e9);
    int k = log(r - l + 1) / log(2);
    return make_pair(max(mx[l][k], mx[r-(1<<k)+1][k]), min(mi[l][k], mi[r-(1<<k)+1][k]));
}

void solve(){
    cin >> n >> X >> Y;
    for(int i=1;i<=n;i++){
        cin >> mx[i][0];
        mi[i][0] = mx[i][0];
    }
    for(int k=1;k<=20;k++){
        for(int i=1;i+(1<<k)-1<=n;i++){
            mi[i][k] = min(mi[i][k-1], mi[i+(1<<(k-1))][k-1]);
            mx[i][k] = max(mx[i][k-1], mx[i+(1<<(k-1))][k-1]);
        }
    }

    ll ans = 0;
    for(int i=1;i<=n;i++){
        int l = i, r = n + 1;
        if(mi[i][0] > X || mi[i][0] < Y) continue;
        while(l < r){
            int mid = (l + r) / 2;
            auto p = get(i, mid);
            if(p.first > X || p.second < Y){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        int rp = l;

        l = i, r = n + 1;
        while(l < r){
            int mid = (l + r) / 2;
            auto p = get(i, mid);
            if(p.first >= X && p.second <= Y){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        int lp = l;

        ans += max(0, rp - lp);
    }
    cout << ans << '\n';
}

神仙解法：

我们可以很轻易的计算出 \(max\le X\) 且 \(min\ge Y\) 的区间个数，找到所有值在 \([X,Y]\) 范围内的数，把他们连成的区间计算一下就好，假设这样的区间个数为 \(g(X,Y)\)

容斥一下，答案即：\(g(X,Y)-g(X-1,Y)-g(X,Y-1)+g(X-1,Y-1)\)

int n, a[maxn];
ll g(int x, int y){
    ll cnt = 0, ans = 0;
    for(int i=1;i<=n;i++){
        if(y <= a[i] && a[i] <= x){
            cnt++;
        }else{
            ans += (cnt * (cnt + 1)) / 2;
            cnt = 0;
        }
    }
    ans += (cnt * (cnt + 1)) / 2;
    return ans;
}

void solve(){
    int x, y;
    cin >> n >> x >> y;
    for(int i=1;i<=n;i++) cin >> a[i];
    cout << g(x, y) - g(x-1, y) - g(x, y+1) + g(x-1, y+1) << '\n';
}

F - Cards

题意：有 \(n\) 张卡片，每张卡片正面和背面各有一个数字，保证其中数字 \(1..n\) 各出现两次，问现在有多少种取卡片的方案，使得取到的卡片包含每一种数字。

如果两个数字出现在同一张卡片上，我们就将它们连边，这样构造出来的图每个点的度数都为2，那就意味着这个图可以被分为若干个互不干涉的简单环。

那么问题就变成了：一个包含 \(x\) 个节点的环中，每条边可以选或不选，有多少中选法使得相邻两边至少有一条选中。

考虑一下递推这个问题：假设已经有 \(x-1\) 条边的环了，考虑在1,2号边之间插入新的边（哪里都一样），如果1,2都选，则这条新边可选可不选，否则新必边须选。除此之外，还需要加上1,2都不选（不包括在 \(x-1\) 的情况内），新边选的情况。

限制1,2都选或都不选的情况数，就等于 \(x-2\) 条边的环的情况数（1,2条可以看做同一条边）

那么就有：\(f_x=f_{x-1}+f_{x-2}\)，容易递推

int n, a[maxn], b[maxn];
int t[maxn], vis[maxn];

int dfs(int p){
    if(vis[p]) return 0;
    vis[p] = true;
    return dfs(t[p]) + 1;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        cin >> b[i];
        t[a[i]] = b[i];
    }

    vector<int> f(n+1);
    f[1] = 1;
    f[2] = 3;
    for(int i=3;i<=n;i++) f[i] = (f[i-1] + f[i-2]) % mode;
    ll ans = 1;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int cnt = dfs(i);
            ans = ans * f[cnt] % mode;
        }
    }
    cout << ans << '\n';
}

G - Dream Team

题意：有 \(n\) 个人，每个人有所在城市 \(A_i\)，所选学科 \(B_i\)，能力 \(C_i\)，现要从中挑选 \(k\) 个人组成梦之队，要求所有选择的人城市各部相同，学科各不相同。问对于每一个可能的 \(k\)，梦之队的能力总和最大值是多少。

• \(1≤N≤3×10^4\)
• \(1 \leq A_i,B_i \leq 150\)
• \(1 \leq C_i \leq 10^9\)

一眼150，鉴定为暴力

考虑费用流，从起点向每个 \(A\) 容量为1的边，从每个 \(B\) 向终点连容量为1的边，限制了每个城市和学科都只能选一次，然后对于每个人，将 \(A_i\) 和 \(B_i\) 之间连一条费用为 \(C_i\) ，容量为1的边。然后跑费用流就可以了。

因为网络流是逐路径增广的，边流量又都为1，那么每次增广就相当于增加了一个人数，记录每次增广后的最小费用即可。

可以将费用改为 \(-C_i\)，计算最小费用流后取反即可。

//板子
namespace Flow{
    int n, st, ed;
    ll dis[maxn], h[maxn], pre[maxn];//记录最短路中连向它的边号
    struct Edge{
        int fr, to, nt;
        ll w, c;
        ll dis()const{//获取修正后的边权
            return c + h[fr] - h[to];
        }
    }e[maxn << 1];
    int head[maxn], ecnt = 1;
    inline void init(int s, int t, int cnt){
        n = cnt, st = s, ed = t;
        for(int i=1;i<=n;i++) head[i] = 0;
    }
    inline void add(int x, int y, ll w, ll c){
        e[++ecnt] = {x, y, head[x], w, c};
        head[x] = ecnt;
        e[++ecnt] = {y, x, head[y], 0, -c};
        head[y] = ecnt;
    }
    void spfa(){
        vector<bool> vis(n+1, false);
        queue<int> q; q.push(st);
        h[st] = 0; vis[st] = true;
        while(!q.empty()){
            int u = q.front(); q.pop();
            vis[u] = false;
            for(int i=head[u];i;i=e[i].nt){
                int v = e[i].to;
                if(e[i].w > 0 && h[v] > h[u] + e[i].c){
                    h[v] = h[u] + e[i].c;
                    if(!vis[v]) vis[v] = true, q.push(v);
                }
            }
        }
    }
    bool dij(){
        struct node{
            ll t, dis;
            bool operator >(const node &x)const{
                return dis > x.dis;
            }
        };
        for(int i=1;i<=n;i++) dis[i] = INF;
        dis[st] = 0;
        priority_queue<node, vector<node>, greater<> > q;
        q.push({st, 0});
        while(!q.empty()){
            node u = q.top();
            q.pop();
            if(u.dis > dis[u.t]) continue;
            for(int i=head[u.t];i;i=e[i].nt){
                int v = e[i].to;
                if(e[i].w > 0 && dis[v] > dis[u.t] + e[i].dis()){
                    dis[v] = dis[u.t] + e[i].dis();
                    pre[v] = i;
                    q.push({v, dis[v]});
                }
            }
        }
        return dis[ed] < INF;
    }

    vector<ll> ans;
    pair<ll, ll> calcu(){
        spfa();
        ll answ = 0, ansc = 0;
        while(dij()){
            ll minf = INF;
            for(int i=ed;i!=st;i=e[pre[i]].fr) minf = min(minf, e[pre[i]].w);
            for(int i=ed;i!=st;i=e[pre[i]].fr){
                e[pre[i]].w -= minf;
                e[pre[i] ^ 1].w += minf;
                ansc += e[pre[i]].c * minf;
            }
            answ += minf;
            ans.push_back(-ansc);
            for(int i=1;i<=n;i++) h[i] += dis[i];
        }
        return {answ, ansc};
    }

    void print(){
        cout << ans.size() << '\n';
        for(ll x: ans) cout << x << '\n';
    }
}

void solve(){
    int n;
    cin >> n;
    Flow::init(301, 302, 302);
    for(int i=151;i<=300;i++) Flow::add(i, 302, 1, 0);
    for(int i=1;i<=150;i++) Flow::add(301, i, 1, 0);

    for(int i=1;i<=n;i++){
        int a, b, c;
        cin >> a >> b >> c;
        Flow::add(a, 150+b, 1, -c);
    }

    Flow::calcu();
    Flow::print();
}