鸽了三年的东西。
[NOI Online #1 入门组] 文具订购
枚举即可。
[NOI Online #1 入门组] 魔法
感觉是道不错的dp。
令 \(f_{k,i,j}\) 表示使用 \(k\) 次魔法后，\(i,j\) 间的最短路的长度。
当 \(k=0\) 时，裸的 floyd。
当 \(k=1\) 时，可以将路径上某条边取反，令取反的边为 \((u,v,w)\)，\(f_{1,i,j}=\min\{f_{0,i,u}+f_{0,v,j}-w\}\)。
当 \(k\ge 2\) 时，每次可以再将某条边取反，此时就像建分层图一样，将每一个 \(k\) 看作一层,可以得到 \(f_{k,i,j}=\min\{f_{k-1,i,p}+f_{1,p,j}\}\)。
虽然不会证，但我们知道这个式子具有分配律和结合律，可以算出 \(f_0,f_1\)，用广义矩阵乘加速。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=110,M=2510;
int n,m,k,f[N][N];
struct edge{
int u,v,w;
}e[M];
struct matrix{
int a[N][N];
matrix(){
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++){
a[i][i]=0;
}
}
matrix operator *(const matrix &rhs){
matrix ans;
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],a[i][k]+rhs.a[k][j]);
}
}
}
return ans;
}
}base,res;
matrix qpow(matrix a,int b){
matrix ans;
while(b){
if(b&1){
ans=ans*a;
}
a=a*a;
b>>=1;
}
return ans;
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(k);
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
f[i][i]=0;
}
for(int i=1;i<=m;i++){
int u,v,w;
read(u),read(v),read(w);
f[u][v]=w;
e[i].u=u,e[i].v=v,e[i].w=w;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(i==k){
continue;
}
for(int j=1;j<=n;j++){
if(j==k||i==k){
continue;
}
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
res.a[i][j]=f[i][j];
}
}
if(!k){
write_endl(f[1][n]);
return 0;
}
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
base.a[j][k]=min(base.a[j][k],min(f[j][u]+f[v][k]-w,f[j][k]));
}
}
}
res=res*qpow(base,k);
write_endl(res.a[1][n]);
return 0;
}
[NOI Online #1 入门组] 跑步
题目转化一下，变成求分拆数的方案数。
分拆数dp有两种写法：
第一种，令 \(f_{i,j}\) 表示将 \(j\) 分成不大于 \(i\) 的数的方案数。
\[f_{i,j}=f_{i-1,j}+f_{i,j-i},f_{0,0}=1
\]
我们发现，这其实就是个完全背包问题，第一维枚举 \(i\)，第二维枚举 \(j\)，将其降维得到：
\[f_j=f_j+f_{j-i},f_0=1
\]
第二种，令 \(g_{i,j}\) 表示将 \(j\) 分成 \(i\) 个数的方案数。
\[g_{i,j}=g_{i-1,j-1}+g_{i,j-i},g_{0,0}=1
\]
这个可以理解一下，就是要么在序列后面加 \(1\) 个 \(1\)，要么将所有数加上 \(1\)。
但问题来了，这两个dp都是 \(O(n^2)\) 级别的，需要优化。
考虑根号分治，对于小于等于根号的做第一种dp，复杂度为 \(O(n\sqrt n\)，对于大于根号的做第二种dp，不过令在序列后加的数为 \(\sqrt n+1\)，因为总数量不会超过 \(\sqrt n\)，所以复杂度为 \(O(n\sqrt n)\)，总复杂度也为 \(O(n\sqrt n)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e5+10,M=500;
int f[N],g[M][N],n,mod;
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(mod);
int B=sqrt(n)+1;
f[0]=1;
for(int i=1;i<B;i++){
for(int j=i;j<=n;j++){
f[j]=(f[j]+f[j-i])%mod;
}
}
g[0][0]=1;
for(int i=1;i<B;i++){
for(int j=i;j<=n;j++){
g[i][j]=g[i][j-i];
if(j>=B){
g[i][j]=g[i][j]+g[i-1][j-B];
}
g[i][j]%=mod;
}
}
int ans=0;
for(int i=0;i<=n;i++){
int s=0;
for(int j=0;j<B;j++){
s+=g[j][i];
}
s%=mod;
ans+=s*f[n-i]%mod;
ans%=mod;
}
write_endl(ans);
return 0;
}