目录

• 「赛后总结」20230724 CSP 模拟赛
  • 总结。
  • 题解
    • T1 最长上升子序列 ARC125C
      • 思路
      • 代码
    • T2 独特序列 ARC125D
      • 思路
      • 代码
    • T3 最大 GCD ARC126C
      • 思路
      • 代码
    • T4 连续子段 ARC126D
      • 思路
      • 代码

const ll N = 2e5 + 10;
namespace SOLVE {
	ll n, k, m, a[N], vis[N], ans[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void In () {
		n = rnt (), k = rnt (), m = 0;
		_for (i, 1, k) vis[a[i] = rnt ()] = 1;
		return;
	}
	inline void Solve () {
		ll j = 1;
		_for (i, 1, k - 1) {
			ans[++m] = a[i];
			while (vis[j]) ++j;
			if (j > a[i]) continue;
			ans[++m] = j, ++j;
		}
		for_ (i, n, a[k] + 1) if (!vis[i]) ans[++m] = i;
		ans[++m] = a[k];
		for_ (i, a[k] - 1, j) if (!vis[i]) ans[++m] = i;
		return;
	}
	inline void Out () {
		_for (i, 1, n) printf ("%lld ", ans[i]);
		puts ("");
		return;
	}
}

const ll N = 2e5 + 10, P = 998244353;

namespace BIT {
	class BIT {
	public:
		ll n;
	private:
		ll b[N];
		inline ll lowbit (ll x) { return x & -x; }
	public:
		inline void Update (ll x, ll y){
			if (x <= 0) return;
			while (x <= n) b[x] = (b[x] + y + P) % P, x += lowbit (x);
			return;
		}
		inline ll Query (ll x){
			ll sum = 0;
			while (x > 0) sum = (sum + b[x]) % P, x -= lowbit (x);
			return sum;
		}
	};
}

namespace SOLVE {
	ll n, a[N], la[N], f[N], vis[N], ans;
	BIT::BIT tr;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void In () {
		tr.n = n = rnt ();
		_for (i, 1, n) {
			a[i] = rnt ();
			la[i] = vis[a[i]], vis[a[i]] = i;
		}
		return;
	}
	inline void Solve () {
		_for (i, 1, n) {
			f[i] = (!la[i] + tr.Query (i - 1) - tr.Query (la[i] - 1) + P) % P;
			tr.Update (la[i], -f[la[i]]), f[la[i]] = 0, tr.Update (i, f[i]);
		}
		ans = tr.Query (n);
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

const ll N = 1e6 + 10;
namespace SOLVE {
	ll n, k, sum, mx, mn, a[N], t[N], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline bool Check (ll x) {
		ll q = -sum;
		_for (i, 1, (mx - 1) / x + 1) q += (t[i * x] - t[(i - 1) * x]) * i * x;
		return q <= k;
	}
	inline void In () {
		n = rnt (), k = rnt ();
		_for (i, 1, n) {
			a[i] = rnt ();
			++t[a[i]], sum += a[i];
			mx = std::max (mx, a[i]);
			mn = std::min (mn, a[i]);
		}
		return;
	}
	inline void Solve () {
		_for (i, 1, mx * 2) t[i] += t[i - 1];
		if (mx * n - sum <= k) {
			ans = mx + (k - mx * n + sum) / n;
			return;
		}
		for_ (i, mx, 1) if (Check (i)) { ans = i; break; }
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

const ll N = 210, S = 1 << 16, inf = 1ll << 40;
namespace SOLVE {
	ll n, k, a[N], f[S], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline ll Count (ll x) { ll s = 0; while (x) s += x & 1, x >>= 1; return s; }
	inline void In () {
		n = rnt (), k = rnt ();
		_for (i, 1, n) a[i] = rnt ();
		return;
	}
	inline void Solve () {
		memset (f, 0x3f, sizeof (f));
		f[0] = 0;
		_for (i, 1, n) {
			ll x = a[i];
			for_ (j, (1 << k) - 1, 0) {
				if (f[j] >= inf) continue;
				if (!((1 << (x - 1)) & j)) 
					f[j | (1 << (x - 1))] = std::min (f[j | (1 << (x - 1))], f[j] + __builtin_popcount (j >> (x - 1)));
				f[j] += std::min (__builtin_popcount (j), (int)(k) - __builtin_popcount (j));
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", f[(1 << k) - 1]);
		return;
	}
}