详解OJ(Online Judge)中PHP代码的提交方法及要点【举例:ZOJ 1001 (A + B Problem)】
OJ中针对与PHP的测试用例的输入方式是文件读取,输出是echo或print,注意加上"\n"表示换行... 整体而言,OJ中的PHP输入输出规范和C语言差不多,区别在用:PHP可以不声明变量类型,另外PHP中自定义的抽象数据结构ADT用class实现,而C中用struct.
STDIN是OJ中的PHP环境提供的常量,STDIN等价于fopen("php://stdin","r"));
PHP中的 fscanf($fd, "%d %d %d", $var1, $var2, $varN)==N 用来从文件中按行读取数据。
ZOJ 1001
提交网址: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1
Input
The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line.Output
For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input.Sample Input
1 5
Sample Output
6
Hint
Use + operator试着提交了几次代码,只有下面3种可以AC:
<?php
$fd = STDIN; // STDIN是oj提供的常量,等价于 fopen("php://stdin","r"));
// $fd=fopen('inputfileName','+r');
while(fscanf($fd, "%d %d", $a, $b)==2)
echo ($a + $b)."\n";
?>
将测试的输入放入inputfileName(有无文件扩展名皆可)中,使用注释中的$fd=fopen('inputfileName','+r'); 代替 $fd = STDIN;,即可进行 本地测试 。
<?php
while(fscanf(STDIN, "%d %d", $a, $b) == 2)
echo ($a + $b)."\n"; // '\n' 或 PHP_EOL常量均不允许使用
?>
或
<?php
while(fscanf(STDIN, "%d %d", $a, $b) == 2)
print ($a + $b)."\n";
*推荐使用第一种写法,本地测试略方便,上文已提过...
再附上ZOJ 1088相应的已AC代码:
<?php
function judge($m, $n)
{
$from = 0;
for($i = 2; $i < $n; $i++)
$from = ($from + $m)%($i);
if($from + 1 == 1) return 1;
else return 0;
}
$fd = STDIN; // STDIN是oj提供的常量,等价于 fopen("php://stdin","r"));
while(fscanf($fd, "%d", $n)==1 && $n!=0)
{
$m = 1;
while(!judge($m, $n))
{
++$m;
}
echo $m."\n";
}
本地测试 代码1(独立文件保存测试输入,fopen):
在php文件的同一目录下创建文件stdin,把测试数据放进去~
<?php
// To-Do: 约瑟夫环问题
$fd = fopen("stdin", "r");
// $fd = STDIN;
function judge($m, $n)
{
$from = 0;
for($i = 2; $i < $n; $i++)
$from = ($from + $m)%($i);
if($from + 1 == 1) return 1;
else return 0;
}
while(fscanf($fd,"%d", $n)==1 && $n!=0)
{
$m = 1;
while(!judge($m, $n))
{
++$m;
}
echo $m."\n";
}
本地测试 代码2(测试数据放在程序代码中, fwrite,fopen,array, 支持批量测试)
<?php
// To-Do: 约瑟夫环问题
$inFile="./stdin.txt";
$fd0 = fopen($inFile, "w+");
$data = array(
"3
4
5
6
7
8
9
10
11
12
0"
);
fwrite($fd0, $data[0]); // 将测试数据放进$data中
fclose($fd0);
$fd = fopen($inFile, "r");
// $fd = STDIN;
function judge($m, $n)
{
$from = 0;
for($i = 2; $i < $n; $i++)
$from = ($from + $m)%($i);
if($from + 1 == 1) return 1;
else return 0;
}
while(fscanf($fd,"%d", $n)==1 && $n!=0)
{
$m = 1;
while(!judge($m, $n))
{
++$m;
}
echo $m."\n";
}
本地测试 代码3(测试数据放在程序代码中, file_put_contents,fopen,array, 更简洁,不过file_put_contents( )只能向已经存在的文件中写入数据)
<?php
// To-Do: 约瑟夫环问题
$inFile="./stdin.txt";
$data = array(
"3
4
5
6
7
8
9
10
11
12
0"
);
file_put_contents($inFile, $data[0]);
$fd = fopen($inFile, "r");
// $fd = STDIN;
function judge($m, $n)
{
$from = 0;
for($i = 2; $i < $n; $i++)
$from = ($from + $m)%($i);
if($from + 1 == 1) return 1;
else return 0;
}
while(fscanf($fd,"%d", $n)==1 && $n!=0)
{
$m = 1;
while(!judge($m, $n))
{
++$m;
}
echo $m."\n";
}
几点发现:
1. OJ中PHP的标准输入输出与C的fscanf基本一致;
2. 换行,要求使用"\n",如果用'\n' 或 PHP_EOL常量替代会提示Non-zero Exit Code;
3. PHP文件最后的结束符 ?> 可以省略,当然也可写上...
PHP标准库(SPL)中提供的数据结构 PHP version >= 5.3
目录列表
- SplDoublyLinkedList
- SplStack
- SplQueue
- SplHeap
- SplMaxHeap
- SplMinHeap
- SplPriorityQueue
- SplFixedArray
- SplObjectStorage
SPL提供了一组标准数据结构. They are grouped here by their underlying implementation which usually defines their general field of application.
双向链表(DoublyLinkedList)
A Doubly Linked List (DLL) is a list of nodes linked in both directions to each others. Iterator's operations, access to both ends, addition or removal of nodes have a cost of O(1) when the underlying structure is a DLL. It hence provides a decent implementation for stacks and queues.
堆(stack)
Heaps are tree-like structures that follow the heap-property: each node is greater than or equal to its children, when compared using the implemented compare method which is global to the heap.
数组(array)
Arrays are structures that store the data in a continuous way, accessible via indexes. Don't confuse them with PHP arrays: PHP arrays are in fact implemented as ordered hashtables.
映射(map)
A map is a datastructure holding key-value pairs. PHP arrays can be seen as maps from integers/strings to values. SPL provides a map from objects to data. This map can also be used as an object set.
其他
下面举一个splheap堆的实例:
<?php
class MySimpleHeap extends SplHeap
{
//compare()方法用来比较两个元素的大小,决定他们在堆中的位置
public function compare( $value1, $value2 ) {
return ( $value1 - $value2 );
}
}
$obj = new MySimpleHeap();
$obj->insert( 4 );
$obj->insert( 8 );
$obj->insert( 1 );
$obj->insert( 0 );
echo $obj->top(); //8
echo $obj->count(); //4
foreach($obj as $number)
echo $number."\n";
此段代码执行结果如下:
相关链接:
http://acm.zju.edu.cn/onlinejudge/faq.do#sample
New SPL Features in PHP 5.3 http://matthewturland.com/2010/05/20/new-spl-features-in-php-5-3/
SPL 数据结构 http://php.net/manual/zh/spl.datastructures.php