Codeforces Round 1699 解题报告

发布于 # algorithm

考试链接： https://codeforces.com/contest/1699

考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了，我大受震撼。

A The Third Three Number Problem

求能否找到任意三个数字 a,b,ca,b,c 使得 (a⊕b)+(a⊕c)+(b⊕c)=n(a \oplus b) + (a \oplus c) + (b \oplus c) = n 。 容易发现奇数根本不可能，偶数随便构造。

B Almost Ternary Matrix

给表格染色。使得对于任意一个格子，有且只有两个相邻格子和这个颜色不同。 以 2x2 为一个单位，交叉构造即可。

C The Third Problem

给定一个 0⋯n−10 \cdots n - 1 的排列 aa ，求有多少个排序 bb 满足 ∀i,j\forall i,j ，有 mexa(i,j)=mexb(i,j)mex_a(i,j) = mex_b(i,j) ，模 109+710^9 +7 。 n≤105n \leq 10^5

思路

容易注意到 00 是固定的，考虑从 0 出发维护当前的满足 mex=imex = i 的最小区间。 如果在移动 ii 的时候，区间没有变大，这 ii 可以在这个区间的任意位置。 否则这个数字的位置就是确定的。 O(n)O(n) 处理即可。

Code

/*
 * c.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; isdigit(ch) == 0; ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}
template <class T>
T pow( T a, int p ) {
	T res = 1;
	while( p ) {
		if( p & 1 )
			res = res * a;
		a = a * a;
		p >>= 1;
	}
	return res;
}/*}}}*/

const int mod = 1e9 + 7;

struct ModInt {/*{{{*/
	int cur;
	ModInt( ll _cur = 0 ) { cur = ( ( ( _cur % mod ) + mod ) % mod ); }

	inline ModInt operator+ ( const ModInt &b ) const { return ( cur + b.cur ) % mod; }
	inline ModInt operator- ( const ModInt &b ) const { return ( ( ( cur - b.cur ) % mod ) + mod ) % mod; }
	inline ModInt operator* ( const ModInt &b ) const { return ( 1LL * cur * b.cur ) % mod; }
	inline ModInt operator/ ( const ModInt &b ) const { return ( 1LL * cur * pow( b, mod - 2 ).cur ) % mod; }

	inline void operator+= ( const ModInt &b ) { (*this) = (*this) + b; }
	inline void operator-= ( const ModInt &b ) { (*this) = (*this) - b; }
	inline void operator*= ( const ModInt &b ) { (*this) = (*this) * b; }
	inline void operator/= ( const ModInt &b ) { (*this) = (*this) / b; }

	inline void output( const char end = '\n' ) { printf( "%d%c", cur, end ); }
};/*}}}*/

const int N = 1e5 + 1e4;

int a[N], pos[N];
ModInt fac[N];

int main() {
	int T = read<int>();

	fac[0] = 1;
	for( int i = 1; i < N; i ++ )
		fac[i] = fac[ i - 1 ] * i;

	while( T -- ) {
		cint n = read<int>();
		for( int i = 1; i <= n; i ++ ) {
			a[i] = read<int>();
			pos[ a[i] ] = i;
		}

		ModInt res = 1;
		int left = pos[0], rig = pos[0];
		for( int i = 1; i < n; i ++ ) {
			cint p = pos[i];
			if( left <= p && p <= rig ) {
				res *= ( rig - left + 1 - i );
			}
			else {
				chk_Min( left, p );
				chk_Max( rig, p );
			}
		}

		res.output();
	}
}

D Almost Triple Deletions

给定序列 aa ，每次操作可以选择 i,i<∣a∣i, i < |a| 且 ai≠ai+1a_i \neq a_{i+1} 然后删除这两个数字。 容易注意到最后只能剩下空串或者所有元素相同的序列，求最长剩余序列长度。 ∣a∣≤5000,1≤ai≤n|a| \leq 5000, 1 \leq a_i \leq n

做法

考场上的时候糊了个 dp，下了冷静思考了一下发现情况讨论的不够，而且讨论全了会好写很多，很难绷得住。 令 fif_i 表示当前 \[1,i\] 能有的最长剩余序列长度。 容易构造转移 fi=max⁡j<i,ai=aj,fj>0,g(i,j)=1fj−1+1f_i = \max_{ j < i, a_i = a_j, f_j > 0, g(i,j)=1} f_{j-1} + 1 其中 g(i,j)g(i,j) 表示能不能将子串 \[i,j\] 删光。 现在考虑处理 gg 。 容易发现一个序列可以删光当且仅当序列中出现次数最多的元素不占多数，这个是可以 O(n2)O(n^2) 处理的。 转移方程也可以 O(n2)O(n^2) 处理，问题结束。

Code

/*
 * d.cpp
 * Copyright (C) 2022 Woshiluo Luo <[email protected]>
 *
 * 「Two roads diverged in a wood,and I—
 * I took the one less traveled by,
 * And that has made all the difference.」
 *
 * Distributed under terms of the GNU AGPLv3+ license.
 */

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>

typedef const int cint;
typedef long long ll;
typedef unsigned long long ull;

inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/
template <class T>
T Max( T a, T b ) { return a > b? a: b; }
template <class T>
T Min( T a, T b ) { return a < b? a: b; }
template <class T>
void chk_Max( T &a, T b ) { if( b > a ) a = b; }
template <class T>
void chk_Min( T &a, T b ) { if( b < a ) a = b; }
template <typename T>
T read() {
	T sum = 0, fl = 1;
	char ch = getchar();
	for (; isdigit(ch) == 0; ch = getchar())
		if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
	return sum * fl;
}
template <class T>
T pow( T a, int p ) {
	T res = 1;
	while( p ) {
		if( p & 1 )
			res = res * a;
		a = a * a;
		p >>= 1;
	}
	return res;
}/*}}}*/

