题目链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=132
题目类型: 搜索, 拓扑排序
题目:
In 1979, Dan Bricklin and Bob Frankston wrote VisiCalc, the first spreadsheet application. It became a huge success and, at that time, was the killer application for the Apple II computers. Today, spreadsheets
are found on most desktop computers.
The idea behind spreadsheets is very simple, though powerful. A spreadsheet consists of a table where each cell contains either a number or a formula. A formula can compute an expression that depends on the values
of other cells. Text and graphics can be added for presentation purposes.
You are to write a very simple spreadsheet application. Your program should accept several spreadsheets. Each cell of the spreadsheet contains either a numeric value (integers only) or a formula, which only support
sums. After having computed the values of all formulas, your program should output the resulting spreadsheet where all formulas have been replaced by their value.
Figure:Naming of the top left cells
题目大意翻译:
背景:1979年, Dan Bricklin和Bob Frankston写出了世界上第一款电子表格应用程序。它很快取得了巨大的成功,是当时苹果II型电脑的杀手级应用软件。今天,电子表格在大多数桌面计算机中广泛应用。
电子表格背后的思想虽然非常简单, 但是却非常强大。电子表格包含一个表,其中每个格子中会包含一个数字或公式。一个公式是一个表达式,这个表达式的值取决于其他格子的值。并且还可以添加文本和图形进行演示。
你的任务是写一个非常简单的电子表格应用程序。你的程序应该接受几个电子表格。电子表格中的每个单元(格子)会包含一个数值(只有整数)或一个公式, 这个公式只支持加法。 你的程序应该计算出所有表达式的值,计算完后输出表格的结果。
样例输入:
1
4 3
10 34 37 =A1+B1+C1
40 17 34 =A2+B2+C2
=A1+A2 =B1+B2 =C1+C2 =D1+D2
样例输出:
10 34 37 81
40 17 34 91
50 51 71 172
分析与总结:
第一次看到这题是,我被吓到了,的的确确真的被吓到了! 倒不是说这题有多么多么地难,而是题目所给的数据范围: 表格有999行,18278列。 如果开一个
二维数组的话,那么就要开个1千8百万的数组, 在当前几乎所有的OJ上都是直接Runtime Error的。也就是说,这题就算写出程序来,也不可能AC的。
于是便暂时放下了。 后来,队友告诉我被题目给坑了, 实际上只需要开个1000*1000的数组就足矣了。 我倒!!
既然数据量这么少,那么就好办了。 这题只需要直接用递归搜索即可。
题目比较麻烦的是数据的转换,就是形如A3,B4, AB22这些的转换,字母相当于是26进制的数,表示的是列数, 数字的是表示行。
用拓扑排序做时,需要做一个转换, 把二维数组转换成一位数组。当然,除了搜索的解法,还可以用拓扑排序来解。
递归搜索解法:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<cctype>
#include<string>
#define MAXN 1010
#define MARK -2147483645 //用来标记未得到结果的、是公式的格子
using namespace std;
int sheet[MAXN][MAXN];
int row, col;
string str;
string fm[MAXN][MAXN]; // 保存公式
int dfs(int r,int c){
if(sheet[r][c] != MARK) return sheet[r][c];
if(sheet[r][c] == MARK){
int m_row, m_col;
char temp[MAXN];
string str = fm[r][c];
sheet[r][c] = 0;
for(int i=1, pos=0; i<=str.size()+1; ++i){
if(str[i]=='+' || i==str.size()){
temp[pos] = '\0';
m_row=0, m_col=0;
int k;
for(k=0; k<strlen(temp) && !isdigit(temp[k]); ++k){
m_col = m_col*26+temp[k]-'A'+1;
}
for( ; k<strlen(temp); ++k){
m_row = m_row*10+temp[k]-'0';
}
pos = 0;
sheet[r][c] += dfs(m_row, m_col);
}
else{
temp[pos++] = str[i];
}
}
return sheet[r][c];
}
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
#endif
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d",&col, &row);
memset(sheet, 0, sizeof(sheet));
int val;
for(int i=1; i<=row; ++i){
for(int j=1; j<=col; ++j){
cin >> str;
if(str[0]=='='){
sheet[i][j] = MARK;
fm[i][j] = str;
}
else{
val = atoi(str.c_str());
sheet[i][j] = val;
}
}
}
for(int i=1; i<=row; ++i){
for(int j=1; j<=col; ++j) if(sheet[i][j]==MARK){
dfs(i,j);
}
}
for(int i=1; i<=row; ++i){
printf("%d",sheet[i][1]);
for(int j=2; j<=col; ++j){
printf(" %d",sheet[i][j]);
}
printf("\n");
}
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
google-spreadsheet-javascript, 从google电子表格读取数据 Google-Spreadsheet-Javascript这是一个简单的jQuery插件类,允许JavaScript应用程序从Google电子表格中提取数据。有关最基本的用法( 请看这里的行动。),...
资源分类:Python库 所属语言:Python 资源全名:python-barcode-spreadSheet-1.1.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
电子表格 基于WebJavaScript电子表格文件恩CDN < link rel =" stylesheet " href =" ... x_spreadsheet ( '#xspreadsheet' ) ;</ script >NP
import Spreadsheet from "react-spreadsheet" ; const data = [ [ { value : "Vanilla" } , { value : "Chocolate" } ] , [ { value : "Strawberry" } , { value : "Cookies" } ] , ] ; const MyComponent = ( ) ...
前端好用的web-excel,轻巧灵活,支持多个浏览器版本。
jupyterlab-spreadsheet支持 XLS、XLSX、ODS 和 CSV 文件,并允许进行基本格式设置(例如单元格合并)。 该插件处于 alpha 阶段,不支持工作簿的所有功能(高级格式、公式等)。 有关详细的发行说明,请参阅。入门...
Laravel开发-google-spreadsheet-exporter laravel-artisan命令从谷歌电子表格生成laravel语言文件
Laravel开发-laravel-lang-google-spreadsheet-importer laravel-artisan命令从谷歌电子表格生成laravel语言文件
formula one 控件的升级版说明文档, 可嵌入类中的excel控件
matlab开发-Spreadsheet。演示Microsoft Office电子表格ActiveX对象。
这是一个建立在 Web(es6) 画布上的轻量级 Excel 开发库。 这些参数在第一次实例化时加载,也可以稍后设置,但建议提前修改并加载您需要更改的更改。 可以调整默认显示的列数len,AZ,每列默认宽度,左序列列默认宽度...
DevExpress VCL - Spreadsheet Overview [720p]
关于Spreadsheet 对象的方法、事件、属性的东东,在网上搜集的,txt格式的方便大家阅读,虽然内容不是很全,但还是比较有用的,希望大家喜欢。
cat input.csv | secure-spreadsheet --password secret > output.xlsx 保护现有的XLSX cat input.xlsx | secure-spreadsheet --password secret --input-format xlsx > output.xlsx 语言能力 许多语言没有创建...
资源来自pypi官网。 资源全名:portable-spreadsheet-2.1.5.tar.gz
matlab开发-Spreadsheet2Structure.zip.zip
Vue电子表格 项目设置 npm install 编译和热重装以进行开发 npm run dev 怎么运行的: 基本用法 您可以使用键盘上的箭头键来选择一个单元格,也可以直接单击它。 按空格键或双击一个单元格进行编辑。...
matlab开发-Spreadsheet2Structure。读取电子表格并将其转换为字段名取自H列的结构
xspreadsheet 是一款基于javascript开发的,简单的,易用的在线表格插件
parse-ft-spreadsheet-key 简单的功能,可以从FT Google表格URL或Bertha URL解析电子表格密钥。 安装 前端 $ bower install --save parse-ft-spreadsheet-key < script src =" bower_components/parse-ft-...