B   计算几何

题意：问两个三角形是相交、包含还是相离。

tags：套板子。。求出相交的面积，再判断一下

/*    多边形相交面积模板*/#define maxn 510const double eps=1E-8;int sig(double d){    return(d>eps)-(d<-eps);}struct Point{    double x,y; Point(){}    Point(double x,double y):x(x),y(y){}    bool operator==(const Point&p)const{        return sig(x-p.x)==0&&sig(y-p.y)==0;    }};double cross(Point o,Point a,Point b){    return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);}double area(Point* ps,int n){    ps[n]=ps[0];    double res=0;    for(int i=0;i
      
       0) pp[m++]=p[i];        if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+1])))            lineCross(a,b,p[i],p[i+1],pp[m++]);    }    n=0;    for(int i=0;i
       
        1&&p[n-1]==p[0])n--;}//---------------华丽的分隔线-----------------////返回三角形oab和三角形ocd的有向交面积,o是原点//double intersectArea(Point a,Point b,Point c,Point d){    Point o(0,0);    int s1=sig(cross(o,a,b));    int s2=sig(cross(o,c,d));    if(s1==0||s2==0)return 0.0;//退化，面积为0    if(s1==-1) swap(a,b);    if(s2==-1) swap(c,d);    Point p[10]={o,a,b};    int n=3;    polygon_cut(p,n,o,c);    polygon_cut(p,n,c,d);    polygon_cut(p,n,d,o);    double res=fabs(area(p,n));    if(s1*s2==-1) res=-res;return res;}//求两多边形的交面积double intersectArea(Point*ps1,int n1,Point*ps2,int n2){    if(area(ps1,n1)<0) reverse(ps1,ps1+n1);    if(area(ps2,n2)<0) reverse(ps2,ps2+n2);    ps1[n1]=ps1[0];    ps2[n2]=ps2[0];    double res=0;    for(int i=0;i
       
      

/*    类型：多边形相交面积模板*/#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 510const double eps=1E-8;int sig(double d){    return(d>eps)-(d<-eps);}struct Point{    double x,y; Point(){}    Point(double x,double y):x(x),y(y){}    bool operator==(const Point&p)const{        return sig(x-p.x)==0&&sig(y-p.y)==0;    }};double cross(Point o,Point a,Point b){    return(a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);}double area(Point* ps,int n){    ps[n]=ps[0];    double res=0;    for(int i=0;i
           
            0) pp[m++]=p[i]; if(sig(cross(a,b,p[i]))!=sig(cross(a,b,p[i+1]))) lineCross(a,b,p[i],p[i+1],pp[m++]); } n=0; for(int i=0;i
            
             1&&p[n-1]==p[0])n--;}//---------------华丽的分隔线-----------------////返回三角形oab和三角形ocd的有向交面积,o是原点//double intersectArea(Point a,Point b,Point c,Point d){ Point o(0,0); int s1=sig(cross(o,a,b)); int s2=sig(cross(o,c,d)); if(s1==0||s2==0)return 0.0;//退化，面积为0 if(s1==-1) swap(a,b); if(s2==-1) swap(c,d); Point p[10]={o,a,b}; int n=3; polygon_cut(p,n,o,c); polygon_cut(p,n,c,d); polygon_cut(p,n,d,o); double res=fabs(area(p,n)); if(s1*s2==-1) res=-res;return res;}//求两多边形的交面积double intersectArea(Point*ps1,int n1,Point*ps2,int n2){ if(area(ps1,n1)<0) reverse(ps1,ps1+n1); if(area(ps2,n2)<0) reverse(ps2,ps2+n2); ps1[n1]=ps1[0]; ps2[n2]=ps2[0]; double res=0; for(int i=0;i
             
              eps && min(Area1,Area2)-ans
              
               eps && min(Area1,Area2)-ans>eps) puts("intersect"); else { int mp=0; for(int i=0; i
              
             
            
           
          
         
        
       
      

D    KMP，水

题意：两个数 a, b 分别给两个人，两人轮流对自己的那个数进行操作。有两种操作：把数反转，或把最后一位数去掉。 如果会出现 a==b的情况，则A胜，反之B胜。

tags：只要看 b有没有在 a或 逆序a 中出现。然后 b==0特判。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
              
             
            
           
          
         
        
       
      

K   水题

记一下错排公式

// 递推的推导错排公式d[0]=1, d[1]=0, d[2]=1;for(int i=3; i

还有 Lucas求逆元的板子。。

ll exp_mod(ll a, ll b, ll p) {    ll res = 1;    while(b != 0) {        if(b&1) res = (res * a) % p;        a = (a*a) % p;        b >>= 1;    }    return res;}ll Comb(ll a, ll b, ll p) {    if(a < b)   return 0;    if(a == b)  return 1;    if(b > a - b)   b = a - b;    ll ans = 1, ca = 1, cb = 1;    for(ll i = 0; i < b; ++i) {        ca = (ca * (a - i))%p;        cb = (cb * (b - i))%p;    }    ans = (ca*exp_mod(cb, p - 2, p)) % p;    return ans;}ll Lucas(int n, int m, int p) {     ll ans = 1;     while(n&&m&&ans) {        ans = (ans*Comb(n%p, m%p, p)) % p;        n /= p;        m /= p;     }     return ans;}

G     大数，java

题意：有 n种东西，每天可以得到一个硬币，有 w (w=n!) 个硬币便可翻一张卡片。每张卡片可以得到一个东西，这个东西的种类是随机的，即是1/n的概率。 现在问你集齐 n种卡片的期望天数。

tags： 真是很好的题呢。。。debug一下午。。。

首先要推出答案来， 设 dp[i]为已有 i 种卡片，要到达 n种卡片的期望天数，则从 i 种卡片出发，过 w天再翻一张卡片，就有两类情况： 1、还是已有的 i 种卡片，概率为 i/n； 2、是另外 n-i 种卡片，概率为(n-i)/n。 所以可以列出式子 dp[i] = (dp[i]+w)*(i/n) + (dp[i+1]+w)*((n-i)/n)，化简后为 dp[i] = dp[i+1] + w*n/(n-i) 。而 dp[n] = 0，所以最后 ans = n!/1 + n!/2 + ........ + n!/n 。   到这里就是上 java 或者 大数板子了。

方法 1： java

//package project1;import java.util.*;import java.math.*;import java.util.Scanner;public class Main {     //Test4 {
             public static void main(String[] argv) throws Exception    {        Scanner sc = new Scanner(System.in);        MathContext mc = new MathContext(7, RoundingMode.HALF_DOWN);                int T = sc.nextInt();        for(int cas=1; cas<=T; ++cas)        {            int  n = sc.nextInt();            BigInteger w = BigInteger.valueOf(1);            for(int i=1; i<=n; ++i)   w = w.multiply(BigInteger.valueOf(i));            BigInteger ans=BigInteger.valueOf(0);            for(int i=n; i>0; --i)            {                ans = ans.add(w.divide(BigInteger.valueOf(i)));            }            System.out.println(ans+".0");        }    }}

方法 2： 大数， 懒得写了，待补。。