首页 > 代码库 > 第八届福建省大学生程序设计竞赛-重现赛

第八届福建省大学生程序设计竞赛-重现赛

第八届福建省大学生程序设计竞赛-重现赛

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<n;i++){        res+=ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x;    }    return res/2.0;}int lineCross(Point a,Point b,Point c,Point d,Point&p){    double s1,s2;    s1=cross(a,b,c);    s2=cross(a,b,d);    if(sig(s1)==0&&sig(s2)==0) return 2;    if(sig(s2-s1)==0) return 0;    p.x=(c.x*s2-d.x*s1)/(s2-s1);    p.y=(c.y*s2-d.y*s1)/(s2-s1);    return 1;}//多边形切割//用直线ab切割多边形p,切割后的在向量(a,b)的左侧,并原地保存切割结果//如果退化为一个点,也会返回去,此时n为1void polygon_cut(Point*p,int&n,Point a,Point b){    static Point pp[maxn];    int m=0;p[n]=p[0];    for(int i=0;i<n;i++){        if(sig(cross(a,b,p[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<m;i++)        if(!i||!(pp[i]==pp[i-1]))            p[n++]=pp[i];    while(n>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<n1;i++){        for(int j=0;j<n2;j++){            res+=intersectArea(ps1[i],ps1[i+1],ps2[j],ps2[j+1]);        }    }    return res;//assumeresispositive!}//hdu-3060求两个任意简单多边形的并面积Point ps1[maxn], ps2[maxn];int n1, n2;
多边形相交面积模板
技术分享
/*    类型:多边形相交面积模板*/#include<cstdio>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>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<n;i++){        res+=ps[i].x*ps[i+1].y-ps[i].y*ps[i+1].x;    }    return res/2.0;}int lineCross(Point a,Point b,Point c,Point d,Point&p){    double s1,s2;    s1=cross(a,b,c);    s2=cross(a,b,d);    if(sig(s1)==0&&sig(s2)==0) return 2;    if(sig(s2-s1)==0) return 0;    p.x=(c.x*s2-d.x*s1)/(s2-s1);    p.y=(c.y*s2-d.y*s1)/(s2-s1);    return 1;}//多边形切割//用直线ab切割多边形p,切割后的在向量(a,b)的左侧,并原地保存切割结果//如果退化为一个点,也会返回去,此时n为1void polygon_cut(Point*p,int&n,Point a,Point b){    static Point pp[maxn];    int m=0;p[n]=p[0];    for(int i=0;i<n;i++){        if(sig(cross(a,b,p[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<m;i++)        if(!i||!(pp[i]==pp[i-1]))            p[n++]=pp[i];    while(n>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<n1;i++){        for(int j=0;j<n2;j++){            res+=intersectArea(ps1[i],ps1[i+1],ps2[j],ps2[j+1]);        }    }    return res;//assumeresispositive!}//hdu-3060求两个任意简单多边形的并面积Point ps1[maxn],ps2[maxn];int n1=3, n2=3;int main(){    int T;  scanf("%d", &T);    while(T--)    {        for(int i=0;i<n1;i++)            scanf("%lf%lf",&ps1[i].x,&ps1[i].y);        for(int i=0;i<n2;i++)            scanf("%lf%lf",&ps2[i].x,&ps2[i].y);        double ans=intersectArea(ps1,n1,ps2,n2);        //ans=fabs(area(ps1,n1))+fabs(area(ps2,n2))-ans;  //容斥,求并面积        double Area1=area(ps1, n1), Area2=area(ps2, n2);        if(ans>eps && min(Area1,Area2)-ans<eps) puts("contain") ;        else if(ans>eps && min(Area1,Area2)-ans>eps) puts("intersect");        else        {            int mp=0;            for(int i=0; i<n1; ++i)                for(int j=0; j<n2; ++j)                if(ps1[i].x==ps2[j].x && ps1[i].y==ps2[j].y)                    ++mp;            if(mp==2) puts("intersect");            else puts("disjoint");        }    }    return 0;}
View Code

D    KMP,水

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

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

技术分享
#include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>#include<cstring>#include<string>#include<cmath>#include<queue>#include<stack>#include<map>#include<bitset>#include<vector>#include<set>#include<list>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 200005;int nex[N];void getnext(char *B, int lenb){    mes(nex, 0);   nex[0]=-1;    for(int i=0,k=-1; i<lenb; )    {        if(k==-1 || B[i]==B[k]) nex[++i]=++k;        else k=nex[k];    }}bool KMP(char *A, char *B, int lena, int lenb){    getnext(B, lenb);    for(int i=0,j=0; i<lena; )    {        if(j==-1 || A[i]==B[j]) ++i,++j;        else j=nex[j];        if(j==lenb) return true;    }    return false;}char A[N], B[N], A2[N];int main(){    int T;  scanf("%d", &T);    while(T--)    {        scanf("%s %s", A, B);        int lena=strlen(A), lenb=strlen(B), lena2=lena;        if(lenb==1 && B[0]==0) { puts("Alice"); continue; }        for(int i=0,j=lena-1; i<lena2; ++i,--j) A2[i]=A[j];        if(lena<lenb || (KMP(A,B,lena,lenb)==0 && KMP(A2,B,lena2,lenb)==0)) puts("Bob") ;        else puts("Alice");    }    return 0;}
View Code

K   水题

记一下错排公式

// 递推的推导错排公式d[0]=1, d[1]=0, d[2]=1;for(int i=3; i<N; ++i)  d[i]=(i-1)*(d[i-2]+d[i-1])%mod;

还有 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");        }    }}
View Code

方法 2: 大数, 懒得写了,待补。。

第八届福建省大学生程序设计竞赛-重现赛