t1 jzoj3762 过河
路径分段，计算出向上移对答案贡献最大的一段路，再使用堆来维护即可
代码：
#include<bits/stdc++.h>
using namespace std;
double dis(double x,double y){
return sqrt(x*x+y*y);
}
struct no{
int x,y,v;
double w;
bool operator <(const no &rhs)const{
return w>rhs.w;
}
};
int v[100010],w[100010];
double ans;
int n,y,u;
priority_queue<no>q;
int main(){
scanf("%d%d%d",&n,&y,&u);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
no p;
for(int i=1;i<=n;i++){
ans+=w[i]/(double)v[i];
p.w=(dis(w[i],1)-w[i])/(double)v[i];
p.x=w[i];p.y=0;p.v=v[i];
q.push(p);
}
p.w=1/(double)u;
p.x=p.y=0;p.v=u;
q.push(p);
for(int i=1;i<=y;i++){
no x=q.top();q.pop();
ans+=x.w;
x.y++;
x.w=(dis(x.x,x.y+1)-dis(x.x,x.y))/(double)x.v;
q.push(x);
}
printf("%.4f",ans);
}t2:jzoj3763 逃离迷宫
题解：状压dp+搜索，首先求出每一个结点到其他结点的距离，然后状压dp,f[i][j]表示上一次取的药水编号为i，选过的药水集合为j所能耗费体力的最小值，上一次选的药水和这次选的药水都要枚举
代码：
#include<bits/stdc++.h>
using namespace std;
int o[4]={0,1,0,-1},p[4]={1,0,-1,0};
long long n,m,k,sx,sy,tx,ty,h[101][101],g[17][101][101],f[17][(1<<17)+2],d[17][17],a[17],b[17],c[17],ans;
struct node{int x,y;};
void bfs(){
memset(g,127,sizeof(g));
for(int i=0;i<=k;i++){
queue<node>q;q.push((node){a[i],b[i]});
g[i][a[i]][b[i]]=0;
while(!q.empty()){
node x=q.front();q.pop();
for(int j=0;j<4;j++){
int nx=o[j]+x.x,ny=p[j]+x.y;
if(nx>0&&nx<=n&&ny>0&&ny<=m)
if(g[i][nx][ny]>g[i][x.x][x.y]+(h[x.x][x.y]-h[nx][ny])*(h[x.x][x.y]-h[nx][ny])){
g[i][nx][ny]=g[i][x.x][x.y]+(h[x.x][x.y]-h[nx][ny])*(h[x.x][x.y]-h[nx][ny]);
q.push((node){nx,ny});
}
}
}for(int j=0;j<=k+1;j++)if(i!=j)d[i][j]=g[i][a[j]][b[j]];
}
}void dp(){
memset(f,127,sizeof(f));
f[0][1]=0;ans=2139062143;
for(int s=1;s<=(1<<(k+1))-1;s++)
for(int i=0;i<=k;i++)
if((1<<i)&s){
for(int j=0;j<=k;j++)
if(!(s&(1<<j)))f[j][s|(1<<j)]=min(f[j][s|(1<<j)],f[i][s]+d[i][j]-c[j]);
ans=min(ans,f[i][s]+d[i][k+1]);
}
}
int main(){
scanf("%d%d%d%d%d%d%d",&n,&m,&k,&sx,&sy,&tx,&ty);a[0]=sx;b[0]=sy;a[k+1]=tx;b[k+1]=ty;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%lld",&h[i][j]);
for(int i=1;i<=k;i++)scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
bfs();dp();printf("%lld",ans);return 0;
}t3:jzoj3764 幸运数
奇怪的枚举，使用深搜枚举，当sum(当前选的数的乘积)乘p乘p（即现在选的数）（乘两次）大于n的时候应该二分范围，这是唯一能过的终极剪枝
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[1000005],p[1000005],ct,cc;
void shai(){
for(int i=2;i<=m;i++){
if(!vis[i])p[++ct]=i;
for(int j=1;j<=ct&&(long long)i*p[j]<=m;j++){
vis[i*p[j]]=1;
if(i%p[j]==0)break;
}
}
}
void ef(int k,int s){
int l=k,r=ct,ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(s*(long long)p[mid]<=n)
l=mid+1,ans=mid;
else r=mid-1;
}
if(~ans)cc+=ans-k+1;
cc++;
}
void dfs(int x,int s){
if(x>ct){
cc++;
return;
}
if(s*(long long)p[x]*p[x]>n){
ef(x,s);
return;
}
dfs(x+1,s);
long long tp=p[x];
for(int i=1;i<=50;i++){
if(s*tp>n)break;
dfs(x+1,s*tp);
tp=tp*p[x]*p[x];
}
}
int main(){
scanf("%d%d",&n,&m);
m=min(n,m);
shai();
dfs(1,1);
printf("%d",cc);
}