DP+卡常数+高精度/ 计算几何+二分+判区间交/ 凸包

　　首先感谢徐老师的慷慨，让蒟蒻有幸膜拜了学军的神题。祝NOI2015圆满成功

　　同时膜拜碾压了蒟蒻的众神QAQ

填填填

　　我的DP比较逗比……（当时看到其他大神有更加优秀的做法）

　　f[i][j]表示前 i 个数，第一行填了 j 个的方案数，那么如果 i 并没有固定位置，f[i][j]=f[i-1][j]+f[i-1][j-1];即 i 这个数放在第一行或是第二行。。。（废话）

　　如果 i 固定的位置是第一行（1，y），那么f[i]中只有f[i][y]=f[i-1][y-1];（这个数一定放在第一行）

　　如果 i 固定的位置是第二行（2，y），那么f[i]中只有f[i][i-y]=f[i-1][i-y];（一定放在第二行）

　　这个DP是会爆空间的，但是我们发现f[i]只跟f[i-1]有关，所以滚动数组优化一下就好了……（我一开始还在蛋疼高精度的数组开不下）

　　我比较傻逼，不知道XJOI是不能用#ifndef ONLINE_JUDGE的，所以第一题没删文件操作……爆零滚粗了，删掉后是70分，两RE四TLE。

　　然后开始了漫漫卡常之路……比如高精从int压9位改成long long压17位，高精加的过程用指针实现（Orz Davidlee1999）

　　RE的那两个点是怎么回事呢？因为如果 i 固定的位置是第二行的时候，i-y可能会越界！（也就是无法得到一组合法解）那么这个时候我需要特判一下……

 //XJOI test7 A

 #include<ctime>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 struct bint{

     LL a[],l;

     bint(){l=;memset(a,,sizeof a);}

     LL& operator [] (int x){return a[x];}

 }f[][N];

 const LL Limit=100000000000000000LL;

 void print(bint a){

     printf("%lld",a[a.l]);

     D(i,a.l-,) printf("%017lld",a[i]);

     puts("");

 }

 bint operator + (bint a,bint &b){

     LL *it1=a.a+,*it2=b.a+;

     int l=max(a.l,b.l);

     F(i,,l){

         *it1+=*it2;

         it1++; it2++;

     }

     it1=a.a+,it2=a.a+;

     F(i,,l){

         if (*it1>=Limit) *it1-=Limit,(*it2)++;

         it1++; it2++;

     }

     if (a[l+]>) a.l=l+; else a.l=l;

     return a;

 }

 int n,v[][N];

 typedef pair<int,int> pii;

 #define mp make_pair

 #define fi first

 #define se second

 pii pos[N];

 int main(){

 //  time_t start,end; start=clock();

     n=getint();

     F(i,,) F(j,,n){

         v[i][j]=getint();

         if (v[i][j]) pos[v[i][j]]=mp(i,j);

     }

     f[][].l=f[][][]=;

     F(i,,*n){

         int now=i&;

         if (pos[i].fi==){

             int j=pos[i].se;

             f[now][j]=f[now^][j-];

         }else if (pos[i].fi==){

             int j=i-pos[i].se;

             if (j<=){printf("0\n"); return ;}

             f[now][j]=f[now^][j];

         }else{

             F(j,(i+)/,min(i,n)){

                  f[now][j]=f[now^][j-]+f[now^][j];

 //                 f[now][j]=f[now][j]+f[now^1][j];

             }

         }

         F(j,i/,min(i-,n)) f[now^][j]=bint();

     }

     print(f[][n]);

 /*  end=clock();

     cout <<"start : "<<start<<endl;

     cout <<"end : "<<end<<endl;

     cout <<"time : "<<double(end-start)/CLOCKS_PER_SEC<<endl;

 */  return ;

 }

线线线

　　计算几何QAQ

　　这题……倒是很容易想到可以二分这个dist，那么对于$S$中的每一个点，以它为圆心，dist为半径画一个圆，只要直线与这个圆的交集不为空那么这个圆就可以满足了……那么满足条件的直线所组成的明显是个扇形（只看一侧的话，因为是直线，两边加起来是对称的两个扇形）。

　　然而我并不会算扇形的交……（由此可见多么傻逼）

　　想到这里我就弃疗了……没有写……连暴力都不会……

　　然而其实并不用算扇形交= =因为这个直线不是过定点嘛，那么所谓扇形……其实就是极角对应的区间罢了！所以其实就是求区间交！找是否有一段被n个区间覆盖即可……注意由于是直线，所以反向的那一边穿过去也可以……所以一个$S$中的点应该是对应两个区间！（Orz zld神犇）

