CF1187D. Subarray Sorting

想要把一个数x换到前面，x一定是小一点的值。由于B串是固定的，A串可调整，我们可以遍历B数组，对于B【i】，找到对于在A数组的位子pos，判断1～pos中，是不是A【pos】最小，如果是最小，说明可以换到最前面，把A【pos】的值变为inf后，继续遍历。

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const int MOD = 1e9+;

/**********showtime************/

            const int maxn = 3e5+;

            int a[maxn], b[maxn];

            queue<int>que[maxn];

            int mn[maxn<<];

            void update(int pos, int val, int le, int ri, int rt) {

                if(le == ri) {

                    mn[rt] = val;

                    return ;

                }

                int mid = (le + ri) >> ;

                if(mid >= pos) update(pos, val, le, mid, rt<<);

                else update(pos, val, mid+, ri, rt<<|);

                mn[rt] = min(mn[rt<<], mn[rt<<|]);

            }

            int query(int L, int R, int le, int ri, int rt) {

                if(le >= L && ri <= R) {

                    return mn[rt];

                }

                int mid = (le + ri) >> ;

                int res = inf;

                if(mid >= L) res = min(res, query(L,R,le, mid, rt<<));

                if(mid < R) res = min(res, query(L,R,mid+, ri, rt<<|));

                return res;

            }

            void build(int le, int ri, int rt) {

                if(le == ri) return ;

                int mid = (le + ri) >> ;

                build(le, mid, rt<<);

                build(mid+, ri, rt<<|);

            }

int main(){

            int T;  scanf("%d", &T);

            while(T--) {

                int n;  scanf("%d", &n);

                build(, n, );

                for(int i=; i<=n; i++) scanf("%d", &a[i]), que[a[i]].push(i), update(i, a[i], , n, );

                for(int i=; i<=n; i++) scanf("%d", &b[i]);

                int flag = ;

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

                    if(!que[b[i]].empty()) {

                        int p = que[b[i]].front();  que[b[i]].pop();

                        if(query(, p, , n, ) < b[i]) flag = ;

                        else update(p, inf, , n, );

                    }

                    else flag = ;

                }

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

                    while(!que[a[i]].empty()) que[a[i]].pop();

                }

                puts(flag?"YES":"NO");

            }

            return ;

}

E Tree Painting

树形DP，换根的转移。

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x7f7f7f7f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9+;

const double eps = 1e-;

/**********showtime************/

            const int maxn = 2e5+;

            vector<int> mp[maxn];

            int sz[maxn];

            ll ans = ;

            int n;

            void dfs(int u, int fa) {

                sz[u] = ;

                for(int i=; i<mp[u].size(); i++) {

                    int v = mp[u][i];

                    if(v == fa) continue;

                    dfs(v, u);

                    sz[u] += sz[v];

                }

                ans += sz[u];

            }

            void dfs2(int u, int fa, ll pre) {

                for(int i=; i<mp[u].size(); i++) {

                    int v = mp[u][i];

                    if(v == fa) continue;

                    ll tmp = pre + n - 2ll * sz[v];

                    ans = max(ans, tmp);

                    dfs2(v, u, tmp);

                }

            }

int main(){

            scanf("%d", &n);

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

                int u,v;

                scanf("%d%d", &u, &v);

                mp[u].pb(v);

                mp[v].pb(u);

            }

            dfs(, -);

            dfs2(, -, ans);

            printf("%lld\n", ans);

            return ;

}

G Gang Up

网络流，搞好了。

这道题要把每个点拆成多个点表示不同的时间，每条边要对应多条道路，就是把1,4,9....变成容量为1,费用位1,3,5的边。

每个点要拆成100个点，就是最多会等待100的时间单位。因为第一个人最迟50个时间，那个第50个人就要100个时间到。

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const int mod = 1e9+;

