bef-> NO.16

Veröffentlicht am

P2416 泡芙

题目背景

此题空间限制256M，保证系统栈空间与内存限制大小相同

此题空间限制256M，保证系统栈空间与内存限制大小相同

此题空间限制256M，保证系统栈空间与内存限制大小相同

题目描述

火星猫经过一番努力终于到达了冥王星。他发现冥王星有 N 座城市，M 条无向边。火星猫准备出发去找冥王兔，他听说有若干泡芙掉落在一些边上，他准备采集一些去送给冥王兔。但是火星猫的火星光环和冥王星相生相克，当火星猫走过一条路之后，这条路就不能再走了。如果冥王兔吃不到泡芙，他们就不能嘿嘿嘿了。所以告诉你火星猫和冥王兔的位置，请问冥王兔能不能吃到泡芙。

输入输出格式

输入格式：

第一行 N,M 表示点数和边数。

接下来 M 行每行 X,Y,Z 表示 X 到 Y 有一条无向边，Z=1 表示有泡芙，Z=0 表示没有

接下来一行是 Q，表示有 Q 组询问。

每行 S,T 表示火星猫和冥王兔的位置。

输出格式：

对于每组询问输出 YES 或 NO

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1
1 6

输出样例#1：

1
YES

说明

1
2
3
4
5
6
no    N<=    M<=    Q<=    备注
3-4    1000    N-1    50000    保证图是一棵树
5-8    300000    N-1    300000    
9-10    20    50    5    无
11-14    1000    5000    50000    
15-20    300000    300000    300000

保证图联通

题解

这道题还是有一定思维难度的，让我们来分析一波。

也许我们会考虑最大生成树，因为那样可以使两点间最小的边最大化，但是并不能使两点间最大的边最大化。

然后我们看了看数据范围，发现和树上倍增的范围很像，于是想到缩边双联通分量把图缩成树。

下面我们来说这是为什么正确的，首先ECC有一个性质：ECC内任意两点均有两条严格不相交的路线（否则就会有桥）。这意味着只要ECC内有一条边长度为1，那么我们就能走过这条边而选择另一条严格不相交路径到达ECC其他点

因此本题算法是Tarjan ECC + LCA

将ECC视为点，处理点权即ECC内是否有边为1，然后做树上点权前缀和与边权前缀和（倍增也行，而且更加好想）

