| 题目名称 | 912. [IOI 1997][USACO]字符识别 |
|---|---|
| 输入输出 | charrec1.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 9 |
| 题目来源 |
 cstdio
于2013-11-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：35， 通过率：22.86% | ||||
 mildark |
100 | 0.193 s | 3.34 MiB | C++ |
|
cstdio |
100 | 0.201 s | 2.97 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.619 s | 13.74 MiB | C++ |
 Arrow |
100 | 0.675 s | 0.39 MiB | C++ |
 KZNS |
100 | 2.110 s | 0.32 MiB | C++ |
 Imone NOI2018Au |
100 | 2.298 s | 0.36 MiB | C++ |
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 3.607 s | 0.34 MiB | C++ |
|
mikumikumi |
100 | 3.870 s | 0.39 MiB | C++ |
|
mildark |
88 | 0.333 s | 3.04 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
88 | 3.166 s | 0.26 MiB | C++ |
| 关于 字符识别 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
attention！！
这个“空格字符_” 不是某种字符图案的新定义 它真的是24K纯空格！！ 一定要 输 出 空 格 Arrow
2017-10-12 18:14
4楼
| ||||
|
题目描述有问题，行被复制时 和上一行不一样！！！
| ||||
|
果然string的常数巨大
| ||||
|
这道题有力地证明了验证码的可靠性……
由于COGS上程序只能打开.in文件，故将font.in的内容附在所有.in文件的开头，除此之外输入输出格式与原题一样 网上下到的数据中，输出文件是意义不明的数而非识别出的字符串，故用标程重新造了输出文件，符合nocow上C++标程的第2,3,4个程序 我的DP顺序是：19->20->21，字符_abcd……不知道会不会有影响 | ||||
- 最多有一行被可能被复制了（一定接在原来那一行的下面）
- 最多有一行可能丢失了
- 有些“0”可能被改成“1”
- 有些“1”可能被改成“0”
【题目描述】
这个问题需要你写一个程序完成字符识别的任务。
每个完整的字符图案有 20 行，20 位。每个位是“0”或“1”。图 1a 是输入文件中的符号图案的一部分。
输入文件charrec1.in的前541行包含了27个字符图案的信息，以这样的顺序记录：
_abcdefghijklmnopqrstuvwxyz
其中 _ 表示空格字符。每个完整字符长 20 行。
输入文件的其余部分包含一个或多个可能损坏的字符图案。一个字符图案可能以这些方式被损坏。
不会有任何一个字符图案既多余了一行并且又丢失了一行。
被复制的那一行中，原来的行和多余的行可能都损坏了，而且损坏的部分可能并不相同。
写一个程序，使用输入文件提供的字体，在输入文件提供的图象中识别出一个或多个的字符序列。
使用提供的字体图象来识别字符的时候，要找出最佳的多余行或遗漏行，使找出的所有“0”和“1”的变化数量最小。你必须确定和输入序列最接近的字符序列（就是损坏数据最少的那一个）。每个测试数据有唯一的最优解。
INPUT FORMAT (both input files)
输入文件charrec1.in的第一行是一个正整数N1，描述了字体文件的行数（在所有的数据中N1=540）
输入文件charrec1.in的第2~第541行是由0和1组成的字体文件，形如下图所示
(位1)(位2)(位3) ... (位20)
(位1)(位2)(位3) ... (位20)
...
输入文件charrec1.in的第542行是一个正整数N2，描述了要求识别的文件行数（19<N2<1200）
输入文件charrec1.in的第543~542+N2行是由0和1组成的文本文件，表示要求识别的文本，形式与字体文件相同。
字体文件和文本文件的每行有20位的宽度。在0和1之间没有空格分开。
OUTPUT FORMAT
你的程序必须建立一个输出文件，包含一个识别出来的字符串。它的格式是一个单行的 ASCII 文本。输出文件中不应该包含任何分隔符。
SAMPLE INPUT (file charrec1.in)
|
例：charrec1.in 的开头（不完全的），有“空格”和“a” |
例：charrec1.in 的其余部分显示了一个损坏的“a” |
|
charrec1.in的前若干行(部分) |
charrec1.in的其余部分 |
|
540 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00000111111011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00000001000001110000 00001111111111110000 00001111111111110000 00001111111111000000 00001000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 |
19 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00100111011011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00001111011111110000 00001111111111110000 00001111111111000000 00001000010000000000 00000000000000000000 00000000000001000000 00000000000000000000 00000000000000000000 |
| 图 1a | 图 1b |
SAMPLE OUTPUT (file charrec1.out)
a
提示
1.少的一行不计算在变化数量内
2.对于多的一行，若第i+1行是第i行的重复，那么应计算第i行的变化数量而忽略第i+1行
3.原题称改变量不会超过30%（否则输出一个问号），但这个说法是错误的。你的程序不应在任何情况下输出问号，也不必判断改变量是否大于30%
【题目来源】
USACO/charrec(译 by Felicia Crazy)