2020牛客暑期多校第三场

Author Avatar
MorphLing 7月 24, 2020

C.Operation-Love

按照顺序依次计算两点之间的距离

如果(a,b)长度为6，(b,c)长度为1，说明(a,b)是拇指的线段（指向指尖）

如果(a,b)长度为6，(b,c)长度为9，说明(b,a)是拇指的线段（指向指尖）

如果是左手，那么其他所有点都在拇指线段的左侧，反之则在右侧。

判断点在线段左侧还是右侧可以通过叉乘的方法。

假设线段为(x1,y1)->(x2,y2)，点坐标为(x0,y0)

那么计算(x2-x1,y2-y1)×(x0-x1,y0-y1)的值，<0为右侧,>0为左侧

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN=2e3+5;
const double eps=1e-4;

class Point {
public:
    double x,y;
    bool operator !=(Point &P)
    {
        return fabs(x-P.x)>eps && fabs(y-P.y)>eps;
    }
    Point(double a=0,double b=0):x(a),y(b){}
};
class Line {
public:
    bool ifk;
    double dis;
    double k,b;
    //求过两点的直线
    void mkline (Point A,Point B) {
        dis=sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
        ifk=true;k=b=0;
        if (A.x==B.x) {
            ifk=0;
            b=A.x;
        } else {
            if (A.y==B.y) {
                k=0;
                b=(A.x+B.x)/2;
            } else {
                k=(B.y-A.y)/(B.x-A.x);
                b=A.y-k*A.x;
            }
        }
    }
    //求两点中垂线
    void mkbisector (Point A,Point B) {
        ifk=true;k=b=0;
        if (A.x==B.x) {
            k=0;
            b=(A.y+B.y)/2;
        } else if (A.y==B.y) {
                ifk=0;
                b=(A.x+B.x)/2;
            } else {
                k=-1/(B.y-A.y)*(B.x-A.x);
                b=(A.y+B.y)/2-k*(A.x+B.x)/2;
            }
    }
    bool operator == (Line &T) {
        return (ifk==T.ifk) && fabs(k-T.k)<eps && fabs(b-T.b)<eps;
    }
};

Point p[30];

Line l[30];

int T;
int main()
{
    cin>>T;
    while(T--)
    {
        for (int i=1;i<=20;i++)
        {
            cin>>p[i].x>>p[i].y;
        }
        p[21]=p[1];
        for (int i=1;i<=20;i++)
        {
            l[i].mkline(p[i],p[i+1]);
        }
        l[21]=l[1];
        Point a,b,c;
        for (int i=1;i<=20;i++)
        {
            if (fabs(l[i].dis-6)<eps && fabs(l[i+1].dis-1)<eps)
            {
                a=p[i],b=p[i+1];
            }
            if (fabs(l[i].dis-6)<eps && fabs(l[i+1].dis-9)<eps)
            {
                a=p[i+1],b=p[i];
            }
        }
        for (int i=1;i<=20;i++)
            if (p[i]!=a && p[i]!=b)
            {
                c=p[i];
                break;
            }
        double p=b.x-a.x,q=b.y-a.y,w=c.x-a.x,o=c.y-a.y;
        if (p*o-q*w<0) printf("right\n");
        else printf("left\n");
    }
    return 0;
}

E.Two-Matchings

本身是一个图论问题，要使得每个点都连上两条边且边的权值和最小，权值为两个数之差的绝对值。可以把n个数从小到大排序，把问题变成在一列有序数上连线的问题。

首先考虑到n=4或n=6的情况，可以发现此时答案是固定的，也就是(A[n]-A[1])*2，而对于n>=8的情况，总是可以拆成若干个长度为4或6的分块，并使答案减少分块连接处的两数之差。也就是dp[n]总是从dp[n-4]或dp[n-6]减去连接处的权值后转移过来，这样就可以通过dp计算答案了。

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

const int N=2e5+5;

const ll INF=0x3f3f3f3f3f3f3f3f;

int T,n,m,A[N];

ll dp[N];

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

F.Fraction-Construction-Problem

如果a，b不互质那么答案比较显然，取$\frac{a}{b}$约分之后的分母即可。

考虑a、b互质的情况，把原式转换成$\frac{cf-ed}{df}=\frac{a}{b}$

如果b自身是质数或者1，那么d、f中至少有一个大于等于b，不符合条件。

如果b不是质数且不是1，那么d总能分解成两个互质因子，令b的两个互质因子分别为d、f，那么由扩展欧几里得算法可知$cf-ed=a$一定有整数解。将d、f代入后求正整数解即可。

