{"problem":{"name":"「SvR-2」1+2=3（加强版）","description":{"content":"你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[0,c)$ 的自然数，你要将所有木棒拼起来，使相邻的数和为 $c$ 的对数最大。 例如，$c=3$，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9153"},"statements":[{"statement_type":"Markdown","content":"你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[0,c)$ 的自然数，你要将所有木棒拼起来，使相邻的数和为 $c$ 的对数最大。\n\n例如，$c=3$，$1\\text{ - }2$ 和 $1\\text{ - }0$ 两个木棒，如果按 $1\\text{ - }0,1\\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\\text{ - }\\textcolor{red}{\\underline{\\textbf 2}},\\textcolor{red}{\\underline{\\textbf 1}}\\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。\n\n## Input\n\n**本题有多组数据。**\n\n输入的第一行一个正整数表示数据组数 $T$。\n\n对于每组数据，第一行输入一个正整数 $c$，之后 $c$ 行，每行 $c$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 为 $(i-1)\\text{ - }(j-1)$ 型木棒的个数。\n\n## Output\n\n共 $T$ 行，每行一个整数表示答案。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，$1\\le T\\le10^5$，$1\\le a_{i,j}\\le10^9$，$3\\le c\\le10^3$，$\\sum c^2\\le5\\times10^6$。\n\n**注：本题数据较弱，如有 hack 欢迎告知出题人。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9153","tags":["欧拉回路"],"sample_group":[["1\n3\n4 1 3\n4 7 7\n9 10 3\n","31\n"]],"created_at":"2026-03-03 11:09:25"}}