P6161.md

[Cnoi2020]高维

题目描述

Cirno 捕获了一只 $n$ 维蚂蚁，它想从 $S(0,0,...,0)$ 爬到 $T(1,1,...,1)$ 。

被封闭在这个 $1\times1\times...\times1$ 的方格中，蚂蚁每一步只能爬向一个坐标相邻的点。

现在 Cirno 想考考你蚂蚁最多能找到多少条从 $S$ 到 $T$ 的路径两两没有交点( 除 $S$, $T$ )。

并要求你构造这样一组路径。

输入格式

一行，一个整数 $n$ 。

输出格式

第一行，一个整数 $t$，表示最多的路径数。

以下 $t$ 行，每行一条合法路径。

合法路径表示方式 :

$S$ [空格] $P_1$ [空格] $P_2$ [空格] ... [空格] $T$

其中 $P_i$ 是一个二进制压缩的 $01$ 串 表示一个 $n$ 维坐标。

请不要输出多余的空格。

样例 #1

样例输入 #1

2

样例输出 #1

2
0 1 3
0 2 3

提示

「本题使用 Special Judge」

Sample1解释

第 $1$ 条路径：$(0,0) \rightarrow (0,1) \rightarrow (1,1)$

第 $2$ 条路径：$(0,0) \rightarrow (1,0) \rightarrow (1,1)$

二者除了 $S$ 与 $T$ 无交点。

数据范围约定

「本题不采用捆绑测试，数据有梯度」

对于 100% 的数据 $3 \le n \le 60$。

后置代码片段

• 二进制压位函数

/**
 * For only cpp11, cpp14, cpp17, cpp20.
 *
 * @param: __s : The binary high-dimension position inputed.
 * @return: Standard output format( U64 ).
**/

unsigned long long zip( std::string __s ) 
  { unsigned long long __r = 0;
    for( auto __c : __s ) 
      { ( __r <<= 1ull ) |= ( __c - 0x30 ); }
    return __r; }

• SPJ代码

//SPJ
#include "testlib.h"
#include<bits/stdc++.h>

typedef unsigned long long ULL;
typedef std::vector<std::string> SEQ;
typedef std::string STR;

SEQ split( std::string _par, char _sgn )
  { SEQ _rat = SEQ();
	STR _rem = STR();
	
    for( char __c : _par )
      { if( __c = _sgn ) _rat.push_back( _rem ), _rem = "";
	    else _rem += __c; }
	
	if( _rem != "" ) _rat.push_back( _rem );
	
	return _rat; }

ULL to_ULL( std::string _str ) 
  { ULL _rat = 0;
	
	for( char __c : _str )
	  { ( _rat *= 10ull ) += (ULL)( __c - '0' ); }
	
	return _rat; }

bool isPw2( ULL x )
  { return !( x & (x - 1ull) ); }

std::map<ULL, bool> MP;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);
	
	ULL n = inf.readLong();
	ULL S = 0, T = (1ull << n) - 1ull;
	ULL N = ouf.readLong();
	
	if( N != n ) quitf( _wa, "Count paths wrongly." );
	
	ouf.readEoln();
	
    while( n -- ) {
    	std::string path = ouf.readLine();
    
    	ULL _lst = 0;
    	
    	for( auto N : split( path, " " ) )
    	  { ULL _now = to_ULL( N );
    		if( _now != S and _now != T and MP[_now] ) 
			  { quitf( _wa, "Paths crossing" ); }
    	    if( !isPw2( _now ^ _lst ) ) 
			  { quitf( _wa, "Wrong path format" ); }
    	    _lst = _now; MP[_now] = true; }
    	
    	if( _lst != T ) quitf( _wa, "Wrong path ending" );
	}
	
	quitf( _ok, "Accepted" );
	
    return 0;
}