时间复杂度

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// luogu-judger-enable-o2
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <stack>
#include <cstring>
#define maxn 300005
int head[maxn] , cnt , n , m , ecc[maxn] , tot , dfn[maxn] , low[maxn] , f[maxn][22] , dep[maxn] , lg[maxn] , idx , gg , SE[maxn] , SV[maxn];
bool ins[maxn];
std::stack<int> st;
struct edge{
    int next ,to ,dis;
}e[maxn*2];
struct E{
    int f , t  ,d;
}ed[maxn*2];
inline void add(int x, int y , int d)
{
    e[++cnt].next = head[x];
    e[cnt].to = y;
    e[cnt].dis = d;
    head[x] = cnt;
}
void Tarjan(int x , int fx)
{
    dfn[x] = low[x] = ++idx;
    st.push(x);
    // ins[x] = true;
    for(int i = head[x] ; i ; i = e[i].next)
    {
        if(!dfn[e[i].to])
        {
            // printf("Tarjan! %d -> %d\n",x,e[i].to);
            Tarjan(e[i].to , x);
            low[x] = std::min(low[x] , low[e[i].to]);
        }
        else if(e[i].to != fx) low[x] = std::min(low[x] , dfn[e[i].to]);
    }
    if(dfn[x] == low[x])
    {
        ++tot;
        while(st.top() != x)
        {
            ecc[st.top()] = tot;
            // ins[st.top()] = false;
            st.pop();
        }
        ecc[st.top()] = tot;
        st.pop();
    }
}
void dfs(int x , int fx , int fd)
{
    // printf("%d %d %d:\n",x,fx,fd);
    f[x][0] = fx;
    // printf("%d\n",f[x][0]);
    // printf("g[%d][0] = %d\n",x,g[x][0]);
    SE[x] = SE[fx] + fd;
    SV[x] += SV[fx];
    dep[x] = dep[fx] + 1;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x , e[i].dis);
}
inline void OPTI()
{
    for(int i = 1 ; i <= tot ; ++i)
        lg[i] = lg[i-1] + ((1 << lg[i-1] )== i);
    for(int j = 1 ; j <= 21 ; ++j)
        for(int i = 1 ; i <= tot ; ++i)
            f[i][j] = f[f[i][j-1]][j-1];
}
inline int LCA(int x , int y)
{
    if(dep[x] < dep[y]) std::swap(x,y);
    while(dep[x] > dep[y])
        x = f[x][lg[dep[x]-dep[y]]-1];
    if(x == y) return x;
    for(int i = lg[dep[x]] ; i >= 0 ; --i)
        if(f[x][i] != f[y][i])
            x = f[x][i] , y = f[y][i];
    return f[x][0];
}
void test(int x , int fx)
{
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            printf("%d ->%d\n",x,e[i].to) , test(e[i].to , x);
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y , d;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d%d",&x,&y,&d) , add(x,y,d) , add(y,x,d) , ed[++gg].f = x , ed[gg].t = y , ed[gg].d = d , ed[++gg].f = y , ed[gg].t = x , ed[gg].d = d;
    Tarjan(1,0);
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d ",ecc[i]);
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    cnt = 0;
    // for(int i = 1 ; i <= 2 * m ; ++i)
    //     printf("%d %d %d\n",ed[i].f , ed[i].t , ed[i].d);
    for(int i = 1 ; i <= 2 * m ; ++i)
    {
        int u = ed[i].f , v = ed[i].t;
        if(ecc[u] == ecc[v]) SV[ecc[u]] += ed[i].d;
        if(ecc[u] != ecc[v])
            add(ecc[u] , ecc[v] , ed[i].d);
    }//clear
    // test(1,0);
    dfs(1,0,0);
    // for(int i = 1 ; i <= tot ; ++i)
    //     printf("%d ",dep[i]);
    // printf("%d\n",g[2][0]);
    //clear
    OPTI();
    // printf("%d\n",g[2][0]);
    // puts("OK")；
    // printf("%d\n",tot);
    int q;
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
    {
        scanf("%d%d",&x,&y);
        int u = ecc[x] , v = ecc[y];
        int fx = LCA(u,v);
        int ans = SV[u] + SV[v] - SV[fx] - SV[f[fx][0]] + SE[u] + SE[v] - 2 * SE[fx];
        if(ans > 0) puts("YES");
        else puts("NO"); 
        // printf("%d %d %d\n",s[u] , s[v] , s[LCA(u,v)]);

    }


}

Trie字典树

一种将每个字符串的每个字符按位置对应到树上节点的算法，可以O(n)插入，O(n)查询前缀等等等等。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 50005
#define maxz 60
int trie[maxn][maxz] , n  , tot , q;
bool mark[maxn * maxz];
std::string s[maxn] , p[maxn];
inline void insert(std::string s)
{
    int u = 1;
    for(int i = 0 ; i < s.length() ; ++i)
    {
        int c = s[i] - 'a' ;// not all
        if(!trie[u][c])
            trie[u][c] = ++tot;
        u = trie[u][c];
    }
    mark[u] = true;
}
inline int queryLCP(std::string s)
{
    int u = 1 , ans = 0;
    for(int i = 0 ; i < s.length() ; ++i)
    {
        int c = s[i] - 'a';
        if(trie[u][c])  ++ans;
        else return ans;
        u = trie[u][c];
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        std::cin>>s[i];
    for(int i = 1 ; i <= n ; ++i)
        insert(s[i]);
    scanf("%d",&q);
    for(int i = 1 ; i <= q ; ++i)
        std::cin>>p[i] , printf("%d\n",queryLCP(p[i]));
}

Phone List

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

  • Emergency 911
  • Alice 97 625 999
  • Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

1
2
NO
YES

Source

Nordic 2007

题解

显然是一道Trie字典树的题。在线插入的同时分别看看当前插入的字符串是不是之前的字符串前缀以及之前是否有当前串的前缀。思维难度海星

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 100005
#define maxlen 10
int trie[maxn][maxlen] , n , t , tot = 1;
std::string s;
bool mark[maxn];
inline bool insert(const std::string& s)
{
    int u = 1;
    bool flag = false , nw = true;
    for(int i = 0 ; i < s.length() ; ++i)
    {
        int c = s[i] - 48;
        if(!trie[u][c]) trie[u][c] = ++tot , nw = false;
        u = trie[u][c] ;
        if(mark[u]) flag = true;
    }
    mark[u] = true;
    flag = flag || nw ;
    return flag;
}
int main()
{
    // freopen("data.in","r",stdin);
    // freopen("my.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        std::memset(trie,0,sizeof(trie));
        std::memset(mark,false,sizeof(mark));
        tot = 1 ;
        bool flag = false;
        scanf("%d",&n);
        for(int i = 1 ; i <= n ; ++i)
        {
            std::cin>>s;
            if(insert(s)) flag = true ;
        }
        if(!flag) puts("YES");
        else puts("NO");
    }
}

