[TJOI2013]最长上升子序列
题目描述
运行代码
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n; int f[N], tr[N]; vector<int> v; void add(int x, int k) { for ( ; x <= n; x += x & -x) tr[x] = max(tr[x], k); } int query(int x) { int r = 0; for ( ; x; x -= x & -x) r = max(r, tr[x]); return r; } int main() { cin>>n; for (int i = 1; i <= n; i ++ ) { int x; cin>>x; v.insert(v.begin() + x, i); } for (auto x : v) { f[x] = query(x - 1) + 1; add(x, f[x]); } for (int i = 1; i <= n; i ++ ) { f[i] = max(f[i], f[i - 1]); cout<<f[i]<<endl; } return 0; }
代码思路
int f[N], tr[N];分别存储原序列每个位置的最长上升子序列长度和树状数组。vector<int> v;用于存储离散化后的序列位置。- 函数
add(x, k): 更新树状数组tr[]，使得位置x对应的值变为max(tr[x], k)。这是通过位运算快速定位并更新相关位置实现的。 - 函数
query(x): 查询位置x之前（包括x）的最大值。这是树状数组查询操作的基本应用。 - 主函数
main():
- 输入序列长度
n。 - 遍历输入每个元素的位置
x，并在向量v的对应位置插入当前的序号i，实现离散化。 - 遍历离散化后的序列
v，对每个位置x：
- 计算其最长上升子序列长度
f[x]为当前位置左边最大长度加上 1。 - 更新树状数组
tr[]。
- 最后再次遍历
f[]，利用前一个位置的最长上升子序列长度更新当前的f[i]，保证连续性，并输出最终的最长上升子序列长度序列。
[SCOI2009]游戏
题目描述
运行代码
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e4; int p[N],v[N],dp[N]; signed main() { int n; cin>>n; for(int i=2;i<=n;i++) { if(!v[i]) p[++p[0]]=i; for(int j=1;j<=p[0] && i*p[j]<=n;j++) { v[i*p[j]]=1; if(!(i%p[j])) break; } } for(int i=dp[0]=1;i<=p[0];i++) for(int j=n;j>=p[i];j--) for(int k=p[i];k<=j;k*=p[i]) dp[j]+=dp[j-k]; dp[0]=0; for(int i=1;i<=n;i++) dp[0]+=dp[i]; cout<<dp[0]+1<<endl; return 0; }
代码思路
素数筛
- 使用埃拉托斯特尼筛法生成素数：初始化数组
v[N]标记每个数是否为合数，数组p[N]存储素数。
- 当遍历到数i时，如果
v[i]为0，说明i是素数，将其存入素数数组p中。 - 针对当前素数
i，将所有i的倍数标记为合数（v[i*p[j]]=1），当遇到i的平方时跳出内层循环，减少重复计算。
计算欧拉函数之和
- 初始化动态规划数组
dp[N]，其中dp[i]表示小于等于i的数中，欧拉函数值的和。 - 外层循环遍历素数数组
p。内层循环倒序遍历从n到每个素数的倍数（步进为当前素数）。内内层循环计算当前素数的幂次方（不超过当前数j），累加到dp数组中，实际上是在计算形如φ(j-k)的和，其中k是当前素数的幂次方序列，这样做可以高效地累加每个数的欧拉函数值。 - 最后，
dp[0]=0用于初始化累加和的起始值。 - 遍历dp数组，累加所有dp[i]的值，得到小于等于n的所有欧拉函数值之和。
- 输出结果加1（因为题目要求包括n自身），
cout<<dp[0]+1<<endl;。
