Journey / Solution Set - 「NOIP-S 2020」「Prob. A-C」

首页

关于

笔记

文章

友链

Journey / Solution Set - 「NOIP-S 2020」「Prob. A-C」

cirnovsky / Dec 09, 2020

这种东西怎么写啊。。。

∆ Day 1（好像也没有 Day 2

到了 NK 后发现正好可以进门，于是就什么也没有检查的进去了。

进门前问了一下 LYC 之前问过的一个问题，他说没有头绪，然后就没怎么说话了。

在去考场的途中和大 LJS 瞎扯了一下 CF 的 bitmasks 瘤子题。

小 ljs 在考场外面等的时候问我 KMP 怎么打。（伏笔 x1

我告诉他没有关系，碰见全部哈希（伏笔 x2。

快要进门的时候发现 WXK、TR、高一正在互相进行仪式。

然后就没有什么了。

进了考场之后打开 Dev，把快读之类的东西打了打，果然还是不习惯辣么大个的 Enter。

右边的右边是 WXK，坐下时互相说了句：“好巧啊”，然后互相迷惑地做了一下 orz 动作。

左边的左边是 TLY，直接 yyds。

然后，然后就发题了嘛，打开看见文件夹里一个 string 我就知道事情不对。

此时尧姐的 flag 倒了：“今年考字符串、计数我把这个键盘夹着草稿纸吃了。”

打开 PDF，先用了整整半个小时通读了一下，感觉 T1、T2 简单题，T3、T4 只能骗。

于是乎细读了一下 T1，发现是个 DFS 模拟水题。（当时没有往拓扑想，不过反正都是对的）

然后花了半个小时的样子过完了所有大样例，还很 sb 地认为不会报 int。不过保险起见还是在代码开头和考场的草稿纸（指记事本 text.txt，事实上考场上的草稿纸质量太劣我没用）都写了一句 Beware of your LONG LONG 以提醒自己最后十五分钟再重新考虑会不会爆。

然后看 T2，想了大概五分钟出了一个翻过来枚举就是 $\Theta(n\ln n)$ 大众 84pts 的垃圾做法。

此时想起了 YHN 学长在暑假的时候讲的话：“在考场上有一个暴力就先打一个，可以在正解死亡时应急以及对拍。”

然后就开始打这个伪· $\Theta(n^{2})$ 。然后打出了一个 180+ 行的垃圾。

T3 带 SPJ，此时教练的 flag 倒了：“NOIP 不会考带 SPJ 的东西，以后不要考了。”

T3 又是个构造，此时教练的 flag 又倒了：“NOIP 不会考构造，以后不要考了。”

到了后面就根本不想打正解了，只想着调自己的暴力。结果就是调到后面越调越慌，连改思路的想法都没有。

最后就改了个 T1 的 long long，什么也没有干。

于是，NOIP2020 成了至暗时刻。

出来考场后，我问 LYC T2 的复杂度，他说：“ $\Theta(Tn\sqrt{n})$ ”。我当时就以为块 YC 打了个分块。

中午大家一起到某个不知名的地方吃了一个疑似火锅的东西。

桌子上小 ljs 跟我一样 T2 陷在 $\Theta(n^2)$ 潮流中，其他人都打了 84。

然后说着说着 LYC 发现自己 T1 读错了题（后来被证实是出题人语文差，自己也没考虑这些，于是读错题没有关系），蒙着发现自己也读错了。

然后就觉得，要完，这下没了（本来就没了好吧）。

本来大家都十分快乐的对着自己的答案，然后尧姐冒了一句：“大家不要对了，伤感情。”

于是 LYC 对着这个 T12 没对出错 T34 骗分稳健的人喊了一句：“对了半天没对出错，有优越感了是吧。”

十分奇妙的，本来大家都对吃没有什么兴趣，LYC 和 LJS 这两个饭量小的早就不吃了，结果 TR 点的虾滑来之后一个二个都站了起来。

感觉就这样了吧，NOIP2020 是灰色但打醒的。

∆ Sol.

A 排水系统

找出所有的起点 DFS 即可，可以手动实现一个分数类。

/* Beware of your __INT128 */

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