为了求d的互质因子，在素数筛中可以加入pfactor[i]数组记录i的第一个质因数。将第一个质因数全部取出后，分离出的两个数一定互质。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN=2e6+5;

int T,n,m,a,b;

int vis[MAXN],prime[MAXN],num_p;
int pfactor[MAXN];
void getPrime()
{
    for (int i=2;i<MAXN;i++)
    {
        if (!vis[i]) prime[++num_p]=i;
        for (int j=1;j<=num_p;j++)
        {
            if (i*prime[j]>=MAXN) break;
            pfactor[i*prime[j]]=prime[j];
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}

void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 3;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}

void solve()
{
    cin>>a>>b;
    ll c,d,e,f;
    int g=__gcd(a,b);
    if (g!=1)
    {
        d=f=b/g;
        e=1,c=a/g+1;
        printf("%lld %lld %lld %lld\n",c,d,e,f);
        return;
    }
    a/=g,b/=g;
    if (pfactor[b]!=0)
    {
        int d=1,f=b;
        while(f%pfactor[b]==0) f/=pfactor[b],d*=pfactor[b];
        if (f!=1) {
            Exgcd(f,d,c,e);
            e=-e;
            while(c<=0 || e<=0)
                c+=d,e+=f;
            c*=a,e*=a;
            printf("%lld %lld %lld %lld\n",c,d,e,f);
            return;
        }
    }
    printf("-1 -1 -1 -1\n");
}
int main()
{
    cin>>T;
    getPrime();
    while(T--) solve();
    return 0;
}

G.Operating-on-a-Graph

其实就是并查集，但是需要一些技巧。

两个重点，一是启发式合并，将b合并入a时，若b中元素较多，则直接交换a、b中的元素。

二是合并前清空原有的元素，合并后只保留新增的元素。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int MAXN=1e6+5;

int T,n,m,q,t,u,v;

int FA[MAXN];
vector<int>G[MAXN];
vector<int>group[MAXN];

int fnd(int x)
{
    if (FA[x]==x) return x;
    else return FA[x]=fnd(FA[x]);
}
void solve()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
    {
        G[i].clear();
        group[i].clear();
        FA[i]=i;
        group[i].push_back(i);
    }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cin>>q;
    while(q--)
    {
        scanf("%d",&t);
        if (fnd(t)!=t) continue;
        vector<int>now;
        for (auto h:group[t])
            for (auto to:G[h])
            {
                now.push_back(fnd(to));
            }
        group[t].clear();
        for (auto x:now)
        {
            if (fnd(x)==t) continue;
            FA[x]=t;
            if (group[x].size()>group[t].size()) swap(group[x],group[t]);
            for (auto tt:group[x]) group[t].push_back(tt);
            group[x].clear();
        }
    }
    for (int i=0;i<n;i++) printf("%d ",fnd(i));
    printf("\n");
}
int main()
{
    cin>>T;
    while(T--) solve();
    return 0;
}

D.Points Construction Problem

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

const int N=1e5+5;

int T,n,m;

bool check(int x) {
    int sq=sqrt(x);
    if (x==sq*sq+1 || x==sq*(sq+1)+1) return 0;
    else return 1;
}

int getMn(int x) {
    int sq=sqrt(x);
    if (sq*sq==x) return sq*4;
    if (sq*(sq+1)>=x) return (sq+sq+1)*2;
    return (sq+1)*4;
}
int main() {
    cin>>T;
    while(T--) {
        scanf("%d%d",&n,&m);
        int mx=4*n,mn=getMn(n);
        if (m<mn || m>mx || m%2!=0) {
            printf("No\n");
            continue;
        }
        printf("Yes\n");
        int now=mn,cnt=n;
        while(now<m) {
            if (check(cnt)) {
                cnt--;
                now+=4;
            }
            else {
                cnt--;
                now+=2;
            }
        }
        int fix=0;
        if (now>m) {
            fix=1;
            printf("0 1\n");
        }
        int x=sqrt(cnt-1)+1,t=0;
        for (int i=1;i<=x;i++){
            for (int j=1;j<=x;j++){
                printf("%d %d\n",i,j);
                t++;
                if (t==cnt) break;
            }
            if (t==cnt) break;
        }
        for (int i=100;i<=100+n-cnt-1-fix;i++)
            printf("%d %d\n",i,i);
    }
    return 0;
}