UVa12657（附对拍教程）

Posted on

UVa12657
代码
用两个数组来表示双向链表

题解：

数组Left[i]表示编号为i的箱子的左边箱子是几号，并编写一个辅助函数link来设置链接关系，对于模式4反转链表，因为修改数组的耗时太大，因此可以通过flag来标记，但是需要注意的是，后续的操作都要考虑这个flag的影响。

总结：

这道题给了实现双向链表的新思路，也就是使用两个数组，但显然这样时间上节省，空间上消耗很多，运算量也很大。

对拍教程：

很多时候，自认为正确的程序提交之后却是WA，但是给的测试数据太少，找不出错误在哪里，又嫌弃手写测试数据太慢，就可以利用操作系统的脚本功能，自动完成对比测试，当然首先你要有一个正确的程序，才能顺利的和自己的程序进行对比测试。

  • 先写一个测试数据生成器，生成符合条件的数据
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    /*题目需要的数据格式：

    */
    #include<iostream> 
    #include<stdlib.h>  // rand()和srand（）需要  
    #include<time.h>  //time（）需要
    using namespace std;

    int random(int m)
    {	
    	int n;
    	return n = rand() % m;
    }
    int main()
    {
    	srand(time(NULL)); // 初始化随机数种子  

    	int n, m;
    	for (int c = 1; c <= 10; c++)
    	{
    		//括号内的数字可以任意改
    		n = random(100) + 1;
    		m = random(100) + 1;
    		cout << n <<" "<< m<<endl;
    		for (int i = 0; i < m; i++)
    		{
    			int ch = random(4) + 1;
    			int b1 = random(n) + 1;
    			int b2 = random(n) + 1;
    			if (ch == 4)cout << ch << endl;
    			else {
    				//避免输出相等的x和y
    				if (b1 != b2) { cout << ch << " " << b1 << " " << b2 << endl; }
    				else i--;
    			}
    		}
    	}
    	return 0;
    }

    /*这是我用数据生成器生成的一组数据
    24 12
    1 13 6
    4
    1 20 7
    1 11 12
    3 22 8
    4
    3 10 8
    1 23 4
    2 20 18
    1 1 16
    3 4 19
    1 22 3
    */

并将数据生成器生成的数据保存在data.txt中

  • 将正确的代码输入生成一个ans.exe，自己写的代码输入生成my.exe，所有生成的文件都放在名为对拍的文件中，就不用文件定位了。

  • 打开记事本，输入以下脚本，并且保存为.bat格式

    1
    2
    3
    4
    5
    6
    :again   
    my < data.txt > my_output.txt  
    ans < data.txt > ans_output.txt  
    fc my_output.txt ans_output.txt  //对比两个输出文件
    if not errorlevel 1 goto again  
    pause

之后运行该脚本，就会自动生成两个输出文件ans_output.txt和my_output.txt