/**********showtime************/

            const int maxn = ;

            int st[maxn];

            struct E{

                int u,v,w,cost;

                int nxt;

            } edge[];

            int gtot = ,head[maxn * ];

            void addedge(int u, int v, int w, int cost) {

                edge[gtot].v = v;

                edge[gtot].w = w;

                edge[gtot].cost = cost;

                edge[gtot].nxt = head[u];

                head[u] = gtot++;

                edge[gtot].v = u;

                edge[gtot].w = ;

                edge[gtot].cost = -cost;

                edge[gtot].nxt = head[v];

                head[v] = gtot++;

            }

            int dis[maxn * ],path[],vis[maxn*],pre[maxn*];

            bool spfa(int s,int t){

                memset(pre, - ,sizeof(pre));

                memset(dis, inf,sizeof(dis));

                memset(vis, , sizeof(vis));

                queue<int>que;  que.push(s);

                vis[s] = ; dis[s] = ;

                while(!que.empty()){

                    int u = que.front(); que.pop();

                    vis[u] = ;

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

                        int v = edge[i].v, val = edge[i].w, cost = edge[i].cost;

                        if(val >  && dis[v] > dis[u] + cost){

                            dis[v] = dis[u] + cost;

                            pre[v] = u; path[v] = i;

                            if(vis[v] == ){

                                vis[v] = ;

                                que.push(v);

                            }

                        }

                    }

                }

                return pre[t] != -;

            }

            int mcmf(int s,int t){

                int flow = ,cost = ;

                while(spfa(s, t)){

                    int f = inf;

                    for(int i=t; i!=s; i = pre[i]){

                        f = min(f, edge[path[i]].w);

                    }

                    flow += f;

                    cost += f * dis[t];

                    for(int i=t; i!=s; i = pre[i]){

                        edge[path[i]].w -= f;

                        edge[path[i]^].w += f;

                    }

                }

                return cost;

            }

int main(){

            memset(head, -, sizeof(head));

            gtot = ;

            int n,m,k,c,d;

            scanf("%d%d%d%d%d", &n, &m, &k, &c, &d);

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

                int x;

                scanf("%d", &x);

                st[x]++;

            }

            int s = , t =  * n + ;

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

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

                    addedge((i-)*+j-, (i-)* + j, inf, c);

                }

            }

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

                if(st[i]) addedge(s, (i-)* + , st[i], );

            }

            for(int i=; i<=; i++) addedge(i, t, inf, );

            for(int i=; i<=m; i++) {

                int u,v;

                scanf("%d%d", &u, &v);

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

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

                        addedge((u-)* + j - , (v-)* + j, , (k*k - (k-)*(k-)) * d + c);

                        addedge((v-)* + j - , (u-)* + j, , (k*k - (k-)*(k-)) * d + c);

                    }

                }

            }

            printf("%d\n", mcmf(s, t));

            return ;

}

也可以两个点之间只建立一条道路，那么费用就需要根据流量重新计算。

#include <cstdio>

#include <vector>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <queue>

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a)

typedef long long ll;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

template<class T> void _R(T &x) { cin >> x; }

void _R(int &x) { scanf("%d", &x); }

void _R(ll &x) { scanf("%lld", &x); }

void _R(double &x) { scanf("%lf", &x); }

void _R(char &x) { scanf(" %c", &x); }

void _R(char *x) { scanf("%s", x); }

void R() {}

template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }

const int inf = 0x3f3f3f3f;

const int mod = 1e9+;

/**********showtime************/

            const int maxn = ;

            int st[maxn];

            // Min-Cost Flow with positive convex edge weights

class MinCostFlow {

    private:

        struct Edge {

            int a, b; // source, target

            int f, c; // flow, capacity

            ll m1, m2; // constants for cost

            Edge(int av, int bv, int cv, ll m1v, ll m2v)

                : a(av), b(bv), f(), c(cv), m1(m1v), m2(m2v) {}

            // Get other end of edge

            int getOth(int i) {

                return i == a ? b : a;

            }

            // Get change in cost of pushing flow from i to getOth(i)

            ll getCost(int i) {

                int tf = f + (i == a ?  : -);

                if (tf <  || tf > c) return inf;

                return m1*(tf-f) + m2*(tf*tf-f*f);

            }

            void pushUnit(int i) {

                f += (i == a ?  : -);

            }

        };

        vector<Edge> eds;

        vector<vector<int> > conns;

    public:

        MinCostFlow(int n) : conns(n) {}