namespace MySpace {
typedef long long LL;

const __int128 MAXN = 1e5 + 5, MAXS = 10 + 5, MAXE = 1e5 + 5;

__int128 rint () {
	__int128 x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = ( c == '-' ? -1 : f );
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 + '0' );
}

__int128 calcGCD ( const __int128 a, const __int128 b ) ;
__int128 calcLCM ( const __int128 a, const __int128 b ) ;

struct GraphSet {
	__int128 to, nx;
	GraphSet ( __int128 T = 0, __int128 N = 0 ) { to = T, nx = N; }
} as[MAXN * 5 * 4];

struct Frac {
	__int128 one, ano;
	Frac ( __int128 O = 0, __int128 A = 0 ) { one = O, ano = A; }
} nds[MAXN];

__int128 n, stn, edn, bgn[MAXN], cnte, ind[MAXN], outd[MAXN], sts[MAXN], eds[MAXN], stnd, ednd, vis[MAXN];

void makeEdge ( const __int128 u, const __int128 v ) { as[++ cnte] = GraphSet ( v, bgn[u] ), bgn[u] = cnte; }
__int128 calcGCD ( const __int128 a, const __int128 b ) { return ! b ? a : calcGCD ( b, a % b ); }
__int128 calcLCM ( const __int128 a, const __int128 b ) { return ( ! a || ! b ) ? 0 : ( __int128 )a / calcGCD ( a, b ) * b; }
void getSimp ( Frac& fr ) { __int128 ret = calcGCD ( fr.one, fr.ano ); if ( ! ret )	fr = Frac (); else fr.one /= ret, fr.ano /= ret; }

void dfs ( const __int128 u ) {
	for ( __int128 i = bgn[u]; i; i = as[i].nx ) {
		__int128 v = as[i].to;
		Frac ad = Frac ( nds[u].one, nds[u].ano * outd[u] );
		getSimp ( ad );
		__int128 ret = calcLCM ( ad.ano, nds[v].ano );
		if ( ! ret )	nds[v] = ad, dfs ( v );
		else {
			__int128 ads = ret / ad.ano, us = ret / nds[v].ano;
			ad.one *= ads, ad.ano *= ads;
			nds[v].one *= us, nds[v].ano *= us;
			nds[v].one += ad.one;
			getSimp ( nds[v] );
			dfs ( v );
		}
	}
	if ( bgn[u] )	nds[u] = Frac ();
}

void Main () {
	n = rint (), stn = rint ();
	for ( __int128 i = 1; i <= n; ++ i ) {
		__int128 eg = rint ();
		for ( __int128 j = 1; j <= eg; ++ j ) {
			__int128 to = rint ();
			makeEdge ( i, to );
			ind[to] ++, outd[i] ++;
		}
	}
	for ( __int128 i = 1; i <= n; ++ i ) {
		if ( ! ind[i] )	sts[++ stnd] = i;
		if ( ! outd[i] )	eds[++ ednd] = i;
	}
	for ( __int128 i = 1; i <= stnd; ++ i )	nds[sts[i]].one = nds[sts[i]].ano = 1;
	sort ( eds + 1, eds + 1 + ednd );
	for ( __int128 i = 1; i <= stnd; ++ i )	dfs ( i );
	for ( __int128 i = 1; i <= ednd; ++ i )	wint ( nds[eds[i]].one ), putchar ( ' ' ), wint ( nds[eds[i]].ano ), putchar ( '\n' );
}
}

int main () {
//	freopen ( "water.in", "r", stdin );
//	freopen ( "water.out", "w", stdout );
	MySpace :: Main ();
	return 0;
}

B 字符串匹配

这里是 $\Theta(Tn\ln n+26Tn)$ ，我 yy 出来的一个 $\Theta(n\ln n+Tn)$ 的做法由于太过繁杂不想想了。

首先枚举 $AB$ 即循环节，然后挨个往后面跳记个数就好了。

#include <cstdio>
#include <cstring>

