初三奥赛模拟测试一

陈年老题了

T1 回文 $ 79pts/100pts $

典，建议回去做传纸条

部分分是双向搜索

正解从左上角右下角分别DP,开三维，分别记录上面的点向下走次数，下面的向上走步数和目前走的总步数即可，时空复杂度$(nm*(n+m))$，开long long会MLE,所以把记录步数的$(n+m)$滚掉(其实也可以开unsigned int)

最后统计答案的时候分讨n+m奇偶算一下即可

赛时写正解x,y写反了，遂挂分，寄！

CODE

#include<bits/stdc++.h>
using namespace std;
const long long mod=993244853;
long long n,m,step,ans[510][510],nxt[510][510],r,x,y,nowx[510][2],nowy[510][2],sz,last;
char us[510][510];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf(" %s",us[i]+1);
    step=n+m-1;
    if(us[1][1]==us[n][m])
        nxt[1][1]=1;
    else   
    {
        puts("0");
        return 0;
    }
	nowx[1][0]=nowy[1][0]=1;
	nowx[1][1]=n,nowy[1][1]=m;
	sz=1;
for(int i=2;i<=step/2;i++)
    {
        for(int j=1;j<=sz;j++)
		{
			nowy[j][0]++;
			nowy[j][1]--;
		}
		if(nowx[sz][0]<=n)
		{
			sz++,nowy[sz][0]=1,nowx[sz][0]=nowx[sz-1][0]+1;
			nowy[sz][1]=m,nowx[sz][1]=nowx[sz-1][1]-1;
		}
		for(int j=1;j<=sz;j++)
		{
			for(int k=1;k<=sz;k++)
			{
				if(us[nowx[j][0]][nowy[j][0]]==us[nowx[k][1]][nowy[k][1]])
					ans[j][k]=(nxt[j-1][k-1]+nxt[j-1][k]+nxt[j][k]+nxt[j][k-1])%mod;
				else
					ans[j][k]=0;
			}
		}
		for(int j=1;j<=sz;j++)
			for(int k=1;k<=sz;k++)
				nxt[j][k]=ans[j][k];
    }
	if(step%2==0)
		for(int j=1;j<=sz;j++)
			for(int k=1;k<=sz;k++)
				if(us[nowx[j][0]][nowy[j][0]]==us[nowx[k][1]][nowy[k][1]])
				{
					if(nowx[j][0]+1==nowx[k][1]&&nowy[j][0]==nowy[k][1])
						last=(ans[j][k]+last)%mod;
					if(nowx[j][0]==nowx[k][1]&&nowy[j][0]+1==nowy[k][1])
						last=(ans[j][k]+last)%mod;
				}
	if(step%2==1)
	{
		for(int j=1;j<=sz;j++)
			for(int k=1;k<=sz;k++)
				if(us[nowx[j][0]][nowy[j][0]]==us[nowx[k][1]][nowy[k][1]])
				{
					if(nowx[j][0]+2==nowx[k][1]&&nowy[j][0]==nowy[k][1])
						last=(ans[j][k]+last)%mod;
					if(nowx[j][0]==nowx[k][1]&&nowy[j][0]+2==nowy[k][1])
						last=(ans[j][k]+last)%mod;
					if(nowx[j][0]+1==nowx[k][1]&&nowy[j][0]+1==nowy[k][1])
						last=(ans[j][k]*2+last)%mod;
				}
	}
	printf("%lld\n",last);
    return 0;
}

T2 快速排序 $36pts/100pts$

没看懂伪代码，遂看真代码

真代码

struct number
{
	bool isnan;
	int value;
};
bool operator < (const number& x, const number& y)
{
	if(x.isnan || y.isnan)
		return false;
	return x.value < y.value;
}
number tmp[1 << 20];
void qsort(number* _begin, number* _end)
{
	if(_begin + 1 >= _end)
		return;
	number a = *_begin, *s = _begin, *t = tmp;
	for(number* p = _begin + 1; p < _end; p++)
	{
		if(*p < a)*s = *p, s++;
		else *t = *p, t++;
	}
	*s = a, s++;
	for(t--; t >= tmp; t--) *(s + (t - tmp)) = *t;
	qsort(_begin, s - 1);
	qsort(s, _end);
}

喜欢用指针是吧，我也喜欢用

翻译过来就是每次排序从头开始，如果当前数为$nan$，就直接跳过，否则将所有在当前数后面且小于当前数的数放到该数前面，然后正常排序

