NOI.AC NOIP模拟赛 第五场 游记
count
题目大意：
长度为\(n+1(n\le10^5)\)的序列\(A\)，其中的每个数都是不大于\(n\)的正整数，且\(n\)以内每个正整数至少出现一次。
对于每一个正整数\(k=1,..,n+1\)，求出的本质不同的长度为\(k\)的子序列的数量。对\(10^9+7\)取模。
思路：
由于只会有一个数会重复，因此考虑重复的这个数取\(0\)个、\(1\)个和\(2\)个的情况，用组合数直接算即可。
源代码:
#include<cstdio>
#include<cctype>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
typedef long long int64;
const int N=1e5+2,mod=1e9+7;
int a[N],fac[N],ifac[N],last[N];
void exgcd(const int &a,const int &b,int &x,int &y) {
if(!b) {
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
inline int inv(const int &x) {
int ret,tmp;
exgcd(x,mod,ret,tmp);
return ret;
}
inline int C(const int &n,const int &m) {
if(n<m) return 0;
return (int64)fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main() {
const int n=getint();
for(register int i=fac[0]=1;i<=n+1;i++) {
fac[i]=(int64)fac[i-1]*i%mod;
}
ifac[n+1]=inv(fac[n+1]);
for(register int i=n+1;i>=1;i--) {
ifac[i-1]=(int64)ifac[i]*i%mod;
}
int l;
for(register int i=1;i<=n+1;i++) {
a[i]=getint();
if(last[a[i]]) l=i-last[a[i]];
last[a[i]]=i;
}
for(register int i=1;i<=n+1;i++) {
printf("%d\n",(C(n+1,i)-C(n-l,i-1)+mod)%mod);
}
return 0;
}
delete
题目大意：
长度为\(n(n\le10^6)\)的序列\(A\)，从中删去恰好\(k\)个元素（右边的元素往左边移动），记\(cnt\)为新序列中\(A_i=i\)的元素个数。求\(cnt\)的最大值。
思路：
将\(A\)以\(i-A_i\)为第一关键字、\(A_i\)为第二关键字排序。就转化成了LIS问题。
时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e6+1;
int n,m;
std::pair<int,int> a[N];
class FenwickTree {
private:
int val[N];
int lowbit(const int &x) const {
return x&-x;
}
public:
void modify(int p,const int &x) {
for(;p<=n;p+=lowbit(p)) {
val[p]=std::max(val[p],x);
}
}
int query(int p) const {
int ret=0;
for(;p;p-=lowbit(p)) {
ret=std::max(ret,val[p]);
}
return ret;
}
};
FenwickTree bit;
int main() {
n=getint(),m=n-getint();
for(register int i=1;i<=n;i++) {
const int &x=getint();
a[i]=std::make_pair(i-x,x);
}
std::sort(&a[1],&a[n]+1);
int ans=0;
for(register int i=1;i<=n;i++) {
if(a[i].first<0) continue;
if(a[i].second>n) continue;
const int tmp=bit.query(a[i].second-1)+1;
if(tmp>m) continue;
bit.modify(a[i].second,tmp);
if(a[i].first<=n-m&&a[i].second<=m) ans=std::max(ans,tmp);
}
printf("%d\n",ans);
return 0;
}
power
题目大意：
一棵包含\(n(n\le10^5)\)个节点的树，对于这棵树中的一个连通块，它的能量为它拥有的节点中编号连续的最长的一段。求大小不超过\(k\)的连通块的最大能量值。
思路：
包含若干点的最小连通块的大小是这些点按照DFS序排序后，（相邻点之间距离和+首尾两点距离）/2+1。
使用尺取法枚举连续段，同时用set按照DFS序维护这些结点，同时维护每一时刻连通块的大小即可。
时间复杂度\(\mathcal O(n\log n)\)。
源代码：
#include<set>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=1e5+1,logN=17;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
int dfn[N],id[N],tmp,dep[N],anc[N][logN];
inline int lg2(const float &x) {
return ((unsigned&)x>>23&255)-127;
}
void dfs(const int &x,const int &par) {
anc[x][0]=par;
dep[x]=dep[par]+1;
id[dfn[x]=++dfn[0]]=x;
for(register int i=1;i<=lg2(dep[x]);i++) {
anc[x][i]=anc[anc[x][i-1]][i-1];
}
for(auto &y:e[x]) {
if(y==par) continue;
dfs(y,x);
}
}
inline int lca(int x,int y) {
if(dep[x]<dep[y]) std::swap(x,y);
for(register int i=lg2(dep[x]-dep[y]);i>=0;i--) {
if(dep[anc[x][i]]>=dep[y]) x=anc[x][i];
}
for(register int i=lg2(dep[x]);i>=0;i--) {
if(anc[x][i]!=anc[y][i]) {
x=anc[x][i];
y=anc[y][i];
}
}
return x==y?x:anc[x][0];
}
inline int dist(const int &x,const int &y) {
const int z=lca(x,y);
return dep[x]+dep[y]-dep[z]*2;
}
std::set<int> set;
inline void ins(const int &x) {
const auto p=--set.lower_bound(x);
const auto q=set.upper_bound(x);
if(*p!=INT_MIN) tmp+=dist(id[x],id[*p]);
if(*q!=INT_MAX) tmp+=dist(id[x],id[*q]);
if(*p!=INT_MIN&&*q!=INT_MAX) tmp-=dist(id[*p],id[*q]);
set.insert(x);
}
inline void del(const int &x) {
const auto p=--set.lower_bound(x);
const auto q=set.upper_bound(x);
if(*p!=INT_MIN) tmp-=dist(id[x],id[*p]);
if(*q!=INT_MAX) tmp-=dist(id[x],id[*q]);
if(*p!=INT_MIN&&*q!=INT_MAX) tmp+=dist(id[*p],id[*q]);
set.erase(x);
}
inline int dist2() {
const int x=*++set.begin();
const int y=*++set.rbegin();
if(x==INT_MIN||y==INT_MAX) return 0;
return dist(id[x],id[y]);
}
int main() {
const int n=getint(),k=getint();
for(register int i=1;i<n;i++) {
add_edge(getint(),getint());
}
dfs(1,0);
int ans=0;
set.insert(INT_MAX);
set.insert(INT_MIN);
ins(1);
for(register int p=1,q=1;q<=n;ins(dfn[++q])) {
while((tmp+dist2())/2+1>k) del(dfn[p++]);
ans=std::max(ans,q-p+1);
}
printf("%d\n",ans);
return 0;
}