own problem, ICPC Asia regionals, Amritapuri 2010 部分题解

我不是女神ヾ 2022-08-10 15:49 167阅读 0赞

今天比赛做了一下own problem, ICPC Asia regionals, Amritapuri 2010，很坑啊、、、

比赛链接：http://vjudge.net/contest/view.action?cid=51403\#overview

F题和G题是两道水题，上来就发现了。两道题目A完花8min多，排名第二

然后看A题有人A了，上去搞A题，没想坑死在这题目上了、

题目链接：http://www.bnuoj.com/bnuoj/problem\_show.php?pid=22532

题意：给出一个凸多边形，然后50000次询问，每次询问给出两个点变成一个直线把凸多边形划分两部分小的部分的面积。

分析：正好前几天搞了计算几何，马上准备切掉，分析发现满足前缀和性质，可以把从0点开始到 i 点的多边形所有的面积和求出来存在一个数组里面，然后求的时候只用这两点的面积差减去一个三角形就ok。

![Center][]

![Image 1][]

假如给出上面一个多边形，我们知道求多边形面积的时候把多边形划分为三角形，然后用一个ans数组存从0开始到 i 点的面积。

那么现在我要求直线2---4划分后较小的面积，我可以用abs【4】- ans【2】为多边形，0,2,3,4 的面积，然后我减去三角形0,2,4的面积就是所要求的面积，50000次查询，每次O（1）的复杂度，完全没有问题。

但是我的代码写的时候，用叉积求出平行四边形面积除以2，ans存的是三角形的面积，然后按三角形的面积处理，一直wa....11次、

后面看别人直接存平行四边形，最后结果除以2，我改成那样就AC了。。。难道有精度损失，不解啊！！！坑死了。

代码：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <string>
    using namespace std;
    #define Del(a,b) memset(a,b,sizeof(a))
    const int N = 55000;
    const double esp = 1e-10;
    struct Point
    {
        double x,y;
        Point(double x=0,double y=0):x(x),y(y) {}
    };
    Point a[N];
    double ans[N];
    typedef Point Vector;
    Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }
    Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }
    Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); }
    Vector operator / (Vector A,double p) { return Vector(A.x/p,A.y/p); }
    
    double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); }
    double Area2(Vector A,Vector B,Vector C)  { return Cross(B-A,C-A)/2; }
    double ConvexPolygonArea(int n)//多边形面积,，点按顺序
    {
        double area=0;
        for(int i=1;i<n-1;i++)  {
            area+=Area2(a[0],a[i],a[i+1]);
            ans[i+1]=area;
        }
        return area;
    }
    
    int main()
    {
        int n,q;
        while(~scanf("%d%d",&n,&q))
        {
            for(int i=0;i<n;i++)
                scanf("%lf%lf",&a[i].x,&a[i].y);
            memset(ans,0,sizeof(ans));
            double sum=ConvexPolygonArea(n);
            int x,y;
            while(q--)
            {
                scanf("%d%d",&x,&y);
                double tmp=fabs(ans[y]-ans[x]-Area2(a[0],a[x],a[y]));
                tmp=min(tmp,fabs(sum)-tmp);
                printf("%.1lf\n",tmp);
            }
        }
    }

然后是I题，题目链接：http://www.bnuoj.com/bnuoj/problem\_show.php?pid=22540

题意：给一个数n，可以把n分成一些数的和，然后这些数乘起来得到x，问最多能得到多少个不同的 x 。

分析：有这样两个结论：

结论1：任何一个数 n 拆分后乘积可以种数等效于只把n拆分成素数之后的解。

结论2：任何一个数 n 可以有小于 n 的所有 2^i 的和来表示，这其实是二进制表示数的原理。

那么就可以暴搜了，把 n 无限拆分素数，拆分后的解用set计数就ok

代码：

#include<cstdio>
    #include<cstring>
    #include<set>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    set<LL> s;
    int prime[21] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73};
    int n, p;
    
    void dfs(int num, int cur, LL ans)  ///表示拆分的素数的编号，要拆分的数以及，得到的结果
    {
        s.insert(ans);
        if(cur < prime[num]) return ;
        dfs(num, cur - prime[num], ans * prime[num] % p);
        dfs(num+1, cur, ans);
    }
    
    int main()
    {
        int T, i, j;
        scanf("%d",&T);
        while(T--) {
            scanf("%d%d",&n,&p);
            s.clear();
            dfs(0, n, 1);
            printf("%d\n", s.size());
        }
        printf("\n");
    }

[Center]: /images/20220810/5cd1203019974c4b9c979d8f5b2b57d3.png
[Image 1]: