四道比较水的题
T1:SPFA+状压
#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define INF 0x3f3f3f3f using namespace std; ],dis[][],num,N,f[<<][],ans,vis[],mp[][]; void get_dis(int num){ queue<,sizeof(vis)); Q.push(num); dis[num][num]=INF; vis[num]=; while (!Q.empty()){ int now=Q.front(); Q.pop(); ; i<=n; i++){ ){ dis[num][i]=max(dis[num][i],min(dis[num][now],mp[now][i])); ; } } } } int main(){ scanf("%d%d%d", &n, &m, &K); ; i<=K; i++) scanf("%d", &id[i]); memset(dis,,sizeof(dis)); ,u,v,w; i<=m; i++) scanf("%d%d%d", &u, &v, &w),mp[v][u]=mp[u][v]=w; ; i<=n; i++) get_dis(i); N=(<<K); ; i<=K; i++) f[<<(i-)][i]=; ; s<N; s++){ num=; ; i<=K; i++) <<(i-))) num++; ; i<=K; i++) <<(i-))){ ; j<=K; j++) <<(j-)))) <<(j-))][j]|=f[s][i]; } ; i<=K; i++) <<(i-))) && f[s][i]){ ]); ans=max(ans,t); } } printf("%d\n", ans); ; }
T2:裸RMQ
#include<stdio.h> #include<string.h> #include<algorithm> #include<cmath> using namespace std; ; ]; int main(){ scanf("%d%d", &n, &m); ; i<=n; i++) scanf(]); ; (<<j)<=n; j++) ; i+(<<(j-))<=n; i++) f[i][j]=min(f[i][j-],f[i+(<<(j-))][j-]); ,a,b; i<=m; i++){ scanf("%d%d", &a, &b); )/log(); printf(<<t)+][t])); } ; }
T3:曼哈顿距离转切比雪夫距离
#include<stdio.h> #include<algorithm> #include<string.h> #define INF 1000010 using namespace std; int n,a,b,x,y,mxx,mxy,mnx,mny; int main(){ scanf("%d", &n); mxx=mxy=-INF; mnx=mny=INF; ; i<=n; i++){ scanf("%d%d", &a, &b); x=b+a; y=b-a; mnx=min(mnx,x); mxx=max(mxx,x); mny=min(mny,y); mxy=max(mxy,y); } printf("%d\n", max(mxx-mnx,mxy-mny)); ; }
T4:set+最短路
#include<stdio.h> #include<string.h> #include<queue> #include<set> #include<algorithm> using namespace std; ; struct node{ int x,y,id; friend bool operator<(node a, node b){ if (a.x==b.x) return a.y<b.y; return a.x<b.x; } }; int n,t,x[maxn],y[maxn],dis[maxn]; queue<int> Q; set<node> st; node mk(int x, int y, int id){ node a; a.x=x; a.y=y; a.id=id; return a; } int main(){ scanf("%d%d", &n, &t); ; i<=n; i++){ scanf("%d%d", &x[i], &y[i]); st.insert(mk(x[i],y[i],i)); } dis[]=; x[]=y[]=; Q.push(); while (!Q.empty()){ int now=Q.front(); Q.pop(); ; i<=; i++) ; j<=; j++){ int X=x[now]+i, Y=y[now]+j; )); if (next!=st.end()){ dis[next->id]=dis[now]+; Q.push(next->id); if (Y>=t){ printf("%d\n", dis[next->id]); ; } st.erase(next); } } } puts("-1"); ; }