Content Preview: rss
7 days ago
好长时间没做题了，拿这个来练练手... 时限居然有 5s ，看来得做好极限优化的准备。 开始想的是用一个 int [4][4][5] 数组记录每格周围有同种羊的格数，然后 dfs 时每放一格就改变周围 8 格的数字。运行下貌似很慢，在我的机器上都 10s 多。 于是想到以前写过五子棋的位运算优化，这题一共 16 格，每格数字最多不大于 4，因此可用一个 64位 unsigned int 放下，每格数字只用 4 bit 表示即可。位运算的优点是可同时操作 64 位，这样只用一句便可同时改变周围 8 格的数据。 可惜在我的机器上依然跑到了 6s，考虑到还开着耗 CPU 的 APE 在听，正常应该能跑进 5s 吧。结果提交一看在评测机上只用了 2.1s 。。。哦 ... 咱的机器看来该淘汰了 = = 按 6:2 来算不加位运算优化的估计也能进 5s 了... TASK: wissqu LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [2.117 secs, 2940 KB] All tests OK. C++语言 : USACO 5.2.3 wissqu #include<cstdlib> #include<fstream> #include<iterator> #include<algorithm> using namespace std ; class farm { int cnt , cowat [ 16 ], cowleft [ 5 ]; bool nochange [ 16 ]; unsigned long long ajtcnt [ 5 ]; const unsigned long long mask , maskl , maskr ; pair < int , int > putorder [ 16 ]; ...
21 days ago
C++ : while ( step > 0.02 ){ for (;;){ if ( x + step <= 100.0 && ( ttlen = ttl ( x + step , y )) < minlength ){ minlength = ttlen ; x += step ; } else if ( x - step >= 0.0 && ( ttlen = ttl ( x - step , y )) < minlength ){ minlength = ttlen ; x -= step ; } else if ( y + step <= 100.0 && ( ttlen = ttl ( x , y + step )) < minlength ){ minlength = ttlen ; y += step ; } else if ( y - step >= 0.0 && ( ttlen = ttl ( x , y - step )) < minlength ){ minlength = ttlen ; y -= step ; } else break ; } step /= 2.0 ; } 在 x-y 平面上寻找一个对 ttl 函数的极值点。先用 step ...
34 days ago
继续关注文件读写...这次测试写的效率 其实关于这个问题的讨论似乎总会以类似语言信仰问题而告终，再加 C++ IO 库的复杂性，很多半调子 C++ 程序员总会出现各种误用，反过来却作为攻击 C++ IO 效率低的凭证。 比如经常有人边在输出时大量使用类似 fout<<...<<endl; 的语句边嚷嚷着写文件速度超慢的，只能说这些人根本不知道自己写的句子都做了什么... 所以说在评价任何东西之前先要做到最起码的了解 咱也算是大致研究过 C++ IO stream 各方面的内容，虽然不能说完全掌握仍在学习中，但自认为还是可以写点东西的。 总之还是用数据说话。 平台 XPsp3 + VC2008 Express Edition SP1 + STLport / MinGW(GCC4.4.0) 实验内容： 共做了三种类型写入的比较，每种类型采用几种不同方法实现： 1. 纯字节流写入 (1) C fputs() (2) C fprintf() (3) C++ ofstream<< (4) C++ ofstream.rdbuf()->sputn() 2. 宽字符流通过转码写入 (1) C++ locale + wofstream<< (2) C++ codecvt<> facet + ofstream.rdbuf()->sputn() (3) WinAPI WideCharToMultiByte() + ofstream<< 3. 格式化写入 (一个 int 一个 double + 一个字符串) (1) C fprintf() (2) C++ ofstream<< (3) C++ ostream.rdbuf()->sputn() sputc() + num_put<> facet 前两类比较时写入的内容是完全一致的，也可以横向做下参照。 结果：(由于和硬盘寻道时间等也有关系，尽量多次测试取受影响最小的值) 以 C Runtime library 的 fputs 函数所用时间为 ...
40 days ago
于是连 python 也成了关键词 www.python.org/download 哪天你把 c, java, php, 或者干脆 linux windows 都封了算了。。。
58 days ago
http://dantvt.is-programmer.com/posts/11949.html 很多时候较大数据量的文件 IO 总是成为瓶颈，为了提高效率，有时想要先将文件大块大块的读入再行处理。下面分析两种惯常的处理手法。 1. 将文件一次性读入 string 中。 貌似 std::getline 、 istream::getline 或是 operator<< operator>> 等都不提供一次读到文件结尾的机制，只有 istreambuf_iterator 可以做到： ifstream in ( "input.txt" ) ; string instr ( ( istreambuf_iterator<char> ( in ) ) , istreambuf_iterator<char> ( ) ) ; string 的构造函数前一个参数要多加一层 () 以免编译器误认为是函数声明 = = ... 这样读入 string 会随着内容动态增长，空间不足时会触发额外的 realloc 及 copy 操作，为提高效率有必要预分配足够的空间： ifstream in ( "input.txt" ) ; in. seekg ( 0 , ios:: end ) ; streampos len = in. tellg ( ) ; in. seekg ( 0 , ios:: beg ) ; string instr; instr. reserve ( len ) ; instr. assign ( istreambuf_iterator<char> ( in ) , istreambuf_iterator<char> ( ) ) ; 2. 将文件一次性读入 stringstream 中。 filebuf 和 stringbuf 无法直接通过 rdbuf() 重定向，因此从 filebuf 到 stringbuf 需要一次 copy 操作。最简单的方法是直接复制整个 streambuf ： ifstream in ( ...
