Codeforces Round 1699 解题报告

by woshiluo

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

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

A The Third Three Number Problem

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

B Almost Ternary Matrix

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

C The Third Problem

给定一个 $0 \cdots n – 1$ 的排列 $a$ ，求有多少个排序 $b$ 满足 $\forall i,j$ ，有 $mex_a(i,j) = mex_b(i,j)$ ，模 $10^9 +7$ 。
$n \leq 10^5$

思路

容易注意到 $0$ 是固定的，考虑从 0 出发维护当前的满足 $mex = i$ 的最小区间。
如果在移动 $i$ 的时候，区间没有变大，这 $i$ 可以在这个区间的任意位置。
否则这个数字的位置就是确定的。
$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

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

做法

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

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

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

求在若干次操作后，最小化 $\max s – \min s$ 。
$1 \leq n \leq 10^6, 1 \leq m \leq 5 \times 10^6, 1 \leq s_i \leq m$

做法

容易发现这个集合可重不可重并不重要，那就当不可重的吧。
肯定是固定一个值然后最值化另一个值。
考虑现在确定 $i$ 是集合最小值，考虑定义 $f_j$ 表示在当前限制下，如果有 $f_j$ ，最大值最小是多少。
如果现在已经求出在 $i+1$ 是最小值时的 $f$ ，容易得出转移方程
$$
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 );
	}
}

4 thoughts on “Codeforces Round 1699 解题报告”

  • Zemu | 泽木
    2022年8月28日 12:49

    贺喜！Luo 大佬喜获 NOI 2022 Ag！

    回复
    1. woshiluo
      2022年9月13日 09:14

      我菜死了

      回复
  • Tiger1218
    2022年11月2日 16:15

    贺喜！Luo 大佬喜获 NOI 2022 Ag！

    回复
    1. woshiluo
      2022年11月2日 16:22

      我菜死了

      回复

    发表回复

    您的邮箱地址不会被公开。 必填项已用 * 标注

    message
    account_circle
    Please input name.
    email
    Please input email address.
    links

    此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。