2012-C18-team5
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
E 题数论，不会做，我上机乱搞了一阵是 WA，没有办法只好放弃去搞其他题。后来题目做得没什么可做的时候，学姐写了个对拍程序，很快就就找到 WA 的地方了，不过还是不会做
比赛快结束的时候，再推了一下式子，发现似乎能用 exgcd 来求，结果时间比较紧，抄 exgcd 模板时抄错了...
其他题还好，没有多大的问题
顺便想起前几场比赛时的情况，建议学长学姐们在讨论题目看看数据范围，能先想 DP 时就不要去想贪心，尤其不知道贪心对不对的时候（此时一般想的贪心都是错的，比如天津的 1006 那题）
by 猛犸也钻地
附：I 题代码，处理直线相交时，需注意考虑重合的情况，我在这个地方 WA 了 1 小时才发现
{{{
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#include <cassert>
#include <algorithm>
using namespace std;
using namespace rel_ops;
typedef double NUM;
const NUM EPS = 1e-12, MAGIC = 2.71828e18;
inline NUM sqr(NUM a){return a*a;}
inline NUM cmp(NUM a, NUM b){
return fabs(a-b)>=EPS+fabs(a)*EPS?a-b:0;
}
struct VEC{NUM x,y;} NOVEC = {MAGIC,MAGIC};
struct RAY{VEC u,v;} NORAY = {NOVEC,NOVEC};
inline NUM sqr(const VEC& a){return sqr(a.x)+sqr(a.y);}
inline double abs(const VEC& a){return sqrt(sqr(a));}
inline NUM cmp(const VEC& a, const VEC& b){
NUM at=cmp(a.x,b.x);
return !at?cmp(a.y,b.y):at;
}
inline VEC operator +(const VEC& a, const VEC& b)
{return (VEC){a.x+b.x,a.y+b.y};}
inline VEC operator -(const VEC& a, const VEC& b)
{return (VEC){a.x-b.x,a.y-b.y};}
inline NUM operator *(const VEC& a, const VEC& b)
{return a.x*b.y-a.y*b.x;}
inline NUM operator %(const VEC& a, const VEC& b)
{return a.x*b.x+a.y*b.y;}
inline VEC operator -(const VEC& a){return (VEC){-a.x,-a.y};}
inline VEC operator ~(const VEC& a){return (VEC){-a.y,+a.x};}
inline VEC operator *(NUM u, const VEC& a){return (VEC){u*a.x,u*a.y};}
inline VEC operator *(const VEC& a, NUM u){return (VEC){a.x*u,a.y*u};}
inline VEC operator /(const VEC& a, NUM u){return (VEC){a.x/u,a.y/u};}
inline VEC operator /(const VEC& a, const VEC& b){return a%b/sqr(b)*b;}
inline bool operator ==(const VEC& a, const VEC& b){return !cmp(a,b);}
inline bool operator <(const VEC& a, const VEC& b){return cmp(a,b)<0;}
NUM cmp_side(const VEC& a, const VEC& b){return cmp(a.x*b.y,+a.y*b.x);}
NUM cmp_axis(const VEC& a, const VEC& b){return cmp(a.x*b.x,-a.y*b.y);}
VEC cross(const RAY& a, const RAY& b){
VEC s=a.u-a.v,t=b.u-b.v;
NUM at=cmp_side(s,t);
if(!at) return NOVEC;
return a.u+(b.u-a.u)*t/at*s;
}
bool seg_range(const VEC& p, const RAY& l){
return cmp_axis(p-l.u,p-l.v)<=0;
}
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
typedef vector<PII> VP;
int x[100005],y[100005];
vector<VEC> dot[100005],all;
vector<PDI> e[2100005];
double l[2100005];
double dijkstra(int s, int t){
priority_queue<PDI> q;
q.push(PDI(l[s]=0,s));
while(q.size()){
int x=q.top().second;
double now=-q.top().first;
q.pop();
if(cmp(l[x],now)) continue;
if(x==t) break;
for(size_t i=0;i<e[x].size();i++){
int y=e[x][i].second;
double w=e[x][i].first;
if(cmp(w+l[x],l[y])<0){
l[y]=l[x]+w;
q.push(PDI(-l[y],y));
}
}
}
return l[t];
}
int main(){
int cs,n;
scanf("%d",&cs);
while(cs--){
scanf("%d",&n);
map<int,VP> u;
for(int i=0;i<n;i++){
scanf("%d%d",x+i,y+i);
u[x[i]].push_back(PII(y[i],i));
}
all.push_back((VEC){x[0],y[0]});
u[-10000100];
u[+10000100];
for(map<int,VP>::iterator t=u.begin();t!=u.end();++t)
sort(t->second.begin(),t->second.end());
for(int i=0;i+1<n;i++){
vector<int> c;
for(map<int,VP>::iterator t=u.lower_bound(x[i]-43);t->first<=x[i]+43;++t){
vector<PII>& r=t->second;
vector<PII>::iterator o=lower_bound(r.begin(),r.end(),PII(y[i]-43,0));
while(o!=r.end() && o->first<=y[i]+43){
if(o->second<i){
c.push_back(o->second);
c.push_back(o->second-1);
}else if(o->second==i){
c.push_back(o->second-1);
}
o++;
}
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
RAY l={{x[i],y[i]},{x[i+1],y[i+1]}};
dot[i].push_back(l.u);
dot[i].push_back(l.v);
all.push_back(l.v);
for(size_t o=0;o<c.size();o++){
int j=c[o];
if(j<0) continue;
RAY g={{x[j],y[j]},{x[j+1],y[j+1]}};
VEC r=cross(g,l);
if(r==NOVEC){
if(cmp_side(g.u-l.u,l.v-l.u)
|| cmp_side(l.u-g.u,g.v-g.u)) continue;
if(seg_range(g.u,l)) dot[i].push_back(g.u);
if(seg_range(g.v,l)) dot[i].push_back(g.v);
if(seg_range(l.u,g)) dot[j].push_back(l.u);
if(seg_range(l.v,g)) dot[j].push_back(l.v);
}else if(seg_range(r,g) && seg_range(r,l)){
dot[i].push_back(r);
dot[j].push_back(r);
all.push_back(r);
}
}
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i=0;i+1<n;i++){
sort(dot[i].begin(),dot[i].end());
dot[i].erase(unique(dot[i].begin(),dot[i].end()),dot[i].end());
int x=lower_bound(all.begin(),all.end(),dot[i][0])-all.begin(),y;
for(size_t j=1;j<dot[i].size();j++,x=y){
y=lower_bound(all.begin(),all.end(),dot[i][j])-all.begin();
double l=abs(dot[i][j]-dot[i][j-1]);
e[x].push_back(PDI(l,y));
e[y].push_back(PDI(l,x));
}
dot[i].clear();
}
int s=lower_bound(all.begin(),all.end(),(VEC){x[0],y[0]})-all.begin();
int t=lower_bound(all.begin(),all.end(),(VEC){x[n-1],y[n-1]})-all.begin();
for(size_t i=0;i<all.size();i++) l[i]=1e20;
double ans=dijkstra(s,t);
printf("%.0f\n",fabs(ans));
for(size_t i=0;i<all.size();i++) e[i].clear();
all.clear();
}
}
}}}E 题数论，不会做，我上机乱搞了一阵是 WA，没有办法只好放弃去搞其他题。后来题目做得没什么可做的时候，学姐写了个对拍程序，很快就就找到 WA 的地方了，不过还是不会做
比赛快结束的时候，再推了一下式子，发现似乎能用 exgcd 来求，结果时间比较紧，抄 exgcd 模板时抄错了...
其他题还好，没有多大的问题
顺便想起前几场比赛时的情况，建议学长学姐们在讨论题目看看数据范围，能先想 DP 时就不要去想贪心，尤其不知道贪心对不对的时候（此时一般想的贪心都是错的，比如天津的 1006 那题）
by 猛犸也钻地
附：I 题代码，处理直线相交时，需注意考虑重合的情况，我在这个地方 WA 了 1 小时才发现
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <utility>
#include <cassert>
#include <algorithm>
using namespace std;
using namespace rel_ops;
typedef double NUM;
const NUM EPS = 1e-12, MAGIC = 2.71828e18;
inline NUM sqr(NUM a){return a*a;}
inline NUM cmp(NUM a, NUM b){
return fabs(a-b)>=EPS+fabs(a)*EPS?a-b:0;
}
struct VEC{NUM x,y;} NOVEC = {MAGIC,MAGIC};
struct RAY{VEC u,v;} NORAY = {NOVEC,NOVEC};
inline NUM sqr(const VEC& a){return sqr(a.x)+sqr(a.y);}
inline double abs(const VEC& a){return sqrt(sqr(a));}
inline NUM cmp(const VEC& a, const VEC& b){
NUM at=cmp(a.x,b.x);
return !at?cmp(a.y,b.y):at;
}
inline VEC operator +(const VEC& a, const VEC& b)
{return (VEC){a.x+b.x,a.y+b.y};}
inline VEC operator -(const VEC& a, const VEC& b)
{return (VEC){a.x-b.x,a.y-b.y};}
inline NUM operator *(const VEC& a, const VEC& b)
{return a.x*b.y-a.y*b.x;}
inline NUM operator %(const VEC& a, const VEC& b)
{return a.x*b.x+a.y*b.y;}
inline VEC operator -(const VEC& a){return (VEC){-a.x,-a.y};}
inline VEC operator ~(const VEC& a){return (VEC){-a.y,+a.x};}
inline VEC operator *(NUM u, const VEC& a){return (VEC){u*a.x,u*a.y};}
inline VEC operator *(const VEC& a, NUM u){return (VEC){a.x*u,a.y*u};}
inline VEC operator /(const VEC& a, NUM u){return (VEC){a.x/u,a.y/u};}
inline VEC operator /(const VEC& a, const VEC& b){return a%b/sqr(b)*b;}
inline bool operator ==(const VEC& a, const VEC& b){return !cmp(a,b);}
inline bool operator <(const VEC& a, const VEC& b){return cmp(a,b)<0;}
NUM cmp_side(const VEC& a, const VEC& b){return cmp(a.x*b.y,+a.y*b.x);}
NUM cmp_axis(const VEC& a, const VEC& b){return cmp(a.x*b.x,-a.y*b.y);}
VEC cross(const RAY& a, const RAY& b){
VEC s=a.u-a.v,t=b.u-b.v;
NUM at=cmp_side(s,t);
if(!at) return NOVEC;
return a.u+(b.u-a.u)*t/at*s;
}
bool seg_range(const VEC& p, const RAY& l){
return cmp_axis(p-l.u,p-l.v)<=0;
}
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
typedef vector<PII> VP;
int x[100005],y[100005];
vector<VEC> dot[100005],all;
vector<PDI> e[2100005];
double l[2100005];
double dijkstra(int s, int t){
priority_queue<PDI> q;
q.push(PDI(l[s]=0,s));
while(q.size()){
int x=q.top().second;
double now=-q.top().first;
q.pop();
if(cmp(l[x],now)) continue;
if(x==t) break;
for(size_t i=0;i<e[x].size();i++){
int y=e[x][i].second;
double w=e[x][i].first;
if(cmp(w+l[x],l[y])<0){
l[y]=l[x]+w;
q.push(PDI(-l[y],y));
}
}
}
return l[t];
}
int main(){
int cs,n;
scanf("%d",&cs);
while(cs--){
scanf("%d",&n);
map<int,VP> u;
for(int i=0;i<n;i++){
scanf("%d%d",x+i,y+i);
u[x[i]].push_back(PII(y[i],i));
}
all.push_back((VEC){x[0],y[0]});
u[-10000100];
u[+10000100];
for(map<int,VP>::iterator t=u.begin();t!=u.end();++t)
sort(t->second.begin(),t->second.end());
for(int i=0;i+1<n;i++){
vector<int> c;
for(map<int,VP>::iterator t=u.lower_bound(x[i]-43);t->first<=x[i]+43;++t){
vector<PII>& r=t->second;
vector<PII>::iterator o=lower_bound(r.begin(),r.end(),PII(y[i]-43,0));
while(o!=r.end() && o->first<=y[i]+43){
if(o->second<i){
c.push_back(o->second);
c.push_back(o->second-1);
}else if(o->second==i){
c.push_back(o->second-1);
}
o++;
}
}
sort(c.begin(),c.end());
c.erase(unique(c.begin(),c.end()),c.end());
RAY l={{x[i],y[i]},{x[i+1],y[i+1]}};
dot[i].push_back(l.u);
dot[i].push_back(l.v);
all.push_back(l.v);
for(size_t o=0;o<c.size();o++){
int j=c[o];
if(j<0) continue;
RAY g={{x[j],y[j]},{x[j+1],y[j+1]}};
VEC r=cross(g,l);
if(r==NOVEC){
if(cmp_side(g.u-l.u,l.v-l.u)
|| cmp_side(l.u-g.u,g.v-g.u)) continue;
if(seg_range(g.u,l)) dot[i].push_back(g.u);
if(seg_range(g.v,l)) dot[i].push_back(g.v);
if(seg_range(l.u,g)) dot[j].push_back(l.u);
if(seg_range(l.v,g)) dot[j].push_back(l.v);
}else if(seg_range(r,g) && seg_range(r,l)){
dot[i].push_back(r);
dot[j].push_back(r);
all.push_back(r);
}
}
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(int i=0;i+1<n;i++){
sort(dot[i].begin(),dot[i].end());
dot[i].erase(unique(dot[i].begin(),dot[i].end()),dot[i].end());
int x=lower_bound(all.begin(),all.end(),dot[i][0])-all.begin(),y;
for(size_t j=1;j<dot[i].size();j++,x=y){
y=lower_bound(all.begin(),all.end(),dot[i][j])-all.begin();
double l=abs(dot[i][j]-dot[i][j-1]);
e[x].push_back(PDI(l,y));
e[y].push_back(PDI(l,x));
}
dot[i].clear();
}
int s=lower_bound(all.begin(),all.end(),(VEC){x[0],y[0]})-all.begin();
int t=lower_bound(all.begin(),all.end(),(VEC){x[n-1],y[n-1]})-all.begin();
for(size_t i=0;i<all.size();i++) l[i]=1e20;
double ans=dijkstra(s,t);
printf("%.0f\n",fabs(ans));
for(size_t i=0;i<all.size();i++) e[i].clear();
all.clear();
}
}
附加文件
- Contest 18 by way to answer.zip by oldjunyi