2020牛客暑期多校训练营（第二场）

B. Boundary

题意：给定n个点的点坐标，求所有过(0,0)的圆中，圆上能覆盖最多给定点的圆。输出覆盖点的最大个数。
$图片说明$

分析：
n=1,那么答案就是1.
n>1,因为三个点能确定一个圆，n^2枚举两个点与原点连成三角形，求三角形的外心，然后存储坐标。这样我们可以枚举c出所有覆盖点>=2的圆。(~~求三角形外心直接百度板子~~
由于这道题卡常数，不能用map计数，我们可以sort一遍，然后遍历计算圆心的出现次数。求得最大值 $图片说明$ .
假如一个圆覆盖了 $图片说明$ 个点，那么对于 $图片说明$ 个点两两组合，重复计数圆心次数有 $图片说明$ 次。所以最后计算答案还要再转换一下。

#include<bits/stdc++.h>

using namespace std;
typedef double db;

struct point{
    db x,y;
    point(){}
    point( db _x,db _y ):x(_x),y(_y){ }
    db operator * ( const point &rhs ) const { return 1ll*x*rhs.y-1ll*y*rhs.x; } 
    point operator - ( const point &rhs ) const { return point(x-rhs.x,y-rhs.y); }
}a[2005]; 

db X,Y;
vector< pair<db,db> > p;
void solve( point x,point y,point z )
{
    db x1=x.x,x2=y.x,x3=z.x;
    db y1=x.y,y2=y.y,y3=z.y;
    if( (x-y)*(y-z)==0 ) X=1e18,Y=1e18;
    else
    {
        db G=(y3-y2)*x1+(y1-y3)*x2+(y2-y1)*x3;
        db A=x1*x1+y1*y1,B=x2*x2+y2*y2,C=x3*x3+y3*y3;
        X=( (B-C)*y1+(C-A)*y2+(A-B)*y3 )/(2*G);
        Y=( (C-B)*x1+(A-C)*x2+(B-A)*x3 )/(2*G);
        p.push_back( make_pair(X,Y) );
    }

}

int main()
{
    int n;
    scanf("%d",&n);
    point zero=point(0,0);
    for( int i=1;i<=n;i++ ) scanf("%lf%lf",&a[i].x,&a[i].y);
    for( int i=1;i<=n;i++ )
    {
        for( int j=i+1;j<=n;j++ )    solve(zero,a[i],a[j]);
    }
    sort(p.begin(),p.end());
    int ans=0,cnt=0;
    pair<db,db> now=p[0];
    for( int i=0;i<p.size();i++ )
    {
        if(now==p[i] )    cnt++;    
        else now=p[i],cnt=1;
        ans=max(ans,cnt);
    }
    for( int i=1;i<=n;i++ )
    {
        if( i*(i-1)==ans*2 ) 
        {
            printf("%d",i);
            return 0;
        }
    }
}

C.Cover the Tree

题意：给定一颗无根树，m条无向边，请找到最少的长链，覆盖所有无向边。
分析：长链的一端一定是叶子节点，我们先处理出每个点的度，然后找出所有度为1的叶子节点，然后随便指定一个点为根，进行深度遍历，记录每个结点的深度，然后将叶子节点根据深度从小到大排序，首尾选点进行组合成长链，如果叶子节点的个数是奇数个，那么排序后最中间的叶子结点连向根即可。(~~证明我也不会~~
$图片说明$

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;

vector<int> g[maxn]; 
vector<int> L;
vector<int> R;     
int root;
int fa[maxn];

void dfs( int x,int f )
{
    int flag=1;
    fa[x]=f;
    int cnt=0;
    for( int v : g[x] )
    {
        cnt++;
        if( v==f ) continue;
        flag=0;
        dfs(v,x);
    }
    if( root==x && cnt==1 ) L.push_back(root);
    if( flag ) L.push_back(x);
}

int d[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for( int i=1;i<n;i++ )
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
        d[u]++;
        d[v]++;
        if( d[i]>1 ) root=i;
    }
    dfs(root,root);
    int m=L.size();
    vector< pair<int,int> > ans;
   // for( int i:L ) cout<<i<<" ";
    for( int i=0;i<m/2;i++ )
    {
        ans.push_back( make_pair( L[i],L[m-1-i] ) );
    }
    if( m%2==1 )
    {
        ans.push_back( make_pair( L[m/2],root ) );
    } 
    printf("%d\n",ans.size());
    for( pair<int,int> v:ans )
    {
        printf("%d %d\n",v.first,v.second);
    }
}

D.Duration

签到

F.Fake Maxpooling

题意：n * m的矩阵, $图片说明$ .
定义k* k子矩阵的权值为矩阵内元素的最大值。求所有k* k矩阵的权值和。

分析: 先处理出 $图片说明$ ,可以用记忆化gcd降至 $图片说明$ .
对于k* k 的矩阵。
k=1 的时候每个ij位置的值就是权值。
k>1 的时候，可以简单验证得出i j 进行小等于k次减一操作后可以使得gcd(i,j)==1,获得最大的lcm(i,j).(~~打表可以验证次规律~~
那么转移方程:
$图片说明$ .
这种一种偷懒的计算方式。
当然也可以用单调队列解决k* k子矩阵的最大值。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=5000+10;


int dp[maxn][maxn];
int a[maxn][maxn];

int gcd( int x,int y )
{
    if( y==0 ) return x;
    if( dp[x][y] ) return dp[x][y];
    return dp[x][y]=gcd(y,x%y);
}


int main()
{
    int n,m,k;
    ll ans=0;
    cin>>n>>m>>k;
     for( int i=1;i<=n;i++ )
     {
         for( int j=1;j<=m;j++ )
         {
             if( k==1 ) a[i][j]=i*j/gcd(i,j);
             else a[i][j]=max(i*j/gcd(i,j),max(a[i][j-1],a[i-1][j]));
             if( i>=k && j>=k ) ans+=a[i][j];
         }
     }
     printf("%lld\n",ans);
}

G.Greater and Greater

题意:给定长度为n的a序列和长度为m的b序列，求在a序列中找到连续长度为m的子序列S,满足 $图片说明$ .
求满足的序列个数。
$图片说明$

分析：出题人说看到这种题目的数据范围就能想到 $图片说明$ .(~~反正我是写线段树和st表乱搞写自闭了~~
参考博客

https://www.cnblogs.com/EchoZQN/p/13320776.html

我们先从简单的 $图片说明$ 分析。
$图片说明$ 表示从后面往前匹配， $图片说明$ 串匹配到了第 $图片说明$ 位， $图片说明$ 串匹配到了第 $图片说明$ 位，是否完全匹配。
计算答案只用每次加上 $图片说明$ 的值.
状态转移方程:
$图片说明$ .
内存为 $图片说明$ 一定MLE.
考虑用 $图片说明$ 优化第二维.
因为 $图片说明$ 的值只用两种，0或1.是否能用一个 $图片说明$ 表示第二维 $j$ 的状态.
进一步分析，对于每个 $图片说明$ 与 $图片说明$ 进行比较，最后获得的状态一共有 $图片说明$ 种。
举个例子：对于样例B: 2 3 3 . $图片说明$ 的状态就三种,000 ,100,111.
所以我们可以枚举出所有 $图片说明$ 可能状态.枚举有个小技巧先对 $图片说明$ 按照大小为第一关键字排序.
假如m=5,每个状态就是00000, 10000, 11000, 11100, 11110, 11111.每个状态比上一个状态多1.
每次让 $图片说明$ ,并且让当前这位的初始位置上添加一个1---- $图片说明$ .
可以在 $图片说明$ 的时间和空间内处理出来。
考虑 $图片说明$ 的 $图片说明$ 转移.

$图片说明$ .
$图片说明$ 表示 $图片说明$ 对应的状态，下标 $图片说明$ 可以用二分求得。

因为 $图片说明$ 对应 $图片说明$ 的状态，我们只需要将 $图片说明$ 进行右移一位对应转移.
因为右移了一位， $图片说明$ ，考虑 $图片说明$ 序列中第 $图片说明$ 位与 $图片说明$ 序列中的第 $图片说明$ 位匹配，根据 $图片说明$ 进行添1操作转移。
$图片说明$ 也可以用一个 $图片说明$ 变量进行滚动转移.

#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;

bitset<40010>a,b[maxn];
int n,m,ans,c[maxn],d[maxn],e[maxn];
int cmp( int x,int y ) {  return d[x]<d[y]; }

int main()
{
    scanf("%d%d",&n,&m);
    for( int i=0;i<n;i++ ) scanf("%d",&c[i]);
    for( int i=0;i<m;i++ ) scanf("%d",&d[i]),e[i]=i;
    sort(e,e+m,cmp);
    for( int i=1;i<=m;i++ ) b[i]=b[i-1],b[i].set(e[i-1]);
    for( int i=n-1;i>=0;i-- )
    {
        a>>=1;
        int l=0,r=m;
        while( l<r )
        {
            int mid=l+r>>1;
            if( c[i]<d[e[mid]] ) r=mid;
            else l=mid+1;
        }
        a&=b[l];
        if( c[i]>=d[m-1] ) a.set(m-1);
        ans+=a[0];
    }
    printf("%d\n",ans);
}

I. Interval

平面图转对偶图.网络流

H.Happy Triangle

题意：一个 $图片说明$ 序列。三种操作。
操作一：删除一个元素 $图片说明$ 。
操作二：添加一个元素 $图片说明$ 。
操作三：询问序列中是否存在两个元素，使得和 $图片说明$ 作为三条边形成非退化三角形(面积不为0

分析:定义选择的两个元素 $图片说明$ 并且 $图片说明$ ， $图片说明$ 一定是相邻数。 $图片说明$ .

我们只需要在map中找到 $图片说明$ 的位置 $图片说明$ ， $图片说明$ 之后的位置两数相加都会大于 $x$ .
再找区间 $图片说明$ 位置两数之差的最小值。用线段树实现，动态开点线段树，每个值存于前面一个数的差值。支持点修改，区间查询。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=2e5+10;
const int inf=1e9;
int n,m,op;
int ls[maxn*21],rs[maxn*21],val[maxn*21],cnt,rt;
map<int,int> mp;

void update( int &cur, int l,int r, int pos,int p )
{
    if( !cur ) cur=++cnt,val[cnt]=p;
    if( l==r )
    {
        val[cur]=p;return;
    }
    int mid=l+r>>1;
    if( pos<=mid ) update(ls[cur],l,mid,pos,p);
    if( pos>mid ) update(rs[cur],mid+1,r,pos,p);
    int ans=inf*2;
    if ( ls[cur] ) ans = min(ans, val[ls[cur]] );
    if ( rs[cur] ) ans = min(ans, val[rs[cur]] );
    val[cur] = ans;
}

int query_min( int cur,int l,int r,int L,int R )
{
    if( l>r || !cur ) return inf*2;
    if( L<=l && R>=r ) return val[cur];
    int mid=(l+r)/2;
    int ans=inf*2;
    if( L<=mid ) ans=min(ans,query_min(ls[cur],l,mid,L,R));
    if( R>mid ) ans=min(ans,query_min(rs[cur],mid+1,r,L,R));
    return ans;
}

int query( int x )
{
    int y=x/2+1;
    auto it=mp.lower_bound(y);
    if( it==mp.end() ) return inf*2;
    if( it->second > 1 ) return it->first;
    if( it!=mp.begin() )
    {
        auto l=it;
        l--;
        if( l->first+it->first > x ) return it->first;
    }
    if( (++it)!=mp.end() ) return it->first;
    return inf*2;
}

void add( int x )
{
    mp[x]++;
    if( mp[x]==1 )
    {
        auto it=mp.lower_bound(x);
        ++it;
        if( it!=mp.end() && it->second==1 ) // if  it->second >1  差值为 0 是最优的 所以不需要更改 
        {
            update(rt,0,inf,it->first,it->first-x );
        }
        it--;
        int l=-inf*2;
        if( it!=mp.begin() ) l=(--it)->first;
        update(rt,0,inf,x,x-l);
    }
    else if( mp[x]==2 ) update(rt,0,inf,x,0);
}

void del( int x )
{
    auto it=mp.lower_bound(x);
    mp[x]--;
    int l=-inf;
    if( it!=mp.begin() ) l=(--it)->first,it++;
    if( mp[x]==0 )
    {
        if(  (++it)!=mp.end() && it->second==1 )
        {
            update(rt,0,inf,it->first,it->first-l);
        }
        update(rt,0,inf,x,inf*2);
        mp.erase(x);
    }
    else if( mp[x]==1 ) update(rt,0,inf,x,x-l);
}

int main()
{
    scanf("%d",&n);
    for( int i=1;i<=n;i++ )
    {
        scanf("%d%d",&op,&m);
        if( op==1 ) add(m);
        if( op==2 ) del(m);
        if( op==3 )
        {
            if( query_min(rt,0,inf,query(m),inf)<m ) puts("Yes");
            else puts("No");
        }
    }
}

J.Just Shuffle

题意：对于一个排列A，给定一个置换规则P，排列B{1,2,3,....,n}在使用置换P，K 次后得到排列A.输出第一次置换的结果.
分析：
因为B{1,2,3,..,n} 所以B置换一次输出的序列就是置换P。

$图片说明$
$图片说明$ ， $图片说明$ 为置换循环节的长度。
$图片说明$
$图片说明$
$图片说明$ .
我们遍历A所有的置换环，枚举出 $图片说明$ ,对每个 $图片说明$ 求出 $图片说明$ .对第 $图片说明$ 个环的元素进行 $图片说明$ 次置换.就可以得到一个合法解。因为 $图片说明$ 是一个大质数，所以一定有解。

  #include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn=1e5+10;

int vis[maxn],a[maxn],b[maxn];
vector<int> v;
int n,k;

void gao()
{
    int r=v.size(),inv;
    for( int i=0;i<r;i++ ) if( (ll)k*i%r==1 ) inv=i;
    for( int i=0;i<r;i++ ) b[v[i]]=v[(i+inv)%r];
}

int main()
{
     cin>>n>>k;
     for( int i=1;i<=n;i++ ) cin>>a[i];

     for( int i=1;i<=n;i++ )
     {
         if( !vis[i] )
         {
             v.clear();
             int x=a[i];
             while( !vis[x] )
             {
                 vis[x]=1;
                 v.push_back(x);
                 x=a[x];
             }
             gao();
         }
     }
     for( int i=1;i<=n;i++ ) printf("%d ",b[i]);
     puts("");
}

K.Keyboard Free

参考博客：https://www.cnblogs.com/wlzhouzhuan/p/13301358.html
非常棒的题解。

附一个自适应辛普森法求积分。

#include<bits/stdc++.h>

using namespace std;

typedef double db;
// https://www.luogu.com.cn/problem/P4525 
db a,b,c,d,l,r;
const db PI=acos(-1.0);

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;
}
// 积分 
// ( 0 ~ π)        H + r3 ×sin(x)
// ( 0 ~ alpha )    H - r3 ×sin(x)
// ( alpha ~ π- alpha )  r3 ×sin(x) - H

inline db f( db x ) // 在[l,r] 定积分收敛的函数 
{
    return pow(x,a/x-x); // 函数
}

inline db simpson( db l,db r ) //Simpson公式
{
    db mid=(l+r)/2;
    return ( f(l)+4*f(mid)+f(r) )*(r-l)/6;
}

db asr( db l, db r,db eps ,db ans )
{
    db mid=(l+r)/2;
    db ls=simpson(l,mid),rs=simpson(mid,r);
    if( fabs(ls+rs-ans)<=15*eps ) return ls+rs+(ls+rs-ans)/15; //确认精度
    return asr(l,mid,eps/2,ls)+asr(mid,r,eps/2,rs);   //精度不够则递归调用
}

inline db asr( db l,db r,db eps ) { return asr(l,r,eps,simpson(l,r)) ; }

int main()
{
    int t;
    t=readb();
    while( t-- )
    {
        db r1=readb(),r2=readb(),r3=readb();
        if( r1>r2 ) swap(r1,r2);
        if( r2>r3 ) swap(r2,r3);
        if( r1>r3 ) swap(r1,r3);
        db ans=0.0;
        for( int i=1;i<=1000;i++ )
        {
            db sin_x=sin(2.0*PI/1000.0*i);
            db cos_x=cos(2.0*PI/1000.0*i);

            db X=r2*cos_x,Y=r2*sin_x;
            db L=sqrt(  (X-r1)*(X-r1)+Y*Y );
            db H=Y/L*r1;
            db alpha=asin(H/r3);
            db h=(4.0*r3*cos(alpha)+4.0*alpha*H)/(2.0*PI);
            ans+=h*L/2.0;
        }        
        ans/=1000.0;
        printf("%.1lf\n",ans);
    }
}

2020牛客暑假多校赛补题文章被收录于专栏

自闭补题