第二场
比赛总结
今天又是零贡献的一天┭┮﹏┭┮
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;