题目列表
书
简单题，但是有个小丑挂掉了。
对于每个 $[10^x,10^{x+1}-1]$ 的区间，计算 $n$ 覆盖了多大范围。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
freopen("book.in", "r", stdin);
freopen("book.out", "w", stdout);
ll n, ans = 0;
cin >> n;
ll pw = 1, cnt = 1;
for (int i = 1; i <= 10; i++)
{
if (pw * 10 - 1 <= n)
ans += cnt * 9 * pw;
else
{
ans += cnt * (n - pw + 1);
break;
}
pw *= 10;
cnt++;
}
cout << ans << endl;
return 0;
}
/*
[1,9]
[10,99]
[100,999]
...
[10**x,10**(x+1)-1]
*/数
我没记错的话我在 cses.fi 上做过这题。但这题本来就很典，估计很多 OJ 都有。
设 $f_i$ 表示凑到 $i$ 的最小步数。
转移 $f_i\gets\min\{f_{i-1},f_{i\times 2},f_{i\times 3}\}+1$。
但是有一个小丑以为 CF 打多了误以为多测只要每个 $\mathcal O(n)$ 就能过，喜提 TLE。
#include <bits/stdc++.h>
using namespace std;
int f[1000020];
void init()
{
int n = 1000000;
f[f[f[2] = f[3] = 1] = 0] = 1000;
for (int i = 4; i <= n; i++)
{
int x, y, z;
x = y = z = INT_MAX;
x = f[i - 1];
if (i % 2 == 0)
y = f[i / 2];
if (i % 3 == 0)
z = f[i / 3];
f[i] = min({x, y, z}) + 1;
}
}
void solve()
{
int n;
cin >> n;
cout << f[n] << '\n';
}
int main()
{
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
init();
int t;
cin >> t;
while (t--)
solve();
return 0;
}盒
一眼 dp，状态很容易设出 $f_{i,0/1/2}$ 表示第 $i$ 个位置往左不动往右的答案。
转移需要分讨。
-
当前有盖子
-
左边有盖子
$f_{i,0}\gets f_{i-1,0}+a_{i-1}$
$f_{i,1}\gets \max\{f_{i-1,0},f_{i-1,1}\}+a_{i}$
$f_{i,2}\gets\max\{f_{i-1,0},f_{i-1,1},f_{i-1,2}\}+a_{i+1}$
-
反之
$f_{i,0}\gets f_{i-1,0}+a_{i-1}$
$f_{i,1}\gets f_{i-1,1}+a_{i}$
$f_{i,2}\gets f_{i-1,1}+a_{i+1}$
-
-
反之
$f_{i,0}\gets\max\{f_{i-1,0},f_{i-1,1}\}$
$f_{i,1}\gets\max\{f_{i-1,0},f_{i-1,1},f_{i-1,2}\}$
这里不需要转移 $f_{i,2}$，它本来就没有盖子，无需转移。转移 $f_{i,0}$ 是为了让之后的 $f_{i+1,0}$ 能够转移。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[200020][3];
int n;
ll a[200020];
int b[200020];
//f[i][0/1/2] left,mid,right
int main()
{
freopen("box.in", "r", stdin);
freopen("box.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
scanf("%lld", a + i);
for (int i = 1; i <= n; i++)
scanf("%d", b + i);
for (int i = 1; i <= n; i++)
{
if (b[i]) //有盖子
{
f[i][0] = f[i - 1][0] + a[i - 1];
if (b[i - 1]) //左边也有盖子
{
f[i][1] = max(f[i - 1][0], f[i - 1][1]) + a[i];
f[i][2] = max({f[i - 1][0], f[i - 1][1], f[i - 1][2]}) + a[i + 1];
}
else
{
f[i][1] = f[i - 1][1] + a[i];
f[i][2] = f[i - 1][1] + a[i + 1];
}
}
else
{
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = max({f[i - 1][0], f[i - 1][1], f[i - 1][2]});
}
}
cout << max(f[n][0], f[n][1]) << endl;
return 0;
}和
很厉害的一道题！
首先考虑暴力怎么写。我说的不是 $3^n$ 级别的，如果你只想到这一层建议先想出多项式复杂度的代码再看。
我们的暴力应该是 $\mathcal O(Vn^3)$。
暴力的写法，应该是 $\mathcal O(n)$ 枚举更改哪个位置，$\mathcal O(V)$ 枚举更改成什么结果，$\mathcal O(n^2)$ 枚举子序列计算。
考虑优化哪一个。$O(n^2)$ ，枚举子序列大抵是可以优化的，但我不会。
考虑优化 $O(V)$ 枚举更改值。
显然的，由于只有 $300$ 个更改方案，所以能构成的完全平方数不会过多，大约是根号级别的。
那么就很好优化了，$\mathcal O(n)$ 枚举修改哪个位置，先算出它没有干扰到哪些子序列，这些子序列会产生多少贡献，这个是很好算的。
然后，我们算出更改这个位置之后的某个子序列上界和下界，这里记作 $L$ 和 $R$。
$[L,R]$ 之间的完全平方数 $p^2$ 不会过多，我们枚举可行的 $p$。$p$ 的范围应为 $[\left\lceil\sqrt L\right\rceil,\left\lfloor\sqrt R\right\rfloor]$。找完全平方数选择枚举它的因子降低复杂度是一个很典的 trick。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
void gmx(T &x, T y) { x = max(x, y); }
int n;
int a[320];
int s[320];
bool sq[100020];
ll f[320];
ll ans;
int S(int l, int r) { return s[r] - s[l - 1]; }
int main()
{
freopen("sum.in", "r", stdin);
freopen("sum.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 1; i <= 300; i++)
sq[i * i] = 1;
for (int i = 1; i <= n; i++) //修改第i个位置
{
int tmp = 0;
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++)
if (i < l || r < i)
if (sq[S(l, r)])
tmp++;
memset(f, 0, sizeof(f));
for (int l = 1; l <= n; l++)
{
for (int r = l; r <= n; r++)
{
if (i < l || r < i)
continue;
int L = 1, R = 300;
int sum = S(l, r) - a[i];
L += sum;
R += sum;
// cout << L << " " << R << endl;
int mayL = ceil(sqrt(L)), mayR = sqrt(R);
// cout << mayL << " " << mayR << endl;
// cout << endl;
for (int k = mayL; k <= mayR; k++)
if (k * k - sum <= 300)
f[k * k - sum]++;
}
}
for (int i = 1; i <= 300; i++)
gmx(ans, f[i] + tmp);
}
cout << ans << endl;
return 0;
}