Redundant Paths

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 18836 Accepted: 7795

Description

In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rotten Apples. The cows are now tired of often being forced to take a particular path and want to build some new paths so that they will always have a choice of at least two separate routes between any pair of fields. They currently have at least one route between each pair of fields and want to have at least two. Of course, they can only travel on Official Paths when they move from one field to another.

Given a description of the current set of R (F-1 <= R <= 10,000) paths that each connect exactly two different fields, determine the minimum number of new paths (each of which connects exactly two fields) that must be built so that there are at least two separate routes between any pair of fields. Routes are considered separate if they use none of the same paths, even if they visit the same intermediate field along the way.

There might already be more than one paths between the same pair of fields, and you may also build a new path that connects the same fields as some other path.

Input

Line 1: Two space-separated integers: F and R

Lines 2..R+1: Each line contains two space-separated integers which are the fields at the endpoints of some path.

Output

Line 1: A single integer that is the number of new paths that must be built.

Sample Input

1
2
3
4
5
6
7
8
7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

Sample Output

1
2

Hint

Explanation of the sample:

One visualization of the paths is:

1
2
3
4
5
6
7
8
9
  1   2   3
  +---+---+  
      |   |
      |   |
6 +---+---+ 4
     / 5
    / 
   / 
7 +

Building new paths from 1 to 6 and from 4 to 7 satisfies the conditions.

1
2
3
4
5
6
7
8
9
  1   2   3
  +---+---+  
  :   |   |
  :   |   |
6 +---+---+ 4
     / 5  :
    /     :
   /      :
7 + - - - -

Check some of the routes:

1 – 2: 1 –> 2 and 1 –> 6 –> 5 –> 2
1 – 4: 1 –> 2 –> 3 –> 4 and 1 –> 6 –> 5 –> 4
3 – 7: 3 –> 4 –> 7 and 3 –> 2 –> 5 –> 7

Every pair of fields is, in fact, connected by two routes.

It’s possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.

Source

USACO 2006 January Gold

题解

显然对于任何一个ECC，其中的任意两点都可以找到两条严格不相交路径，所以对于整个图的任意两点，经过ECC可以视为一个整体。所以我们将原图缩ECC成一颗树，通过推导树的性质我们可以发现只需要将树的叶子两两配对(奇数多出的连向任意一个叶子)，这样对于树上任何两点都处于一个环中，整个图就联通了，这是充分条件。（就是本方案一定正确的原因）

