这套题是2024湖北icpc省赛题,五月一号集训没时间写,现在慢慢补。
这套题是2024湖北icpc省赛题,五月一号集训没时间写,现在慢慢补。
考个csp认证被这个鬼问题卡了,真是服了。
1 | vector<int> vec; |
1 | vector<int>().swap(vec); |
1 | vec.clear(); |
1 | vec.resize(n); |
题意:定义好数组为:一个由$m$个非负整数组成的数组$b$中,若$b$中所有元素可以通过以下操作使其为$0$。选择一个区间$(l, r)(1\le l< r\le m), \forall{i}, \ i\in(l, r),b_i$减去$1$。询问长度为$n$的数组,每个元素最大为$k$时,好数组个数。
可以证明,一个三元组$(a, b, c)$,当$a+c\ge b$时可以将其减为$0$。
于是设$dp[i][a][b]$为前i个数,第i-1个是a,第i个是b时的方案数。那么转移方程则为$dp[i][b][c] = \sum\limits_{a=b-c}^{k}{dp[i-1][a][b]}$。
对于求和用前缀和维护则可做到$O(n^3)$。
1 |
|
题意:给定一棵树,最初所有结点为白色。你可以进行操作:选定一个节点v和距离k,使树上与v的简单路径距离为k的所有点染色为黑色。构造操作序列,使操作次数最小化。
不难发现,影响操作次数的是树中最长的一条路径,即树的直径。所以我们只要找出树的直径并选定最中间的点(奇数长度则一个,偶数则两个),然后再使距离包含整条直径即可。
1 |
|
题意:称一个字符串为$k$-good字符串,当该字符串至少有一个长度为$k$的子串不是回文串。给定一个字符串,询问$[l, r]$子串的$\sum{k}$
通过模拟可以发现对于一个字符串:
不是回文串,则$k$可以取$2 \sim len$中的每一个值。
每个字符都相同,则答案为$0$。
是交错型的字符串,则$k$可以取$2 \sim len$中的每一个偶数。
只是回文串,则$k$可以取$2 \sim {len - 1}$中的每一个值。
判断回文串使用了双Hash(好久没用过了,写一个规范点的出来用)
1 |
|
题意:加多少次1可以改变中位数大小。
显然比中位数位置大的与中位数相同的数有多少个就加多少次
1 |
|
题意:一个长度为$n$的数组$a$,你可以进行k次操作,每一次操作选一个子段和添加到数组的任意位置,最大化数组总和。
当最大子段和小于$0$时显然不进行操作,当最大子段和大于$0$时不断加入$k$次目前最大子段和。
1 |
|
$$\int_{0}^{+\infty}e^{-x^{2}}dx$$
设$I(t)={(\int_{0}^{t} e^{-x^{2}}dx)}^2$, 则求
$$\sqrt{\lim\limits_{t \to +\infty}I(t)}$$
$$I^{‘}(t) = 2(\int_{0}^{t}e^{-x^{2}}dx)e^{-t^2} = 2\int_{0}^{t}e^{-x^2-t^2}dx = 2\int_{0}^{1}2te^{(y^2+1)t^2}dy$$
$$\frac{dI(t)}{dt} = \frac{\int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}dy}{dt}$$
$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+C$$
$$I(0)=\int_0^1\frac{-1}{y^2+1}dy+C = -\frac{\pi}{4} + C=0,C=\frac{\pi}{4}$$
$$I(t) = \int_0^1\frac{e^{-(y^2+1)t^2}}{-(y^2+1)}+\frac{\pi}{4}$$
$$\lim\limits_{t \to +\infty}I(t)=0+\frac{\pi}{4} = \frac{\pi}{4}$$
$$\therefore\int_{0}^{+\infty}e^{-x^{2}}dx=\frac{\sqrt{\pi}}{2}$$