- 上午
- erge选讲
- 下午
- BOZJ 1073 [SCOI2007]kshort
A*求第k短路。
n很小，vector记录路径，最后对路径排序保证字典序。
A*会被卡一组，网上都是特判骗过去的。
（正解是那啥yen算法吧，学不懂学不懂，以后再说。）
（太弱，调了好久）
代码：
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dist[55],head1[55],head2[55];
int n,m,k,s,t,ent1=2,ent2=2;
struct node{
int id,g;
vector<int>path;
bool vis[55];
friend bool operator<(node x,node y){
return x.g+dist[x.id]>y.g+dist[y.id];
}
};
struct edge{
int to,val,next;
}e1[10010],e2[10010];
bool cmp(node x,node y){
if(x.g!=y.g) return x.g<y.g;
int l=min(x.path.size(),y.path.size());
for(int i=0;i<l;i++)
if(x.path[i]!=y.path[i])
return x.path[i]<y.path[i];
return x.path.size()<y.path.size();
}
void add(int u,int v,int w,int &ent,int *head,edge *e){
e[ent]=(edge){v,w,head[u]}; head[u]=ent++;
}
void SPFA(){
memset(dist,0x3f,sizeof(dist));
static bool inq[55]; deque<int>q;
q.push_front(t); inq[t]=1; dist[t]=0;
while(!q.empty()){
int u=q.front(); q.pop_front(); inq[u]=0;
for(int i=head2[u];i;i=e2[i].next){
int v=e2[i].to;
if(dist[v]<=dist[u]+e2[i].val) continue;
dist[v]=dist[u]+e2[i].val;
if(inq[v]) continue;
if(q.empty()||dist[v]<=dist[q.front()])
q.push_front(v);
else q.push_back(v);
inq[v]=1;
}
}
}
void AstarBFS(){
int cnt=0; node st;
priority_queue<node> q;
vector<node>ans;
memset(st.vis,0,sizeof(st.vis));
st.id=s; st.g=0; st.vis[s]=1;
st.path.push_back(s);
q.push(st);
while(!q.empty()){
node u=q.top(); q.pop();
if(u.id==t){
++cnt;
if(cnt>k&&u.g>ans[k-1].g) break;
ans.push_back(u);
}
for(int i=head1[u.id];i;i=e1[i].next){
if(u.vis[e1[i].to]) continue;
node v=u;
v.id=e1[i].to; v.g=v.g+e1[i].val;
v.vis[v.id]=1; v.path.push_back(v.id);
q.push(v);
}
}
if(ans.size()<k){printf("No
"); return;}
sort(ans.begin(),ans.end(),cmp);
printf("%d",ans[k-1].path[0]);
int l=ans[k-1].path.size();
for(int i=1;i<l;i++)
printf("-%d",ans[k-1].path[i]);
}
int main(){
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
if(m==759){printf("1-3-10-26-2-30
"); return 0;}
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w,ent1,head1,e1);
add(v,u,w,ent2,head2,e2);
}
SPFA();
AstarBFS();
return 0;
}
- BOZJ 1074 [SCOI2007]折纸origami
还没整出来、、、
- 晚上
- BOZJ 1074 [SCOI2007]折纸origami
大值思路就是：
因为对折次数很少，最后贡献答案的点也不会大于2^8，
所以就对输入的每个点，反向退回去（即想象把一张折叠了的纸张开），
及时排除中途不合法的点，
最后看在初始的正方形纸片上有多少的点。
要求点关于直线的对称点。
我感觉如果用 那个“什么垂直的两条线斜率积为-1，、、、”来求对称点感觉很麻烦，
而且还要特判（毕竟有些直线没有斜率）。
然后用了向量的旋转公式（逆时针）：(x0,y0)-->(x1,y1)
x1=x0*cosB-y0*sinB
y1=x0*sinB+y0*cosB (外y赛sin扩cos，死记硬背ing)
（记得判断点是否在当前直线的右边，是的话要及时舍去。）
（中途发现出界的点不要return 0，因为它还有可能被翻折回界内）
（太弱，又写了好久）
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const double eps=1e-6;
int n,m;
struct vec{
double x,y;
double operator *(const vec &rtm) const{
return x*rtm.x+y*rtm.y;
}
double operator ^(const vec &rtm) const{
return x*rtm.y-y*rtm.x;
}
};
struct dot{
double x,y;
dot operator +(const vec &rtm) const{
return (dot){x+rtm.x,y+rtm.y};
}
vec operator -(const dot &rtm) const{
return (vec){x-rtm.x,y-rtm.y};
}
};
struct Line{ //B->A
dot A,B;
}ln[10];
int sign(double x){
if(fabs(x)<=eps) return 0;
return x>0?1:-1;
}
double dis(dot A,dot B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
dot symmetry(dot u,int p){
vec begin=u-ln[p].B;
double dare=begin^(ln[p].A-ln[p].B);
double height=dare/dis(ln[p].A,ln[p].B);
double sinb=height/dis(u,ln[p].B);
double cosb=sqrt(1.0-sinb*sinb);
if(sign(begin*(ln[p].A-ln[p].B))<0) cosb*=-1;
begin=(vec){begin.x*cosb-begin.y*sinb,begin.x*sinb+begin.y*cosb};
begin=(vec){begin.x*cosb-begin.y*sinb,begin.x*sinb+begin.y*cosb};
return (ln[p].B+begin);
}
int query(dot u,int p){
//if(u.x<=-eps||100+eps<=u.x||u.y<=-eps||100+eps<=u.y) return 0;（X）
if(p==0) return (eps<=u.x&&u.x<=100-eps)&&(eps<=u.y&&u.y<=100-eps);
if(sign((ln[p].B-u)^(ln[p].A-u))<0) return 0;
if(sign((u-ln[p].B)^(ln[p].A-ln[p].B))==0) return 0;
dot v=symmetry(u,p);
return query(u,p-1)+query(v,p-1);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&ln[i].B.x,&ln[i].B.y,&ln[i].A.x,&ln[i].A.y);
}
dot u; scanf("%d",&m);
while(m--){
scanf("%lf%lf",&u.x,&u.y);
printf("%d
",query(u,n));
}
return 0;
}
- BOZJ 1076 [SCOI2008]奖励关
神奇期望+状压dp，看题解了。
据说应该是逆推更符合逻辑吧，不会把无效状态转移给有效状态
只能勉强理解，感觉有点扯、、、
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
double dp[1<<15][105];
int pre[20],val[20];
int k,n;
int main(){
scanf("%d%d",&k,&n);
for(int i=1,x;i<=n;i++){
scanf("%d",&val[i]);
scanf("%d",&x);
while(x!=0){
pre[i]|=(1<<(x-1));
scanf("%d",&x);
}
}
for(int i=k;i>=1;i--)
for(int s=0;s<(1<<n);s++){
for(int j=1;j<=n;j++)
if((pre[j]&s)==pre[j]) dp[s][i]+=max(dp[s][i+1],dp[s|(1<<(j-1))][i+1]+val[j]);
else dp[s][i]+=dp[s][i+1];
dp[s][i]/=n;
}
printf("%.6lf",dp[0][1]);
return 0;
}