const int N = 5100;

int a[N];
int g[N];
bool f[N][N];

int main() {
#ifdef woshiluo
	freopen( "d.in", "r", stdin );
	freopen( "d.out", "w", stdout );
#endif
	int T = read<int>();
	while( T -- ) {
		cint n = read<int>();

		for( int i = 1; i <= n; i ++ ) {
			g[i] = 0;
			for( int j = 1; j <= n; j ++ ) {
				f[i][j] = false;
			}
		}

		for( int i = 1; i <= n; i ++ )
			a[i] = read<int>();

		for( int i = 1; i <= n; i ++ ) {
			static int pool[N];
			for( int j = 1; j <= n; j ++ )
				pool[j] = 0;

			int max = 0;
			auto len = []( cint left, cint rig ) { return rig - left + 1; };
			for( int j = i; j <= n; j ++ ) {
				pool[ a[j] ] ++;
				chk_Max( max, pool[ a[j] ] );
				if( max <= ( len( i, j ) >> 1 ) && ( len( i, j ) % 2 == 0 ) )
					f[i][j] = true;
				else
					f[i][j] = false;
			}
		}

		int res = 0;
		f[1][0] = true;
		for( int i = 1; i <= n; i ++ ) {
			g[i] = f[1][ i - 1 ];
			for( int j = 1; j < i; j ++ ) {
				if( g[j] > 0 && a[i] == a[j] && ( ( j + 1 > i - 1 ) || f[ j + 1 ][ i - 1 ] ) )
					chk_Max( g[i], g[j] + 1 );
			}
			if( i == n || f[ i + 1 ][n] )
				chk_Max( res, g[i] );
		}
		printf( "%d\n", res );
	}
}

E Three Days Grace

给定可重集合 ss ，定义一次操作是：

  1. 选定一个数字 x∈sx \in s 。
  2. 选择任意 p,qp,q 满足 pq=x,p,q>1pq = x, p,q > 1 。
  3. 在 ss 中删除 xx ，插入 p,qp,q 。

求在若干次操作后，最小化 max⁡s−min⁡s\max s - \min s 。 1≤n≤106,1≤m≤5×106,1≤si≤m1 \leq n \leq 10^6, 1 \leq m \leq 5 \times 10^6, 1 \leq s_i \leq m

做法

容易发现这个集合可重不可重并不重要，那就当不可重的吧。 肯定是固定一个值然后最值化另一个值。 考虑现在确定 ii 是集合最小值，考虑定义 fjf_j 表示在当前限制下，如果有 fjf_j ，最大值最小是多少。 如果现在已经求出在 i+1i+1 是最小值时的 ff ，容易得出转移方程

f_{ki} = \min( f_{ki}, \max( f_{k}, i ) ) ( k \in N^{+}, ki \leq m) $$ 如果 $f_j$ 不能满足当前限制，设为 $m$ 即可。 这样如果在所有 $f_i$ 都满足限制的情况下，这个限制下的答案就是 $\max{f} - i$ 。 从大到小枚举 $i$ ，每次更新答案。 ### Code ``` /* * e.cpp * Copyright (C) 2022 Woshiluo Luo <[email protected]> * * 「Two roads diverged in a wood,and I— * I took the one less traveled by, * And that has made all the difference.」 * * Distributed under terms of the GNU AGPLv3+ license. */ #include <cstdio> #include <cstdlib> #include <cstring> #include <set> #include <algorithm> typedef const int cint; typedef long long ll; typedef unsigned long long ull; inline bool isdigit( const char cur ) { return cur >= '0' && cur <= '9'; }/*{{{*/ template <class T> T Max( T a, T b ) { return a > b? a: b; } template <class T> T Min( T a, T b ) { return a < b? a: b; } template <class T> void chk_Max( T &a, T b ) { if( b > a ) a = b; } template <class T> void chk_Min( T &a, T b ) { if( b < a ) a = b; } template <typename T> T read() { T sum = 0, fl = 1; char ch = getchar(); for (; isdigit(ch) == 0; ch = getchar()) if (ch == '-') fl = -1; for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0'; return sum * fl; } template <class T> T pow( T a, int p ) { T res = 1; while( p ) { if( p & 1 ) res = res * a; a = a * a; p >>= 1; } return res; }/*}}}*/ const int N = 5e6 + 1e5; int main() { #ifdef woshiluo freopen( "e.in", "r", stdin ); freopen( "e.out", "w", stdout ); #endif int T = read<int>(); while( T -- ) { static int pool[N], f[N]; static bool have[N]; cint n = read<int>(); cint m = read<int>(); int min = m, max = m, res = m; for( int i = 0; i <= m; i ++ ) { f[i] = m; pool[i] = 0; have[i] = 0; } for( int i = 1; i <= n; i ++ ) { cint p = read<int>(); have[p] = 1; chk_Min( min, p ); } for( int i = 1; i <= m; i ++ ) pool[ f[i] ] += have[i]; auto update = [&]( cint cur, cint val ) { if( have[cur] ) pool[ f[cur] ] --; chk_Min( f[cur], val ); if( have[cur] ) pool[ f[cur] ] ++; }; for( int i = m; i >= 1; i -- ) { update( i, i ); for( int j = 1; 1LL * i * j <= m; j ++ ) { cint nxt = i * j; update( nxt, Max( i, f[j] ) ); } while( pool[max] == 0 ) max --; if( i <= min ) chk_Min( res, max - i ); } printf( "%d\n", res ); } } ```
Comment seems to stuck. Try to refresh?✨

Woshiluo's NoteBook

「Jump up HIGH!!」