首先这代码是不能直接用的，因为关于$nan$的小于运算不满足不反性，发现$nan$不影响数字的排序，STL给数排一遍序，之后遇到数字就把小于该数的剩余全部数字升序输出，有$nan$直接输出即可

赛时脑抽没判数输出完的边界，挂了$64pts$

CODE

#include<bits/stdc++.h>
using namespace std;
long long t,n,l,num,s[1000100],siz=1,save[1000100],maxx=1,p;
char in[20];
int main()
{
    /*#ifndef ONLINE_JUDGE
        freopen("2.in","r",stdin);
        freopen("2.out","w",stdout);
    #endif*/
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        maxx=siz=1;
        for(int i=1;i<=n;i++)
        {
            save[i]=0;
            scanf(" %s",in);
            num=0;
            if(in[0]>='0'&&in[0]<='9')//nan全部作为0存在save数组里
            {
                l=strlen(in);
                for(int j=0;j<l;j++)
                    num=num*10+in[j]-'0';
                s[siz]=num;
                save[i]=num;
                siz++;
            }
        }
        sort(s+1,s+siz),p=1;
        s[siz]=1e18; 
        for(int i=1;i<=n;)
        {
            if(save[i]>=maxx)
            {
                while(save[i]!=0) 
                {
                    maxx=max(maxx,save[i]);
					while(s[p]<maxx) printf("%lld ",s[p]),p++;
					if(save[i]==maxx) 
               			printf("%lld ",s[p]),p++;
					i++;
					if(i>n)
                        break;
                }
            }
            else
            {
                while(save[i]<maxx) 
                {
                    if(save[i]==0)
                        printf("nan ");
                    i++;
                    if(i>n)
                        break;
                }
            }
        }
        puts("");
    }
    return 0;
}

T3 混乱邪恶 $0pts/20pts$

赛时暴力全$Re$了

正解是这样的首先容易发现当符合题意时一定有解，可以通过数学归纳法证明（就是下面过程）

先按升序排序

首先考虑$m=n$的部分分，通过简单构造可以发现当$m=n$时一定有解，若$2 \mid n$,可以通过将相邻两个分成一组，取异号得到若干个$1$,否则在$1$的前面添上$0$转换为偶数情况

若 $n<m$ 则依然按照上述方法分组,但是会出现若干结果比一大的组，使用等于一的组消去即可，因为$n > \left\lfloor \frac{2m}{3} \right\rfloor $所以可以证明这样一定有一组解

还有一个贪心乱搞做法正确率很高，贴代码

CODE（贪心）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
long long n,m,c[N],last,ans[N];
struct Node
{
	int val,id;
}e[N];
bool cmp(Node & u, Node & v)
{return u.val<v.val;}
void output()
{
	for(int i=1;i<=n;i++)
		if(ans[i]==1)
			printf("1 ");
		else	
			printf("-1 ");
}
bool solve(int st,long long now)
{
	if(now==last){output();return 1;}
	if(st<=0)	return 0;
	if(now+e[st].val<=last){ans[e[st].id]=1;return solve(st-1,now+e[st].val);}
	else return solve(st-1,now);
}
int main()
{
	#ifndef ONLINE_JUDGE
	    freopen("1.in","r",stdin);
	    freopen("1.out","w",stdout);
	#endif
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&e[i].val),e[i].id=i;
	sort(e+1,e+1+n,cmp);
	long long sum=0;
	for(int i=1;i<=n;i++)
		sum+=e[i].val;
	last=sum/2;
	puts("NP-Hard solved");
	for(int i=n;i>=1;i--)
		if(solve(i,0))	return 0;
		else memset(ans,0,sizeof(ans));
	return 0;
}

T4 校门外歪脖子树上的鸽子 $0pts/0pts$

树剖题，这题就是标记永久化，但不上传标记递归寻找修改节点显然不行修改思路考虑参考张昆伟树，区别就是张昆伟树是满二叉树

区间修改：闭区间转开区间，共同向上跳
比如这棵树

修改2——4
转化为1——5（开区间），1是左儿子，修改2；5是右儿子，修改4；6也是右儿子，修改3，8和7互为兄弟，停止修改

具体内容可以看下面代码

张昆伟树

