NOIP模拟赛第五场（noi.ac）Solution

Posted On 2018年9月27日

A. count

Solution

只有一个数出现2次，直接组合数计数去重即可。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
#include <iostream>
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=1e5+100,P=1e9+7;
int a[maxn],jc[maxn],inv[maxn];
int vis[maxn];
inline int C(const int a,const int b){return a<b?0:1ll*jc[a]*inv[b]%P*inv[a-b]%P;}
inline int pow(int a,int b)
{
	int ans=1;
	for (;b;b>>=1)(b&1)&&(ans=1ll*ans*a%P),a=1ll*a*a%P;
	return ans;
}
signed main()
{
	int n=read(),p=0,pre=0;
	jc[0]=1;
	for (int i=1;i<=n+1;i++)jc[i]=1ll*jc[i-1]*i%P;
	inv[n+1]=pow(jc[n+1],P-2);
	for (int i=n;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;
	for (int i=1;i<=n+1;i++)a[i]=read(),vis[a[i]]?(p=i):(vis[a[i]]=i);
	pre=vis[a[p]];
	for (int i=1;i<=n+1;i++)
		printf("%d\n",(1ll*C(n+1,i)-C(n+1-p+1-1+pre-1,i-1)+P)%P);
}

#include <cstdio>

#include <cstring>

#include <cmath>

#include <bitset>

#include <iostream>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=1e5+100,P=1e9+7;

int a[maxn],jc[maxn],inv[maxn];

int vis[maxn];

inline int C(const int a,const int b){return a<b?0:1ll*jc[a]*inv[b]%P*inv[a-b]%P;}

inline int pow(int a,int b)

{

int ans=1;

for (;b;b>>=1)(b&1)&&(ans=1ll*ans*a%P),a=1ll*a*a%P;

return ans;

}

signed main()

{

int n=read(),p=0,pre=0;

jc[0]=1;

for (int i=1;i<=n+1;i++)jc[i]=1ll*jc[i-1]*i%P;

inv[n+1]=pow(jc[n+1],P-2);

for (int i=n;~i;i--)inv[i]=1ll*inv[i+1]*(i+1)%P;

for (int i=1;i<=n+1;i++)a[i]=read(),vis[a[i]]?(p=i):(vis[a[i]]=i);

pre=vis[a[p]];

for (int i=1;i<=n+1;i++)

printf("%d\n",(1ll*C(n+1,i)-C(n+1-p+1-1+pre-1,i-1)+P)%P);

}

B. delete

Solution

DP转移条件：\(i<j \ 且\ i-a[i] \leq j-a[j]\ 且\ a[i] \leq a[j]\)

那么按\(i-a[i]\)排序，求LIS即可

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <iostream>
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=2e6+100,P=1e9+7;
int a[maxn],f[maxn];
int n,k;
vector<int>v[maxn];
inline void upd(int x,const int p)
{
	for (;x<=n-k;x+=(x&-x))f[x]=max(f[x],p);
}
inline int query(int x)
{
	int ans=0;
	for (;x;x-=(x&-x))ans=max(ans,f[x]);
	return ans;
}
signed main()
{
	n=read();int ans=0;k=read();
	for (int i=1;i<=n;i++)
	{
		a[i]=read();
		if (a[i]<=i&&i-a[i]<=k)v[a[i]].push_back(i-a[i]+1); ;
	}
	for (int i=1,tmp;i<=n-k;i++)
		for (int j=v[i].size()-1;~j;j--)
		{
			ans=max(ans,tmp=query(v[i][j])+1);
			upd(v[i][j],tmp);
		}
	printf("%d\n",ans);
}

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <bitset>

#include <iostream>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=2e6+100,P=1e9+7;

int a[maxn],f[maxn];

int n,k;

vector<int>v[maxn];

inline void upd(int x,const int p)

{

for (;x<=n-k;x+=(x&-x))f[x]=max(f[x],p);

}

inline int query(int x)

{

int ans=0;

for (;x;x-=(x&-x))ans=max(ans,f[x]);

return ans;

}

signed main()

{

n=read();int ans=0;k=read();

for (int i=1;i<=n;i++)

{

a[i]=read();

if (a[i]<=i&&i-a[i]<=k)v[a[i]].push_back(i-a[i]+1); ;

}

for (int i=1,tmp;i<=n-k;i++)

for (int j=v[i].size()-1;~j;j--)

{

ans=max(ans,tmp=query(v[i][j])+1);

upd(v[i][j],tmp);

}

printf("%d\n",ans);

}

C. power

Solution

Two Pointers（值域右端点随着左端点增加不降）

维护方法：

#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <set>
#include <iostream>
typedef long long ll;
using namespace std;
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
const int maxn=1e5+100;
int last[maxn],dep[maxn],fa[maxn],siz[maxn],heavy[maxn],dfn[maxn],top[maxn],tot;
struct mc{int too,nxt;}e[maxn<<1];
void dfs(const int cur)
{
	siz[cur]=1;
	dfn[cur]=++tot;
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur])
			fa[e[i].too]=cur,
			dep[e[i].too]=dep[cur]+1,
			dfs(e[i].too),
			siz[cur]+=siz[e[i].too],siz[heavy[cur]]<siz[e[i].too]&&(heavy[cur]=e[i].too);
}
void _dfs(const int cur,const int ancestor)
{
	top[cur]=ancestor;
	if (heavy[cur])_dfs(heavy[cur],ancestor);
	for (int i=last[cur];i;i=e[i].nxt)
		if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])_dfs(e[i].too,e[i].too);
}
inline int LCA(int a,int b)
{
	while (top[a]!=top[b])
	{
		if (dep[top[a]]<dep[top[b]])swap(a,b);
		a=fa[top[a]];
	}
	return dep[a]<dep[b]?a:b;
}
inline int DIS(const int a,const int b)
{
	return dep[b]+dep[a]-dep[LCA(a,b)]*2;
}
set<pair<int,int> >s;
inline int upd(const int l,const int r,const int pos,const int delta)
{
	if (delta==1&&l>r)return 0;
	int ans=0;
	auto it=s.lower_bound(make_pair(dfn[pos],pos)),itt=s.upper_bound(make_pair(dfn[pos],pos));
	if (it!=s.begin())--it;
	else it=s.end(),--it;
	if (itt==s.end())itt=s.begin();
	ans-=DIS((*it).second,(*itt).second)*delta;
	ans+=DIS(pos,(*it).second)*delta;
	ans+=DIS(pos,(*itt).second)*delta;
	return ans;
}
signed main()
{
	int n=read(),k=read(),ans=0;
	for (int i=1;i<n;i++)
	{
		int a=read(),b=read();
		e[i<<1].too=b;e[i<<1].nxt=last[a];last[a]=i<<1;
		e[i<<1|1].too=a;e[i<<1|1].nxt=last[b];last[b]=i<<1|1;
	}
	dfs(1);
	_dfs(1,1);
	for (int l=1,r=0,tot=0;l<=n;l++)
	{
		while (r<n)
		{
			int tmp=upd(l,r,r+1,1);
			if ((tmp+tot)/2+1<=k)++r,s.insert(make_pair(dfn[r],r)),tot+=tmp;
			else break;
		}
		ans=max(ans,r-l+1);
		tot+=upd(l,r,l,-1);
		s.erase(make_pair(dfn[l],l));
	}
	printf("%d\n",ans);
}

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <bitset>

