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

A.Clam and Fish

题意：一个游戏有n个阶段。
每个阶段是四种状态中的一种.

0：没有鱼、没有蛤蜊
1：没有鱼、有一个蛤蜊
2：有一条鱼、没有蛤蜊
3: 有一条鱼、有一个蛤蜊
游戏规则：
一个蛤蜊可以做成鱼饵存储起来，在0状态下如果有鱼饵，那么可以钓到一条鱼。
有蛤蜊并且也有鱼，可以直接用蛤蜊钓到鱼。

问在n个阶段后，能钓到最大的鱼条数是多少。

分析：有一个贪心策略，在没有鱼只有蛤蜊（1状态）的时候进行制作鱼饵，在有一条鱼和一个蛤蜊的时候（3状态）直接钓鱼，在没有鱼没有蛤蜊的时候（0状态）如果当前有鱼饵那么直接钓鱼。这个策略下有可能会剩下a个鱼饵，那么我们只需要将减少a/2个制作鱼饵的阶段，用来钓鱼，可以达到最优。

#include <bits/stdc++.h>

using namespace std;
const int maxn=2e6+7;
const int inf=0x3f3f3f3f;
typedef long long ll;

char s[maxn];

int main()
{
    int n,m,t;
    cin>>t;

    while( t-- )
    {
        cin>>n;
        cin>>s;
        int len=strlen(s);
        ll res=0,a=0;
        for( int i=0;i<len;i++ )
        {
            if( s[i]=='1' )  a++;
            else if( s[i]=='0' )
            {
                if( a>0 ) a--,res++;    
            }
            else if( s[i]=='2' || s[i]=='3' )     res++;
        }
        if( a>0 ) res+=a/2;
        printf("%d\n",res);
    }
    return 0;
}

B. Classical String Problem

题意：给定一个字符串S.
两种操作：
M +pos : 将字符串前pos个的字符移动到字符串末尾位置。
M -pos : 将字符串后pos个的字符移动到字符串首端位置。
A pos: 询问当前字符串第pos位置的字符是多少。

分析：我们只用维护字符的起始指针位置，便可以O(1)回答询问。

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

string s;

int main()
{
    cin>>s;
    int t;
    cin>>t;
    int n=s.size(),m=0;
    while( t-- )
    {
        char c[2];int pos;
        scanf("%s%d",c,&pos);
        if( c[0]=='M' )    m=(m+pos+n)%n;
        else printf("%c\n",s[(m+pos-1)%n]);
    } 
}

C.Operation Love

题意；给定20个点坐标，点依次连接形成一个手掌的形状，该图形是经过给定图示初始点旋转拼音得到，长度不变。
问给出旋转平移后的图形是左手还是右手。
分析：看给定的图形，手掌下端长度为9，然后逆时针长度是8.顺时针长度是6.所以我们只需要找到长度为9的线段两点位置，然后判断与之相邻的两个线段的长度大小。(注意这个需要判断给出的点的顺序是逆时针还是顺时针，这个只需要用到两点的叉积判断正负)
并且这道题精度不能设置太大，因为所有长度都是整数，但是点坐标精度比较大，计算时候只需要eps=（1e-4,0.5）都可以.

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctype.h>

using namespace std;

typedef double db;
const db eps=1e-4;

const int maxn=5e3+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 db &rhs ) const { return point(x/rhs,y/rhs); }
    db operator * ( const point &rhs ) const { return x*rhs.y-y*rhs.x; }
    db dot( const point &rhs ) const { return x*rhs.x+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 ; }
    // bool operator < ( const point &rhs ) const { return (*this)*rhs>0 ; } 极角排序
};


struct segment{ // 线段
    point s,e;
    db len;
    segment(){}
    segment( point _s,point _e ) { s=_s,e=_e; }
    void get( point _s,point _e ) { s=_s,e=_e; }

};


point p[20];
segment seg1[50],seg2[50];

db dis( point a, point b )
{
    return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}


void get_ans( point now[20] )
{


        point a,b,c,d;
        for( int i=0;i<20;i++ )
        {
            if( fabs(dis(now[i],now[(i+1)%20])-9)<eps )
            {
                a=p[(i-1+20)%20]; b=now[i];
                c=now[(i+1)%20];  d=p[(i+2)%20];
                break;
            }
        }
        db len1=dis(a,b),len3=dis(b,c),len2=dis(c,d);

        if( (a-b)*(c-a)<0 ) //逆时针
        {
        //    db len1=dis(a,b),len2=dis(c,d);
            if( len1<len2 ) puts("right");
            else puts("left");
        }
        else //顺时针
        {
      //      db len1=dis(a,b),len2=dis(c,d);
            if( len1>len2 ) puts("right");
            else puts("left");
        }
}



int main()
{
    int t=readb();

    while( t-- )
    {
        for( int i=0;i<20;i++ )  p[i].get();
        get_ans(p);
    }
}

D. Points Construction Problem

题意；给定一个无限大的二维平面，每个整点都被染色成了白色。
先将n个点染色乘黑色。问是否存在一种染色方案满足条件:
染色完后，图上有m对点，对于每对点染色互不相同。
并且每对点的曼哈顿距离是1.

分析：题解讲的很详细。我就只说明其中一个构造方法。

