多校A层冲刺NOIP2024模拟赛09
考试唐完了，T2、T4 都挂了 100 分，人麻了。
排列最小生成树
给定一个 \(1, 2,\dots , n\) 的排列 \(p_1, p_2,\dots, p_n\)。
构造一个 \(n\) 个点的完全无向图，节点编号分别是 \(1, 2,\dots, n\) 。
节点 i 和节点 j 之间的边边权为 \(|pi − pj| ×|i − j|\)，其中 \(|x\) 表示 \(x\) 的绝对值。
请问这个完全图的最小生成树的所有边的权值和是多少？
\(n\leq 5\times 10^4\)。
易发现边的长度都不大于 \(n\)，考虑记录一个点连向其他点的边中长度小于 \(n\) 的边。
对于 \(i\) 来说，这些点的满足以下之一：
- 距离在 \(\sqrt n\) 以内，即 \(|i-j|\leq \sqrt n\)。
- 大小在 \(\sqrt n\)，即 \(|p_i-p_j| \leq \sqrt n\)。
把这些点枚举出来，桶排后使用 \(Kruskal\) 求解。
瓶颈在 \(Kruskal\) 的并查集，时间复杂度 \(O(n\sqrt n\alpha)\)。
当然由于 \(Prim\) 的优先队列跑不满，所以说时间复杂度 \(O(n\sqrt n\log n)\) \(Prim\) 也可以通过本题。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const int maxn=5e4+5,maxB=255;
ll ans;
int n,B;
int p[maxn],pid[maxn],dis[maxn];
bool vis[maxn];
priority_queue<pii,vector<pii>,greater<pii>>que;
int tmp=1e9,id=0;
inline void check(int u)
{
tmp=1e9,id=0;
for(int i=1;i<=n;i++)
if(i!=u)
{
if(1ll*tmp>1ll*abs(u-i)*abs(p[u]-p[i])) tmp=1ll*abs(u-i)*abs(p[u]-p[i]),id=i;
}
}
int main()
{
freopen("ex_pmst2.in","r",stdin);
// freopen("pmst.in","r",stdin);
freopen("pmst.out","w",stdout);
check(1);
scanf("%d",&n);
B=sqrt(n);
for(int i=1;i<=n;i++) scanf("%d",&p[i]),pid[p[i]]=i,dis[i]=n+1;
dis[1]=0;que.push({0,1});
int cnt=0;
while(cnt<n)
{
int u=que.top().se;que.pop();
if(vis[u]) continue;
ans+=dis[u];vis[u]=true;cnt++;
for(int j=max(u-B,1);j<=min(u+B,n);j++)
{
if(dis[j]>abs(u-j)*abs(p[u]-p[j]))
{
dis[j]=abs(u-j)*abs(p[u]-p[j]);
que.push({dis[j],j});
}
}
for(int j=max(p[u]-B,1);j<=min(p[u]+B,n);j++)
{
if(dis[pid[j]]>abs(u-pid[j])*abs(p[u]-j))
{
dis[pid[j]]=abs(u-pid[j])*abs(p[u]-j);
que.push({dis[pid[j]],pid[j]});
}
}
}
printf("%lld",ans);
// cerr<<clock()/1000;
}
卡牌游戏
形式化的，求：
\[\sum_{i=1}^{n}\sum_{k=0}^{m-1} [A_i>B_{i+k\times n \mod m}] \]其中若 \(i+k\times n\equiv 0 \mod m\)，则小于号右边为 \(B_m\)。
打表发现对于一个 \(i\) 而言 \(i+k\times n \mod m\) 会形成循环节，不同的循环节之间没有交集；循环节的长度等于 \(\gcd(n,m)\)，或者说循环节一定完整；不同的 \(i\) 循环节会重复。
8 12
1:
1 9 5 1 9 5 1 9 5 1 9 5
2:
2 10 6 2 10 6 2 10 6 2 10 6
3:
3 11 7 3 11 7 3 11 7 3 11 7
4:
4 0 8 4 0 8 4 0 8 4 0 8
5:
5 1 9 5 1 9 5 1 9 5 1 9
6:
6 2 10 6 2 10 6 2 10 6 2 10
7:
7 3 11 7 3 11 7 3 11 7 3 11
8:
8 4 0 8 4 0 8 4 0 8 4 0
暴力跑出循环节，对于 \(A\) 中的每一个元素，在循环节上查询比自己小的数的个数，然后乘循环次数即可。
对于剩下两个答案同理，是 easy 的。
然而场上没开 long long 导致溢出了（悲。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
bool swp;
int col,n,m;
int a[maxn],b[maxn],tc[maxn],vis[maxn];
ll ans1,ans2,ans3;
vector<int>vec[maxn],vect[maxn];
struct treearray
{
#define N 200000
int ts[maxn];
inline int lowbit(int x) {return x&(-x);}
inline void updata(int x,int y) {for(;x<=N;x+=lowbit(x)) ts[x]+=y;}
inline int getsum(int x) {int sum=0;for(;x;x-=lowbit(x)) sum+=ts[x];return sum;}
}T;
map<int,int>mp;
int main()
{
// freopen("ex_cardgame2.in","r",stdin);
freopen("cardgame.in","r",stdin);
freopen("cardgame.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
if(n>m) swap(n,m),swap(a,b),swp=1;
for(int i=1;i<=n;i++)
{
int flg=1;
for(int k=0;k<=m;k++)
{
int v=(i+1ll*k*n)%m;
if(v==0) v=m;
if(vis[v]) {tc[i]=vis[v];break;}
col+=flg;flg=0;
vis[v]=col;vec[col].emplace_back(v);
}
vect[tc[i]].emplace_back(i);
}
for(int i=1;i<=n;i++) mp[a[i]]=1;
for(int i=1;i<=m;i++) mp[b[i]]=1;
auto it1=mp.begin(),it2=mp.begin();
for(it2++;it2!=mp.end();it1++,it2++) it2->second+=it1->second;
for(int i=1;i<=m;i++) b[i]=mp[b[i]];
for(int i=1;i<=n;i++) a[i]=mp[a[i]];
for(int i=1;i<=col;i++)
{
for(auto v:vec[i])
{
if(b[v]==0)
{
b[v]=0;
}
T.updata(b[v],1);
}
for(auto v:vect[i])
{
ans1+=1ll*T.getsum(a[v]-1)*(m/vec[i].size());
ans3+=1ll*(T.getsum(N)-T.getsum(a[v]))*(m/vec[i].size());
}
for(auto v:vec[i]) T.updata(b[v],-1);
}
ans2=1ll*n*m-ans1-ans3;
if(swp) swap(ans1,ans3);
printf("%lld\n%lld\n%lld",ans1,ans3,ans2);
}
比特跳跃
探求位运算性质的好题，就是我不会做。
分类讨论：
1.\(s=1\)。
对于所有最高位不为 \(1\) 的，都可以与最高位 \(1\) 其他位为 \(0\) 的数 \(\&\) 得到 \(0\)。对于剩下最高位为 \(1\) 的数，按位取反后不为 \(0\)，答案为 \(0\)，否则为 \(k\) 和连向其的边中区较小值。
2.\(s=2\)。
将每个点与有一位是不一样的点连边，跑最短路即可。
3.\(s=3\)。
先跑一次最短路，每个点 \(x\) 递推的求出满足 \(x|y=x\) 的最小的 \(dis_y\)，然后判断是否有 \(dis_x>dis_y+x\times k\)，如果有就令 \(dis_x=dis_y+x\times k\)。
再跑一次最短路即可求得答案。
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pli pair<ll,int>
#define fi first
#define se second
const int maxn=2e6+5;
int n,m,s,k;
int f[maxn];
struct Edge
{
int tot;
int head[maxn];
struct edgenode{int to,nxt;ll w;}edge[maxn*2];
inline void add(int x,int y,ll w)
{
tot++;
edge[tot].to=y;
edge[tot].w=w;
edge[tot].nxt=head[x];
head[x]=tot;
}
}G;
priority_queue<pli,vector<pli>,greater<pli>>que;
ll dis[maxn];
bool vis[maxn];
int flg=0;
inline void dij()
{
if(!flg) memset(dis,0x3f,sizeof(dis));
else for(int i=2;i<=n;i++) que.push({dis[i],i});
flg++;
memset(vis,0,sizeof(vis));
dis[1]=0;que.push({0,1});
while(!que.empty())
{
int u=que.top().se;que.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=G.head[u];i;i=G.edge[i].nxt)
{
int w=G.edge[i].w,v=G.edge[i].to;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
que.push({dis[v],v});
}
}
}
}
signed main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
scanf("%lld%lld%lld%lld",&n,&m,&s,&k);
for(int i=1,u,v,w;i<=m;i++) scanf("%lld%lld%lld",&u,&v,&w),G.add(u,v,w),G.add(v,u,w);
if(s==1)
{
for(int i=2;i<n;i++) printf("0 ");
bool flg=0;
for(int i=1;i<=20;i++) flg|=(n==((1<<i)-1));
if(!flg) printf("0");
else
{
ll ans=k;
for(int i=G.head[n];i;i=G.edge[i].nxt) ans=min(ans,G.edge[i].w);
printf("%lld ",ans);
}
}
else if(s==2)
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<=20&&(n>>j);j++)
{
int st=i^(1<<j);
if(st<=n) G.add(i,st,1ll*k*(1<<j)),G.add(st,i,1ll*k*(1<<j));
}
}
dij();
for(int i=2;i<=n;i++) printf("%lld ",dis[i]);
}
else
{
for(int i=2;i<=n;i++) G.add(1,i,(1|i)*k);
dij();
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=20;j++)
{
if((i>>j)&1)
{
if(dis[f[i]]>dis[f[i^(1<<j)]]) f[i]=f[i^(1<<j)];
}
}
dis[i]=min(dis[f[i]]+1ll*i*k,dis[i]);
}
dij();
for(int i=2;i<=n;i++) printf("%lld ",dis[i]);
}
}
区间
固定二元组的右端点 \(r\)，找到一个最小的 \(l\) 使得二元组 \((l,r)\) 满足条件 \(2\)。
观察 \((l,r)\) 中满足条件 \(1\) 的左端点，发现这些点是一个从 \(l\) 开始的单调递减的单调栈中小于 \(B_r\) 的部分。
假设所有的查询的 \(L_i=1\)，离线完询问后枚举二元组右端点，同时维护单调栈，每次二分查询单调栈里有多少点小于 \(B_r\) 即可。
可是 \(L_i\) 并不全部等于一，那么我们设 \(val_i\) 表示 \(i\) 这个点可以作为多少个二元组中的左端点出现，每次二分查询时，给栈内小于 \(B_r\) 的部分的 \(val_i\) 加一，每次查询 \([L_i,R_i]\) 的 \(val\) 的和即可。
由于单调栈内的节点编号并不会连续，如果暴力实现 \(val\) 值的更改显然不合适，那么我们把栈内的 \(val\) 值附上新的编号，维护在线段树上，如果这个点被栈弹出了，那么他的 \(val\) 值存在本身编号的位置。
由于栈内的原编号是递增的，在 \(R_i\) 时求出栈内原编号大于 \(L_i\) 点的 \(val\) 值和，以及弹出栈的 \([L_i,R_i]\) 的 \(val\) 值和。
场上手残了，树状数组写挂了。
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=3e5+5;
int n,m;
int a[maxn],b[maxn],l[maxn],r[maxn],flg[maxn];
vector<int>vec[maxn];
ll ans[maxn];
struct treearray
{
#define N 300000
ll ts[maxn];
inline int lowbit(int x) {return x&(-x);}
inline void updata(int x,int y) {for(;x<=N;x+=lowbit(x)) ts[x]+=y;}
inline ll getsum(int x) {ll sum=0;for(;x;x-=lowbit(x)) sum+=ts[x];return sum;}
}Ta;
namespace linetree
{
#define lch(p) p*2
#define rch(p) p*2+1
struct treenode{ll sum,lz;}tr[maxn*12];
inline void updata(int p){tr[p].sum=tr[lch(p)].sum+tr[rch(p)].sum;}
inline void push_down(int p,int l,int r)
{
if(!tr[p].lz||l==r) return ;
int mid=(l+r)>>1;
tr[lch(p)].sum+=tr[p].lz*(mid-l+1),tr[lch(p)].lz+=tr[p].lz;
tr[rch(p)].sum+=tr[p].lz*(r-mid),tr[rch(p)].lz+=tr[p].lz;
tr[p].lz=0;
}
inline void insert(int p,int l,int r,int lx,int rx,int v)
{
if(r<lx||l>rx) return ;
if(lx<=l&&r<=rx)
{
tr[p].sum+=(r-l+1)*v;
tr[p].lz+=v;
return ;
}
push_down(p,l,r);
int mid=(l+r)>>1;
insert(lch(p),l,mid,lx,rx,v),insert(rch(p),mid+1,r,lx,rx,v);
updata(p);
}
inline ll qry(int p,int l,int r,int lx,int rx)
{
if(r<lx||l>rx) return 0;
if(lx<=l&&r<=rx) return tr[p].sum;
push_down(p,l,r);
int mid=(l+r)>>1;
return qry(lch(p),l,mid,lx,rx)+qry(rch(p),mid+1,r,lx,rx);
}
}
int tp;
int stk[maxn];
inline int fr(int x)
{
int l=1,r=tp,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(a[stk[mid]]<x) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
inline int fr_id(int x)
{
int l=1,r=tp,ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(stk[mid]>=x) ans=mid,r=mid-1;
else l=mid+1;
}
return ans;
}
int main()
{
// freopen("ex_interval2.in","r",stdin);
freopen("interval.in","r",stdin);
freopen("interval.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=2;i<=n;i++) scanf("%d",&b[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l[i],&r[i]);
vec[r[i]].push_back(i);
}
stk[++tp]=1;
for(int i=2;i<=n;i++)
{
int tmp=fr(b[i]);
if(tmp)
{
linetree::insert(1,1,n,tmp,tp,1);
}
for(auto v:vec[i])
{
tmp=fr_id(l[v]);
ans[v]=(Ta.getsum(r[v])-Ta.getsum(l[v]-1));
if(tmp) ans[v]+=linetree::qry(1,1,n,tmp,tp);
}
while(tp&&a[stk[tp]]<=a[i])
{
ll val=linetree::qry(1,1,n,tp,tp);
Ta.updata(stk[tp],val);
linetree::insert(1,1,n,tp,tp,-val);
tp--;
}
stk[++tp]=i;
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}