struct ZKW_SEGMENT_TREE
{
    long long tag[N<<2],node[N<<2],leaf,siz;
    void build()//建树，leaf存第一个结点的编号
    {
        for(int i=1;i<=siz;i++)
            node[leaf+i]=tree.q[tree.is[i]];
        for(int i=leaf-1;i>=1;i--)
            node[i]=node[i<<1]+node[(i<<1)|1];
    }
    void change(int x,int y,int delta)
    {
        long long numx=0,numy=0,now=1;
        x=leaf+x-1,y=leaf+y+1;//开区间转闭区间
        while((x^1)!=y)//改到x,y互为兄弟
        {
            node[x]+=numx*delta,node[y]+=numy*delta;//numx和numy是目前节点子树内修改值的和，上传标记
            if(x&1^1)    tag[x^1]+=delta,node[x^1]+=delta*now,numx+=now;//x^1是x的兄弟，若左边是左儿子就修改兄弟
            if(y&1)     tag[y^1]+=delta,node[y^1]+=delta*now,numy+=now;
            x>>=1,y>>=1,now<<=1;//x,y向上跳父亲，now是当前层节点所代表元素个数
        }
        while(x)//上传标记，去掉这里即和本题修改逻辑一样
            node[x]+=numx*delta,node[y]+=numy*delta,x>>=1,y>>=1;
    }
    long long find_value(int x,int y)
    {
        long long ans=0,t1=0,t2=0,now=1;
        x=leaf+x-1,y=leaf+y+1;
        while((x^1)!=y)
        {
            ans+=t1*tag[x],ans+=t2*tag[y];
            if(x&1^1)   ans+=node[x^1],t1+=now;
            if(y&1)     ans+=node[y^1],t2+=now;
            x>>=1,y>>=1,now<<=1;
        }
        while(x)//这里的统计标记和修改同理
            ans+=t1*tag[x],ans+=t2*tag[y],x>>=1,y>>=1;
        return ans;
    }
}s_tree;

之后就是优化复杂度，因为这样跳复杂度依然是深度级别，无法通过本题；但是我们发现，修改时两个端点的路径是两条链

因为无论查询还是修改，都需要自己的兄弟在链上，所以直接将每个结点的信息存在其兄弟节点上，树剖维护即可，一些细节和特判可以看代码

CODE

