Solved	Pro.ID	Title	Ratio(Accepted / Submitted)
	1001	Acesrc and Cube Hypernet	7.32%(3/41)
	1002	Acesrc and Girlfriend	4.35%(2/46)
	1003	Acesrc and Good Numbers　　　　　　　　　　　　暴力打表	24.80%(213/859)
	1004	Acesrc and Hunting	21.74%(90/414)
	1005	Acesrc and String Theory	23.46%(38/162)
	1006	Acesrc and Travel　　　　　　　　　　　　　　　　换根树形DP	12.01%(123/1024)
	1007	Andy and Data Structure	0.85%(1/117)
	1008	Andy and Maze　　　　　　　　　　　　　　　　　　随机染色+状压DP	15.71%(33/210)
	1009	Calabash and Landlord	18.99%(613/3228)
	1010	Quailty and CCPC	33.48%(1060/3166)
	1011	Roundgod and Milk Tea	17.70%(776/4384)

1006 Acesrc and Travel

换根树形DP

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

#include <unordered_map>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

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 unsigned long long ull;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

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

            const int maxn = 1e5+;

            int a[maxn],b[maxn];

            vector<int>mp[maxn];

            int n;

            ll dpa[maxn][], dpb[maxn][];

            ///dpa[u][0]表示a从u开始选最大所能得，需要从dpb最小的转移过来，实际是个最小值

            ///dpa[u][1] 表示次小值。

            ///dpb[u][0]表示b的，它只能从dpa最大的转移过来，实际上是个最大值。

            ///dpb[u][1]表示次大值

            int sona[maxn], sonb[maxn];

            void dfs1(int u, int fa) {

                dpa[u][] = dpa[u][] = inff;

                dpb[u][] = dpb[u][] = -inff;

                sona[u] = sonb[u] = ;

                for(int v : mp[u]) {

                    if(v == fa) continue;

                    dfs1(v, u);

                    if(dpb[v][] + a[u] - b[u] <= dpa[u][]) {

                        dpa[u][] = dpb[v][] + a[u] - b[u];

                        if(dpa[u][] < dpa[u][]) {

                            swap(dpa[u][] , dpa[u][]);

                            sona[u] = v;

                        }

                    }

                    if(dpa[v][] + a[u] - b[u] >= dpb[u][]) {

                        dpb[u][] = dpa[v][] + a[u] - b[u];

                        if(dpb[u][] > dpb[u][]) {

                            swap(dpb[u][], dpb[u][]);

                            sonb[u] = v;

                        }

                    }

                }

                ///度数为1的节点需要特殊判断，还要区分根节点和叶子节点

                if(mp[u].size() <=  && fa != ) {

                    dpa[u][] = dpb[u][] = a[u] - b[u];

                }

            }

            ll ans;

            ll cupa[maxn], cupb[maxn];

            void dfs2(int u, int fa) {

                ll tmp = min(dpa[u][], cupa[u]);

                if(mp[u].size() ==  && fa) tmp = cupa[u];

                ans = max(ans, tmp);

                for(int v : mp[u]) {

                    if(v == fa) continue;

                    cupa[v] = max(cupb[u], dpb[u][ sonb[u] == v ? : ]) + a[v] - b[v];

                    cupb[v] = min(cupa[u], dpa[u][ sona[u] == v ? : ]) + a[v] - b[v];

                    dfs2(v, u);

                }

            }

int main(){

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

            while(T--) {

                scanf("%d", &n);

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

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

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

                    int u,v;

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

                    mp[u].pb(v);

                    mp[v].pb(u);

                }

                dfs1(, );

                ans = dpa[][];

                if(mp[].size() == ) cupa[] = cupb[] = a[] - b[];

                else cupa[] = inff, cupb[] = -inff;

                dfs2(, );

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

                for(int i=; i<=n; i++) mp[i].clear();

            }

            return ;

}

1008 Andy and Maze

用到了color coding技巧。

参考和学习

/*

* @Author: chenkexing

* @Date:   2019-08-16 22:30:07

* @Last Modified by:   chenkexing

* @Last Modified time: 2019-08-16 23:30:32

*/

// #pragma GCC optimize(2)

// #pragma GCC optimize(3)

// #pragma GCC optimize(4)

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <ctime>

#include    <random>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

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;

typedef pair<pii, ll> p3;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

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

            mt19937 rnd(time());

            const int maxn = 1e4+;

            struct E

            {

                int u,v,w;

            }edge[maxn];

            int col[maxn];

            int n,m,k;

            ll dp[maxn][];

            ll randgao() {

                for(int i=; i<=n; i++) col[i] = rnd() % k;

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

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

                        dp[i][j] = -inff;

                    }

                    int j = ( << col[i]);

                    dp[i][j] = ;

                }

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

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

                        int u = edge[i].u, v = edge[i].v, w = edge[i].w;

                        if((j & ( << col[u])))

                            dp[u][j] = max(dp[u][j], dp[v][j ^ ( << col[u])] + w);

                        if((j & ( << col[v])))

                            dp[v][j] = max(dp[v][j], dp[u][j ^ ( << col[v])] + w);

                    }

                }

                int up = ( << k) - ;

                ll res = -inff;

                for(int i=; i<=n; i++) res = max(res, dp[i][up]);

                return res == -inff ? - : res;

            }

int main(){

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

            while(T--) {

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

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

                    scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);

                }

                ll ans = -;

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

                    ans = max(ans, randgao());

                }

                if(ans == -) puts("impossible");

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

            }

            return ;

}

巴特西

2019DX#8

1006 Acesrc and Travel

1008 Andy and Maze

最新文章

热门文章