9.19
洛谷月赛
(1)雷雨——dij
啊啊啊差点点想到，还是太菜
一直想从一个点跑最短路然后$$ dis[1][a]+dis[n][b]+dis[n][c] $$然后复杂度很假，最后摸了整场考试——殊不知这是巨简单的一场
正解其实是从(1,a) (n,b) (n,c) 每个点为起点跑dij，然后复杂度O(3*n^2) 。。。
学到了一点：函数里传数组
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1005;
inline int read() {
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x;
}
typedef long long LL;
int n,m,a,b,c;
LL ans=1e18;//开到1e18,0x3f3f3f3f不够
LL A[N][N],B[N][N],C[N][N],val[N][N];
struct node{
int x,y;LL d;
node(){}
node(int x_,int y_,LL d_):x(x_),y(y_),d(d_){}
bool operator < (const node &w) const {
return d>w.d;
}
};
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
bool vis[N][N];
void dij(int stx,int sty,LL (*dis)[N]) {
priority_queue<node>q;
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(A));//sizeof
dis[stx][sty]=val[stx][sty];
q.push(node(stx,sty,dis[stx][sty]));
while(!q.empty()) {
int x=q.top().x,y=q.top().y; q.pop();
if(vis[x][y]) continue;
vis[x][y]=1;
for(int i=0;i<4;i++) {
int xx=x+dx[i],yy=y+dy[i];
if(xx>n||xx<1||yy>m||yy<1) continue;
if(dis[xx][yy]>dis[x][y]+val[xx][yy])
dis[xx][yy]=dis[x][y]+val[xx][yy],q.push(node(xx,yy,dis[xx][yy]));
}
}
}
int main() {
n=read();m=read();a=read();b=read();c=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
val[i][j]=read();
dij(1,a,A);
dij(n,b,B);
dij(n,c,C);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
ans=min(ans,A[i][j]+B[i][j]+C[i][j]-val[i][j]*2);
printf("%lld
",ans);
return 0;
}
//dij
(2)梦原——权值树状数组
如果新的点比并上去的点苹果少，那么每次往上并上一个新的点，所产生的代价是0
如果新的点比并上去的点苹果多，那你就需要多花 多出来的苹果数 那么多，
那么对于新加的点i，所产生的期望代价就是看[i - k，i - 1]这里面的点哪些点比新点的val少，答案加上差值，然后除k
这可以用离散化的权值树状数组维护
具体代码中的a[i]是离散后的排名，c[a[i]]就是原始值
我们要维护区间 [i-k,i-1]中 sum_a[i]及 其个数siz，产生的代价即为a[now]*siz-sum_a[i];
#include <queue>
#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2005000;
const int P=998244353;
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
#define MP make_pair
typedef long long LL;
int n,m,k;
int a[N],c[N];
LL inv[N];
inline void Max(int &x,int y){if(x<y)x=y;}
inline void Min(int &x,int y){if(x>y)x=y;}
inline void plu(int &x,int y){x+=y;x>=P&&(x-=P);}
int ct[N],cd[N];//权值树状数组——个数/和
inline void upd(int x,int v,int vv) {
for(;x<=m;x+=x&(-x)) plu(cd[x],v),ct[x]+=vv;
}
inline pair<int,int> query(int x) {
int sum=0,siz=0;
for(;x;x-=x&(-x)) plu(sum,cd[x]),siz+=ct[x];
return MP(sum,siz);
}
int main() {
n=read();k=read();
for(int i=1;i<=n;i++) c[i]=a[i]=read();
sort(c+1,c+1+n);m=unique(c+1,c+1+n)-c-1;
LL ans=a[1];
a[1]=lower_bound(c+1,c+1+m,a[1])-c;
upd(a[1],c[a[1]],1);
inv[0]=inv[1]=1;
for(int i=2;i<=k;i++)
inv[i]=(P-P/i)*inv[P%i]%P;
for(int i=2;i<=n;i++) {
if(i-k-1>=1) upd(a[i-k-1],P-c[a[i-k-1]],-1);
a[i]=lower_bound(c+1,c+1+m,a[i])-c;
pair<int,int> s=query(a[i]);
ans=(ans+inv[min(k,i-1)]*(1ll*c[a[i]]*s.second%P-s.first+P)%P)%P;
upd(a[i],c[a[i]],1);
}
printf("%lld
",ans);
return 0;
}
(3)线形生物——期望dp
大力推式子
https://www.luogu.com.cn/blog/tyf233/p6835-cnoi2020-xian-xing-sheng-wu
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5;
const int P=998244353;
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
typedef long long LL;
int id,n,m;
LL ans,sum[N],f[N];
vector<int>pre[N];
int main() {
id=read();n=read();m=read();
for(int i=1,x,y;i<=m;i++) {
x=read(),y=read();
pre[x].push_back(y);
}
for(int i=1;i<=n;i++) {
for(int j=0;j<pre[i].size();j++) {
f[i]=(f[i]+sum[i-1]-sum[pre[i][j]-1]+P)%P;
}
f[i]=(f[i]+pre[i].size()+1)%P;
sum[i]=(sum[i-1]+f[i])%P;
}
printf("%lld
",sum[n]);
return 0;
}