初三奥赛模拟测试一

陈年老题了

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;
}