\(\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\)
答案就是到 \(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\) 题做得太少，考场遇到没有想法
主要是以前很少考这种题，今年直接疯狂连击！
确实很无语
出这种题的好处是出题人十分开心
要做做这方面的题（虽然这类题很无聊）