必要条件（即证明本方案最优）也十分好证明，假设任意两片叶子没有连边，那么这两点间只有一条路（树的性质）。对不是叶节点的点连边显然会导致比不连要更劣（因为每个叶子）。因此这个方法是正确的。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
#include <map>
#define maxn 5005
#define maxm 10005
int head[maxn] , cnt , n , m , dfn[maxn] , low[maxn] , idx , ecc[maxn] , tot , sz[maxn];
std::stack<int> st;
std::map<int,int> vis[maxn];
struct edge{
    int next , to;
}e[maxm * 2];
struct E{
    int from , to;
}ed[maxm*2];
inline void add(int x , int y)
{
    e[++cnt].next = head[x];
    e[cnt].to = y ;
    head[x] = cnt;
}
void Tarjan(int x , int fx)
{
    dfn[x] = low[x] = ++idx;
    st.push(x);
    for(int i = head[x] ; i ; i = e[i].next)
    {
        if(!dfn[e[i].to])
        {
            // printf("Tarjan! %d -> %d\n",x,e[i].to);
            Tarjan(e[i].to , x);
            low[x] = std::min(low[x] , low[e[i].to]);
        }
        else if(e[i].to != fx) low[x] = std::min(low[x] , dfn[e[i].to]);
    }
    if(dfn[x] == low[x])
    {
        ++tot;
        while(st.top() != x)
        {
            ecc[st.top()] = tot;
            st.pop();
        }
        ecc[st.top()] = tot;
        st.pop();
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int x , y , d;
    int g = 0;
    for(int i = 1 ; i <= m ; ++i)
        scanf("%d%d",&x,&y) , add(x,y) , add(y,x) , ed[++g].from = x , ed[g].to = y , ed[++g].from = y , ed[g].to = x;
    Tarjan(1,1);
    std::memset(head,0,sizeof(head));
    std::memset(e,0,sizeof(e));
    cnt = 0;
    // for(int i = 1 ; i <= n ; ++i)
    //     printf("%d ",ecc[i]);
    for(int i = 1 ; i <= 2 * m ; i++)
    {
        int u = ed[i].from , v = ed[i].to;
        if(!vis[ecc[v]][ecc[u]] && !vis[ecc[v]][ecc[u]] && ecc[v] != ecc[u])
            add(ecc[u] , ecc[v]) , add(ecc[v] , ecc[u]) , sz[ecc[u]] ++ , sz[ecc[v]] ++ , vis[ecc[v]][ecc[u]] = vis[ecc[u]][ecc[v]] = 1;
    }
    int ans = 0;
    for(int i = 1 ; i <= tot ; ++i)
        if(sz[i] == 1) ++ans;
    ans = (ans + 1) / 2;
    printf("%d",ans);
}

P4551 最长异或路径

题目描述

给定一棵nn个点的带权树，结点下标从11开始到NN。寻找树中找两个结点，求最长的异或路径。

异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

输入输出格式

输入格式：

第一行一个整数NN，表示点数。

接下来 n-1n−1 行，给出 u,v,wu,v,w ，分别表示树上的 uu 点和 vv 点有连边，边的权值是 ww。

输出格式：

一行，一个整数表示答案。

输入输出样例

输入样例#1：

复制

1
2
3
4
4
1 2 3
2 3 4
2 4 6

输出样例#1：

复制

1
7

说明

最长异或序列是1-2-3，答案是 7 (=3 ⊕ 4)

数据范围

题解

首先树上任意两点路径的XorSum就是两点到root的Xorsum在Xor，这是Xor的自反律。

然后我们做树上前缀Xor，然后问题就等价为从这些前缀xor中选出两个xorsum最大。

显然对于一个数来说，从其它的数中不同的位越高Xor越大，如果多个在最高位都不同一样，就再比下一位。

我们将每个数插入Trie树，然后对每个数这样在字典树上求出最大就行了

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int head[maxn] , cnt , n , trie[maxn * 33][3] , Xor[maxn] , tot , ans;
bool mark[maxn*33];
struct edge{
    int next , to , dis;
}e[maxn * 2];
inline void add(int x,  int y , int d)
{
    e[++cnt].next = head[x] ;
    e[cnt].to = y;
    e[cnt].dis = d;
    head[x] = cnt;
}
void dfs(int x , int fx , int dis)
{
    Xor[x] = Xor[fx] ^ dis;
    for(int i = head[x] ; i ; i = e[i].next)
        if(e[i].to != fx)
            dfs(e[i].to , x , e[i].dis);
}
inline void insert(int x)
{
    int u = 0 , lr = 30;
    for( ; lr >= 0 ; --lr)
    {
        if(!trie[u][(x>>lr)&1])   trie[u][1&(x>>lr)] = ++tot;
        u = trie[u][(x>>lr)&1];
    }
    mark[u] = true;
}
inline int query(int x)
{
    int u = 0 , lr = 30 , ans = 0;
    for( ; lr >= 0 ; --lr)
    {
        if(trie[u][((x>>lr)&1)^1]) ans += (1<<lr) , u = trie[u][((x>>lr)&1)^1];
        else u = trie[u][(x>>lr)&1];
    }
    return ans;
}
int main()
{
    scanf("%d",&n);
    int x , y , dis;
    for(int i = 1 ; i <= n - 1 ; ++i)
        scanf("%d%d%d",&x,&y,&dis) , add(x,y,dis) , add(y,x,dis);
    dfs(1,0,0);
    for(int i = 1 ; i <= n ; ++i)
        insert(Xor[i]);
    for(int i = 1 ; i <= n ; ++i)
        ans = std::max(ans , query(Xor[i]));
    printf("%d",ans);
}

4260: Codechef REBXOR

Description

imgimg.jpg)

Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

