T1
以为计算几何不会，
据说正解做法很玄学每条线段拆成若干点跑SPFA，取两个最小距离的点构成的线段继续做.
爆0
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define rep(i,s,t) for(register int i=s;i<t;++i)
#define Rep(i,s,t) for(register int i=s;i<=t;++i)
#define copy(x,y) memcpy(x,y,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> pa;
typedef double db;
typedef long double ld;
const int maxn=205;
const ld eps=1e-9;
inline ld sqr(ld x){return x*x;}
inline int sgn(ld x){return fabs(x)<eps?0:((x>0)?1:-1);}
struct point{
ld x, y;
point(ld _x = 0, ld _y = 0) { x = _x; y = _y; }
inline point operator+(const point &b)const{return point(x+b.x,y+b.y);}
inline point operator-(const point &b)const{return point(x-b.x,y-b.y);}
inline point operator*(const ld &b)const{return point(x*b,y*b);}
inline bool operator==(const point &b)const{return !sgn(x-b.x)&&!sgn(y-b.y);}
}t[maxn],S,T,t2[maxn];
inline ld dot(point a,point b){return a.x*b.x+a.y*b.y;}
inline ld len(point a){return sqrt(dot(a,a));}
int n, v_p, v_r, tn;
ld ans;
inline point get(point A,point B,point P){ld tmp=dot(B-A,P-A)/dot(B-A,B-A);return A+(B-A)*tmp;}
inline ld getp(ld w,ld h){
ld tmp=(sqr(h)*sqr(v_r))/(sqr(v_p)-sqr(v_r));tmp=sqrt(tmp);ld ret=tmp+w;
if(sgn(ret-w)>0){ret=w-tmp;if(sgn(ret)<0) return 0;}
return ret;
}
inline ld getp(point A,point B,point P){point G=get(A,B,P);return getp(len(A-G),len(P-G));}
inline ld getf(ld w,ld h){ld tmp=getp(w,h);return tmp*v_r+v_p*sqrt(sqr(w-tmp)+sqr(h));}
inline ld getf(point A, point B, point P){point G=get(A,B,P);return getf(len(A-G),len(P-G));}
inline void solve(){
tn=0;
rep(i,0,n){
t2[tn++]=t[i];
if(i^(n-1)){
ld v=getp(t[i],t[i+1],T);
point tmp=t[i+1]-t[i],nxtpos=t[i]+tmp*(v/len(tmp));
if(!(t[i]==nxtpos)&&!(t[i+1]==nxtpos)&&!sgn(len(nxtpos-t[i])+len(nxtpos-t[i+1])-len(t[i+1]-t[i])))t2[tn++]=nxtpos;
}
}
n=tn;copy(t,t2);ld dis[maxn];dis[0]=0;
rep(i,1,n){
dis[i]=dis[i-1]+v_r*len(t[i]-t[i-1]);
rep(j,1,i)
dis[i]=min(dis[i],dis[j-1]+getf(t[j-1],t[j],t[i])),
dis[i]=min(dis[i],dis[j-1]+getf(t[i],t[i-1],t[j-1]));
ans=min(ans,dis[i-1]+getf(t[i-1],t[i],T));
}
}
int main(){
int tt;cin>>tt;
while(tt--){
scanf("%d",&n);
rep(i,0,n)cin>>t[i].x>>t[i].y;t[n]=t[0];
cin>>v_r>>v_p>>S.x>>S.y>>T.x>>T.y;
rep(i,0,n){
if(t[i]==S){
t2[tn++]=t[i];
for(register int j=i+1;j^i;(++j)%=n)t2[tn++]=t[j];break;
}
if(!sgn(len(t[i]-S)+len(t[i+1]-S)-len(t[i+1]-t[i]))){
t2[tn++]=S;t2[tn++]=t[i+1];
for(register int j=(i+2)%n;j^((i+1)%n);(++j)%=n)t2[tn++]=t[j];break;
}
}
copy(t,t2);
n=tn;ans=len(S-T)*v_p;
solve();
reverse(t+1,t+n);
solve();
printf("%.6f
",db(ans));
tn=0;
}
return 0;
}
T2
据说是去年二试加强版
我写了dfs
最后10分
T3
先吐槽一下附中的老爷机，写了40的矩乘被卡成10分，搞得和暴力分一样
其次T3居然是BZOJ原题
最后10分
BZOJ3583
http://www.lydsy.com/JudgeOnline/problem.php?id=3583
#include<cstdio>
#include<cstdlib>
using namespace std;
const int mod=1e9+7;
int O[1001][21],I[1001][21];
int n,m,q,x,y,z,ans;
int f[1001];
struct matrix{
int a[21][21];
matrix(){
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j)
a[i][j]=0;
}
inline matrix operator*(matrix A)const{
matrix ret;
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j)
for(register int k=0;k<m;++k)
ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*A.a[k][j]%mod)%mod;
return ret;
}
inline matrix operator+(matrix A)const{
matrix ret;
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j){
ret.a[i][j]=a[i][j]+A.a[i][j];
if(ret.a[i][j]>=mod)
ret.a[i][j]-=mod;
}
return ret;
}
}A[51],B[51],G,S;
inline void calc(int n){
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j)
G.a[i][j]=S.a[i][j]=0;
for(register int i=0;i<m;++i)
G.a[i][i]=S.a[i][i]=1;
for(register int i=0;i<=31;++i)
if((n>>i)&1){
S=S+(B[i]*G);
G=G*A[i];
}
}
int main(){
scanf("%d%d",&n,&m);
for(register int i=0;i<n;++i){
for(register int j=0;j<m;++j)scanf("%d",O[i]+j),O[i][j]%=mod;
for(register int j=0;j<m;++j)scanf("%d",I[i]+j),I[i][j]%=mod;
}
for(register int k=0;k<n;++k)
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j)
A[0].a[i][j]=(A[0].a[i][j]+1ll*I[k][i]*O[k][j]%mod)%mod;
B[0]=A[0];
for(register int i=0;i<=31;++i){
A[i+1]=A[i]*A[i];
for(register int j=0;j<m;++j)
++A[i].a[j][j];
B[i+1]=B[i]*A[i];
for(register int j=0;j<m;++j)
--A[i].a[j][j];
}
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&x,&y,&z);--x;--y;
if(!z){
printf("%d
",(x==y));
continue;
}
calc(z-1);
for(register int i=0;i<m;++i)f[i]=0;
ans=0;
for(register int i=0;i<m;++i)
for(register int j=0;j<m;++j)
f[i]=(f[i]+1ll*O[x][j]*S.a[j][i]%mod)%mod;
for(register int i=0;i<m;++i)
ans=(ans+1ll*I[y][i]*f[i]%mod)%mod;
printf("%d
",(ans+(x==y))%mod);
}
return 0;
}