初三奥赛模拟测试一
陈年老题了
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;
}
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