Output

输出一行包含给定表达式可能的最大值。

Sample Input

5
1 2 3 1 2

Sample Output

6

HINT

满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。

对于100%的数据，

Source

By yts1999

题解

从序列选两个不相交的区间，使得两个区间异或和最大。

Xor一般可以想三个：

前缀，trie，自反

然后我们发现一个区间xor最大相当于这个区间右端点前缀xor左端点前缀最大（自反），因此本题算法似乎很显然，从前开始一遍找出对于i之前的最大的一个区间，然后最后线性枚举中间点求出最后答案。

但是要注意是枚举点并不是要求定住的区间边界，而是小于等于或大于等于这个点的边界都可以，也就是说假设i+1计算的值不如i优，i+1左边显然应该继承i的值。

写题思路一定要清晰。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 400005
int  tot , A[maxn] , fr[maxn] , se[maxn] , n , sf[maxn] , sa[maxn];
struct trie{
    int tr[maxn*30][2] , tot;
    bool mark[maxn*30];
    inline void insert(int x)
    {
        int lr = 30 , u = 0;
        for( ; lr >= 0 ; --lr)
        {
            if(!tr[u][(x>>lr)&1]) tr[u][(x>>lr)&1] = ++tot;
            u = tr[u][(x>>lr)&1];
        }
        mark[u] = true;
    }
    inline int query(int x)
    {
        int lr = 30 , u = 0, ans = 0;
        for( ; lr >= 0 ; --lr)
        {
            if(tr[u][((x>>lr)&1)^1])    ans += (1<<lr) , u = tr[u][((x>>lr)&1)^1];
            else u = tr[u][(x>>lr)&1];
        }
        return ans;
    }
}tr1 , tr2 ;
int main()
{
    // freopen("rbzno1.in","r",stdin);
    scanf("%d",&n);
    for(int i = 1 ; i <= n ; ++i)
        scanf("%d",&A[i]);
    for(int i = 1 ; i <= n ; ++i)
        sf[i] = sf[i-1] ^ A[i];
    for(int i = n ; i >= 1 ; --i)
        sa[i] = sa[i+1] ^ A[i];
    tr1.insert(0) , tr2.insert(0);
    tr1.insert(sf[1]) , tr2.insert(sa[n]);
    for(int i = 2 ; i <= n ; ++i)
    {
        tr1.insert(sf[i]);
        fr[i] = std::max(fr[i-1] ,tr1.query(sf[i]));
    }
    for(int i = n-1 ; i >= 1 ; --i)
    {
        tr2.insert(sa[i]);
        se[i] = std::max(tr2.query(sa[i]) , se[i+1]);
    }
    int ans = 0;
    fr[1] = sf[1] , se[n] = sa[n];
    for(int i = 1 ; i < n ; ++i)
        ans = std::max(ans , fr[i] + se[i + 1]);
    printf("%d",ans);
}