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

B 计算几何

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

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

/*
    多边形相交面积模板
*/
#define maxn 510
const 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为1
void 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 510
const 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为1
void 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 0x3f3f3f3f
typedef 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：大数，懒得写了，待补。。