Arbitrage
A 货币可以以 \(x\) 的汇率兑换 B 货币，就从 A 向 B 连一条权值为 \(x\) 的边，改一下 \(Floyd\) 即可。
点击查看代码
#include <iostream>
#include <string>
#include <cstdio>
#include <map>
#define Hibiki namespace
#define Wataru std
using Hibiki Wataru;
int n,m;
double e[32][32];
string s1,s2;
map<string,int> Map;
int main() {
int tot=0;
while(~scanf("%d",&n)) {
if(n==0) break;
tot++;
for(int i=1;i<=n;i++) cin>>s1,Map[s1]=i;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) e[i][j]=1e-5;
scanf("%d",&m);
for(int i=1;i<=m;i++) {
double x;
cin>>s1;
cin>>x;
cin>>s2;
e[Map[s1]][Map[s2]]=x;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++) e[i][j]=max(e[i][j],e[i][k]*e[k][j]);
double ma=-1.0;
for(int i=1;i<=n;i++) ma=max(ma,e[i][i]);
if(ma>1.000) printf("Case %d: Yes\n",tot);
else printf("Case %d: No\n",tot);
}
return 0;
}
没有硝烟的战争
设 \(f_{i,j}\) 为第 \(i\) 只动物报 \(j\) 是否可以获胜，分类讨论：
-
若 \(a_i = a_{i+1}\)，即 \(i\) 和 \(i+1\) 同一种族，那么只要 \(f_{i+1,j+1}\lor f_{i+1,j+2}\lor\dots\lor f_{i+1,j+k}\) 为 \(1\) 即可。
-
若 \(a_i \ne a_{i+1}\)，即 \(i\) 和 \(i+1\) 不为同一种族，则与第一种情况相反。
实现时从 \(m\) 往前遍历，加上后缀和优化可过。
点击查看代码
#include <iostream>
#include <cstdio>
#define Hibiki namespace
#define Wataru std
using Hibiki Wataru;
int n,m,k,sum[5002][5002];
bool a[5002],f[5002][5002];
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int j=m-1;j>0;j--)
for(int i=n;i>0;i--) {
if(a[i%n+1]==a[i])
f[i][j]=sum[i%n+1][j+1]-sum[i%n+1][min(j+k,m)+1];
else f[i][j]=!(sum[i%n+1][j+1]-sum[i%n+1][min(j+k,m)+1]);
sum[i][j]=sum[i][j+1]+f[i][j];
}
for(int i=1;i<=n;i++)
printf("%d ",(sum[i][1]-sum[i][k+1])?a[i]:a[i]^1);
return 0;
}
秘密通道
每块地向四周连边，并分别记录四个方向第一块遇到的墙壁，其中距离最短的墙壁前的空地向其他三个方向的空地连边，然后跑 \(dijkstra\)。
点击查看代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#define Hibiki namespace
#define Wataru std
using Hibiki Wataru;
int n,m,sx,sy,tx,ty,cnt,dis[600002],head[600002];
int arrx[4]={1,0,-1,0},arry[4]={0,1,0,-1},gt[4][2];
bool a[502][502];
char s[502];
int Num(int x,int y) {
return (x-1)*m+y;
}
struct edge{
int to,nxt,len;
}e[5000002];
void addedge(int A,int B,int C) {
e[++cnt].to=B;
e[cnt].len=C;
e[cnt].nxt=head[A];
head[A]=cnt;
}
struct node{
int pos,dis;
bool operator<(const node &x) const{
return x.dis<dis;
}
};
priority_queue<node> p;
void dijkstra() {
for(int i=1;i<=n*m;i++) dis[i]=2147483647;
dis[Num(sx,sy)]=0;
p.push((node){Num(sx,sy),0});
while(p.size()) {
node tmp=p.top();
p.pop();
int u=tmp.pos;
for(int i=head[u];i;i=e[i].nxt) {
int v=e[i].to;
if(dis[u]+e[i].len<dis[v]) {
dis[v]=dis[u]+e[i].len;
p.push((node){v,dis[v]});
}
}
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) {
scanf("%s",s+1);
for(int j=1;j<=m;j++) {
a[i][j]=(s[j]=='#');
if(s[j]=='C') sx=i,sy=j;
if(s[j]=='F') tx=i,ty=j;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if(a[i][j]) continue;
int xx,yy,mi=2147483647,minum;
for(int k=0;k<4;k++) {
xx=i+arrx[k],yy=j+arry[k];
if(!a[xx][yy]) addedge(Num(i,j),Num(xx,yy),1);
xx=i,yy=j;
while(!a[xx+arrx[k]][yy+arry[k]]) xx+=arrx[k],yy+=arry[k];
gt[k][0]=xx,gt[k][1]=yy;
if(abs(xx-i)+abs(yy-j)<mi) mi=abs(xx-i)+abs(yy-j),minum=k;
}
if(mi) addedge(Num(i,j),Num(gt[minum][0],gt[minum][1]),mi);
for(int k=0;k<4;k++)
if(k!=minum)
addedge(Num(i,j),Num(gt[k][0],gt[k][1]),mi+1);
}
dijkstra();
if(dis[Num(tx,ty)]==2147483647) printf("nemoguce\n");
else printf("%d\n",dis[Num(tx,ty)]);
return 0;
}
城市猎人
暴力枚举每个 \(i\) 的倍数，并查集按秩合并，开数组记录每个点连上父亲的时间，查询时跳 \(lca\) 求最大值。
注意不能路径压缩，\(dep\) 可以 \(getf\) 时顺便求出来。
点击查看代码
#include <iostream>
#include <cstdio>
#include <queue>
#define Hibiki namespace
#define Wataru std
using Hibiki Wataru;
int n,m,q,fa[100002],siz[100002],dep[100002],tim[100002];
int Getf(int x) {
if(fa[x]==x) {
dep[x]=0;
return x;
}
int res=Getf(fa[x]);
dep[x]=dep[fa[x]]+1;
return res;
}
int main() {
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
for(int i=1;i<=m;i++) {
int u=m-i+1;
for(int v=u*2;v<=n;v+=u) {
int uu=Getf(u),vv=Getf(v);
if(uu==vv) continue;
if(siz[uu]>siz[vv]) swap(uu,vv);
fa[uu]=vv,siz[vv]=max(siz[vv],siz[uu]+1),tim[uu]=i;
}
}
while(q--) {
int u,v;
scanf("%d%d",&u,&v);
int ans=0;
Getf(u),Getf(v);
if(dep[u]<dep[v]) swap(u,v);
while(dep[u]>dep[v]) ans=max(ans,tim[u]),u=fa[u];
while(u!=v) {
ans=max(ans,tim[u]),u=fa[u];
ans=max(ans,tim[v]),v=fa[v];
}
printf("%d\n",ans);
}
return 0;
}
完结撒花 OwO
标签：Hibiki,int,题解,CSP2022,fa,ans,S2,include,define From： https://www.cnblogs.com/Sharing666/p/16730630.html