#include<bits/stdc++.h>
#define N 401000
#define mid ((st+ed)>>1)
using namespace std;
long long n,m,ls[N],rs[N],f[N],lb[N],rb[N],leaf,root,op,a,b,c,lca,ansroot;
bool judge[N];
struct TREE
{
    long long top[N],siz[N],dep[N],in[N],is[N],fa[N],sz,num[N];
    void dfs(int now,int h)
    {
        siz[now]=1;
        dep[now]=h;
        if(now<=n){ num[now]=1;return;}
        dfs(ls[now],h+1);
        dfs(rs[now],h+1);
        num[now]=num[ls[now]]+num[rs[now]];
        siz[now]=1+siz[ls[now]]+siz[rs[now]];
        if(siz[ls[now]]<siz[rs[now]])
            swap(ls[now],rs[now]);
    }
    void build(int now,int t)
    {
        top[now]=t;
        sz++,in[now]=sz,is[sz]=now;
        if(now<=n)
            return;
        build(ls[now],t);
        build(rs[now],rs[now]);
    }
}tree;
struct SEGMENT_TREE
{
    long long tag[N<<2],node[N<<2],tms[N<<2];
    void push_down(int now)
	{
        if(tag[now]==0)
            return;
        tag[now<<1]+=tag[now],tag[(now<<1)|1]+=tag[now];
        node[now<<1]+=tag[now]*tms[now<<1],node[(now<<1)|1]+=tag[now]*tms[(now<<1)|1];
        tag[now]=0;
	}
    void change(int now,int st,int ed,int x,int y,long long v)
	{
		if(st>=x&&ed<=y)
        {
            tag[now]+=v;
            node[now]+=v*tms[now];
            return;
        }
        if(st>y||ed<x)
            return;
        push_down(now);
        change(now<<1,st,mid,x,y,v);
        change((now<<1)|1,mid+1,ed,x,y,v);
        node[now]=node[now<<1]+node[(now<<1)|1];
	}
	long long find_sum(int now,int st,int ed,int x,int y)
	{
		if(st>=x&&ed<=y)
            return node[now];
        if(st>y||ed<x)
            return 0;
        push_down(now);
        return find_sum(now<<1,st,mid,x,y)+find_sum((now<<1)|1,mid+1,ed,x,y);
	}
}s_treel,s_treer;
void s_build(int now,int st,int ed)
{
    if(st==ed)
    {
        s_treel.tms[now]=tree.num[lb[tree.is[st]]];
        s_treer.tms[now]=tree.num[rb[tree.is[st]]];
        return;
    }
    s_build(now<<1,st,mid);
    s_build((now<<1)|1,mid+1,ed);
    s_treel.tms[now]=s_treel.tms[now<<1]+s_treel.tms[(now<<1)|1];
    s_treer.tms[now]=s_treer.tms[now<<1]+s_treer.tms[(now<<1)|1];
}
int find_LCA(int x,int y)
{
    if(tree.dep[x]<tree.dep[y])
        swap(x,y);
    while(tree.top[x]!=tree.top[y])
	{
		if(tree.dep[tree.top[x]]<tree.dep[tree.top[y]])
			swap(x,y);
        x=f[tree.top[x]];
	}
	if(tree.dep[x]>tree.dep[y]) 
		return y;
    return x;
}
void modify(int x,int y,SEGMENT_TREE & s_tree,long long delta)
{
    while(tree.top[x]!=tree.top[y])
	{
		s_tree.change(1,1,2*n-1,tree.in[tree.top[x]],tree.in[x],delta);
        x=f[tree.top[x]];
	}
	s_tree.change(1,1,2*n-1,tree.in[y]+1,tree.in[x],delta);
}
long long ask(int x,int y,SEGMENT_TREE & s_tree)
{
    long long ans=0;
    while(tree.top[x]!=tree.top[y])
	{
		ans+=s_tree.find_sum(1,1,2*n-1,tree.in[tree.top[x]],tree.in[x]);
        x=f[tree.top[x]];
	}
	ans+=s_tree.find_sum(1,1,2*n-1,tree.in[y]+1,tree.in[x]);
    return ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
	    freopen("1.in","r",stdin);
	    freopen("1.out","w",stdout);
	#endif
    scanf("%lld%lld",&n,&m);
    for(int i=n+1;i<n*2;i++)
    {
        scanf("%lld%lld",&ls[i],&rs[i]);
        f[ls[i]]=f[rs[i]]=i;
        lb[rs[i]]=ls[i];
        rb[ls[i]]=rs[i];
        judge[ls[i]]=judge[rs[i]]=1;
    }
    for(int i=n+1;i<n*2;i++)
        if(judge[i]==0)
        {
            root=i;
            break;
        }
    tree.dfs(root,0);
    tree.build(root,root);
    s_build(1,1,2*n-1);
    ls[0]=rs[0]=root;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&op);
        if(op==1)
        {
            scanf("%lld%lld%lld",&a,&b,&c);
            a=a-1,b=b+1;
            if(a==0&&b==n+1){ansroot+=c*n;continue;}
            if(a==0){modify(b,root,s_treel,c);continue;}
            if(b==n+1){modify(a,root,s_treer,c);continue;}
            lca=find_LCA(a,b);
            if(tree.in[ls[lca]]<tree.in[a]&&tree.in[ls[lca]]+tree.siz[ls[lca]]>=tree.in[a]+tree.siz[a])
                modify(a,ls[lca],s_treer,c),modify(b,rs[lca],s_treel,c);
            else
                modify(a,rs[lca],s_treer,c),modify(b,ls[lca],s_treel,c);
        }
        if(op==2)
        {
            scanf("%lld%lld",&a,&b);
            a=a-1,b=b+1;
            if(a==0&&b==n+1){printf("%lld\n",ansroot);continue;}
            if(a==0){printf("%lld\n",ask(b,root,s_treel));continue;}
            if(b==n+1){printf("%lld\n",ask(a,root,s_treer));continue;}
            lca=find_LCA(a,b);
            if(tree.in[ls[lca]]<tree.in[a]&&tree.in[ls[lca]]+tree.siz[ls[lca]]>=tree.in[a]+tree.siz[a])
                printf("%lld\n",ask(a,ls[lca],s_treer)+ask(b,rs[lca],s_treel));
            else
                printf("%lld\n",ask(a,rs[lca],s_treer)+ask(b,ls[lca],s_treel));
        }
    }
    return 0;
}

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

初三奥赛模拟测试一

初三奥赛模拟测试一

T1 回文 $ 79pts/100pts $

T2 快速排序 \(36pts/100pts\)

T3 混乱邪恶 \(0pts/20pts\)

T4 校门外歪脖子树上的鸽子 \(0pts/0pts\)

初三奥赛模拟测试一

初三奥赛模拟测试一

T1 回文 $ 79pts/100pts $

T2 快速排序 \(36pts/100pts\)

T3 混乱邪恶 \(0pts/20pts\)

T4 校门外歪脖子树上的鸽子 \(0pts/0pts\)

相关文章

面试官：如果不允许线程池丢弃任务，应该选择哪个拒绝策略？

关于js数组方法sort()负数排序的陷阱

有几种获取session值的方法在html页面中？方法总结！

Django怎么使用channels + websocket打造在线聊天室