A
求最小的桥
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define inf 1e9+7 #define MAXN 1010 int head[MAXN],cnt,time; int dfn[MAXN],low[MAXN]; struct node { int u,v,w,nex; }edge[MAXN*MAXN]; void add(int u,int v,int w) { edge[cnt].u=u; edge[cnt].v=v; edge[cnt].w=w; edge[cnt].nex=head[u]; head[u]=cnt++; } int mx; void dfs(int u,int fa) { low[u]=dfn[u]=++time; for(int i=head[u];i!=-1;i=edge[i].nex) { int v=edge[i].v; if(i==(fa^1)) continue; if(!dfn[v]){ dfs(v,i); low[u]=min(low[u],low[v]); if(dfn[u]<low[v]){ mx=min(mx,edge[i].w); } } else low[u]=min(low[u],low[v]); } } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { if(n==m&&m==0) break; cnt=0; memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } mx=inf; time=0; memset(dfn,0,sizeof(dfn)); int c1=0; for(int i=1;i<=n;i++) { if(!dfn[i]) { dfs(i,-1); c1++; } } if(c1>1) printf("0 "); else if(mx==inf) printf("-1 "); else { if(mx<=0) mx=1; printf("%d ",mx); } } return 0; }
B
状态压缩DP
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> using namespace std; #define inf 1e9+7 #define MAXN 1010 struct node { int x,y; }z[MAXN]; bool cmp(node a,node b) { if(a.x==b.x) return a.y<b.y; return a.x<b.x; } vector<int>v[25]; bool check(int ind1,int ind2,int ind3,int ind4) { if(z[ind1].x==z[ind2].x&&z[ind1].y==z[ind3].y&&z[ind2].y==z[ind4].y&&z[ind3].x==z[ind4].x&&(abs(z[ind2].y-z[ind1].y)==abs(z[ind3].x-z[ind1].x))) return 1; return 0; } int dp[(1<<20)+10]; int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==-1) break; for(int i=0;i<n;i++) { scanf("%d%d",&z[i].x,&z[i].y); v[i].clear(); } memset(dp,0,sizeof(dp)); sort(z,z+n,cmp); for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { for(int k=j+1;k<n;k++) { for(int l=k+1;l<n;l++) { int s=0; s=s|(1<<i); s=s|(1<<j); s=s|(1<<k); s=s|(1<<l); if(check(i,j,k,l)) v[i].push_back(s); } } } } int en=1<<n; for(int i=0;i<en;i++) { for(int j=0;j<n;j++) { if(i&(1<<j)) { for(int k=0;k<v[j].size();k++) { if((i|v[j][k])==i) { dp[i]=max(dp[i],dp[i^v[j][k]]+4); } } } } } printf("%d ",dp[en-1]); } return 0; }
C
模拟
#include <iostream> #include <algorithm> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <cstdio> #include <queue> #include <cmath> #include <string.h> #include <assert.h> #include <stack> #include <sstream> #include <map> #include <set> #define M 1020 #define LL __int64 using namespace std; bool vis1[M][M]; bool vis2[M][M]; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; int main() { int i,j,x1,y1,z1,x2,y2,z2,xx1,yy1,xx2,yy2,n; bool flag,ok1,ok2; while(scanf("%d",&n),n) { scanf("%d%d%d",&x1,&y1,&z1); scanf("%d%d%d",&x2,&y2,&z2); memset(vis1,false,sizeof(vis1)); memset(vis2,false,sizeof(vis2)); ok1=true; ok2=true; flag=false; while(1) { if(x1==x2&&y1==y2) { flag=true; break; } if(!ok1&&!ok2) break; vis1[x1][y1]=true; vis2[x2][y2]=true; if(ok1) { xx1=x1+dx[z1]; yy1=y1+dy[z1]; if(xx1>=0&&xx1<n&&yy1>=0&&yy1<n&&!vis1[xx1][yy1]) { x1=xx1; y1=yy1; z1=z1; } else { xx1=x1+dx[(z1+1)%4]; yy1=y1+dy[(z1+1)%4]; if(xx1>=0&&xx1<n&&yy1>=0&&yy1<n&&!vis1[xx1][yy1]) { x1=xx1; y1=yy1; z1=(z1+1)%4; } else { x1=x1; y1=y1; z1=z1; ok1=false; } } } if(ok2) { xx2=x2+dx[z2]; yy2=y2+dy[z2]; if(xx2>=0&&xx2<n&&yy2>=0&&yy2<n&&!vis2[xx2][yy2]) { x2=xx2; y2=yy2; z2=z2; } else { xx2=x2+dx[((z2-1)%4+4)%4]; yy2=y2+dy[((z2-1)%4+4)%4]; if(xx2>=0&&xx2<n&&yy2>=0&&yy2<n&&!vis2[xx2][yy2]) { x2=xx2; y2=yy2; z2=((z2-1)%4+4)%4; } else { x2=x2; y2=y2; z2=z2; ok2=false; } } } } if(flag) { printf("%d %d ",x1,y1); } else { printf("-1 "); } } return 0; }
D
给你空间上4个点 组成2条直线 求公垂线 长度 和 公垂线和1 2直线的交点
公垂线方向向量可以叉积得到 那么公垂线方向向量和 一条直线构成一个平面 和另一条直线的交点就是交点了
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #include<math.h> using namespace std; #define inf 1e9+7 #define MAXN 1010 #define exp 1e-8 double dis(double x,double y,double z) { return sqrt(x*x+y*y+z*z); } int main() { int t; scanf("%d",&t); while(t--) { double x1,y1,z1,x2,y2,z2,x3,y3,z3,x4,y4,z4; scanf("%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&z1,&x2,&y2,&z2,&x3,&y3,&z3,&x4,&y4,&z4); long double f1x,f1y,f1z,f2x,f2y,f2z; f1x=x2-x1; f1y=y2-y1; f1z=z2-z1; f2x=x4-x3; f2y=y4-y3; f2z=z4-z3; double fax,fay,faz,fcx,fcy,fcz; fax=f1y*f2z-f1z*f2y; fay=f1z*f2x-f1x*f2z; faz=f1x*f2y-f1y*f2x; double len; fcx=x1-x3; fcy=y1-y3; fcz=z1-z3; len=1.0*(fax*fcx+fay*fcy+faz*fcz)/dis(fax,fay,faz); if(len<0) len*=(-1); printf("%.6lf ",len); double fbbx,fbby,fbbz,faax,faay,faaz; fbbx=fay*f2z-faz*f2y; fbby=faz*f2x-fax*f2z; fbbz=fax*f2y-fay*f2x; faax=fay*f1z-faz*f1y; faay=faz*f1x-fax*f1z; faaz=fax*f1y-fay*f1x; double xx1,yy1,zz1,xx2,yy2,zz2,t; t=(fbbx*(x3-x1)+fbby*(y3-y1)+fbbz*(z3-z1))/(fbbx*f1x+fbby*f1y+f1z*fbbz); xx1=t*f1x+x1; yy1=t*f1y+y1; zz1=t*f1z+z1; t=(faax*(x1-x3)+faay*(y1-y3)+faaz*(z1-z3))/(faax*f2x+faay*f2y+f2z*faaz); xx2=t*f2x+x3; yy2=t*f2y+y3; zz2=t*f2z+z3; printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf ",xx1,yy1,zz1,xx2,yy2,zz2); } return 0; }
H
把区间分成2段回文
区间DP
#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; #define MAXN 1010 int z[MAXN]; int dp[MAXN][MAXN]; int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&z[i]); dp[i][i]=1; } for(int l=1;l<n;l++) { for(int j=1;j+l<=n;j++) { int en=j+l; dp[j][en] = max(dp[j + 1][en],dp[j][en - 1]); if(z[j]==z[en]) dp[j][en]=max(dp[j+1][en-1]+2,dp[j][en]); } } int mx=0; for(int i=1;i<=n;i++) mx=max(dp[1][i]+dp[i+1][n],mx); printf("%d ",mx); } return 0; }