「F·S·Y·O」on 10.17
T1 F
解題思路
因為每個點會産生貢獻當且僅當它在可以到他的點之前被删除，并且此題遵守期望的線性性。
是以設所有可以到達點 \(i\) 的數量為 \(c_i\) 那麼答案就是 \(\sum \frac{1}{c_i}\) 。
縮點+拓撲排序+bitset 可以做到 \(\mathcal{O}(\frac{n^3}{w})\) 直接搜就是 \(\mathcal{O}(n^2)\)
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e3+10,mod=998244353;
int n,ans,all,tim,top,sta[N],dfn[N],low[N],bel[N],cnt[N],du[N],can[N];
int tot=1,head[N],ver[N*N],nxt[N*N],fro[N*N];
char ch[N];
bool vis[N];
vector<int> v[N];
void add_edge(int x,int y)
{
ver[++tot]=y; fro[tot]=x;
nxt[tot]=head[x]; head[x]=tot;
}
int power(int x,int y,int p=mod)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%mod;
x=x*x%mod; y>>=1;
}
return temp;
}
void tarjan(int x)
{
int temp; vis[x]=true; dfn[x]=low[x]=++tim; sta[++top]=x;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(!dfn[to]) tarjan(to),low[x]=min(low[x],low[to]);
else if(vis[to]) low[x]=min(low[x],dfn[to]);
}
if(low[x]!=dfn[x]) return ; all++;
do
{
temp=sta[top--]; vis[temp]=false;
bel[temp]=all; cnt[all]++;
}while(temp!=x);
}
void dfs(int x,int from)
{
vis[x]=true; can[x]+=cnt[from];
for(auto to:v[x]) if(!vis[to]) dfs(to,from);
}
signed main()
{
freopen("f.in","r",stdin); freopen("f.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)
{
scanf("%s",ch+1);
for(int j=1;j<=n;j++)
if(ch[j]^48)
add_edge(i,j);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int i=2;i<=tot;i++)
{
int x=fro[i],y=ver[i];
if(bel[x]==bel[y]) continue;
v[bel[x]].push_back(bel[y]); du[bel[y]]++;
}
for(int i=1;i<=all;i++)memset(vis,false,sizeof(vis)),dfs(i,i);
for(int i=1;i<=n;i++) ans=(ans+power(can[bel[i]],mod-2))%mod;
printf("%lld",ans);
return 0;
}
T2 S
字元串 DP(KMP)。
設 \(f_{i,j}\) 表示 \(S\) 到 \(i\) 位置，目前比對到 \(T\) 的位置 \(j\) 。
每次對于删除或者不删除 \(i+1\) 進行轉移，如果不删除就不斷跳 \(nxt\) 看 \(k+1\) 能否和 \(i+1\) 成功比對。
轉移即可。。
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=8e3+10,INF=0x3f3f3f3f;
int n,m,ans=INF,nxt[N],f[N][N];
char s[N],t[N];
signed main()
{
freopen("s.in","r",stdin); freopen("s.out","w",stdout);
scanf("%s%s",s+1,t+1); n=strlen(s+1); m=strlen(t+1);
for(int i=2,j=0;i<=m;i++)
{
while(j&&t[j+1]!=t[i]) j=nxt[j];
if(t[j+1]==t[i]) j++; nxt[i]=j;
}
memset(f,0x3f,sizeof(f));
f[1][0]=(s[1]==t[1]);
if(s[1]==t[1]) f[1][1]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<=min(m-1,i);j++)
{
if(f[i][j]>=INF) continue;
int k=j;
while(k&&s[i+1]!=t[k+1]) k=nxt[k];
if(t[k+1]==s[i+1]) k++;
if(k!=m) f[i+1][k]=min(f[i+1][k],f[i][j]);
f[i+1][j]=min(f[i+1][j],f[i][j]+1);
}
for(int i=0;i<=m;i++) ans=min(ans,f[n][i]);
printf("%d",ans);
return 0;
}
T3 Y
暴搜竟然有 70pts ！！（盡管我沒打出來），BFS 目前空格的位置，開一個四位數組記錄空格以及指定棋子所在位置是否經過過。
枚舉空格的移動，當他移動到指定棋子的位置時兩者位置互換，于是我們得到了一份 70pts 的代碼(\(code\))
然後發現有許多狀态時重複的，于是我們考慮初始化。
枚舉每一個點時指定棋子的位置，在枚舉周圍的點是空格的情況，BFS出這幾個格子之間不經過指定格子到達别的格子的距離，建邊。
對于每一個詢問跑一邊最短路 複雜度 \(\mathcal{O}(n^2m^2+qnmlog(nm))\)
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
#define left Left
#define right Right
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=40,M=4e3+10,INF=0x3f3f3f3f3f3f3f3f;
const int up=0,down=1,left=2,right=3;
int n,m,qus,ans,dis[N][N],dist[M];
int d1[10]={-1,1,0,0};
int d2[10]={0,0,-1,1};
int tot=1,head[M],ver[M],nxt[M],edge[M];
bool can[N][N],vis[M];
void add_edge(int x,int y,int val)
{
ver[++tot]=y; edge[tot]=val;
nxt[tot]=head[x]; head[x]=tot;
}
int id(int x,int y,int sta){return ((x-1)*m+y)*4+sta;}
void bfs(int sx,int sy,int tx,int ty,int sta)
{
queue<pair<int,int> > q; memset(dis,0,sizeof(dis));
q.push(make_pair(sx,sy)); dis[sx][sy]=1;
while(!q.empty())
{
pair<int,int> temp=q.front();q.pop();
int x=temp.first,y=temp.second;
for(int i=0;i<=3;i++)
{
int nx=x+d1[i],ny=y+d2[i];
if(!can[nx][ny]||dis[nx][ny]||(nx==tx&&ny==ty)) continue;
dis[nx][ny]=dis[x][y]+1; q.push(make_pair(nx,ny));
}
}
if(sta==4) return ;
for(int i=0;i<=3;i++)
{
int x=tx+d1[i],y=ty+d2[i];
if(!dis[x][y]||(x==sx&&y==sy)) continue;
add_edge(id(tx,ty,sta),id(tx,ty,i),dis[x][y]-1);
}
add_edge(id(tx,ty,sta),id(sx,sy,sta^1),1);
}
void solve(int sx,int sy)
{
memset(dist,0x3f,sizeof(dist)); memset(vis,false,sizeof(vis));
priority_queue<pair<int,int> > q;
for(int i=0;i<=3;i++)
{
int x=sx+d1[i],y=sy+d2[i];
if(!dis[x][y]) continue;
dist[id(sx,sy,i)]=dis[x][y]-1;
q.push(make_pair(-dist[id(sx,sy,i)],id(sx,sy,i)));
}
while(!q.empty())
{
int x=q.top().second; q.pop();
if(vis[x]) continue; vis[x]=true;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],val=edge[i];
if(dist[to]<=dist[x]+val) continue;
dist[to]=dist[x]+val; q.push(make_pair(-dist[to],to));
}
}
}
signed main()
{
freopen("y.in","r",stdin); freopen("y.out","w",stdout);
n=read(); m=read(); qus=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
can[i][j]=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(!can[i][j]) continue;
if(can[i-1][j]) bfs(i-1,j,i,j,up);
if(can[i+1][j]) bfs(i+1,j,i,j,down);
if(can[i][j-1]) bfs(i,j-1,i,j,left);
if(can[i][j+1]) bfs(i,j+1,i,j,right);
}
while(qus--)
{
int basx,basy,sx,sy,tx,ty;
basx=read(); basy=read(); sx=read(); sy=read(); tx=read(); ty=read();
if(sx==tx&&sy==ty){printf("0\n");continue;}
ans=INF; bfs(basx,basy,sx,sy,4); solve(sx,sy);
for(int i=0;i<=3;i++) ans=min(ans,dist[id(tx,ty,i)]);
printf("%lld\n",ans>=INF?-1ll:ans);
}
return 0;
}