题解：P17193 [KOI 2026 #2] 搭骰子塔

wanganze · 2026-08-07 14:52:42 · 题解

题意

有一些骰子，你要把它们堆成尽可能少的塔，要求每两个上下相邻的骰子的数字要相同。骰子对面之和为 7。

分析

显然，一个塔最多由朝上面为 x 和 7-x 的两种骰子交替形成。我们把骰子按朝上面数字配对成 (1,6),(2,5),(3,4) 三组，每组的问题互不干扰。

显然，如果某一组里两种骰子都没有出现，这一组的答案为 0。否则我们肯定想要让每个塔都有尽可能多的骰子，但是一个塔中两种骰子的数量之差不能超过 1（否则无法交替），而多出来的只能独立一堆。所以答案为 \max(|c_x-c_{7-x}|,1)，其中 c_i 为第 i 种骰子的出现次数。每组的构造方案就是尽可能交替放置两种互补的骰子，多出来的无论如何也要单独放。

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int c[N];
int main()
{
    int n,res = 0;
    cin>>n;
    for(int i = 1,x; i <= n; i ++) cin>>x,c[x] ++;
    for(int i = 1; i <= 3; i ++)
        if(c[i] || c[7 - i]) res += max(abs(c[i] - c[7 - i]),1);
    cout<<res<<'\n'; 
    return 0;
}