【比赛报告】2018.10.23[长乐一中Day2] NOIP练习赛卷二十

比赛时间：2018.10.23 选手：lrllrl 得分：100+0+0=100 用时：40min

对中序遍历得到的序列求一个n-最长不下降子序列，用nlogn算法求

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,w[N],ch[N][2],tot,cnt,a[N],vis[N],b[N],tl;
void dfs(int x)
{
	if(ch[x][0]&&!vis[ch[x][0]])dfs(ch[x][0]);
	a[++tot]=w[x]-tot;vis[x]=1;
	if(ch[x][1]&&!vis[ch[x][1]])dfs(ch[x][1]);
}
int main()
{
	//freopen("binary.in","r",stdin);
	//freopen("binary.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d",&w[i]);
	for(int i=2,d,fa;i<=n;i++)
	    scanf("%d%d",&fa,&d),ch[fa][d]=i;
	dfs(1);b[1]=a[1];tl=1;
	for(int i=2;i<=n;i++)
	{
		if(a[i]>=b[tl])b[++tl]=a[i];
		else
		{
			int l=1,r=tl,mid;
			while(l<=r)
			{
				int mid=l+r>>1;
				if(b[mid]<=a[i])l=mid+1;
				else r=mid-1;
			}
			b[l]=a[i];
		}
	}
	printf("%d\n",n-tl);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

【比赛报告】2018.10.23[长乐一中Day2] NOIP练习赛卷二十

直接硬怼ST算法，二分答案判断区间最小值是否等于区间最大公约数

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
	int s=0,f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	if(f)s=-s;return s;
}
const int N=5e5+10;
int n,m,a[N],f[N][25],g[N][25],ans[N],cnt;
inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline bool check(int mid)
{
	int k=log2(mid--);
	for(int l=1,r;l<=n-(1<<k)+1;l++)
	{
		r=l+mid;
		if(min(f[l][k],f[r-(1<<k)+1][k])==gcd(g[l][k],g[r-(1<<k)+1][k]))return 1;
	}
	return 0;
}
int main()
{
	//freopen("in.txt","r",stdin);
    n=read();m=log2(n);
    for(int i=1;i<=n;i++)
        a[i]=read();
    for(int i=1;i<=n;i++)
        f[i][0]=g[i][0]=a[i];
    for(int j=1;j<=m;j++)
    {
    	for(int i=1;i<=n-(1<<j)+1;i++)
    	{
    		f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    		g[i][j]=gcd(g[i][j-1],g[i+(1<<(j-1))][j-1]);
		}
	}
	int l=1,r=n;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))l=mid+1;
		else r=mid-1;
	}
	if(r==1)
	{
		printf("%d 0\n",n);
		for(int i=1;i<=n;i++)
		    printf("%d ",i);
		return 0;
	}
	int k=log2(r--);int len=r;
	for(l=1,r;l<=n-(1<<k)+1;l++)
	{
		r=l+len;
		if(min(f[l][k],f[r-(1<<k)+1][k])==gcd(g[l][k],g[r-(1<<k)+1][k]))ans[++cnt]=l;
	}
	printf("%d %d\n",cnt,len);
	for(int i=1;i<=cnt;i++)
	    printf("%d ",ans[i]);
	return 0;
}

【比赛报告】2018.10.23[长乐一中Day2] NOIP练习赛卷二十

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int n,dp[52][52],C[52][52],p[52];
//dp[len][low]代表长度为len，low,low+1,...low+len-1且为p的子序列的排列上优美序列的个数 
int dfs(int len,int low)
{
	if(dp[len][low]!=-1)return dp[len][low];
	if(len==1)return dp[len][low]=1;
	int &res=dp[len][low];res=0;
	int t[52],m=0,j,k;
	for(int i=1;i<=n;i++)
	    if(p[i]>=low&&p[i]<low+len)
	        t[++m]=p[i];
	for(int i=1;i<m;i++)//枚举交换相邻元素 
	{
		swap(t[i],t[i+1]);
		for(j=1;j<=i;j++)
		    if(t[j]>=low+i)break;
		for(k=i+1;k<=m;k++)
		    if(t[k]<low+i)break;
		if(j>i&&k>m)//是不是前面都小后面都大 
		{
			ll tmp=1ll*dfs(i,low)*dfs(m-i,low+i)%mod;
			tmp=tmp*1ll*C[m-2][m-i-1]%mod;//左右两边还要进行交换的组合数 
			//相当于n-2个位置选择n-1-k个位置填入
			res=(0ll+res+tmp)%mod;
		}
		swap(t[i],t[i+1]);
	}
	return res;
}
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d",&n);
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
	    scanf("%d",&p[i]);
	for(int i=0;i<=n;i++)//递推求组合数 
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++)
		    C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
	dfs(n,0);//倒着处理 
	if(dp[n][0]!=-1)printf("%d\n",dp[n][0]);
	else puts("0");
	return 0;
}

赛后总结

T1nlogn的LIS应该掌握。T2掌握ST算法。T3掌握组合数递推+dp的状态定义与转移

【比赛报告】2018.10.23[长乐一中Day2] NOIP练习赛卷二十

赛后总结

相关推荐