Press "Enter" to skip to content

牛客暑期多校训练第二场

第二场

比赛总结

今天又是零贡献的一天┭┮﹏┭┮

B.Boundary

题目链接

标签

计算几何 高精度

题意

在n个点中找出最多的点,使得找出的点和原点共圆。

解题思路

构造所有的点和原点的中垂线,然后计算中垂线的交点的众数。
为了保证精度尽量能不用除法就不用除法。
还有需要考虑所有的点与原点共线的情况。(就是因为它我贡献了WA*5?)

代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-5;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
template<typename T>
struct Node
{
    T x,y;
    Node(T x,T y):x(x),y(y){}
    Node(){}
    Node operator+(const Node&a){
        return Node(a.x+x,a.y+y);
    }
    Node operator/(T a){
        return Node(x/a,y/a);
    }
    bool operator==(const Node&a)const &{
        if(abs(a.x-x)>=eps)return false;
        if(abs(a.y-y)>=eps)return false;
        return true;
    }
};
struct Line
{
    double a,b,c;
    Line(double a,double b,double c):a(a),b(b),c(c){}
    Line(){}
};
Line perpendicular_bisector(Node<int> x)
{
    int a=-2*x.x;
    int b=-2*x.y;
    int c=x.x*x.x+x.y*x.y;
    return Line(a,b,c);
}
bool cmp(Node<double> &a,Node<double> &b)
{
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
Node<double> intersect(Line &a,Line &b)
{
    double v1=a.b*b.c-b.b*a.c;
    double v2=b.a*a.c-a.a*b.c;
    double u=a.a*b.b-b.a*a.b;
    Node<double> pt;
    pt.x=v1/u;
    pt.y=v2/u;
    return  pt;
}

vector<Line> lines;
vector<Node<double> > nodes;

int main()
{
    int n,x,y;
    cin>>n;
    rep(i,0,n){cin>>x>>y;lines.push_back(perpendicular_bisector(Node<int>(x,y)));}
    int ans=1;
    rep(i,0,n)
    {
        nodes.clear();
        rep(j,i+1,n)if(lines[i].a*lines[j].b!=lines[i].b*lines[j].a)nodes.push_back(intersect(lines[i],lines[j]));
        int t=1;
        if(nodes.size()>0)t=2;
        sort(all(nodes),cmp);
        for (int j = 1; j < nodes.size(); j++)
        {
            if(nodes[j]==nodes[j-1])t++;
            else
            {
                ans=max(ans,t);
                t=2;
            }
        }
        ans=max(ans,t);
    }
    cout<<ans<<endl;
    return 0;
}

E.Exclusive OR

题目链接

标签

位运算 FWT

题意

就是从n个数字中选择1~n个数量的数字让其做异或,求最大值分别是多少。数字可以重复取。

解题思路

因为$A_i<2^{18}$所以最大的答案为$2^{18}-1$,因为相同的数异或为$0$所以当$n>19$时$ans[n]=ans[n-2]$成立,所以小于19的答案可以根据异或卷积使用快速沃尔什变换(FWT)得到。

代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)2e5+5;
const int mod=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
ll rev;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

void FWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)  
        for(int m=d<<1,i=0;i<n;i+=m)  
            for(int j=0;j<d;j++)  
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;  
            }  
}  
  
void UFWT(int a[],int n)  
{  
    for(int d=1;d<n;d<<=1)  
        for(int m=d<<1,i=0;i<n;i+=m)  
            for(int j=0;j<d;j++)  
            {  
                int x=a[i+j],y=a[i+j+d];  
                a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;  
            }  
}  
void solve(int a[],int n)  
{  
    FWT(a,n);  
    for(int i=0;i<n;i++) a[i]=1LL*a[i]*A[i]%mod;  
    UFWT(a,n);  
} 
int A[(1<<20)],B[(1<<20)];
int ans[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    rev = powmod(2, mod - 2);
    int n,a;
    cin>>n;
    rep(i,0,n){cin>>a;A[a]=B[a]=1;}
    FWT(A,(1<<19));
    rep(i,1,20)
    {
        rep(j,0,(1<<19))if(B[j]){B[j]=1;ans[i]=j;}
        solve(B,(1<<19));
    }
    rep(i,20,n+1)ans[i]=ans[i-2];
    rep(i,1,n+1)cout<<ans[i]<<" ";
    cout<<endl;
    return 0;
}

K.Keyboard Free

题目链接

解题思路

利用叉乘推出三角形面积计算公式,然后使用两次辛普森积分,因为STL的三角函数计算缓慢所以三角函数先打了一个表

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
typedef long long ll;
using namespace std;
const double eps=1e-2;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
namespace mymath{
    const double eps=1e-5;
    double C[200005];
    double S[200005];

    inline double fcos(double x){return C[(int)round(x/eps/PI)];}
    inline double fsin(double x){return S[(int)round(x/eps/PI)];}
    void init()
    {
        for (int i = 0; i <= 2/eps; i++)
        {
            C[i]=cos(i*eps*PI);
            S[i]=sin(i*eps*PI);
        }
    }
}
int r[3];
double Ca,Sa;
inline double simpson(double l,double r,double ans,double (*f)(double));
inline double calc(double l,double r,double (*f)(double));
inline double f1(double x);
inline double f2(double x)
{
    Ca=mymath::fcos(x);
    Sa=mymath::fsin(x);
    return simpson(0,2*PI,calc(0,2*PI,f1),f1)/2/PI;
}
inline double f1(double x){return abs(-r[2]*mymath::fsin(x)*(r[0]-r[1]*Ca)+r[1]*Sa*(r[0]-r[2]*mymath::fcos(x)))*0.5;}
inline double calc(double l,double r,double (*f)(double)) {return (r-l)*(f(l)+f(r)+4*f((l+r)/2))/6;}
inline double simpson(double l,double r,double ans,double (*f)(double))
{
    double mid=(l+r)/2,ans1=calc(l,mid,f),ans2=calc(mid,r,f);
    if(fabs(ans1+ans2-ans)<=eps) return ans;
    return simpson(l,mid,ans1,f)+simpson(mid,r,ans2,f);
}
int main()
{
    int n;
    scanf("%d",&n);
    mymath::init();
    while(n--)
    {
        scanf("%d%d%d",&r[0],&r[1],&r[2]);
        sort(r,r+3);
        double ans=simpson(0,PI,calc(0,PI,f2),f2);
        printf("%.1lf\n",ans/PI);
    }
    return 0;
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x