namespace mySpace {
typedef long long LL;

const int KEY = 1331;
const int MAXN = ( 1 << 20 ) + 5;

int mul ( const LL a, const LL b, const int p ) { return a * b % p; }
int add ( const int a, const int b, const int p ) { return ( a + b ) < p ? ( a + b ) : ( a + b - p ); }
int sub ( const int a, const int b, const int p ) { return ( a - b ) < 0 ? ( a - b + p ) : ( a - b ); }
struct Value {
	static const int onemod = 19260817, anomod = 998244353;
	int p, q;
	Value () : p ( 0 ), q ( 0 ) {}
	Value ( const int x ) : p ( x ), q ( x ) {}
	Value ( const int a, const int b ) : p ( a ), q ( b ) {}
	Value operator * ( const Value &other ) const { return Value ( mul ( p, other.p, onemod ), mul ( q, other.q, anomod ) ); }
	Value operator + ( const Value &other ) const { return Value ( add ( p, other.p, onemod ), add ( q, other.q, anomod ) ); }
	Value operator - ( const Value &other ) const { return Value ( sub ( p, other.p, onemod ), sub ( q, other.q, anomod ) ); }
	bool operator == ( const Value &other ) const { return p == other.p && q == other.q; }
	bool operator != ( const Value &other ) const { return ! ( Value ( p, q ) == other ); }
} pwr[MAXN], has[MAXN];

int n, mps[MAXN], buc[MAXN][26], suf[MAXN];
char str[MAXN];

void initial () {
	scanf ( "%s", str + 1 ), n = strlen ( str + 1 );
	for ( int i = 1; i <= n; ++ i )	mps[i] = str[i] - 'a';
	bool tmp[26] = {}; int cur = 0;
	for ( int i = 1; i <= n; ++ i ) {
		has[i] = has[i - 1] * KEY + mps[i];
		memcpy ( buc[i], buc[i - 1], sizeof ( int ) * 26 );
		tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1;
		for ( int j = cur; j < 26; ++ j )	buc[i][j] ++;
	}
	memset ( tmp, 0, sizeof ( tmp ) ), cur = 0;
	for ( int i = n; i; -- i )	tmp[mps[i]] ^= 1, cur += tmp[mps[i]] ? 1 : -1, suf[i] = cur;
}

Value calcHS ( const int l, const int r ) { return has[r] - has[l - 1] * pwr[r - l + 1]; }
void solve () {
	initial (); LL ans = 0;
	for ( int len = 2; len < n; ++ len ) {
		Value tmp = calcHS ( 1, len );
		for ( int nxt = len; nxt < n; nxt += len ) {
			if ( calcHS ( nxt - len + 1, nxt ) != tmp )	break;
			ans += buc[len - 1][suf[nxt + 1]];
		}
	}
	printf ( "%lld\n", ans );
}

void main () {
	pwr[0] = 1;
	for ( int i = 1; i <= MAXN - 5; ++ i )	pwr[i] = pwr[i - 1] * KEY;
	int TC; scanf ( "%d", &TC );
	while ( TC -- > 0 )	solve ();
}
}

int main () {
//	freopen ( "string.in", "r", stdin );
//	freopen ( "string.out", "w", stdout );
	mySpace :: main ();
	return 0;
}

C 移球游戏

首先肯定这是 $n$ 个栈。先看 $n=2$ 的部分分。

这种情况只有黑白两色。

设 $1$ 柱有 $b$ （总共）个黑棋，有 $w$ 个白棋，把 $2$ 柱上 $b$ 个棋子放到 $3$ 柱上，然后重复：

把 $1$ 柱顶部所有黑棋放到 $2$ 柱上。
然后把 $1$ 柱上所有白棋放到 $3$ 柱。

直到 $1$ 柱为空。

然后把 $3$ 柱上面本属于 $1$ 柱的白棋放回去，又把 $2$ 柱上面的 $b$ 个黑棋放到 $1$ 柱去。

于是乎现在 $1$ 柱的情况大概是这样的：

假设原本是这样的：

\begin{aligned} &\texttt{W W B W W B W W B B B} \\ &\texttt{W B W B B B W B W B W} \end{aligned}

那么现在移完后是这样：

\begin{aligned} &\texttt{W W W W W W B B B B B} \\ &\texttt{W B W B B B} \\ &\texttt{W B W B W} \end{aligned}

然后我们把此时 $2$ 柱上的棋子全部放到 $3$ 柱上去，然后就划分一下就完了。

