{"problem":{"name":"[CCC 2024 S5] Chocolate Bar Partition","description":{"content":"Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \\times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。 如果可以通过向上、向下、向","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10299"},"statements":[{"statement_type":"Markdown","content":"Maxwell 有一块巧克力想和他的朋友们分享。巧克力可以看作 $2\\times N$ 个小方块组成的，每个小方块的美味度可以表示为 $2 \\times N$ 的整数数组 $T_{i,j}$。Maxwell 想把整个巧克力分成若干个连通块，每个连通块的巧克力小方格的平均美味程度都是一样的。Maxwell 想知道根据如上所述，他可以将巧克力棒分成的最大连通块数量是多少。\n\n如果可以通过向上、向下、向左或向右移动的方式访问到每个小方块，则该部分被视为一个连通块。\n\n## Input\n\n输入的第一行包含一个正整数 $N$ 表示巧克力的长度。\n\n第二行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第一行第 $j$ 个小方块的美味度 $T_{1,j}$。\n\n类似地，第三行包含 $N$ 个空格隔开的整数，第 $j$ 个整数表示巧克力的第二行第 $j$ 个小方块的美味度 $T_{2,j}$。\n\n## Output\n\n输出一个整数，表示 Maxwell 最多能把巧克力切分出的连通块数。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n把巧克力分割成 $2$ 块是最优的，一种方案是把右下角的一个小方块作为一个连通块，其余三个小方块作为第二个连通块，如下图所示。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/2yga1u9u.png)\n\n每一个连通块的平均美味度都为 $5$。\n\n**【样例 2 解释】**\n\n一种获得平均分割巧克力的方案如下图所示：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/hty1ata8.png)\n\n注意每一块的平均美味度都为 $1$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n对于所有数据，保证 $1 \\leq N \\leq 2 \\times 10^5$，$0 \\leq T_{i,j} \\leq 10^8$。\n\n下面的表格显示了 $15$ 分的分配方案：\n\n| 分值 | $N$ 的范围 | $T_{i,j}$ 的范围 |\n| :-: | :-: | :-: |\n| $2$ | $N = 2$ | $0 \\leq T_{i,j} \\leq 5$ |\n| $2$ | $1 \\leq N \\leq 8$ | $0 \\leq T_{i,j} \\leq 20$ |\n| $1$ | $1 \\leq N \\leq 20$ | $0 \\leq T_{i,j} \\leq 20$ |\n| $2$ | $1 \\leq N \\leq 100$ | $0 \\leq T_{i,j} \\leq 20$ |\n| $2$ | $1 \\leq N \\leq 1000$ | $0 \\leq T_{i,j} \\leq 100$ |\n| $3$ | $1 \\leq N \\leq 2000$ | $0 \\leq T_{i,j} \\leq 10^5$ |\n| $3$ | $1 \\leq N \\leq 2 \\times 10^5$ | $0 \\leq T_{i,j} \\leq 10^8$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10299","tags":["2024","CCC（加拿大）"],"sample_group":[["2\n5 4\n6 5\n","2\n"],["5\n1 0 1 2 0\n0 2 0 3 1\n","5\n"]],"created_at":"2026-03-03 11:09:25"}}