        void addEdge(int a, int b, int c, int m1, int m2) {

            Edge tmp(a, b, c, m1, m2);

            eds.push_back(tmp);

            conns[a].push_back(eds.size() - );

            conns[b].push_back(eds.size() - );

        }

        ll pushFlow(int source, int sink) {

            int n = conns.size();

            ll res = ;

            vector<int> pre(n);

            vector<ll> cost(n);

            while(true) {

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

                    pre[i] = -;

                    cost[i] = inf;

                }

                cost[source] = ;

                priority_queue<pair<ll, int> > que;

                que.push(pair<ll, int>(, source));

                while(! que.empty()) {

                    int i = que.top().second;

                    ll v = -que.top().first;

                    que.pop();

                    if (v > cost[i]) continue;

                    for (auto j : conns[i]) {

                        int t = eds[j].getOth(i);

                        ll off = cost[i] + eds[j].getCost(i);

                        if (off < cost[t]) {

                            cost[t] = off;

                            pre[t] = j;

                            que.push(pair<ll, int>(-off, t));

                        }

                    }

                }

                int i = sink;

                while(pre[i] != -) {

                    auto& ed = eds[pre[i]];

                    i = ed.getOth(i);

                    ed.pushUnit(i);

                }

                if (i != source) break;

                res += cost[sink];

            }

            return res;

        }

};

int main(){

            int n,m,k,c,d;

          //  scanf("%d%d%d%d%d", &n, &m, &k, &c, &d);

            R(n,m,k,c,d);

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

                int x;

                scanf("%d", &x);

                st[x]++;

            }

            int s = , t =  * n + ;

            MinCostFlow fl(t + );

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

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

                    fl.addEdge((i-)*+j-, (i-)* + j, inf, c, );

                }

            }

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

                if(st[i]) fl.addEdge(s, (i-)* + , st[i], , );

            }

            for(int i=; i<=; i++) fl.addEdge(i, t, inf, , );

            for(int i=; i<=m; i++) {

                int u,v;

                scanf("%d%d", &u, &v);

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

                        fl.addEdge((u-)* + j - , (v-)* + j, k, c, d);

                        fl.addEdge((v-)* + j - , (u-)* + j, k, c, d);

                }

            }

            // printf("%d\n", fl.mcmf(s, t));

            cout<<fl.pushFlow(s, t)<<endl;

            return ;

}

最新文章

  1. Pivot Table
  2. html与Android——webView
  3. angularjs简述
  4. 转帖一篇sixxpack破解的文章！
  5. C# PLINQ 内存列表查询优化历程
  6. Oracle按用户进行统计信息更新
  7. FreeCodeCamp：Return Largest Numbers in Arrays
  8. 201521123115 《Java程序设计》第5周学习总结
  9. z3 巧解CTF逆向题
  10. 【BZOJ2037】Sue的小球（动态规划）
  11. 『ice 离散化广搜』
  12. [android] 隐式意图激活另外一个activity
  13. Nintex Workflow Get Attachment link
  14. python----函数初识
  15. 【vue】中 $parent 和 $children 的使用方法
  16. luogu P4074 [WC2013]糖果公园
  17. spring cloud: zuul: 微网关-简单使用与路由配置
  18. UCore-Lab1
  19. You can Solve a Geometry Problem too （hdu1086）几何，判断两线段相交
  20. unity2D以最小的角度旋转到目标方向（y方向为角色的主方向）

热门文章

  1. springBoot数据校验与统一异常处理
  2. 【iOS】Error: Error Domain=PBErrorDomain Code=7 &quot;Cannot connect to pasteboard server
  3. git项目版本处理--远程分支重新拉取本地代码如何处理
  4. Wpf窗口设置可拖动
  5. 利用MAVEN打包可运行jar包，包括依赖的第三方包
  6. Go中的字符串使用----strings和strconv
  7. Codeforces Round #574 (Div. 2)——C. Basketball Exercise（简单DP）
  8. 转载 | CSS图片下面产生间隙的 6种解决方案
  9. java线程池,阿里为什么不允许使用Executors?
  10. 『开发技术』GPU训练加速原理（附KerasGPU训练技巧）