$m\%2==1$ ， $m$ 为奇数一定无解。(枚举几个构造都是偶数
$n*4<m$ 无解一个黑色最多产生4对
$16*n>m*m$ 无解该式子是由 $4*\sqrt{n}>m$ ----> $16*n>m*m$ 转换。

构造我们简单分成
$图片说明$ ,先构造连续的一行n个数，那么贡献是 $图片说明$ ,如果该行少一个元素，将这个元素放到无限远处，那么贡献是会加2的，所以我们定义 $图片说明$ .那么连续的一行有 $图片说明$ 个数，独立无限远处的黑色点有 $图片说明$ 个点。
$图片说明$ ，我们构造 $图片说明$ 的 $图片说明$ 黑色图形.贡献就是 $图片说明$ .此时我们可以使得 $图片说明$ .
然后将剩下的点逐渐向内部填充这个 $图片说明$ .显然我们的填充并不会增加贡献。

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

string s;

int main()
{
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if( m&1 || n*4<m || 16*n>m*m )
        {
             puts("No");
             continue;
        }
        puts("Yes");
        if( 2*n+2<=m )
        {
            int c=(m-(2*n+2))/2;
            int d=n-c;
            for( int i=1;i<=d;i++ ) printf("%d 1\n",i);
            for( int i=1;i<=2*c;i+=2 ) printf("%d 3\n",i);
        }
        else
        {
            int l=m/4,r=m/2-l;
            for( int i=1;i<=l;i++ ) printf("%d 1\n",i);
            for( int i=2;i<=r;i++ ) printf("1 %d\n",i);
            int yu=n-(l+r-1);
            for( int i=2;i<=l && yu>0 ;i++ )
            {
                for( int j=2;j<=r && yu>0;j++,yu-- ) printf("%d %d\n",i,j);
            }

        }
    }
}

E.Two Matchings

题意：
题解简化的题意---
给定2*n个点的完全图，每个点有个数值，每条边的权重是相连的两个数值的差的绝对值，找出两个边没有交集的完全匹配使得这个两个完全匹配的所有边的权重和最小。
分析：
观察：将点按照权值排序，我们选择应该是若干个连续点依次连接和首尾连接形成的偶环。
观察：对于一个偶环，贡献值是最大值减去最小值乘以二.
观察：偶环的最小长度为4(保证存在次优解),并且对于长度大于等于8的偶环，拆解成若干个长度为4的环和长度为6的环，解一定更优。
所以我们将点进行升序排序，然后动态规划进行转移。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;


const int maxn=2e5+10;
const ll inf=0x7f7f7f7f7f7f7f7f; 

ll a[maxn],dp[maxn]; 

int main()
{
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        int n;
        scanf("%d",&n);
        for( int i=1;i<=n;i++ ) scanf("%d",&a[i]),dp[i]=inf;
        sort(a+1,a+1+n);
        for( int i=1;i<=n;i++ )
        {
            if( i>=4 ) dp[i]=min(dp[i],dp[i-4]+a[i]-a[i-3]);
            if( i>=6 ) dp[i]=min(dp[i],dp[i-6]+a[i]-a[i-5]);
        }
        printf("%lld\n",dp[n]*2);

    }
}

F. Fraction Construction Problem

题意：
$图片说明$ $图片说明$
给定 $a,b$ 的值，求 $图片说明$ .
如果没有解决方案输出-1，-1，-1，-1

分析：
情况一： $图片说明$ 和 $图片说明$ 最大公约数 $图片说明$ 不为 $1$ ，那么我们可以构造 $图片说明$ .

情况二: $图片说明$ 的互异质因子数只有一个。无解。
我们将分式通分 $图片说明$
因为 $图片说明$

情况三: $图片说明$ ,我们将 $图片说明$ 根据 $图片说明$ 的质因子构造出来使得 $图片说明$ ，那么 $图片说明$ .求解这个就是扩展欧几里得定理。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=2e6+10;
int prime[5000000];//保存素数
int vis[maxn];//初始化
int cnt;

void getprime(int n)
{
    cnt=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<n;i++)
    {
        if(vis[i]==0)
            prime[cnt++]=i;
        for(int j=0;j<cnt&&i*prime[j]<n;j++)
        {
            vis[i*prime[j]]=1;
            // vis[i*prime[j]]=prime[j]; 
            if(i%prime[j]==0)
                break;
        }
    }
}

ll  exgcd( ll a,ll b,ll &x,ll &y )
{
    ll ans=a;
    if( b ) ans=exgcd(b,a%b,y,x),y-=(a/b)*x;
    else x=1,y=0;
    return ans;
}

int main()
{
    getprime(maxn);
    int t;
    scanf("%d",&t);
    while( t-- )
    {
        ll a,b;
        scanf("%lld%lld",&a,&b);
        if( b==1 )
        {
            puts("-1 -1 -1 -1");
            continue;
        }
        ll gd=__gcd(a,b);
        if( gd!=1 )
        {
            printf("%lld %lld %lld %lld\n",a/gd+1,b/gd,1ll,b/gd);
            continue;
        }
        vector<ll> p;
        ll tmp=b;
        for( int i=0;i<cnt && tmp>=prime[i];i++ )
        {
            if( tmp%prime[i]==0 )
            {
                ll temp=1;
                while( tmp%prime[i]==0 ) tmp/=prime[i],temp*=prime[i];
                p.push_back(temp);
                break;
            }
            if( vis[tmp]==0 ) 
            {
                p.push_back(tmp);
                break;
            }
        }
        ll d=p[0],f=b/d,c,e;
        if( f==1 )
        {
            puts("-1 -1 -1 -1");
            continue;
        }
        else
        {
            exgcd(f,d,c,e);
            e=-e;
            while( c<=0 || e<=0 ) c+=d,e+=f;
            printf("%lld %lld %lld %lld\n",c*a,d,e*a,f);
        }
    }
}