　　进入区间+1，离开区间-1，每个区间的左右端点都视为一个事件，排序一下，看是否某一时刻前缀和为n即可。

 //XJOI test7 B

 //Orz zld大爷

 #include<vector>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,INF=~0u>>;

 typedef long long LL;

 const double eps=1e-,pi=acos(-);

 #define sqr(x) ((x)*(x))

 /******************tamplate*********************/

 int n;

 double tx,ty;

 double a[N],dis[N];

 typedef pair<double,int> pii;

 #define mp make_pair

 pii c[N*];

 bool check(double d){

     int s=,tot=;

     F(i,,n)

         if (dis[i]<=d) s++;

         else{

             double l=asin(d/dis[i]);

             c[++tot]=mp(a[i]-l,);

             c[++tot]=mp(a[i]+l,-);

             if (a[i]>){

                 c[++tot]=mp(a[i]-pi-l,);

                 c[++tot]=mp(a[i]-pi+l,-);

             }else{

                 c[++tot]=mp(a[i]+pi-l,);

                 c[++tot]=mp(a[i]+pi+l,-);

             }

         }

     sort(c+,c+tot+);

     F(i,,tot){

         s+=c[i].second;

         if (s==n) return ;

     }

     return ;

 }

 int main(){

 //  freopen("B.in","r",stdin);

     n=getint(); tx=getint(); ty=getint();

     double l=,r=;

     F(i,,n){

         double x=getint(),y=getint();

         a[i]=atan2(x-tx,y-ty);

         dis[i]=sqrt(sqr(x-tx)+sqr(y-ty));

         r=max(dis[i],r);

     }

     while(r-l>eps){

         double mid=(l+r)/;

         if (check(mid)) r=mid;

         else l=mid;

     }

     int ans=floor(l*);

     printf("%d.%03d\n",ans/,ans%);

 //  printf("%.3f\n",l-0.0005);

     return ;

 }

凸凸凸

　　蒟蒻并不会啊……码了个暴力凸包，40分

　　正解好像是这样的……

　　矩形框内离上边界最近的点Up，下边界最近的点Down，左Left，右Right，这四个点一定在最终的凸包上……

　　所以只要预处理出来这四个点之间的凸壳，就可以快速回答询问了QAQ

　　这个好像是满足一个树形的结构？然而蒟蒻并不会写……sad

 //XJOI test7 C

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 using namespace std;

 inline int getint(){

     int v=,sign=; char ch=getchar();

     while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}

     while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=,INF=~0u>>;

 typedef long long LL;

 /******************tamplate*********************/

 struct Poi{

     int x,y;

     Poi(){}

     Poi(int x,int y):x(x),y(y){}

     void read(){x=getint(),y=getint();}

 }p[N],a[N],st[N],O(,);

 typedef Poi Vec;

 bool operator < (const Poi &a,const Poi &b){return a.x<b.x ||(a.x==b.x && a.y<b.y);}

 Vec operator - (Poi a,Poi b){return Vec(a.x-b.x,a.y-b.y);}

 double Cross(const Poi &a,const Poi &b){return (double)a.x*b.y-(double)a.y*b.x;}

 int n,m,top,k;

 void solve(){

     top=;

     F(i,,m){

         while(top> && Cross(st[top]-st[top-],a[i]-st[top-])<=) top--;

         st[++top]=a[i];

     }

     int k=top;

     D(i,m,){

         while(top>k && Cross(st[top]-st[top-],a[i]-st[top-])<=) top--;

         st[++top]=a[i];

     }

     double ans=0.0;

     F(i,,top-) ans+=Cross(st[i]-O,st[i+]-O)/;

     printf("%.1f\n",ans);

 }

 int main(){

     k=getint(); n=getint();

     F(i,,n) p[i].read();

     sort(p+,p+n+);

     int q=getint();

     F(i,,q){

         m=;

         int x1=getint(),x2=getint(),y1=getint(),y2=getint();

         F(i,,n) if (p[i].x>=x1 && p[i].x<=x2 && p[i].y>=y1 && p[i].y<=y2)

             a[++m]=p[i];

         solve();

     }

     return ;

 }

巴特西

【XJOI】【NOI考前模拟赛7】

DP+卡常数+高精度/ 计算几何+二分+判区间交/ 凸包

填填填

线线线

凸凸凸

最新文章

热门文章