A
题意：给定一个数组，问有多少 \(i\in [2,n-1],a[i-1]>a[i]<a[i+1]\)。
做法：模拟。
B
题意：按顺序将 \(n\) 个数加入集合，维护前 \(6\) 大的数。对于每个数求出它会将第几个数踢出前 \(6\) 或者不踢出任何其他数。
做法：模拟。可以使用priority_queue实现。但是要注意priority_queue默认大根堆，取相反数即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int n;cin>>n;
int ans=n;
vector<double> A(n);
vector<int> Ans;
for(int i=0;i<n;i++) cin>>A[i],A[i]*=1e8;
priority_queue<pair<int,int> > q;
for(int i=0;i<n;i++)
{
q.push(make_pair(-A[i],i));
if(q.size()>6)
{
if(q.top().second==i) ans--,Ans.push_back(0);
else Ans.push_back(q.top().second+1);
q.pop();
}
else Ans.push_back(0);
}
cout<<ans<<endl;
for(auto x:Ans) cout<<x<<' ';
}
C
题意：给定一棵树，带点权。建立一个无向完全图，边 \((u,v)\) 的权值为 \(lca(u,v)\) 的权值。求一条哈密顿路径，使边权和最大。输出这个边权和。\(n\leq 300\)。
做法：
假设哈密顿路径是有向的，则可以看作每个点对应着一条出边（除了最后一个点）。
维护 \(f[x][i]\) 表示以 \(x\) 为根的子树中有 \(i\) 个点的出边经过根 \(x\) 时子树的答案。
可以发现如果一条出边向上经过 \(x\) ，那么它发源于哪个点其实是无关紧要的，这条出边的贡献可能是点 \(x\) 到点 \(1\) （根节点）的路径上的某一个点的点权。
同时，\(i\) 条出边经过根 \(x\) 也意味着子树 \(x\) 中包含了 \(i\) 条哈密顿路（的一部分）。
考虑转移，将 \(x\) 的一个儿子 \(y\) 的答案合并到 \(x\) 的答案：
其中枚举 \(k\) 表示将来自于 \(y\) 的出边塞到了 \(x\) 的其他子树中，或者是将来自于其他子树的出边塞到了 \(y\) 中，这二者都会对答案产生 \(val[x]\) 的贡献。
关于 \(k\) 还有一些小细节：
1、\(k\in [0,2\min\{i,j\}]\)，假如 \(i<j\) ，则 \(j\) 超出的部分在 \(i\) 中找不到可以链接的位置。
2、\(i+j-k>0\) ，这是为了防止回路的出现。
另外，由于更新前后的 \(f\) 不同，所以用 \(f'\) 表示用子树 \(y\) 更新后的 \(f\) 。
最后用 \(f[1][1]\) 表示答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 1e18
const int N=305;
vector<int> son[N];
int n,a[N],f[N][N],s[N],siz[N];
void dfs(int x)
{
siz[x]=1;
for(int i=0;i<=n;i++) f[x][i]=-inf;
f[x][1]=0;
for(int y:son[x])
{
dfs(y);
for(int i=0;i<=n;i++) s[i]=-inf;
for(int i=0;i<=siz[x];i++)
for(int j=0;j<=siz[y];j++)
for(int k=0;k<=min(i,j)*2;k++)
if(i+j-k) s[i+j-k]=max(s[i+j-k],f[x][i]+f[y][j]+k*a[x]);
siz[x]+=siz[y];
for(int i=0;i<=n;i++) f[x][i]=s[i];
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++)
{
int x;cin>>x;
son[x].push_back(i);
}
dfs(1);
cout<<f[1][1]<<endl;
}
D
题意：给定一个 \(0~n-1\) 的排列，\(m\) 次询问 \(l,r,k\) ，问区间 \([l,r]\) 中第 \(k\) 小的未出现过的数。
做法：
如果不询问区间，那么可以用权值线段树解决。
如果询问的区间都是前缀，那么可以用离线后用权值线段树解决。
如果询问任意区间，那么可以用可持久化权值线段树解决，也就是主席树。
权值线段树可以求第 \(k\) 小，反一下就可以求未出现自然数第 \(k\) 小，所以只要把每次加入的数在主席树中新加一列就可以实现区间第 \(k\) 小。
#include<bits/stdc++.h>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) f=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
const int N=1e6+5;
int tree[N<<5],ls[N<<5],rs[N<<5],rt[N],n,a[N],tot,TOT,m;
#define mid (l+r>>1)
void upd(int l,int r,int pre,int &k,int x,int val)
{
if(!k) k=++tot;
if(l==r) return tree[k]=val,void();
if(mid>=x) rs[k]=rs[pre],upd(l,mid,ls[pre],ls[k],x,val);
else ls[k]=ls[pre],upd(mid+1,r,rs[pre],rs[k],x,val);
tree[k]=tree[ls[k]]+tree[rs[k]];
}
int query(int l,int r,int pre,int k,int rk)
{
if(l==r) return l;
if(mid-l+1-(tree[ls[k]]-tree[ls[pre]])>=rk) return query(l,mid,ls[pre],ls[k],rk);
return query(mid+1,r,rs[pre],rs[k],rk-(mid-l+1-(tree[ls[k]]-tree[ls[pre]])));
}
int main()
{
read(n),read(m);
for(int i=1;i<=n;i++)
{
read(a[i]);
a[i]++;
upd(1,n,rt[i-1],rt[i],a[i],1);
}
while(m--)
{
int l,r;
long long rk;
read(l),read(r),read(rk);
if(rk>n-(r-l+1)) printf("%lld\n",rk+(r-l+1)-1);
else printf("%d\n",query(1,n,rt[l-1],rt[r],rk)-1);
}
return 0;
}