\(\text{Day-1}\)

惨遭遣返······

这真是伟大的啊！！

\(\text{Day1}\)

\(day\) 几好像没有意义，反正只有一天

\(\text{T1}\)

极致 \(H_2O\)

机子跑得非常“快”，样例四直接飙出 \(1s\) 了！

确实无语

还担心过不了呢

提前把 \(10^7\) 内数字含 \(7\) 的数找出来，再把他们的倍数标记掉即可

询问可以离线排序指针做到最坏 \(O(MAXV)\)

也可向 \(dch\) 那样在线二分（真慢）

我考场就打了并查集

\(\text{Code}\)

#include <cstdio>

#include <iostream>

#define re register

using namespace std;

const int N = 1e7;

int Q[6000000], cnt, fa[N + 15], bin[10], q[N + 10];

inline int check(int x)

{

	int d = 0;

	for(; x; x /= 10, ++d) if (x % 10 == 7) return d;

	return -1;

}

void Prework()

{

	bin[0] = 1;

	for(re int i = 1; i <= 8; i++) bin[i] = bin[i - 1] * 10;

	for(re int i = 1; i <= N + 10; i++) fa[i] = i;

	int j;

	for(re int i = 7; i <= N + 10; i = j + 1)

	{

		int k = check(i); j = i;

		if (k == -1) continue;

		for(; j < i + bin[k]; j++) Q[++cnt] = j;

	}

	for(re int i = 1; i <= cnt; i++)

		for(re int j = Q[i]; j <= N + 10; j += Q[i]) fa[j] = fa[j + 1];

}

inline int find(int x)

{

	q[0] = 0;

	while (fa[x] != x) q[++q[0]] = x, x = fa[x];

	for(re int i = 1; i <= q[0]; i++) fa[q[i]] = x;

	return x;

}

inline void read(int &x)

{

	x = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar());

	for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());

}

int main()

{

	freopen("number.in", "r", stdin), freopen("number.out", "w", stdout);

	int T; read(T);

	Prework();

	for(re int i = 1, x; i <= T; i++)

	{

		read(x);

		if (find(x) != x) printf("-1\n");

		else printf("%d\n", find(x + 1));

	}

}

\(\text{T2}\)

这真是悲伤的啊！！怎么 \(T2\) 又是这种题！

最讨厌这种纯 \(DP\) 题了，一点意思都没有

考场简单无脑 \(DP\) 水了 \(50pts\)

正解也很无脑

设 \(f_{i,j,k,l}\) 表示考虑到第 \(i\) 位，前面选了 \(j\) 个数，第 \(0\) 到 \(i-1\) 位产生了 \(k\) 个 \(1\)，这些位置给第 \(i\) 位的进位为 \(l\) 时的答案

转移考虑第 \(i\) 位的选数，枚举选的个数 \(t\)

\[f_{i+1,j+t,\text{k+(t+l)%2},(t+l)/2}+=f_{i,j,k,l} \times v_i^t \times \binom{j+t}{t}
\]

答案就是到 \(m+1\) 位产生的 \(1\) 的个数与进位的数往高位推完后产生的 \(1\) 的个数的和小于等于 \(K\) 的 \(f\) 值之和

\(\text{Code}\)

#include <cstdio>

#define RE register

using namespace std;

typedef long long LL;

const int P = 998244353;

int n, m, K, v[111];

LL f[111][35][35][35], pw[111][35], fac[35], ans, ifac[35];

inline void Add(LL &x, LL y){x += y, x = (x > P ? x - P : x);}

inline LL fpow(LL x, LL y){LL s = 1; for(; y; y >>= 1, x = x * x % P) if (y & 1) s = s * x % P; return s;}

inline LL C(int n, int m){return fac[n] * ifac[m] % P * ifac[n - m] % P;}

inline int calc(int x){int s = 0; for(; x; x >>= 1) s += (x & 1); return s;}

int main()

