专栏广场

我们需要在两种短信套餐和标准计费方式之间找到最优组合，使得总费用最小。 由于 `totalSMS` 可达 $10^{12}$，传统的动态规划或完全枚举方法不可行，可以采取 **启发式搜索 + 二进制优化来减少搜索状态** 观察到剩下的 $10$ 美分每条的不需要特殊计算，放到最后不够再补...

经典前缀和 ```cpp #include <bits/stdc++.h> using namespace std; const int maxn=200005; int a[maxn],b[maxn],n,k,q; void insert(int l,int r,int c){ ...

$01$ 背包板子题 ```cpp #include<bits/stdc++.h> using namespace std; int n,l[1000005],d[1000005],f[1000005]; int main(){ ios::sync_with_stdio(0); ...

首先最大值是特定不变的，因此不妨 $a_i' = max - a_i$，然后都调成 $0$，其中 $max = \max_{i=1}^n a_i$。 ### 算法一 找一个奇点，记忆化搜索。 期望通过测试点 1，期望得分 4。 ### 算法二 由于第一问是一个比较常见的贪心，就是需...

分治+KMP ```cpp #include<bits/stdc++.h> using namespace std; int t,n,a[505],kmp[505][2005],maxn=-1; string s[505]; bool check(int x,int y){ fo...

建表达式之后树形$DP$，复杂度线性 注意： - 多测清空 - 由于都是二元运算，表达式变量 $+$ 操作符总数为 $2n-1$...

简单题。 --- 首先，答案肯定是第一场比赛在 $i$ 前面的人数加第二场前面的人数减去两场都在前面的人数。 也就是说只需要求 $j$，满足 $j$ 在两个序列中均在 $i$ 之前。 于是考虑按顺序遍历第一场比赛的排名序列，这样第一场比赛的条件自然成立，对于第二场比赛不妨用树...

被诈骗了！唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐。 --- 由于 $x,y \le n$，所以 $n$ 其实是没有用的！ 于是答案如下： - 当 $x=y$ 时，答案显然是 $0$。 - 当 $\mathrm{count}(x) = \mathrm{count}(...

### 分析 dp 的状态是两维的，分别表示花和花瓶，这一点观察数据范围 $1\le F,W\le 100$ 也能观察出来 题目中说过“**必须在保持花束顺序的前提下**”，因为我们当前放了 $i$ 束花，下一束就只能放第 $i+1$ 束花了，所以第 $i$ 个位置的最优解只有可能从第 ...