2025年10月12日学校编程集训感言

admin

2025 年 10 月 12 日

30 次浏览

暂无评论

1543字数

OI 编程

# T1

## 【题面】T678583 A美丽数 (beauty)

### 题目描述

小 B 对数字有着独到的见解，他认为一个数是美丽数当且仅当这个数的相邻两位都不相同。

例如12345、12121是美丽数，而123321、11不是美丽数。
现在小B想知道，对于所有满足以下条件的数中，最小的那个数是什么?如果不存在这样的美丽数，则输出-1。

· 对 于i(0≤i≤9),              这个数中是i  的位数一共有ai  个。

· 这个数不能有前导0,即012是不合法的。
有多组测试点，每组测试点现在给你a0～a9,   请你回答小B 的问题。

### 输入格式

第一行包含一个整数T。

接下来T 行，每行10个整数， a0～a9,       含义如题。

### 输出格式

输出T,     每行一个整数，表示答案。

### 输入输出样例 #1

#### 输入 #1

```
12
6 0 0 0 0 0 0 0 0 5
0 1 0 2 0 0 0 0 0 0
3 0 0 0 2 0 0 1 0 0
0 1 2 3 4 5 6 7 8 9
1 2 0 1 5 0 1 0 0 0
2 1 1 0 1 5 0 0 0 0
6 0 1 0 2 0 0 0 1 0
8 1 0 0 1 0 0 0 0 0
5 2 0 0 2 0 1 0 0 0
3 0 0 0 0 3 0 2 1 1
3 1 0 5 0 0 1 0 0 0
0 1 2 0 0 1 0 1 0 5
```

#### 输出 #1

```
-1
313
404070
123234345454565656767676787897979898989898989
1404143464
1505052545
-1
-1
1010404060
5050507879
1303030363
1929295979
```

### 说明/提示

###### 对于100%的数据，保证：T≤10,1≤n,ai≤                 10⁵,    其中$n=∑ai（0≤i≤9）$

| 测试点编号 | 数据范围 | 特殊性质 |
| :--------: | :------: | :------: |
|    1～2    |  n≤10  |    无    |
|    3～4    | n≤10³ |    无    |
|    5～6    |  无限制  |    A    |
|    7～8    |  无限制  |    B    |
|   9～10   |  无限制  |    无    |

A: 保证最多只有2个ai>0。

B:   保证最多只有3个ai>0。

## 【代码】T678583 A美丽数 (beauty)

```cpp
#include <bits/stdc++.h>
using namespace std;
int t,i,d,p,m,c,w,l,g,a[11],cnt[11],f;
string s;
bool j(int t,int b=-1){
    int mx=0;
    for(i=1;i<=10;i++){
        if(i-1==b) continue;
        if(cnt[i]>mx) mx=cnt[i];
    }
    return mx\*2<=t+1;
}
int main(){
    cin>>t;
    while(t--){
        for(i=1;i<=10;i++) cin>>a[i];
        m=c=0;l=-1;s="";
        for(i=1;i<=10;i++) m+=a[i];
        if(m==0){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) if(a[i]>c) c=a[i];
        if(c>(m+1)/2){cout<<-1<<"\\n";continue;}
        for(i=1;i<=10;i++) cnt[i]=a[i];
        for(p=0;p<m;p++){
            f=0;
            for(d=1;d<=10;d++){
                g=d-1;
                if(cnt[d]==0) continue;
                if(g==l) continue;
                if(p==0&&g==0) continue;
                cnt[d]--;
                if(j(m-p-1,g)){
                    s+=char('0'+g);
                    l=g;
                    f=1;
                    break;
                }
                cnt[d]++;
            }
            if(!f){cout<<-1<<"\\n";break;}
        }
        if(f) cout<<s<<"\\n";
    }
}
```

最后修改：2025 年 10 月 12 日