\(\mathcal{Description}\)

Link.

数轴从 \(1\sim 2n\) 的整点上有 \(n\) 个闭区间。你只知道每个区间的部分信息（可能不知道左或右端点，或者都不知道），问是否存在满足已知信息的 \(n\) 个区间，满足：

每个整点是恰好一个区间的端点。
所有包含同一个整点的区间长度相等。

输入信息可能不合法。

\(n\le100\)。

\(\mathcal{Solution}\)

老细节题了。（

考虑数轴上连续的一段区间 \([l,r]\)，记 \(L=r-l+1\)，若该区间内能够满足条件，则显然有：

\(2|L\)。
\([i,i+\frac{L}2]\) 可以存在于区间集合中。

记 \(f(i)\) 表示 \(1\sim i\) 能否合法，\(\mathcal O(n^3)\) 暴力转移即可。

但这个不是难点，if-else 才是难点 qwq。

输入可能多点重合，判否。
若有区间 \([l,?]\) 和 \([?,r]\)，注意不能让 \(l\) 和 \(r\) 组成 \([l,r]\)。

对于第二点，一组 CF 上的 hack 数据为：

2

1 -1

-1 3

answer: No

多堆几个 if-else 就 A 啦！（

\(\mathcal{Code}\)

/* Clearink */

#include <cstdio>

#include <cstdlib>

#include <assert.h>

const int MAXN = 200;

int n, match[MAXN + 5];

bool f[MAXN + 5], vis[MAXN + 5];

inline bool check ( const int l, const int r ) {

	int stp = r - l + 1 >> 1; // i -> i + stp.

	for ( int i = l, j; ( j = i + stp ) <= r; ++ i ) {

		bool acci = 1 <= match[i] && match[i] <= n << 1;

		bool accj = 1 <= match[j] && match[j] <= n << 1;

		if ( match[i] == -1 || ( acci  && match[i] ^ j )

		|| match[j] == ( n << 1 | 1 ) || ( accj && match[j] ^ i )

		|| ( !acci && !accj && match[i] && match[j] ) ) {

			return false;

		}

	}

	return true;

}

int main () {

	scanf ( "%d", &n );

	for ( int i = 1, a, b; i <= n; ++ i ) {

		scanf ( "%d %d", &a, &b );

		if ( ~a && ~b && a >= b ) return puts ( "No" ), 0;

		if ( ~a && ~b ) match[a] = b, match[b] = a;

		else if ( ~a ) match[a] = n << 1 | 1;

		else if ( ~b ) match[b] = -1;

		if ( ~a ) {

			if ( vis[a] ) return puts ( "No" ), 0;

			vis[a] = true;

		}

		if ( ~b ) {

			if ( vis[b] ) return puts ( "No" ), 0;

			vis[b] = true;

		}

	}

	f[0] = true;

	for ( int i = 2; i <= n << 1; i += 2 ) {

		for ( int j = 0; j < i && !f[i]; j += 2 ) {

			f[i] = f[j] && check ( j + 1, i );

		}

	}

	puts ( f[n << 1] ? "Yes" : "No" );

	return 0;

}

巴特西

Solution -「ARC 104C」Fair Elevator

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章