#include <set>

#include <iostream>

typedef long long ll;

using namespace std;

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

const int maxn=1e5+100;

int last[maxn],dep[maxn],fa[maxn],siz[maxn],heavy[maxn],dfn[maxn],top[maxn],tot;

struct mc{int too,nxt;}e[maxn<<1];

void dfs(const int cur)

{

siz[cur]=1;

dfn[cur]=++tot;

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur])

fa[e[i].too]=cur,

dep[e[i].too]=dep[cur]+1,

dfs(e[i].too),

siz[cur]+=siz[e[i].too],siz[heavy[cur]]<siz[e[i].too]&&(heavy[cur]=e[i].too);

}

void _dfs(const int cur,const int ancestor)

{

top[cur]=ancestor;

if (heavy[cur])_dfs(heavy[cur],ancestor);

for (int i=last[cur];i;i=e[i].nxt)

if (e[i].too!=fa[cur]&&e[i].too!=heavy[cur])_dfs(e[i].too,e[i].too);

}

inline int LCA(int a,int b)

{

while (top[a]!=top[b])

{

if (dep[top[a]]<dep[top[b]])swap(a,b);

a=fa[top[a]];

}

return dep[a]<dep[b]?a:b;

}

inline int DIS(const int a,const int b)

{

return dep[b]+dep[a]-dep[LCA(a,b)]*2;

}

set<pair<int,int> >s;

inline int upd(const int l,const int r,const int pos,const int delta)

{

if (delta==1&&l>r)return 0;

int ans=0;

auto it=s.lower_bound(make_pair(dfn[pos],pos)),itt=s.upper_bound(make_pair(dfn[pos],pos));

if (it!=s.begin())--it;

else it=s.end(),--it;

if (itt==s.end())itt=s.begin();

ans-=DIS((*it).second,(*itt).second)*delta;

ans+=DIS(pos,(*it).second)*delta;

ans+=DIS(pos,(*itt).second)*delta;

return ans;

}

signed main()

{

int n=read(),k=read(),ans=0;

for (int i=1;i<n;i++)

{

int a=read(),b=read();

e[i<<1].too=b;e[i<<1].nxt=last[a];last[a]=i<<1;

e[i<<1|1].too=a;e[i<<1|1].nxt=last[b];last[b]=i<<1|1;

}

dfs(1);

_dfs(1,1);

for (int l=1,r=0,tot=0;l<=n;l++)

{

while (r<n)

{

int tmp=upd(l,r,r+1,1);

if ((tmp+tot)/2+1<=k)++r,s.insert(make_pair(dfn[r],r)),tot+=tmp;

else break;

}

ans=max(ans,r-l+1);

tot+=upd(l,r,l,-1);

s.erase(make_pair(dfn[l],l));

}

printf("%d\n",ans);

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments