Solved Pro.ID Title Ratio(Accepted / Submitted)
  1001 Rikka with Quicksort 25.85%(38/147)
  1002 Rikka with Cake 31.69%(379/1196)
  1003 Rikka with Mista 5.57%(45/808)
  1004 Rikka with Geometric Sequence 9.52%(2/21)
  1005 Rikka with Game 35.29%(866/2454)
  1006 Rikka with Coin 7.16%(358/5003)
  1007 Rikka with Travels 21.46%(85/396)
  1008 Rikka with Stable Marriage       字典树+贪心 17.02%(8/47)
  1009 Rikka with Traffic Light 0.00%(0/24)
  1010 Rikka with Defensive Line 0.00%(0/20)
  1011 Rikka with Segment Tree 39.39%(13/33)

1007 Rikka with Travels

思路：

一棵树上最长链处理，分出两种情况，一种是（a,b）各占一个端点，还有一种情况a占整条链，b是全踩在非最长链。

#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 n;

            vector<int>mp[maxn];

            int vis[maxn];

            int dis[maxn];

            vector<int>lian;

            ///扣出最长链

            void koulian() {

                for(int i=; i<=n; i++) dis[i] = inf;

                dis[] = ;

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

                int t = ;

                while(!que.empty()) {

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

                    if(dis[u] > dis[t])t = u;

                    for(int v : mp[u]) {

                        if(dis[v] > dis[u] + ) {

                            dis[v] = dis[u] + ;

                            que.push(v);

                        }

                    }

                }

                for(int i=; i<=n; i++) dis[i] = inf;

                dis[t] = ;

                que.push(t);

                int s = t;

                while(!que.empty()) {

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

                    if(dis[u] > dis[s])s = u;

                    for(int v:mp[u]) {

                        if(dis[v] > dis[u] + ) {

                            dis[v] = dis[u] + ;

                            que.push(v);

                        }

                    }

                }

                lian.pb(s);

                vis[s] = ;

                while(s != t) {

                    for(int v : mp[s]) {

                        if(dis[v] + == dis[s]) {

                            s = v;

                            lian.pb(s);

                            vis[s] = ;

                            break;

                        }

                    }

                }

            }

            int dpa[maxn], dpb[maxn][], pre[maxn];

            int dppre[maxn], dpback[maxn];

            ///求出以最长链上一个点为根节点的不经过最长链的最大深度

            void dfs1(int u, int fa) {

                dpa[u] = ;

                for(int v : mp[u]) {

                    if(v == fa || vis[v]) continue;

                    dfs1(v, u);

                    dpa[u] = max(dpa[u], dpa[v] + );

                }}

            void dfs2(int u, int fa) {

                dpb[u][] = dpb[u][] = ;

                ///dpb[0]表示包含根节点的最长链

                ///dpb[1]表示包含根节点的次长链

                pre[u] = ;

                for(int v : mp[u]) {

                    if(vis[v] || v == fa) continue;

                    dfs2(v, u);

                    pre[u] = max(pre[u], pre[v]);

                    if(dpb[u][] <= dpb[v][] + ){

                        dpb[u][] = dpb[v][] + ;

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

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

                        }

                    }

                }

                pre[u] = max(pre[u], dpb[u][] + dpb[u][] - );

            }

            int hei[maxn];

int main(){

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

            while(T--){

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

                }

                for(int i=; i<=n; i++) vis[i] = , hei[i] = , pre[i] = , dppre[i] = ,dpback[i] = ;

                koulian();

                for(int i=; i<lian.size(); i++) {

                    int v = lian[i];

                    dfs1(v, v);

                    if(i)dppre[i] =  max(dppre[i-], dpa[v] + i);

                    else dppre[i] = dpa[v];

                    for(int p : mp[v]) {

                        if(vis[p]) continue;

                        dfs2(p, p);

                        pre[v] = max(pre[v], pre[p]);

                    }

                    pre[v] = max(pre[v], pre[lian[max(, i-)]]);

                }

                int cc = ;

                for(int i=lian.size()-; i>=; i--) {

                    if(i == lian.size() - ) dpback[i] = dpa[lian[i]];

                    else dpback[i] = max(dpback[i+], dpa[lian[i]] + cc);

                    cc++;

                }

                int all = lian.size();

                hei[all] = pre[lian[all-]];

                hei[pre[lian[all-]]] = all;

                for(int i=lian.size() - ; i>=; i--) {

                    int v = lian[i];

                    int a = dppre[i-];

                    int b = dpback[i];

                    hei[a] = max(hei[a], b);

                    hei[b] = max(hei[b], a);

                }

                ll sum = ;

                int c = ;

                for(int i=all; i>=; i--) {

                    c = max(c, hei[i]);

                    sum = sum + c;

                }

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

                lian.clear();

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

            }

            return ;

}

/*

10

9

1 2

2 3

3 4

4 5

5 8

3 6

3 7

7 9

14

1 2

2 3

3 4

4 5

5 6

6 7

3 8

3 9

4 10

4 11

11 14

5 12

5 13

 = 36

*/

