前言
目前感觉主要就是矩阵加速，一般·看到大一点的范围（加小一点的范围）可能会用到，是一个神奇的东西。
运用在广义矩阵和状态转移上面。
板子还是打得比较舒服的。
广义矩阵乘法具有结合律的条件是分别满足交换律和结合律，内层对外层满足分配律。
[NOI Online #1 入门组] 魔法
题目描述
C 国由 \(n\) 座城市与 \(m\) 条有向道路组成，城市与道路都从 \(1\) 开始编号，经过 \(i\) 号道路需要 \(t_i\) 的费用。
现在你要从 \(1\) 号城市出发去 \(n\) 号城市，你可以施展最多 \(k\) 次魔法，使得通过下一条道路时，需要的费用变为原来的相反数，即费用从 \(t_i\) 变为 \(-t_i\)。请你算一算，你至少要花费多少费用才能完成这次旅程。
注意：使用魔法只是改变一次的花费，而不改变一条道路自身的 \(t_i\)；最终的费用可以为负，并且一个城市可以经过多次（包括 \(n\) 号城市）。
数据规模与约定
对于全部的测试点，保证：
- \(1 \leq n \leq 100\)，\(1 \leq m \leq 2500\)，\(0 \leq k \leq 10^6\)。
- \(1 \leq u_i, v_i \leq n\)，\(1 \leq t_i \leq 10^9\)。
- 给出的图无重边和自环，且至少存在一条能从 \(1\) 到达 \(n\) 的路径。
题解
比较神奇，考虑构造矩阵。首先我们有一个邻接矩阵，表示两点之间的最小花费，所以先做一遍Floyd。 \(O(n^{3})\)
然后暴力枚举每一条边变成负数之后的矩阵，存入新的矩阵，此时得到的就是k=1的情况。 \(O(mn^{2})\)
现在我们重新定义矩阵乘法,原来的加变成取min,原来的*变成+，其实就是松弛操作。
感性的东西来了，每对一个矩阵乘上k=1情况下的矩阵就相当于多施一次魔法，就是这样，其实也很形象。
这个矩阵仍然一样有结合律，证明如下：
+和min分别有交换律和结合律，+对min有分配律，得证。
所以就可以愉快地用矩阵加速了~。 \(O(\log_{k}n^{2})\)
code
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,m,kk;
struct mat{
ll a[105][105];
mat(){memset(a,0x3f,sizeof(a));}
void operator ~(){
for(int i=1;i<=n;i++)
a[i][i]=0;
}
mat operator *(const mat &T)const{
mat res;
ll r;
for(int i=1;i<=n;i++)
for(int k=1;k<=n;k++){
r=a[i][k];
for(int j=1;j<=n;j++)
res.a[i][j]=min(res.a[i][j],r+T.a[k][j]);
}
return res;
}
mat operator ^(const ll &x)const{
mat res,bas=*this;
~res;
for(ll b=x;b;b>>=1,bas=bas*bas)
if(b&1)
res=res*bas;
return res;
}
}ans,ba;
int main(){
ll u[2505],v[2505],w[2505];
scanf("%lld%lld%lld",&n,&m,&kk);
~ans;~ba;
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);
ans.a[u[i]][v[i]]=w[i];
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ans.a[i][j]=min(ans.a[i][j],ans.a[i][k]+ans.a[k][j]);
if(kk==0){
printf("%lld",ans.a[1][n]);
return 0;
}
for(int k=1;k<=m;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
ba.a[i][j]=min(ba.a[i][j],ans.a[i][u[k]]+ans.a[v[k]][j]-w[k]);
ans=ba^kk;
printf("%lld",ans.a[1][n]);
}
GSS3 - Can you answer these queries III
题目描述
\(n\) 个数，\(q\) 次操作
操作0 x y把\(A_x\) 修改为\(y\)
操作1 l r询问区间\([l, r]\) 的最大子段和
题解
这里就是为了练矩阵才写矩阵的。
设 \(f(x)\) 为以当前数结尾的最大子段, \(g(x)\) 为前x个数的最大子段。
有 \(g(x)=max(f(x),g(x))\) , \(f(x)=max(a_x,a_x+f(x-1))\)。
定义矩阵乘法为先取加后取max
考虑矩阵
然后把矩阵放到恰好需要结合律的线段树上。每次修改之后pushup上去就可以了。注意最后一次与 \(i=0\) 时作矩阵运算相当于直接取 \(max((2,1),(2,3))\)
code
#include<iostream>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=50005;
int n,v[N],q;
struct mat{
int a[5][5];
mat(){memset(a,0xcf,sizeof(a));}
mat operator *(const mat &T)const{
mat res;
for(int i=1;i<=3;i++)
for(int k=1;k<=3;k++){
int r=a[i][k];
for(int j=1;j<=3;j++)
res.a[i][j]=max(res.a[i][j],r+T.a[k][j]);
}
return res;
}
}t[N<<2],ba;
void init(mat &res,int x){
res.a[1][1]=res.a[2][1]=res.a[1][3]=res.a[2][3]=x;
res.a[1][2]=res.a[3][1]=res.a[3][2]=-inf;
res.a[2][2]=res.a[3][3]=0;
}
void pushup(int p){
t[p]=t[p<<1]*t[p<<1|1];
}
void biuld(int p=1,int cl=1,int cr=n){
if(cl==cr){
init(t[p],v[cl]);
return ;
}
int mid=cl+cr>>1;
biuld(p<<1,cl,mid);
biuld(p<<1|1,mid+1,cr);
pushup(p);
}
void update(int d,int x,int p=1,int cl=1,int cr=n){
if(cl==cr){
init(t[p],x);
return ;
}
int mid=cl+cr>>1;
if(mid>=d) update(d,x,p<<1,cl,mid);
else update(d,x,p<<1|1,mid+1,cr);
pushup(p);
}
mat query(int l,int r,int p=1,int cl=1,int cr=n){
if(l<=cl&&cr<=r)
return t[p];
int mid=cl+cr>>1;
if(mid>=l&&mid<r) return query(l,r,p<<1,cl,mid)*query(l,r,p<<1|1,mid+1,cr);
else if(mid>=l) return query(l,r,p<<1,cl,mid);
else if(mid<r) return query(l,r,p<<1|1,mid+1,cr);
}
int main(){
int a,b,c;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
biuld();
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&a,&b,&c);
if(a==0)
update(b,c);
else{
mat tmp=query(b,c);
printf("%d\n",max(tmp.a[2][1],tmp.a[2][3]));
}
}
}