模拟赛
T1 挂 \(70pts\)，T2 \(\mathbb{AC}\) 力挽狂澜，T3 暴力爆零，T4 \(5min = 30pts\)。
T1 Cow Toll Paths G
弗洛伊德，跑的过程记最大点权。注意有后效性，需要迭代一下。
按点权排序后再跑可以不用迭代，因为一定会先更新小的，再更新大的。
注意是：变量名别写错？？？
code
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
#define LL long long
int n,m,q;
LL mp[N][N],mx[N][N];
int main()
{
// freopen("path.in","r",stdin);
// freopen("path.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) scanf("%lld",&mx[i][i]);
memset(mp,0x3f,sizeof(mp));
for(int i=1;i<=n;i++) mp[i][i]=0;
for(int i=1;i<=m;i++)
{
int x,y;LL w; scanf("%d%d%lld",&x,&y,&w);
mp[x][y]=mp[y][x]=min(mp[x][y],w); mx[x][y]=mx[y][x]=max(mx[x][x],mx[y][y]);
}
for(int g=1;g<=5;g++)
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][k]+mp[k][j]+max(mx[i][k],mx[k][j])<mp[i][j]+mx[i][j])
{
mx[i][j]=max(mx[i][k],mx[k][j]);
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
while(q--)
{
int x,y; scanf("%d%d",&x,&y);
if(mp[x][y]>1e18) printf("%d\n",-1);
else printf("%lld\n",mp[x][y]+mx[x][y]);
}
return 0;
}
T2 [POI2008] KUP-Plot purchase
对于 \(\gt 2k\) 的一定不可能被选中，\(\le k\) 的才有可能被选，所以我们可以把它转化为 \(0/1\) 矩阵，其中不合法的为 \(0\)，合法的为 \(1\)。
这显然是一道和最大矩形类似的题，用单调栈和二维前缀和维护，先找出以每一行为起点向上延申的最大矩形。
因为每个合法个体都 \(\lt k\)，所以我们如果能找到一个 \(\ge 2k\) 的矩形，那么说明一定会包含一个 \(k \le \&\& \le 2k\) 的合法矩形。
那么如何去确定这个合法矩形呢？
由于我们是从上到下一行一行遍历的，所以显然有以下性质：如果矩形 \(\ge 2k\)，那么最终的合法矩形一定会出现在最下面一行中。
证明：由于我们已经判断过除了最后一行——也就是上面的矩形一定是 \(\lt k\) 的（否则就合法输出了）。而加上最后一行就 \(\ge 2k\) 了，所以最后加的这一行一定 \(\ge k\)。
反正只有一行，暴力就好了。（好像能卡？）
单调栈写的有点丑
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2005;
#define LL long long
int n,rb[N][N],lb[N][N],s[N][N];
LL a[N][N],k,sum[N][N];
bool mp[N][N];
int main()
{
// freopen("matrix.in","r",stdin);
// freopen("matrix.out","w",stdout);
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%lld",&a[i][j]);
if(a[i][j]>=k&&a[i][j]<=2ll*k)
{
printf("%d %d %d %d\n",i,j,i,j);
return 0;
}
else if(a[i][j]<k) mp[i][j]=1;
else if(a[i][j]>2ll*k) mp[i][j]=0;
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mp[i][j]) s[i][j]=s[i-1][j]+1;
else s[i][j]=0;
}
}
for(int i=1;i<=n;i++)
{
stack<int> st;
for(int j=1;j<=n+1;j++)
{
while(!st.empty()&&s[i][j]<s[i][st.top()])
{
rb[i][st.top()]=j-1;
st.pop();
}
st.push(j);
}
while(!st.empty()) st.pop();
for(int j=n;j>=0;j--)
{
while(!st.empty()&&s[i][j]<s[i][st.top()])
{
lb[i][st.top()]=j+1;
st.pop();
}
st.push(j);
}
for(int j=1;j<=n;j++)
{
LL ss=sum[i][rb[i][j]]-sum[i-s[i][j]][rb[i][j]]-sum[i][lb[i][j]-1]+sum[i-s[i][j]][lb[i][j]-1];
if(ss>=k)
{
if(ss<=2ll*k)
{
printf("%d %d %d %d\n",i-s[i][j]+1,lb[i][j],i,rb[i][j]);
return 0;
}
else
{
for(int h=lb[i][j]+1;h<=rb[i][j];h++)
{
int g=sum[i][h]-sum[i][lb[i][j]-1];
if(g>=k&&g<=2*k)
{
printf("%d %d %d %d\n",i,lb[i][j],i,h);
return 0;
}
}
}
}
}
}
printf("-1\n");
return 0;
}
T3 [CF1114F] Please, another Queries on Array?
复习欧拉函数：
\[\varphi(n)=n \prod_i \frac{p_i-1}{p_i} \tag{1} \]\(p\) 为 \(n\) 的质因子。只用算一次！！！而不是完全分解定理。
-
如果两个数互质，\(\varphi(n)\) 满足 \(\varphi(x \times y)=\varphi(x) \times \varphi(y)\)
-
如果两个数不互质，那么只能求出质因子的并集，然后硬算（好像没有特别通用的结论）。
因此我们从式子入手，既然最后维护的是乘积，我们可以把 \((1)\) 拆成两部分，一部分只有 \(n\) 的乘积，另一部分需要维护 \(n\) 的乘积的质因子。
乘积很好维护，线段树即可。而质因子不太好处理。
我们注意到数据范围只有 \(300\)，而 \(300\) 以内的质数只有 \(62\) 个！！！刚好和 long long 的长度一致，于是我们想到long long 状压。
直接用一个数记录状态，而最后统计答案可以用预处理的 \(\frac{p_i-1}{p_i}\)，复习线性求逆元。
坑点较多：
-
乘积和状压可以一棵树，但是 \(lazy\) 标记要用两个，因为一个涉及 \(mod\)。
-
状压从 \(0\) 位开始，并且 long long 必须用
1ll<<i-1。 -
区间修改是乘 \(n^{len}\)，而不是 \(n\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+5,mod = 1e9+7;
#define LL long long
int n,a[N],q;
int prim[N],cnt;
LL nv[N],pv[N];
bool vs[N];
void pre()
{
for(int i=2;i<=300;i++)
{
if(!vs[i]) prim[++cnt]=i;
for(int j=1;j<=cnt&&i*prim[j]<=300;j++)
{
vs[i*prim[j]]=1;
if(i%prim[j]==0) break;
}
}
nv[1]=1;
for(int i=2;i<=300;i++)
nv[i]=(mod-mod/i)*nv[mod%i]%mod;
for(int i=1;i<=cnt;i++)
pv[i]=(prim[i]-1)*1ll*nv[prim[i]]%mod;
}
LL qpow(LL a,LL b)
{
LL res=1;
while(b)
{
if(b & 1) res=res*a%mod;
a=a*a%mod; b>>=1;
}
return res;
}
LL cal(int k)
{
LL res=0;
for(int i=1;i<=cnt&&k!=1;i++)
{
if(k%prim[i]==0) res+=(1ll<<(i-1));
while(k%prim[i]==0) k/=prim[i];
}
return res;
}
struct T
{
int l,r;
LL p,lz2,ck=1,lz1=1;
} tr[N<<2];
void up(int k) {tr[k].ck=tr[k<<1].ck*tr[k<<1|1].ck%mod; tr[k].p=tr[k<<1].p|tr[k<<1|1].p;}
void down(int k)
{
if(tr[k].lz1!=1)
{
tr[k<<1].ck=tr[k<<1].ck*qpow(tr[k].lz1,tr[k<<1].r-tr[k<<1].l+1)%mod;
tr[k<<1|1].ck=tr[k<<1|1].ck*qpow(tr[k].lz1,tr[k<<1|1].r-tr[k<<1|1].l+1)%mod;
tr[k<<1].lz1=tr[k<<1].lz1*tr[k].lz1%mod;
tr[k<<1|1].lz1=tr[k<<1|1].lz1*tr[k].lz1%mod;
tr[k].lz1=1;
}
if(tr[k].lz2)
{
tr[k<<1].p|=tr[k].lz2;
tr[k<<1|1].p|=tr[k].lz2;
tr[k<<1].lz2|=tr[k].lz2;
tr[k<<1|1].lz2|=tr[k].lz2;
tr[k].lz2=0;
}
}
void bui(int k,int l,int r)
{
tr[k].l=l; tr[k].r=r;
if(l==r) return tr[k].ck=a[l],tr[k].p=cal(a[l]),void(0);
int mid=l+r>>1;
bui(k<<1,l,mid); bui(k<<1|1,mid+1,r);
up(k);
}
void mdf(int k,int l,int r,int v)
{
if(l<=tr[k].l&&tr[k].r<=r)
{
LL tmp=cal(v),tmp2=qpow(v,tr[k].r-tr[k].l+1);
tr[k].ck=tr[k].ck*tmp2%mod;
tr[k].p|=tmp;
tr[k].lz2|=tmp;
tr[k].lz1=tr[k].lz1*v%mod;
return;
}
down(k);
int mid=tr[k].l+tr[k].r>>1;
if(l<=mid) mdf(k<<1,l,r,v);
if(r>mid) mdf(k<<1|1,l,r,v);
up(k);
}
LL quec(int k,int l,int r)
{
if(l<=tr[k].l&&r>=tr[k].r) return tr[k].ck;
down(k);
int mid=tr[k].l+tr[k].r>>1;LL res=1;
if(l<=mid) res=res*quec(k<<1,l,r)%mod;
if(r>mid) res=res*quec(k<<1|1,l,r)%mod;
return res;
}
LL quep(int k,int l,int r)
{
if(l<=tr[k].l&&r>=tr[k].r) return tr[k].p;
down(k);
int mid=tr[k].l+tr[k].r>>1;LL res=0;
if(l<=mid) res|=quep(k<<1,l,r);
if(r>mid) res|=quep(k<<1|1,l,r);
return res;
}
int main()
{
// freopen("array.in","r",stdin);
// freopen("array.out","w",stdout);
pre();
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
bui(1,1,n);
while(q--)
{
string c; cin>>c;
if(c[0]=='M')
{
int x,y,z; scanf("%d%d%d",&x,&y,&z);
mdf(1,x,y,z);
}
else
{
int x,y; scanf("%d%d",&x,&y);
LL res=quec(1,x,y),p=quep(1,x,y);
for(int i=1;p;i++)
{
if(p&1) res=res*pv[i]%mod;
p>>=1;
}
printf("%lld\n",res);
}
}
return 0;
}
T4 ODW
明显 LCA，倍增跳。学到新知识：根号分治！！！
就是步长较大的暴跳，一共跳不了几次。步长较小的可以预处理。
复习 LCA。预处理用树上差分，\(v_{u,c}\) 类似前缀和维护从 \(u\) 开始，步长为 \(c\) 到根的权值和。
注意的就是书上差分要考虑某一段不能整除 \(c\) 的情况，需要取整并向上多跳一个步长满足差分。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 50005,B = 20;
int n,m,a[N],b[N];
int lg[N];//preprocess log
int fa[20][N],dep[N] ,va[B][N];
int tot,head[N];
struct E {int u,v;} e[N<<1];
void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
int kth(int u,int k)
{
for(int i=lg[k];i>=0;i--) if(k>>i&1) u=fa[i][u];
return u;
}
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int i=17;i>=0;i--) if(dep[fa[i][x]]>=dep[y]) x=fa[i][x];
if(x==y) return x;
for(int i=17;i>=0;i--) if(fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
void dfs(int u,int f)
{
dep[u]=dep[f]+1; fa[0][u]=f;
for(int i=1;i<=lg[dep[u]];i++) fa[i][u]=fa[i-1][fa[i-1][u]];
for(int i=1,v=f;i<B;i++,v=fa[0][v]) va[i][u]=a[u]+va[i][v];
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v; if(v==f) continue;
dfs(v,u);
}
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
dfs(1,0);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<n;i++)
{
int c,u=b[i],v=b[i+1]; scanf("%d",&c);
int d=lca(u,v),res=0;
if(c>=B)
{
res=a[u]+a[v];
while(1)//voilently jump
{
if(dep[u]<dep[v]) swap(u,v);
int anc=kth(u,c);
if(dep[anc]<dep[d]) break;
res+=a[anc]; u=anc;
}
if(u==d||v==d) res-=a[d];
}
else
{
int gap=dep[u]-dep[d];
int anc=kth(u,gap/c*c+c);//additionally jump one c,for difference
res+=va[c][u]-va[c][anc];
gap=dep[v]-dep[d]-1;//delete node d
anc=kth(v,gap/c*c+c);
if(v!=d) res+=va[c][v]-va[c][anc];
}
printf("%d\n",res) ;
}
return 0;
}