1008 Rikka with Stable Marriage

思路：

就是字典树+贪心，和第五场那个贪心顺序反一下就行了

// #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     <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;

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

            int tot[],rt[];

            int bz[];

            struct node{

                int ch[];

                int fa;

                int sz;

                void init(int f) {

                    ch[] = ch[] = ;

                    fa = f;

                    sz = ;

                }

            }tree[][maxn * ];

            int shu[];

            void add(int p, int len, int flag) {

                if(len == ){

                    tree[flag][p].sz++;

                    return;

                }

                if(tree[flag][p].ch[shu[len]] == )

                {

                    tree[flag][p].ch[shu[len]] = ++ tot[flag];

                    tree[flag][tot[flag]].init(p);

                }

                int nx = tree[flag][p].ch[shu[len]];

                add(nx, len-, flag);

                int lc = tree[flag][p].ch[];

                int rc = tree[flag][p].ch[];

                tree[flag][p].sz = tree[flag][lc].sz + tree[flag][rc].sz;

            }

            void insert(int val, int flag) {

                int len = ;

                for(int i=; i<=; i++) shu[++len] = val % , val /= ;

                add(rt[flag], , flag);

            }

            void display(int rt, int flag) {

                if(rt == ) return ;

//                cout<<tree[flag][rt].sz<<endl;

                display(tree[flag][rt].ch[], flag);

                display(tree[flag][rt].ch[], flag);

            }

            vector<int>vec;

            void find(int a, int b, int cen, int val) {

                if(cen == ) {

                    vec.pb(val);

                    tree[][a].sz--;

                    tree[][b].sz--;

                    return;

                }

                if(tree[][tree[][a].ch[]].sz && tree[][ tree[][b].ch[]].sz){

                    find(tree[][a].ch[], tree[][b].ch[], cen-, val + bz[cen-]);

                }

                else if(tree[][tree[][a].ch[]].sz && tree[][ tree[][b].ch[]].sz){

                    find(tree[][a].ch[], tree[][b].ch[], cen-, val + bz[cen-]);

                }

                else if(tree[][ tree[][a].ch[] ].sz && tree[][ tree[][b].ch[]].sz ) {

                    find(tree[][a].ch[], tree[][b].ch[], cen-, val);

                }

                else if(tree[][ tree[][a].ch[] ].sz && tree[][ tree[][b].ch[]].sz) {

                    find(tree[][a].ch[], tree[][b].ch[], cen-, val);

                }

                tree[][a].sz = tree[][tree[][a].ch[]].sz + tree[][tree[][a].ch[]].sz;

                tree[][b].sz = tree[][tree[][b].ch[]].sz + tree[][tree[][b].ch[]].sz;

            }

int main(){

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

            bz[] = ;

            for(int i=; i<=; i++) bz[i] =  * bz[i-];

            while(T--) {

                tot[] = tot[] = ;

                rt[] = ++tot[];

                tree[][rt[]].init();

                rt[] = ++tot[];

                tree[][rt[]].init();

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

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

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

                vec.clear();

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

                    find(rt[], rt[], , );

                }

                ll sum = ;

                for(int i=; i<vec.size(); i++) sum += vec[i];

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

            }

            return ;

}

最新文章

  1. 我叫Twenty，我是要成为博客王的博客框架
  2. Linux命令学习
  3. BZOJ 4636 蒟蒻的数列
  4. Activiti工作流学习-----基于5.19.0版本(5)
  5. Springmvc和velocity使用的公用后台分页
  6. java反射简解
  7. Zookeeper集群搭建步骤及相关知识点深入了解
  8. Git使用之pull request
  9. if ,while ,for 的掌握
  10. sklearn使用——最小二乘法
  11. 《Netty in action》 读书笔记
  12. python 字符串和字节数互转
  13. linux 修改centos7的网卡ens33修改为eth0
  14. cocos2d JS-(JavaScript) 动态生成方法的例子
  15. zoj 1151 Word Reversal(字符串操作模拟)
  16. Python&#160;Python-MySQLdb中的DictCursor使用方法简介
  17. iOS开发--改变tableHeaderView的高度
  18. 红黑树-算法大神的博客-以及java多线程酷炫的知识
  19. java- Servlet-session
  20. php call_user_func_array

热门文章

  1. nested exception is java.io.FileNotFoundException: class path resource [applicationContext.xml] cannot be opened because it does not exist
  2. 关于STM32F103+ESP8266+阿里云过程之修改SDK支持UART和SmartConfig（四）
  3. 【Android】Jetpack中的ViewModel：自动保存页面数据
  4. poj 1205 ：Water Treatment Plants (DP+高精度)
  5. 全文检索方案Elasticsearch【Python-Django 服务端开发】
  6. python_0基础学习_day02
  7. Docker笔记（七）：常用服务安装——Nginx、MySql、Redis
  8. Java连载16-++传参&amp;关系运算符
  9. golang学习（1）---快速hello world
  10. Daily，一个入门级的 React Native 应用