这是暑假的第一个模拟赛,和新高一的一起打的
T1 | T2 | T3 | T4 | tot |
---|---|---|---|---|
50pts | 45pts | 100pts | 0pts | 195tps |
总的来说不是很满意,最近的状态有点低迷,但考虑到刚刚结束文化课还是情有可原,一切都会好起来的!
题意:
给定 \(n,n\le300\) 个点,\(m,m\le1e4\) 条边的无向图,给出 \(q,q\le1e4\) 次询问求出点 \(u\),\(v\) 直接的定义路径的权值(权值为路径上的点权最大值与路径上所有边权之和)
赛时做法:
我们发现直接在这个图上跑任何最短路算法都是无用的,无法把路径上点权最大值这个东西加到贡献中,所以我们可以枚举最大值然后再跑最短路的时候限制点权,时间复杂度(如果是堆优化迪杰斯特拉求单源最短路)为 \(O(300n(n+m)log_n)\),可以优化但没必要了往下了分析了
赛事稍微优化了一点的代码
const int maxn=330;
const int maxm=1e4+100;
int a[maxn],n,m,q;
int head[maxm<<1],to[maxm<<1],nx[maxm<<1],w[maxm<<1],cnt;
inline void add(int u,int v,int val)
{
++cnt;
to[cnt]=v;
w[cnt]=val;
nx[cnt]=head[u];
head[u]=cnt;
}
ll dis[330][330],d[330];
bool vis[330];
priority_queue<pii>pq;
inline void dj(int o,int cp)
{
if(cp<a[o])return;
memset(vis,0,sizeof vis);
memset(d,0x7f,sizeof d);
d[o]=0;
pq.push({-d[o],o});
while(pq.size())
{
int u=pq.top().se;
pq.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u],v;v=to[i],i;i=nx[i])
if(a[v]<=cp and d[v]>d[u]+w[i])
{
d[v]=d[u]+w[i];
pq.push({-d[v],v});
}
}
for(int i=1;i<=n;++i)
dis[o][i]=min(dis[o][i],d[i]+cp);
}
bool in[330];
int main()
{
n=read(),m=read(),q=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<=m;++i)
{
int u=read(),v=read(),val=read();
add(u,v,val);
add(v,u,val);
}
memset(dis,0x7f,sizeof dis);
while(q--)
{
int u=read(),v=read();
if(!(in[u] or in[v]))
{
for(int j=1;j<=n;++j)
dj(u,a[j]);
in[u]=1;
}
if(!in[u])swap(u,v);
__print(dis[u][v]==dis[0][0]?-1:dis[u][v]);
}
return 0;
}
solution:
就像之前我们发现的那样,在找到的最短路径上去寻找最大值这个东西其实是分割的,答案不一定对,所以还是得去枚举最大值,其实看见 \(n\) 的范围不难想到 \(floyed\),此时就需要对 \(floyed\) 进行改进:
$\ \ \ \ \ \ \ $考虑到其根本原理为 \(DP\) ,可以在其基础上加东西
一般 \(floyed\)
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
最原始的 \(f\) 数组是有三维,\(f_{k,i,j}\)表示 在只经过编号小于 \(k\) 的点时,从 \(i\) 到 \(j\) 的最短路径
动态转移方程为:
和背包同理可以优化掉一维
如果对 \(floyed\) 理解稍微深刻那么一点的话,就会想到我们可以根据点权排序这样就便于在更新最短路时知道这条路径的上的点权最大值了,即为 \(val[\max(\max(i,j),k)]\)
核心代码:
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
dis[i][j]=min(dis[i][j],f[i][k]+f[k][j]+val[max(k,max(i,j))]);
f[i][j]=min(f[i][j],f[i][k]+f[k][j])
}
正解
struct node
{
int w,id;
bool operator < (const node A) const
{
return w<A.w;
}
}nd[330];
int rk[330];
int dis[330][330],d[330][330];
int main()
{
int n=read(),m=read(),q=read();
for(int i=1;i<=n;++i)
nd[i].w=read(),nd[i].id=i;
sort(nd+1,nd+1+n);
for(int i=1;i<=n;++i)
rk[nd[i].id]=i;
M(dis,0x3f),M(d,0x7f);
for(int i=1;i<=n;++i)
dis[i][i]=0;
for(int i=1;i<=m;++i)
{
int u=read(),v=read(),w=read();
u=rk[u],v=rk[v];
dis[v][u]=dis[u][v]=min(dis[u][v],w);
}
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
d[i][j]=min(d[i][j],dis[i][k]+dis[k][j]+nd[max(k,max(i,j))].w);
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
while(q--)
{
int u=read(),v=read();
u=rk[u],v=rk[v];
__print(d[u][v]);
}
return 0;
}
总结:
赛时没能想到正解,有些遗憾,但确实是对 \(floyed\) 这个算法的掌握不太到位,也算是弥补了缺漏了,感觉这也是模拟赛的意义吧
题意:给定一个全为正整数的 \(n×n\) 的矩阵,求出他的一个子矩阵使其元素和在区间 \([k,2k]\),要求输出方案
赛时做法: \(O(n^3)\) 暴力,先求出二维前缀和,枚举每个点作为一个子矩阵的右下角,然后从最左下单调优化去寻找左上角的点
solution:
分类讨论+单调栈优化
首先若直接有属于 \([k,2k]\) 的元素则直接就能输出答案
并且属于 \([2k,+∞]\) 的元素肯定是不能被选入答案矩阵的
这个时候我们如果我们找到了一个和大于 \(2k\) 且含有的全为小于 \(k\) 的子矩阵就能发现一个性质
答案肯定在这个子矩阵中
为啥?我们可以每次减去这个子矩阵的顶部的那一行,有三种情况
- 值还是大于 \(2k\) ,继续减去一行
- 值在 \([k,2k]\) ,即为答案
- 值小于 \(k\) ,说明减去的那一行值会大于 \(k\),而他又只是一行,且其中的元素都小于 \(k\),那么答案肯定就在这被减去的一行中
对于第三种情况在代码实现时一般时从上往下枚举子矩阵的下界的,所以不会有第三种情况,在枚举答案行时就已经把答案判断出来了
然后这个题目就变为了求最大子矩阵的值是多大,若大于等于 \(k\) 则有解,反之无解
类似单调栈优化题目有最大子矩阵,只不过这题是求最大面积,而这个题也类似需要枚举所有面积尽可能大的去求最大子矩阵之和
正解
const int maxn=2200;
ll a[maxn][maxn],mp[maxn][maxn],s[maxn][maxn];
ll get(int x,int y,int a,int b)
{
return s[a][b]-s[a][y-1]-s[x-1][b]+s[x-1][y-1];
}
ll n,k;
void put(int x,int y,int a,int b)
{
for(int i=x;i<=a;++i)
if(get(i,y,a,b)<=2*k)
{
cout<<y<<' '<<i<<' '<<b<<' '<<a<<endl;
exit(0);
}
}
ll st[maxn],top,w[maxn];
int main()
{
k=read(),n=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
a[i][j]=read();
if(a[i][j]>=k and a[i][j]<=2*k)
{
cout<<j<<" "<<i<<" "<<j<<" "<<i<<endl;
return 0;
}
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
if(a[i][j]<k)mp[i][j]=mp[i-1][j]+1;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n+1;++j)
{
int tmp=0;
while(mp[i][j]<st[top])
{
tmp+=w[top];
if(get(i-st[top]+1,j-tmp,i,j-1)>=k)
put(i-st[top]+1,j-tmp,i,j-1);
--top;
}
st[++top]=mp[i][j];
w[top]=tmp+1;
}
M(st,0);
M(w,0);
top=0;
}
puts("NIE");
return 0;
}
总结:
赛时的确是嗅到了单调栈优化的味道,也想过像这样的时间复杂度明显的矩阵类题目最终一般都会转化为求最大最小矩阵类问题,最终败在了分讨思想上
题意:给定一个序列,有两个操作:1.区间乘上一个数;2.求区间积的欧拉函数对 \(1e9+7\) 取模(序列元素值和修改乘上的值都小于等于300)
solution:
线段树+状压
对于欧拉函数的定义有
我们可以把这个式子拆成几个部分
\[φ(n)=n*\frac{1}{\prod p_i}*\prod p_i \]那么回到本题利用线段树能很好求出区间积,并且区间修改也非常方便,完成第一部分的求解
注意到所有值都小于300,那么质数就会有62个,可以装压维护更新区间质数的存在情况,在线段树上做一点小修改就可以了,最后对第二部分求下逆元即可
正解
int prime[330],phi[330],top;
bool vis[330];
bitset<65>num[330];
void pre()
{
for(int i=2;i<=300;++i)
{
if(!vis[i])prime[++top]=i;
for(int j=1;j<=top and i*prime[j]<=300;++j)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
for(int i=2;i<=300;++i)
{
for(int j=1;j<=top and prime[j]<=i;++j)
if(i%prime[j]==0)
num[i][j]=1;
}
}
const int maxn=4e5+10;
const int mod=1e9+7;
int a[maxn];
ll qk(ll a,ll b,int mod)
{
ll ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
ll get_ny(ll a,ll mod)
{
return qk(a,mod-2,mod);
}
struct seg
{
struct node
{
int ls,rs;
bitset<65>tmp,lz;
ll s,tag;
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define s(x) tr[x].s
#define tag(x) tr[x].tag
#define tmp(x) tr[x].tmp
#define lz(x) tr[x].lz
}tr[maxn<<2];
void push_up(int o)
{
s(o)=s(ls(o))*s(rs(o))%mod;
tmp(o)=tmp(ls(o))|tmp(rs(o));
}
void push_down(int o,int l,int r)
{
if(tag(o)!=1)
{
tmp(ls(o))|=lz(o);
tmp(rs(o))|=lz(o);
lz(ls(o))|=lz(o);
lz(rs(o))|=lz(o);
int mid=(l+r)>>1;
s(ls(o))=s(ls(o))*qk(tag(o),mid-l+1,mod)%mod;
s(rs(o))=s(rs(o))*qk(tag(o),r-mid,mod)%mod;
tag(ls(o))=tag(ls(o))*tag(o)%mod;
tag(rs(o))=tag(rs(o))*tag(o)%mod;
tag(o)=1;
}
}
void build(int o,int l,int r)
{
tag(o)=1;
if(l==r)
{
s(o)=a[l];
tmp(o)=num[a[l]];
return;
}
ls(o)=o<<1,rs(o)=ls(o)+1;
int mid=(l+r)>>1;
build(ls(o),l,mid);
build(rs(o),mid+1,r);
push_up(o);
}
void mul(int o,int l,int r,int x,int y,ll v,bitset<65> b)
{
push_down(o,l,r);
if(x<=l and r<=y)
{
s(o)=s(o)*qk(v,r-l+1,mod)%mod;
tag(o)=tag(o)*v%mod;
tmp(o)|=b;
lz(o)|=b;
return;
}
int mid=(l+r)>>1;
if(x<=mid)mul(ls(o),l,mid,x,y,v,b);
if(y>mid)mul(rs(o),mid+1,r,x,y,v,b);
push_up(o);
}
pair<ll,bitset<65>> query_mul(int o,int l,int r,int x,int y)
{
push_down(o,l,r);
if(x<=l and r<=y)return {s(o),tmp(o)};
int mid=(l+r)>>1;
ll res=1;
bitset<65>ans;
if(x<=mid)
{
auto it=query_mul(ls(o),l,mid,x,y);
res=res*it.fi%mod;
ans|=it.se;
}
if(y>mid)
{
auto it=query_mul(rs(o),mid+1,r,x,y);
res=res*it.fi%mod;
ans|=it.se;
}
return {res,ans};
}
}tree;
int main()
{
pre();
int n=read(),q=read();
for(int i=1;i<=n;++i)
a[i]=read();
tree.build(1,1,n);
while(q--)
{
char op[5];
cin>>op;
int l=read(),r=read();
if(op[0]=='M')
{
int v=read();
tree.mul(1,1,n,l,r,v,num[v]);
}
else
{
auto it=tree.query_mul(1,1,n,l,r);
ll ans=it.fi,bt=1,up=1;
for(int i=1;i<=top;++i)
if(it.se[i])
bt=bt*prime[i]%mod,
up=up*(prime[i]-1)%mod;
bt=get_ny(bt,mod);
printf("%lld\n",ans*bt%mod*up%mod);
}
}
return 0;
}
题意:给定一颗带点权的树,第 \(i\) 次询问 回答从一点到另一点,中间间隔走 \(c_i\) 个边到达的点累加其点权的值
solution:
根号分值
首先对于树上路径问题一般得求lca,这里建议用倍增求,当然长链剖这题也很好
对于间隔 \(c_i\) 大于 \(\sqrt{n}\) 的可以直接利用倍增的 \(fa\) 数组直接暴力跳,该情况时间复杂度上界为 \(O(\sqrt{n})\)
对于间隔 \(c_i\) 小于 \(\sqrt{n}\) 的我们可以预处理求出每个点在跳的间隔在 \([1,\sqrt{n}]\) 下的到根部的答案,每次回答就直接用两个点的这个预处理之和减去两点的 \(lca\) 分别往上最近匹配上的点的预处理,利用动规转移,预处理时间复杂度 \(O(n\sqrt{n}log_n)\)
细节比较多
正解
const int maxn=50000+10;
int head[maxn],to[maxn<<1],nx[maxn<<1],cnt;
void add(int u,int v)
{
++cnt;
to[cnt]=v;
nx[cnt]=head[u];
head[u]=cnt;
}
int a[maxn],d[maxn],c[maxn],n;
int dep[maxn],fa[maxn][20],jp[maxn][240];
void dfs1(int o,int f)
{
dep[o]=dep[f]+1;
fa[o][0]=f;
for(int k=1;k<=16;++k)
fa[o][k]=fa[fa[o][k-1]][k-1];
for(int i=head[o],v;v=to[i],i;i=nx[i])
if(v!=f)
dfs1(v,o);
}
int getfa(int o,int k)
{
for(int i=0;i<16;++i)
if(k&(1<<i))
o=fa[o][i];
return o;
}
int getlca(int u,int v)
{
if(dep[u]<dep[v])swap(u,v);
for(int k=16;k>=0;--k)
if(dep[fa[u][k]]>=dep[v])u=fa[u][k];
if(u==v)return u;
for(int k=16;k>=0;--k)
if(fa[u][k]!=fa[v][k])
u=fa[u][k],v=fa[v][k];
return fa[u][0];
}
void dfs2(int o,int f)
{
for(int i=1;i*i<=n;++i)
jp[o][i]=jp[getfa(o,i)][i]+a[o];
for(int i=head[o],v;v=to[i],i;i=nx[i])
if(v!=f)
dfs2(v,o);
}
bool f;
int go_to(int st,int go,int l)
{
int ans=0;
while(dep[st]>=dep[go])
{
ans+=a[st];
st=getfa(st,l);
if(st==go)f=1;
}
return ans;
}
int del(int st,int go,int mod)
{
int ans=0;
int d=(dep[go]%mod-dep[st]%mod+mod)%mod;
if(!d)f=1,d+=mod;
return jp[getfa(go,d)][mod];
}
signed main()
{
n=read();
for(int i=1;i<=n;++i)
a[i]=read();
for(int i=1;i<n;++i)
{
int u=read(),v=read();
add(u,v);
add(v,u);
}
for(int i=1;i<=n;++i)
d[i]=read();
for(int i=1;i<n;++i)
c[i]=read();
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<n;++i)
{
int u=d[i],v=d[i+1],k=c[i];
int lca=getlca(u,v);
f=0;
if(k*k<=n)__print(jp[u][k]+jp[v][k]-del(u,lca,k)-del(v,lca,k)-(f?a[lca]:0));
else __print(go_to(u,lca,k)+go_to(v,lca,k)-(f?a[lca]:0));
}
return 0;
}
总结:这题没写暴力,因为感觉就算暴力得分也不会太乐观,错误的想法QQ,想到了倍增暴力往上跳但时间复杂度怎么分析都不对。这题算是收获最大的一道题吧,根号分治