D.Deep800080
题目大意：给定n个点的坐标，和一条线段两端的坐标，在线段上找到一个点作为圆心，画半径为r的圆，求圆最多能覆盖多少个点。
分析：考虑一个点刚好被圆覆盖，线段上对应的圆心的位置。一般会有两个(存在圆心满足).
圆心在l---r位置，点x一定会被覆盖。那么我们就可以将点变成线段上的一段区间。这段区间上的点就是能覆盖到点x.
那么将所有点进行转换成一段区间进行差分计算，就能得到最优原点的位置。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctype.h>
//#include<bits/stdc++.h>
using namespace std;
typedef double db;
const db eps=1e-8;
const db PI=acos(-1.0);
const int maxn=3e5+10;
int n;
inline db readb()
{
int f=1;db x=0;char s=getchar();
for( ;!isdigit(s);s=='-' && (f=-1),s=getchar());
for( ;isdigit(s);x=x*10+s-48,s=getchar());
if( s=='.' ) for( db l=0.1,s=getchar();isdigit(s);x=x+(s-48)*l,l/=10,s=getchar() );
return x*f;
}
int sgn( double d ) { return (d>eps)-(d<-eps); }; // 精度判断
struct point{
db x,y;
point(){ x=y=0; }
point(db _x,db _y ){ x=_x,y=_y; }
point operator + ( const point &rhs ) const { return point(x+rhs.x,y+rhs.y); }
point operator - ( const point &rhs ) const { return point(x-rhs.x,y-rhs.y); }
point operator / ( const int &rhs ) const { return point(x/rhs,y/rhs); }
db operator * ( const point &rhs ) const { return 1ll*x*rhs.y-1ll*y*rhs.x; }
point operator * ( const db &rhs ) const { return point(x*rhs,y*rhs);}
db dot( const point &rhs ) const { return 1ll*x*rhs.x+1ll*y*rhs.y; }
void get(){ x=readb(),y=readb(); }
bool operator == ( const point &rhs ) const { return x==rhs.x && y==rhs.y; }
bool operator < ( const point &rhs ) const { return sgn(x-rhs.x)<0 || sgn(x-rhs.x)==0 && sgn(y-rhs.y)<0 ; }
point Rotate( db rad ) { return point(x*cos(rad)-y*sin(rad), x*sin(rad)+y*cos(rad) ); }
db sdis() { return sqrt(x*x+y*y); }
// bool operator < ( const point &rhs ) const { return (*this)*rhs>0 ; } 极角排序
};
db dist( point a,point b ) { return sqrt( (b-a).dot(b-a) ); }
bool getdir( point p[],int n ) // true 逆时针存边
{
db ans=0;
for( int i=0;i<n;i++ ) ans+=p[i]*p[(i+1)%n];
return sgn(ans)>0;
}
struct segment{ // 线段
point s,e;
segment(){}
segment( point _s,point _e ) { s=_s,e=_e; }
void get( point _s,point _e ) { s=_s,e=_e; }
bool inter( const segment &l1, const segment &l2 ) // 两线段是否交 1 交 / 0 不交
{
return
max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&
max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&
max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&
max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&
sgn( (l2.s-l1.e)*(l1.s-l1.e) )*sgn( (l2.e-l1.e)*(l1.s-l1.e) ) <= 0 &&
sgn( (l1.s-l2.e)*(l2.s-l2.e) )*sgn( (l1.e-l2.e)*(l2.s-l2.e) ) <= 0;
}
bool inter1( const segment &l1,const segment &l2 ) // 两线段是否正规相交 1 交 / 0 不交
{
if( inter(l1,l2) )
{
if( l1.s==l2.s && l1.e==l2.e || l1.s==l2.e && l1.e==l2.s ) return true; //重合
else if( l1.s==l2.s || l1.s==l2.e || l1.e==l2.s || l1.e==l2.e ) return false; // 端点相交
return true;
}
return false;
}
bool OnSeg( const point &p ) //判断点在线段上 1 在/ 0 不在
{
return sgn( (s-p)*(e-p) )==0
&& sgn( (p.x-s.x)*(p.x-e.x) )<=0
&& sgn( (p.y-s.y)*(p.y-e.y) )<=0;
}
pair<point,int> operator & ( const segment &rhs ) const{ // 两直线相交问题
point res=s; //交点
if( sgn( (s-e)*(rhs.s-rhs.e) )==0 )
{
if( sgn( (rhs.s-s)*(rhs.e-s) )==0 ) return make_pair(res,0); // 两直线重合
else return make_pair( res,1 ); // 两直线平行
}
db t= ( (s-rhs.s)*(rhs.s-rhs.e) )/ ( (s-e)*(rhs.s-rhs.e) ) ; //单位化
res.x+=(e.x-s.x)*t;
res.y+=(e.y-s.y)*t;
return make_pair(res,2); // 有交点
}
point NearestPointToLineSeg( const point &P,const segment &L ) // 线段 最近点对
{
point result;
db t = ( (P-L.s).dot(L.e-L.s) )/( (L.e-L.s).dot(L.e-L.s) );
if( t >= 0 && t <= 1 )
{
result.x = L.s.x + (L.e.x - L.s.x)*t;
result.y = L.s.y + (L.e.y - L.s.y)*t;
}
else
{
if(dist(P,L.s) < dist(P,L.e))
result = L.s;
else result = L.e;
}
return result;
}
};
//--------------------直线----------------
struct sLine{ // 直线
point s,e;
sLine(){}
sLine( point _s,point _e ) { s=_s,e=_e; }
sLine operator * ( const db &rhs ) const { return sLine(s*rhs,e*rhs); }
pair<point,int> operator & ( const sLine &rhs ) const{ // 两直线相交问题
point res=s; //交点
if( sgn( (s-e)*(rhs.s-rhs.e) )==0 )
{
if( sgn( (rhs.s-s)*(rhs.e-s) )==0 ) return make_pair(res,0); // 两直线重合
else return make_pair( res,1 ); // 两直线平行
}
db t= ( (s-rhs.s)*(rhs.s-rhs.e) )/ ( (s-e)*(rhs.s-rhs.e) ) ; //单位化
res.x+=(e.x-s.x)*t;
res.y+=(e.y-s.y)*t;
return make_pair(res,2); // 有交点
}
int segLineCross( const sLine &s1,const segment &s2 ) // 直线和线段相交
{
point a=s1.s,b=s1.e,c=s2.s,d=s2.e;
int d1,d2;
d1 = sgn( (b-a)*(c-a) );
d2 = sgn( (b-a)*(d-a) );
if( (d1^d2)==-2 ) return 1; // 标准相交
if( d1==0 || d2==0 ) return 2; // 不标准相交
return 0; // 不相交
}
db getDistance( point A ) //点到直线的距离
{
return fabs((A-s)*(A-e)/dist(s,e) );
}
sLine Circle_inter( point o,sLine X ,db R ) //圆与直线交点
{
point o2 = o;
o2.x += X.s.y - X.e.y;
o2.y += X.e.x - X.s.x;
o2=
o2 = (sLine(o,o2)&X).first;
db t = sqrt(R * R - (o2 - o).sdis() * (o2 - o).sdis()) / (X.s - X.e).sdis();
point p1 = o2 - (X.e - X.s) * t;
point p2 = o2 + (X.e - X.s) * t;
return sLine(p1,p2);
}
};
point p[maxn];
sLine s;
struct node{
db x,y;
int c;
}cc;
int main()
{
int n,r,a,b;
n=readb(),r=readb(),a=readb(),b=readb();
for( int i=0;i<n;i++ ) p[i].get();
s=sLine(point(0,0),point(a,b));
vector<node> g;
for( int i=0;i<n;i++ )
{
if( s.getDistance(p[i])<=r )
{
sLine tmp=s.Circle_inter(p[i],s,r);
node p1={tmp.s.x,tmp.s.y,1};
node p2={tmp.e.x,tmp.e.y,-1};
if( p1.x>p2.x || ( sgn(p1.x-p2.x)==0 && p1.y>p2.y )) swap(p1.c,p2.c);
g.push_back(p1);
g.push_back(p2);
}
}
sort(g.begin(),g.end(),[&]( node x,node y ) {
if( sgn(x.x-y.x)==0 && sgn(x.y-y.y)==0 ) return x.c>y.c;
if( sgn(x.x-y.x)==0 ) return x.y<y.y;
return x.x<y.x; }
);
int ans=0,sum=0;
for( int i=0;i<g.size();i++ )
{
sum+=g[i].c;
ans=max(ans,sum);
}
printf("%d\n",ans);
}
E.Zeldain Garden
大致题意：求区间[n,m]的每个数的因子和。
分析：我们可以求出每个数作为因子出现的次数。 .
那么这个式子就是整除分块。
# include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL X(LL n)
{
LL l, r;
LL ans = 0;
for( l = 1; l <= n; l = r+1)
{
r = n/(n/l);
ans += n/l * (r - l + 1);
}
return ans;
}
int main(){
LL n,m;
cin>> n>>m;
printf("%lld\n",X(m)-X(n-1));
}H.Ponk Warshall
大致题意：给定两个由A,G,C,T组成的字符串，我们可以操作第一个串，任意位置进行交换，求变成第二个串的最小操作次数。
分析：对于交换，我们肯定优先考虑长度小的循环节，先从长度为2 的循环节进行操作，然后再从长度为3的循环节进行操作，最后操作长度为4的循环节。(这样可以用最小的操作次数满足尽可能多的位置字符相同)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll poww(ll a,ll b,ll mod){
ll ans = 0;//a乘b等价转化为b个a相加，和快速幂原理一致
while(b){
if(b&1) ans = (ans+a)%mod;
a = (a+a)%mod;
b>>=1;
}
return ans;
}
int a[100][100];
int b[4]={'A','G','C','T'};
int main()
{
string s1;
string s2;
cin>>s1>>s2;
int n=s1.size();
int tot=0;
for(int i=0;i<n;i++){
if( s2[i]==s1[i] ) continue;
if(a[s2[i]][s1[i]]){
a[s2[i]][s1[i]]--;
tot++;
}else{
a[s1[i]][s2[i]]++;
}
}
int c;
do{
c=min(a[b[0]][b[1]],min(a[b[1]][b[2]],a[b[2]][b[0]]));
tot+=c*2;
a[b[0]][b[1]]-=c;
a[b[1]][b[2]]-=c;
a[b[2]][b[0]]-=c;
}while(next_permutation(b,b+4));
do{
c=min(a[b[0]][b[1]],min(a[b[1]][b[2]],a[b[2]][b[3]]));
c=min(c,a[b[3]][b[0]]);
tot+=c*3;
a[b[0]][b[1]]-=c;
a[b[1]][b[2]]-=c;
a[b[2]][b[3]]-=c;
a[b[3]][b[0]]-=c;
}while(next_permutation(b,b+4));
printf("%d\n",tot);
}
京公网安备 11010502036488号