{

	scanf("%d%d%d", &n, &m, &K);

	fac[0] = ifac[0] = 1;

	for(RE int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % P, ifac[i] = fpow(fac[i], P - 2);

	for(RE int i = 0; i <= m; i++) scanf("%d", &v[i]);

	for(RE int i = 0; i <= m; i++)

		for(RE int j = 0; j <= n; j++) pw[i][j] = fpow(v[i], j);

	f[0][0][0][0] = 1;

	for(RE int i = 0; i <= m; i++)

		for(RE int j = 0; j <= n; j++)

			for(RE int k = 0; k <= K; k++)

				for(RE int l = 0; l <= (n >> 1); l++)

				if (f[i][j][k][l])

					for(RE int t = 0; t + j <= n; t++)

						Add(f[i+1][j+t][k+((l+t)&1)][l+t>>1], f[i][j][k][l] * pw[i][t] % P * C(j+t, t) % P);

	for(RE int k = 0; k <= K; k++)

		for(RE int l = 0; l <= n / 2; l++)

		if (f[m + 1][n][k][l] && k + calc(l) <= K) Add(ans, f[m + 1][n][k][l]);

	printf("%lld\n", ans);

}

\(\text{T3}\)

直接水分走起，还忘记打模拟退火了！！

正解又是 \(DP\)

发现一些性质

1.对原序列差分之后，修改操作相当于交换相邻两差分值

2.最优序列差分值是一个单谷型的

3.原序列同时减去一个相同的数方差不变

4.对与一个序列答案是 \(n\sum_{i=1}^n a_i^2-(\sum_{i=1}^n a_i)^2\)

那么我们就可以差分后 \(DP\) 构造这个最优解了

设 \(f_{i,j}\) 表示安排完前 \(i\) 个差分值，当前产生的 \(a\) 序列的和为 \(j\) 时最优的 \(\sum a_i^2\)

转移考虑当前差分值序列放前面或后面即可

非常 \(easy\)

\(\text{Code}\)

#include <cstdio>

#include <algorithm>

#define IN inline

#define RE register

using namespace std;

typedef long long LL;

const int N = 10000;

const LL INF = 1e17;

int n, a[N + 5], b[N + 5], cur;

LL f[2][N * 50 + 5];

IN void MIN(LL &x, LL y){x = min(x, y);}

IN LL Sqr(LL x){return x * x;}

int main()

{

	scanf("%d", &n);

	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i]);

	for(RE int i = 1; i < n; i++) b[i] = a[i + 1] - a[i];

	for(RE int i = 0; i <= n * a[n]; i++) f[0][i] = f[1][i] = INF;

	sort(b + 1, b + n);

	int k = 1; while (b[k] == 0 && k + 1 < n) ++k;

	f[k & 1 ^ 1][0] = 0;

	for(RE int i = k; i < n; cur += b[i++])

	{

		for(RE int j = 0; j <= i * a[n]; j++) f[i & 1][j] = INF;

		for(RE int j = 0; j <= (i - 1) * a[n]; j++)

		if (f[i & 1 ^ 1][j] < INF)

		{

			MIN(f[i & 1][j + cur + b[i]], f[i & 1 ^ 1][j] + Sqr(cur + b[i]));

			MIN(f[i & 1][j + i * b[i]], f[i & 1 ^ 1][j] + Sqr(b[i]) * i + 2LL * j * b[i]);

		}

	}

	LL ans = INF;

	for(RE int j = 0; j <= n * a[n]; j++)

	if (f[n & 1 ^ 1][j] < INF) MIN(ans, f[n & 1 ^ 1][j] * n - Sqr(j));

	printf("%lld\n", ans);

}

\(\text{T4}\)

鉴于 \(\text{CSPS2021 T4}\) 的教训题都没看

但后来发现暴力分很高的样子

\(\text{Summary}\)

今年从 \(CSP\) 到 \(NOIP\) 最亏的就是纯 \(DP\) 题

这方面太薄弱了

纯 \(DP\) 题做得太少，考场遇到没有想法

主要是以前很少考这种题，今年直接疯狂连击！

确实很无语

出这种题的好处是出题人十分开心

要做做这方面的题（虽然这类题很无聊）

巴特西

NOIP2021游记总结

\(\text{Day-1}\)

\(\text{Day1}\)

\(\text{T1}\)

\(\text{Code}\)

\(\text{T2}\)

\(\text{Code}\)

\(\text{T3}\)

\(\text{Code}\)

\(\text{T4}\)

\(\text{Summary}\)

最新文章

热门文章