数独

题目描述

数独是根据 $9 \times 9$ 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫内的数字均含 $1 - 9$ ，不重复。每一道合格的数独谜题都有且仅有唯一答案，推理方法也以此为基础，任何无解或多解的题目都是不合格的。

芬兰一位数学家号称设计出全球最难的“数独游戏”，并刊登在报纸上，让大家去挑战。

这位数学家说，他相信只有“智慧最顶尖”的人才有可能破解这个“数独之谜”。

据介绍，目前数独游戏的难度的等级有一到五级，一是入门等级，五则比较难。不过这位数学家说，他所设计的数独游戏难度等级是十一，可以说是所以数独游戏中，难度最高的等级。他还表示，他目前还没遇到解不出来的数独游戏，因此他认为“最具挑战性”的数独游戏并没有出现。

输入格式

一个未填的数独。

输出格式

填好的数独。

样例 #1

样例输入 #1

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

样例输出 #1

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

提示

2022-04-17 @farteryhr 贡献了三组 hack 数据。加入了其中两组。第三组过强（来源：https://www.dcc.fc.up.pt/~acm/sudoku.pdf），放在下边供自测。

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

输出

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

[NOIP2009 提高组] 靶形数独

题目背景

此为远古题，不保证存在可以通过任意符合要求的输入数据的程序。

题目描述

小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向 Z 博士请教，Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。

靶形数独的方格同普通数独一样，在 $9$ 格宽且 $9$ 格高的大九宫格中有 $9$ 个 $3$ 格宽且 $3$ 格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入 $1$ 到 $9$ 的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）

上图具体的分值分布是：最里面一格（黄色区域）为 $10$ 分，黄色区域外面的一圈（红色区域）每个格子为 $9$ 分，再外面一圈（蓝色区域）每个格子为 $8$ 分，蓝色区域外面一圈（棕色区域）每个格子为 $7$ 分，最外面一圈（白色区域）每个格子为 $6$ 分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和

总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为 $2829$。游戏规定，将以总分数的高低决出胜负。

由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。

输入格式

一共 $9$ 行。每行 $9$ 个整数（每个数都在 $0 \sim 9$ 的范围内），表示一个尚未填满的数独方格，未填的空格用“$0$”表示。每两个数字之间用一个空格隔开。

输出格式

输出共 $1$ 行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

2829

样例 #2

样例输入 #2

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

样例输出 #2

2852

提示

数据规模与约定

• 对于 $40\%$ 的数据，数独中非 $0$ 数的个数不少于 $30$；
• 对于 $80\%$ 的数据，数独中非 $0$ 数的个数不少于 $26$；
• 对于 $100\%$ 的数据，数独中非 $0$ 数的个数不少于 $24$。

NOIP 2009 提高组 第三题

[蓝桥杯 2023 省 A] 买瓜

题目描述

小蓝正在一个瓜摊上买瓜。瓜摊上共有 $n$ 个瓜，每个瓜的重量为 $A_i$。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。

小蓝希望买到的瓜的重量的和恰好为 $m$。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 $m$ 的瓜。如果无论怎样小蓝都无法得到总重恰好为 $m$ 的瓜，请输出 $-1$。

输入格式

输入的第一行包含两个整数 $n,m$，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。

第二行包含 $n$ 个整数 $A_i$，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。

输出格式

输出一行包含一个整数表示答案。

样例 #1

样例输入 #1

3 10
1 3 13

样例输出 #1

2

提示

【评测用例规模与约定】

对于 $20 \%$ 的评测用例，$n \leq 10$;

对于 $60 \%$ 的评测用例，$n \leq 20$;

对于所有评测用例，$1 \leq n \leq 30$，$1 \leq A_i \leq 10^9$，$1 \leq m \leq 10^9$。

[ABC387C] Snake Numbers

题面翻译

题目描述

在 $10$ 以上（含）的正整数中，我们称一个数字为蛇数当且仅当其开头的位（首位）数字严格大于其他位数。例如， $31$ 和 $201$ 是蛇数，而 $35$ 和 $202$ 不是。

求 $L$ 以上 $R$ 以下的蛇数的个数。

输入格式

输入按照如下格式由标准输入给出。

$L$ $R$

输出格式

输出答案即可。

说明/提示

约定

• $10\leq L \leq R \leq 10^{18}$
• 输入均为整数

样例说明 1

$97$ 以上 $210$ 以下的蛇数有 $97,98,100,200,201,210$ 这 $6$ 个。

Translation by @$\varLambda\omicron\varrho\acute{\varepsilon}\nu\tau\zeta$.

题目描述

$10$ 以上の正整数のうち、十進数表記したときに先頭の桁（最も大きい位）の数字がそれ以外のどの桁の数字よりも真に大きくなるようなものを ヘビ数 とよびます。 例えば、$31$ や $201$ はヘビ数ですが、$35$ や $202$ はヘビ数ではありません。

$L$ 以上 $R$ 以下のヘビ数が何個あるか求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$L$ $R$

输出格式

答えを出力せよ。

样例 #1

样例输入 #1

97 210

样例输出 #1

6

样例 #2

样例输入 #2

1000 9999

样例输出 #2

2025

样例 #3

样例输入 #3

252509054433933519 760713016476190692

样例输出 #3

221852052834757

提示

制約

• $10\leq\ L\ \leq\ R\ \leq\ 10^{18}$
• 入力は全て整数

Sample Explanation 1

$97$ 以上 $210$ 以下のヘビ数は、$97,98,100,200,201,210$ の $6$ 個です。

[USACO09NOV] Lights G

题目背景

English Edition

题目描述

给出一张 $n$ 个点 $m$ 条边的无向图，每个点的初始状态都为 $0$。

你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。

你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。

输入格式

第一行两个整数 $n, m$。

之后 $m$ 行，每行两个整数 $a, b$，表示在点 $a, b$ 之间有一条边。

输出格式

一行一个整数，表示最少需要的操作次数。

本题保证有解。

样例 #1

样例输入 #1

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

样例输出 #1

3

提示

对于 $100\%$ 的数据，$1\le n\le35,1\le m\le595, 1\le a,b\le n$。保证没有重边和自环。