https://oj.gxyzh.com/d/hzoj/contest/69661ae9c01e1c1c7ca58fc7
毕业旅行
题解
看数据，知道这道题应该用 状压+矩阵快速幂。
赛时拿了部分分。
《观看》测试点 1、2、4、5，再联系旅行商问题，可以轻松使用状压 \(dp\) 解决。
设 \(dp_{i,j,k}\)，表示第 \(i\) 步，走过必经城市集合为 \(j\)，且最后一步为 \(k\)。
设邻接矩阵 \(map_{i,j}\) 表示 \(i\to j\) 的直接边。
转移时 乘上邻接矩阵。
（在这里能发现矩阵快速幂的端倪）。
《观看》测试点 3，发现可以用矩阵快速幂解决：
设 \(dp_{i,j}\) 表示第 \(i\) 步，最后一步为 \(j\)。
有 \(dp_{i,j}=\sum_{k=1}^{n}dp_{i-1,k}\times map_{k,j}\)
写成矩阵形式：
《观看》测试点 6~10，现在想将状压的一维去掉，转化为测试点 3。
发现是集合的关系，因此使用容斥原理。
其中 \(f_i\) 表示关掉 \(i\) 个必经城市，即删掉 \(i\) 个点。
采用 \(2^k\) 枚举关掉的点集，内部套用矩阵快速幂。
代码
#include<iostream>
#define int long long
using namespace std;
constexpr int p=1e9+9;
int n,m,k,d,u[155],v[155],ans;
struct Mat{int a[20][20];void clear(){for(int i=0;i<n;i++)for(int j=0;j<n;j++)a[i][j]=0;}Mat operator *(const Mat &c)const{Mat b=*this,ans; ans.clear();for(int i=0;i<n;i++)for(int k=0;k<n;k++)for(int j=0;j<n;j++)ans.a[i][j]+=b.a[i][k]*c.a[k][j],ans.a[i][j]%=p;return ans;}Mat operator ^(int b)const{Mat a=*this,ans; ans.clear();for(int i=0;i<n;i++)ans.a[i][i]=1;while(b){if(b&1)ans=ans*a;a=a*a,b>>=1;}return ans;}
}a,b;
int get_ans(){b=b*(a^(d-1)); int cc=0;for(int i=0;i<n;i++)cc=(cc+b.a[0][i])%p;return cc;
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>k>>d;for(int i=1;i<=m;i++)cin>>u[i]>>v[i],u[i]--,v[i]--;for(int i=0;i<(1<<k);i++){int cnt=0; a.clear(),b.clear();for(int j=0;j<k;j++)if((i>>j)&1)cnt++;for(int j=1;j<=m;j++){if(((i>>u[j])&1)||((i>>v[j])&1))continue;a.a[u[j]][v[j]]=a.a[v[j]][u[j]]=1;}for(int j=0;j<n;j++)if(!((i>>j)&1))b.a[0][j]=1;int fuc=get_ans();if(cnt&1)ans=(ans-fuc)%p;else ans=(ans+fuc)%p;}cout<<(ans+p)%p<<'\n';return 0;
}
潜入计划
题解
部分分
20% 采用分层图。
另外 20% 对于 \(X=0\)，可以注意到通过最短路可以求出答案 \(ans=dis_{1\to n}\times 2+h_n\)
正解
贪心的想，什么时候需要上升和下降。
对于上升操作来说，只要保证前面飞行合法就不需要上升。当且仅当我飞不过去了才上升。
对于下降操作来说，只要我不会越过目标点就不需要下降。当且仅当我会越过目标点才下降。
可以发现，这就是最优答案。
最后的某条合法最短路径一定是长这样：先一直下降高度，直到高度为零，然后每次都上升到需要的高
度后再飞。
因此，可以将 \(Dijkstra\) 魔改，在中途记录当前高度，从而转移。
代码
#include<iostream>
#include<queue>
#define int long long
using namespace std;
constexpr int N=1e5+5;
int n,m,X,h[N];
struct node{ int to,len; };
vector<node> v[N];
struct C{int to,len;bool operator <(const C &x)const{return len>x.len;}
};
priority_queue<C> q;
int dis[N],now[N];
void Dijkstra(){for(int i=2;i<=n;i++)dis[i]=1e17;now[1]=X,q.push(C{1,0});while(!q.empty()){int x=q.top().to,len=q.top().len; q.pop();if(dis[x]!=len)continue;for(node u:v[x]){int s=len+u.len;if(now[x]-u.len<0){s+=u.len-now[x];if(dis[u.to]>s)dis[u.to]=s,now[u.to]=0,q.push(C{u.to,dis[u.to]});}else if(now[x]-u.len>h[u.to]){s+=now[x]-u.len-h[u.to];if(dis[u.to]>s)dis[u.to]=s,now[u.to]=h[u.to],q.push(C{u.to,dis[u.to]});}else {if(dis[u.to]>s)dis[u.to]=s,now[u.to]=now[x]-u.len,q.push(C{u.to,dis[u.to]});}}}
}signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>X;for(int i=1;i<=n;i++)cin>>h[i];for(int i=1,A,B,T;i<=m;i++){cin>>A>>B>>T;if(h[A]>=T)v[A].push_back(node{B,T});if(h[B]>=T)v[B].push_back(node{A,T});}Dijkstra();if(dis[n]==1e17)cout<<-1<<'\n';else cout<<dis[n]+h[n]-now[n]<<'\n';return 0;
}