NOIP模擬83(多校16)
前言
CSP之後第一次模擬賽，感覺考的一般。
不得不吐槽多校聯測 OJ 上的評測機是真的慢。。。
T1 樹上的數
解題思路
感覺自己思維有些固化了，一看題目就感覺是線段樹。
考完之後才想起來這玩意直接 DFS 一遍就行（大霧
然後就是卡常了，最後的結果就是時限 2s 的題本機 0.6s 才在OJ上過掉，我諤諤
果然迭代比遞歸快，所以直接 BFS 就可以減小常數了QAQ
code
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=5e6+10,base=19760817;
int n,m,A,B,X,Y,q,cnt,hd,tail,que[N];
int tot=1,head[N],ver[N],nxt[N];
bool vis[N];
ll ans;
inline void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int main()
{
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
cnt=n=read(); m=read(); A=read(); B=read(); add_edge(1,2);
for(int i=3,temp=1;i<=n;i++) temp=((1ll*temp*A+B)^base)%(i-1)+1,add_edge(temp,i);
q=read(); X=read(); Y=read();
for(int i=1;i<=m;i++)
{
if(i!=1) q=(((1ll*q*X+Y)^base)^(i<<1))%(n-1)+2;
hd=1;tail=0;if(!vis[q]) que[++tail]=q;
while(hd<=tail)
{
int x=que[hd++]; vis[x]=true; cnt--;
for(int j=head[x];j;j=nxt[j])
if(!vis[ver[j]]) que[++tail]=ver[j];
}
ans^=cnt;
}
printf("%lld",ans);
return 0;
}
T2 時代的眼淚
解題思路
大概有一點換根 DP 的思想吧，但是還是卡常，吐了。
比較直接的思路就是先計算出以 1 為根的答案，然後求出每個點相對於父親節點變化的答案。
主席樹和線段樹合併的複雜度都是對的，但是都會被卡常！！！
因此需要樹狀數組，我們需要的無非就是一個全局的，一個以某棵子樹為根的答案嘛。。
對於全局總體的直接一個桶+前綴和，然後對於某顆子樹的就可以用搜索子樹之前的信息減去搜索子樹之後的信息，這樣就可以用上小常數的樹狀數組了。。
實測差距還是很大的，以後還是要注意常數問題啊。。
code
被卡成 90pts 的線段樹合併
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
#define ls tre[x].l
#define rs tre[x].r
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
inline void write(int x)
{
return printf("%lld",x),void();
#define sta number
int sta[70],top=0; if(x<0) putchar('-'),x=~(x-1);
while(x) sta[++top]=x%10,x/=10; if(!top) sta[++top]=0;
while(top) putchar(sta[top--]+'0');
#undef sta
}
const int N=1e6+10;
int n,m,lim,all,cnt,root[N],s[N],fa[N];
int tot=1,head[N],ver[N<<1],nxt[N<<1];
struct Node{ll dat;int l,r;}tre[N*30];
vector<int> sta;
ll ans[N];
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int New()
{
if(!sta.size()) return ++all;
int x=sta[sta.size()-1];
tre[x].dat=ls=rs=0;
return sta.pop_back(),x;
}
#define push_up(x) tre[x].dat=tre[ls].dat+tre[rs].dat;
inline void insert(int &x,int l,int r,int pos,int val)
{
if(!x) x=New();
if(l==r) return tre[x].dat+=val,void();
int mid=(l+r)>>1;
if(pos<=mid) insert(ls,l,mid,pos,val);
else insert(rs,mid+1,r,pos,val);
push_up(x);
}
inline int merge(int x,int y)
{
if(!x||!y) return x|y; tre[x].dat+=tre[y].dat; sta.push_back(y);
ls=merge(ls,tre[y].l); rs=merge(rs,tre[y].r); return x;
}
inline int query(int x,int l,int r,int L,int R)
{
if(!x||L>R) return 0;
if(L<=l&&r<=R) return tre[x].dat;
int mid=(l+r)>>1;ll sum=0;
if(L<=mid) sum+=query(ls,l,mid,L,R);
if(R>mid) sum+=query(rs,mid+1,r,L,R);
return sum;
}
void dfs(int x)
{
insert(root[x],1,lim,s[x],1);
for(int i=head[x];i;i=nxt[i])
{
if(ver[i]==fa[x]) continue; fa[ver[i]]=x; dfs(ver[i]);
root[x]=merge(root[x],root[ver[i]]),root[ver[i]]=0;
}
int temp=query(root[x],1,lim,1,s[x]-1); ans[1]+=temp; if(x==1) return ;
ans[x]-=temp+query(root[x],1,lim,1,s[fa[x]]-1);
}
void dfs2(int x){ans[x]+=ans[fa[x]]; for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa[x]) dfs2(ver[i]);}
int main()
{
freopen("tears.in","r",stdin); freopen("tears.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++) s[i]=read(),lim=max(lim,s[i]);
for(int i=1,x,y;i<n;i++) x=read(),y=read(),add_edge(x,y),add_edge(y,x);
dfs(1); for(int i=2;i<=n;i++) ans[i]+=query(root[1],1,lim,1,s[i]-1);
dfs2(1); while(m--){int x;x=read();write(ans[x]);putchar('\n');}
return 0;
}
樹狀數組
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
#define ls tre[x].l
#define rs tre[x].r
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
inline void write(ll x)
{
#define sta number
int sta[70],top=0; if(x<0) putchar('-'),x=~(x-1);
while(x) sta[++top]=x%10,x/=10; if(!top) sta[++top]=0;
while(top) putchar(sta[top--]+'0');
#undef sta
}
const int N=1e6+10;
int n,m,lim,cnt,s[N],fa[N],lsh[N],pre[N];
int tot=1,head[N],ver[N<<1],nxt[N<<1];
struct BIT
{
int tre[N];
inline int lowbit(int x){return x&(-x);}
void insert(int x){for(int i=x;i<=lim;i+=lowbit(i))tre[i]++;}
int query(int x){int sum=0;for(int i=x;i>0;i-=lowbit(i))sum+=tre[i];return sum;}
}T;
ll ans[N];
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x)
{
int tmp1=T.query(s[x]-1),tmp2=T.query(s[fa[x]]-1); T.insert(s[x]);
for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa[x]) fa[ver[i]]=x,dfs(ver[i]);
int temp=T.query(s[x]-1)-tmp1; ans[1]+=temp;
if(x!=1) ans[x]-=temp+T.query(s[fa[x]]-1)-tmp2;
}
void dfs2(int x){ans[x]+=ans[fa[x]]; for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa[x]) dfs2(ver[i]);}
int main()
{
freopen("tears.in","r",stdin); freopen("tears.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++) s[i]=read(),lsh[++cnt]=s[i];
sort(lsh+1,lsh+cnt+1); lim=cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
for(int i=1;i<=n;i++) s[i]=lower_bound(lsh+1,lsh+cnt+1,s[i])-lsh,pre[s[i]]++;
for(int i=1;i<=cnt;i++) pre[i]+=pre[i-1];
for(int i=1,x,y;i<n;i++) x=read(),y=read(),add_edge(x,y),add_edge(y,x);
dfs(1); for(int i=2;i<=n;i++) ans[i]+=pre[s[i]-1];
dfs2(1); while(m--){int x;x=read();write(ans[x]);putchar('\n');}
return 0;
}
T3 傳統藝能
解題思路
線段樹維護矩陣乘的題目還是第一次做。。
對於一個以 A 結尾的矩陣，他的對角線都是 1 ，然後第一行也是 1 。 \(A_{i,j}\) 表示以 \(i\) 開頭在結尾多一個 \(j\) 的答案，轉移方程類似矩陣乘，原因顯然。
線段樹維護的每一個節點都是一個矩陣，每次區間查詢單點修改即可。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
#define ls x<<1
#define rs x<<1|1
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e5+10,mod=998244353;
int n,m;
char s[N];
struct Square
{
int a[4][4];
void clear(){memset(a,0,sizeof(a));}
Square friend operator * (Square x,Square y)
{
Square z; z.clear();
for(int i=0;i<=3;i++) for(int j=0;j<=3;j++) for(int k=0;k<=3;k++) z.a[i][j]+=x.a[i][k]*y.a[k][j];
for(int i=0;i<=3;i++) for(int j=0;j<=3;j++) z.a[i][j]%=mod; return z;
}
}S[4];
struct Segment_Tree
{
Square tre[N<<2];
#define push_up(x) tre[x]=tre[ls]*tre[rs];
void update(int x,int l,int r,int pos,int val)
{
if(l==r) return tre[x]=S[val],void();
int mid=(l+r)>>1;
if(pos<=mid) update(ls,l,mid,pos,val);
else update(rs,mid+1,r,pos,val);
push_up(x);
}
Square query(int x,int l,int r,int L,int R)
{
if(L<=l&&r<=R) return tre[x]; int mid=(l+r)>>1;
if(L<=mid&&R>mid) return query(ls,l,mid,L,R)*query(rs,mid+1,r,L,R);
if(L<=mid) return query(ls,l,mid,L,R); return query(rs,mid+1,r,L,R);
}
}T;
#undef int
int main()
{
#define int long long
freopen("string.in","r",stdin); freopen("string.out","w",stdout);
n=read(); m=read(); scanf("%s",s+1);
for(int i=0;i<=3;i++) S[1].a[i][i]=S[2].a[i][i]=S[3].a[i][i]=1;
for(int i=0;i<=3;i++) S[1].a[1][i]=S[2].a[2][i]=S[3].a[3][i]=1;
for(int i=1;i<=n;i++) T.update(1,1,n,i,s[i]-'A'+1);
while(m--)
{
int opt,l,r,p,ans=0; char ch; opt=read();
if(opt==1){p=read();ch=getchar();T.update(1,1,n,p,ch-'A'+1);continue;}
l=read(); r=read(); Square temp=T.query(1,1,n,l,r);
for(int i=1;i<=3;i++) ans=(ans+temp.a[i][0])%mod; printf("%lld\n",ans);
}
return 0;
}
T4 鋪設道路
解題思路
維護一個差分數組，最後消成 0 。
顯然的時間就是 \(\sum\limits_{i=1}^n\max(0,s_i)\)
為了讓答案儘可能的大，我們需要對於每個點消除距離最近的點，把較遠的留給後面。
對於讓答案儘可能小的情況反之。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"RP++"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=3e5+10,mod=1e9+7;
int n,tim,maxn,minn,head,tail,s[N];
pair<int,int> q[N];
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
#undef int
int main()
{
#define int long long
freopen("road.in","r",stdin); freopen("road.out","w",stdout);
n=read(); for(int i=1,pre=0;i<=n;i++) s[i]=read()-pre,pre+=s[i],tim+=max(0ll,s[i]);
head=1; tail=0;
for(int i=1;i<=n;i++)
{
if(s[i]>0){q[++tail]=make_pair(i,s[i]);continue;}
int temp=s[i];
while(temp<0)
{
int x=q[head].first,val=q[head].second;
if(val<=-temp){head++;temp+=val;add(minn,val*(i-x)%mod*(i-x)%mod);continue;}
q[head]=make_pair(x,val+temp); add(minn,-temp*(i-x)%mod*(i-x)%mod); break;
}
}
while(head<=tail) add(minn,q[head].second*(n-q[head].first+1)%mod*(n-q[head].first+1)%mod),head++; head=1; tail=0;
for(int i=1;i<=n;i++)
{
if(s[i]>0){q[++tail]=make_pair(i,s[i]);continue;}
int temp=s[i];
while(temp<0)
{
int x=q[tail].first,val=q[tail].second;
if(val<=-temp){tail--;temp+=val;add(maxn,val*(i-x)%mod*(i-x)%mod);continue;}
q[tail]=make_pair(x,val+temp); add(maxn,-temp*(i-x)%mod*(i-x)%mod); break;
}
}
while(head<=tail) add(maxn,q[head].second*(n-q[head].first+1)%mod*(n-q[head].first+1)%mod),head++;
printf("%lld\n%lld\n%lld",tim,maxn,minn); return 0;
}