后面的事情就简单了，当 $n>2$ 的时候打个分治，一半一半划分染色，然后按着按着整理。

（代码和 CQ 队长 jiangly 对拍过，不过莫名奇妙就变成了基因比照，于是代码就基本变成了 jiangly 的）

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

namespace mySpace {
const int MAXN = 50 + 5, MAXM = 400 + 5, MAXK = 820000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T>
void wint ( _T x ) {
	if ( x < 0 )	putchar ( '-' ), x = ~ x + 1;
	if ( x > 9 )	wint ( x / 10 );
	putchar ( x % 10 ^ '0' );
}

struct Stack {
private:
	int stk[MAXM], _top;
public:
	Stack () { memset ( stk, 0, sizeof ( stk ) ), _top = 0; }
	void push ( const int val ) { stk[_top ++] = val; }
	void pop () { if ( _top )	_top --; }
	int at ( const int pos ) { return stk[pos]; }
	int top () { return stk[_top - 1]; }
	int size () { return _top; }
	bool empty () { return _top < 0; }
	void debug ( char c = ' ' ) {
		putchar ( '[' );
		for ( int i = 0; i < _top; ++ i )	printf ( "%d ", stk[i] );
		printf ( "]%c", c ) ;
	}
} clr[MAXN];

struct Answer {
	int one, ano;
	Answer ( int O = 0, int A = 0 ) { one = O, ano = A; }
} ans[MAXK];

int n, m, cnt;

void trans ( const int one, const int ano ) {
	clr[ano].push ( clr[one].top () );
	clr[one].pop ();
	ans[cnt ++] = Answer ( one, ano );
}

void solve ( const int l, const int r, const vector<int>& col ) {
	if ( r - l == 1 )	return;
	int mid = ( l + r ) >> 1;
	int lst = col[0];
	vector<int> onevec, anovec;
	for ( int i = 1; i < r - l; ++ i ) {
		int one = lst, ano = col[i], cnt = 0;
		for ( int j = 0; j < m; ++ j ) {
			if ( clr[one].at ( j ) < mid )	++ cnt;
		}
		for ( int j = 0; j < cnt; ++ j )	trans ( ano, n );
		for ( int j = m - 1; ~ j; -- j ) {
			if ( clr[one].at ( j ) < mid )	trans ( one, ano );
			else	trans ( one, n );
		}
		for ( int j = 0; j < m - cnt; ++ j )	trans ( n, one );
		for ( int j = 0; j < cnt; ++ j )	trans ( ano, one );
		for ( int j = 0; j < m - cnt; ++ j )	trans ( ano, n );
		for ( int j = 0; j < cnt; ++ j )	trans ( one, ano );
		for ( int j = m - 1; ~ j; -- j ) {
			if ( clr[ano].size () < m && ( clr[n].at ( j ) < mid || clr[one].size () == m ) )	trans ( n, ano );
			else	trans ( n, one );
		}
		bool was = 0;
		for ( int j = 0; j < m; ++ j ) {
			if ( clr[ano].at ( j ) >= mid )	was = 1;
		}
		if ( was )	anovec.push_back ( one ), lst = ano;
		else	onevec.push_back ( ano ), lst = one;
	}
	if ( clr[lst].at ( 0 ) < mid )	onevec.push_back ( lst );
	else	anovec.push_back ( lst );
	solve ( l, mid, onevec ), solve ( mid, r, anovec );
}

void main () {
	n = rint (), m = rint ();
	for ( int i = 0; i < n; ++ i ) {
		for ( int j = 0; j < m; ++ j )	clr[i].push ( rint () - 1 );
	}
	vector<int> col;
	for ( int i = 0; i < n; ++ i )	col.push_back ( i );
	solve ( 0, n, col );
	wint ( cnt ), putchar ( '\n' );
	for ( int i = 0; i < cnt; ++ i ) {
		wint ( ans[i].one + 1 ), putchar ( ' ' );
		wint ( ans[i].ano + 1 ), putchar ( '\n' );
	}
}
}

int main () {
//	freopen ( "ball.in", "r", stdin );
//	freopen ( "ball.out", "w", stdout );
	mySpace :: main ();
	return 0;
}