noip83
2021/10/27 6:39:35
本文主要是介绍noip83，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
考试过程：这次考试，总体来说难度是不大的，我觉得前两题是可做的，首先是第一题，我觉得是个线段树板子题，也没多想，就是数据范围有点大，但是我没什么好方法优化，就打了个线段树走了。
然后是T2，首先想出了\(o(n\times log(n))\)求出以1为根的答案，然后考虑移动。不难发现，当根节点移动一次时，答案相对于上一次的变化量由两部分组成：
1.当前点为根的子树内的点的\(w\)小于上一次的根节点的\(w\)的数量。
2.除去当前点为根的子树，剩下的点中\(w\)小于当前根节点的数量。
但是我在考场上想复杂了，这是我经过优化之后的想法，当时的做法还要考虑每个子树对当前点的贡献，比较复杂，打了个树套树，但是卡在最后一个问题没有解决。就是如何在总复杂度在\(O(n\times log(n))\)左右求出以每个点为根的子树内\(w\)值小于当前根节点的点的个数。
考虑解决这个问题：因为主席树可以支持查询区间第\(k\)大，那么我们可以在\(dfs\)序上建一颗主席树，那么显然我们把\(w\)数组经过离散化之后就知道了\(w\)的排名，那么我们直接在主席树上查询即可。
剩下的T3，T4没什么时间做了，就打了个暴力。
T1 树上的数
思路：因为5e6的数据带个\(log\)达到了\(1e8\)级别，在那个超快的评测机上根本过不去，但是线段树无法进行优化，考虑另外的思路。
思考如果我们要打暴力，那么应该是从当前根节点往下递归，统计出当前子树的大小。
考虑优化这个过程，我们可以对经过的节点打上标记，这样我们就不会经过重复的节点，这样的复杂度是\(o(n+m)\)的。
代码如下：
AC_code
#include<bits/stdc++.h>
#define re register int
#define ii inline int
#define iv inline void
#define next netetet
#define head heaeaea
using namespace std;
const int N=5e6+10;
int n,m,tot,ans,sum;
int to[N],next[N],head[N],Q[N];
int fa,q,l,r;
bool vis[N];
ii read()
{
int x=0;char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?(x):(-x);
}
iv check(int st)
{
vis[st]=1;--sum;
for(re i=head[st];i;i=next[i]) if(!vis[to[i]]) check(to[i]);
}
int main()
{
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
int a,b,x,y;
n=read(),m=read();
a=read(),b=read();
fa=1;
to[++tot]=2;
next[tot]=head[1];
head[1]=tot;
for(re i=3;i<=n;++i)
{
fa=((1ll*fa*a+b)^19760817)%(i-1)+1;
to[++tot]=i;
next[tot]=head[fa];
head[fa]=tot;
}
q=read(),x=read(),y=read();
sum=n;
for(re i=1;i<=m;i++)
{
if(!sum) break;
if(i!=1) q=(((1ll*q*x+y)^19760817)^(i<<1))%(n-1)+2;
if(!vis[q])
{
l=1,r=0;
Q[++r]=q;
while(l<=r)
{
int now=Q[l++];
vis[now]=1;
--sum;
for(re j=head[now];j;j=next[j])
{
if(!vis[to[j]]) Q[++r]=to[j];
}
}
}
ans^=sum;
}
printf("%d\n",ans);
return 0;
}
T2 时代的眼泪
思路：首先想出了\(o(n\times log(n))\)求出以1为根的答案，然后考虑移动。不难发现，当根节点移动一次时，答案相对于上一次的变化量由两部分组成：
1.当前点为根的子树内的点的\(w\)小于上一次的根节点的\(w\)的数量。
2.除去当前点为根的子树，剩下的点中\(w\)小于当前根节点的数量。
但是我在考场上想复杂了，这是我经过优化之后的想法，当时的做法还要考虑每个子树对当前点的贡献，比较复杂，打了个树套树，但是卡在最后一个问题没有解决。就是如何在总复杂度在\(O(n\times log(n))\)左右求出以每个点为根的子树内\(w\)值小于当前根节点的点的个数。
考虑解决这个问题：因为主席树可以支持查询区间第\(k\)大，那么我们可以在\(dfs\)序上建一颗主席树，那么显然我们把\(w\)数组经过离散化之后就知道了\(w\)的排名，那么我们直接在主席树上查询即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
#define next netetetetet
using namespace std;
const int N=1e6+10;
int n,q,tot,cnt,timi,zx;
int w[N],fa[N],lsh[N],dfn[N],size[N],root[N];
ll ans[N],he[N];
int to[N<<1],next[N<<1],head[N];
ii read()
{
int x=0;char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?(x):(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
struct Segment_Tree
{
#define mid ((l+r)>>1)
int sum[N<<2],lc[N<<2],rc[N<<2];
ii insert(int las,int l,int r,int p)
{
int now=++zx;
lc[now]=lc[las];
rc[now]=rc[las];
if(l==r)
{
sum[now]=sum[las]+1;
return now;
}
if(mid>=p) lc[now]=insert(lc[las],l,mid,p);
else rc[now]=insert(rc[las],mid+1,r,p);
sum[now]=sum[lc[now]]+sum[rc[now]];
return now;
}
ll query(int las,int now,int l,int r,int z)
{
if(l==r) return (l==z)?0:sum[now]-sum[las];
int out=0;
if(mid<z)
return sum[lc[now]]-sum[lc[las]]+query(rc[las],rc[now],mid+1,r,z);
return query(lc[las],lc[now],l,mid,z);
}
#undef mid
}T;
struct Seg
{
int sum[N<<1];
iv add(int x) {for(;x<=cnt;x+=(x&(-x))) ++sum[x];}
iv del(int x) {for(;x<=cnt;x+=(x&(-x))) --sum[x];}
ll query(int x)
{
int out=0;
for(;x;x-=(x&(-x))) out+=sum[x];
return out;
}
}S;
iv dfs(int st,int f)
{
dfn[st]=++timi;
size[st]=1;
root[timi]=T.insert(root[timi-1],1,cnt,w[st]);
S.add(w[st]);
ans[1]+=S.query(cnt)-S.query(w[st]);
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f) continue;
dfs(p,st);
size[st]+=size[p];
S.del(w[p]);
}
}
iv check(int st,int f)
{
if(st!=1)
{
ll now=ans[f];
now-=T.query(root[dfn[st]-1],root[dfn[st]+size[st]-1],1,cnt,w[f]);
now+=he[w[st]-1]-T.query(root[dfn[st]-1],root[dfn[st]+size[st]-1],1,cnt,w[st]);
ans[st]=now;
}
for(re i=head[st];i;i=next[i])
{
if(to[i]==f) continue;
check(to[i],st);
}
}
signed main()
{
freopen("tears.in","r",stdin);
freopen("tears.out","w",stdout);
n=read(),q=read();
for(re i=1;i<=n;i++) w[i]=read(),lsh[i]=w[i];
sort(lsh+1,lsh+n+1);
cnt=unique(lsh+1,lsh+n+1)-lsh-1;
for(re i=1;i<=n;i++)
{
w[i]=lower_bound(lsh+1,lsh+cnt+1,w[i])-lsh;
++he[w[i]];
}
for(re i=1;i<=cnt;i++) he[i]+=he[i-1];
int x,y;
for(re i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
dfs(1,0);
check(1,0);
while(q--)
{
x=read();
printf("%lld\n",ans[x]);
}
return 0;
}
T3 传统艺能
思路，先考虑没有修改的情况，设\(f_{i,a}\)表示考虑前\(i\)个位置，以\(a\)为结尾的方案数，那么转移是这样的\(f_{i,a}=f_{i-1,a}+f_{i-1,b}+f_{i-1,c}+1,f_{i,b}=f_{i-1,b},f_{i,c}=f_{i-1,c}\),其余情况同理。
那么这样的转移是\(o(n)\)的，考虑优化。不难发现我们的转移可以写成矩阵乘的形式，
以\(A\)结尾为例：
1 0 0 0
1 1 0 0
1 0 1 0
1 0 0 1
一到三行分别表示\(A,B,C\),最后一行表示\(1\).
因为有修改和区间查询，那么我们可以考虑用线段树维护这个东西。
线段树的每个叶子几点都是一个矩阵，上面的节点维护矩阵相乘的结果。那么修改操作就是单点修改。
对于询问操作，我们可以定义一个初始矩阵\(0 0 0 1\)表示\(A,B,C,1\)，将初始矩阵与线段树进行区间查询的矩阵相乘即可。但是我们发现答案就是线段树上矩阵的第四行的前三列的加和，那么我们直接输出即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
using namespace std;
const int N=1e5+10;
const int mo=998244353;
int n,m;
long long ans;
char s[N],c[N];
ii read()
{
int x=0;char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?(x):(-x);
}
struct mat
{
int a[5][5];
};
mat calc(mat x,mat y)
{
mat z;
memset(z.a,0,sizeof(z.a));
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
for(re k=1;k<=4;k++)
{
z.a[i][j]=(z.a[i][j]+1ll*x.a[i][k]*y.a[k][j])%mo;
}
}
}
return z;
}
struct Segment_Tree
{
#define mid ((l+r)>>1)
#define lc (rt<<1)
#define rc (rt<<1|1)
mat sum[N<<2];
iv pp(int rt)
{
sum[rt]=calc(sum[lc],sum[rc]);
}
iv build(int rt,int l,int r)
{
if(l==r)
{
if(s[l]=='A')
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==1) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
else if(s[l]=='B')
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==2) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
else
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==3) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
return;
}
build(lc,l,mid),build(rc,mid+1,r);
pp(rt);
}
iv change(int rt,int l,int r,int p)
{
if(l==r)
{
if(s[l]=='A')
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==1) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
else if(s[l]=='B')
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==2) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
else
{
for(re i=1;i<=4;i++)
{
for(re j=1;j<=4;j++)
{
if(i==3) sum[rt].a[j][i]=1;
else
{
if(j==i) sum[rt].a[j][i]=1;
else sum[rt].a[j][i]=0;
}
}
}
}
return;
}
if(mid>=p) change(lc,l,mid,p);
else change(rc,mid+1,r,p);
pp(rt);
}
mat query(int rt,int l,int r,int L,int R)
{
if(L<=l and r<=R) return sum[rt];
if(mid>=R) return query(lc,l,mid,L,R);
if(mid<L) return query(rc,mid+1,r,L,R);
return calc(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
}
#undef mid
#undef lc
#undef rc
}T;
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
n=read(),m=read();
scanf("%s",s+1);
T.build(1,1,n);
int opt,x,y;
while(m--)
{
opt=read();
if(opt==1)
{
x=read();
scanf("%s",c+1);
if(s[x]==c[1]) continue;
s[x]=c[1];
T.change(1,1,n,x);
}
else
{
x=read(),y=read();
mat ans=T.query(1,1,n,x,y);
printf("%lld\n",(ans.a[4][1]+ans.a[4][2]+ans.a[4][3])%mo);
}
}
return 0;
}
T4 铺设道路
注意是差分的过程，所以要算\(n+1\)项。
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define re int
#define ii inline int
#define iv inline void
#define f() cout<<"fuck"<<endl
using namespace std;
const int N=3e5+10;
const int mo=1e9+7;
int n,ans,mx,mn;
int d[N],b[N],c[N];
queue<int> q;
stack<int> s;
ii read()
{
int x=0;char ch=getchar(); bool f=1;
while(ch<'0' or ch>'9')
{
if(ch=='-') f=0;
ch=getchar();
}
while(ch>='0' and ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?(x):(-x);
}
signed main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
n=read();
for(re i=1;i<=n;i++) d[i]=read();
for(re i=1;i<=n+1;i++) b[i]=d[i]-d[i-1],c[i]=b[i];
for(re i=1;i<=n+1;i++) ans=ans+max(0ll,b[i]);
printf("%lld\n",ans);
for(re i=1;i<=n+1;i++)
{
if(b[i]>0) q.push(i),s.push(i);
else
{
if(b[i]==0) continue;
int tmp=-b[i];
while(tmp>0 and q.size())
{
if(b[q.front()]<=tmp)
{
tmp-=b[q.front()];
mx=(mx+(i-q.front())*(i-q.front())%mo*b[q.front()])%mo;
q.pop();
}
else
{
mx=(mx+(i-q.front())*(i-q.front())%mo*(tmp))%mo;
b[q.front()]-=tmp;
break;
}
}
tmp=-c[i];
while(tmp>0 and s.size())
{
if(c[s.top()]<=tmp)
{
tmp-=c[s.top()];
mn=(mn+(i-s.top())*(i-s.top())%mo*c[s.top()])%mo;
s.pop();
}
else
{
mn=(mn+(i-s.top())*(i-s.top())%mo*(tmp))%mo;
c[s.top()]-=tmp;
break;
}
}
}
}
printf("%lld\n%lld\n",mn,mx);
return 0;
}
这篇关于noip83的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
