2020牛客国庆集训派对day6 部分题解

前言

好题很多

A Fractions

题意：给出一个n，构造两个数组满足
$图片说明$

分析：
让我们推导一下，假设存在两个数x/a,y/b使得上式成立(为最简式)
$图片说明$
那么可以得知 a * b = n,枚举n的因数，然后可以得到b，因为是分数，再通过枚举x来计算出y的结果，即

for (ll i=2;i<=sqrt(n);i++)
    if(n%i==0)//枚举因子a
        for (ll j=1;j<i;j++)
            if((n-1-j*n/i)%i==0)//枚举分子x，求出y的值
            {
                printf("YES\n2\n%lld %lld\n%lld %lld\n",j,i,(n-1-j*n/i)/i,n/i);//只需要两个即可
                return 0;
            }

代码

B Guest Student

题意：有多组数据，每一组数据，都有一周的课程安排，有七天，每一天有一个a[i]表示是否学习，再出入一个n，问如果总共要学习 n 天，最少要在学校待几天。
分析：
简单模拟就好(差点给我栽这儿了Qwq),因为只有七天，那就以每一天为起点，求出如果总共要学n天一共需要待多长时间。有一些细节要注意。因为这n天肯定不能直接循环去做，那么就将其分为整体和部分两种情况。
代码

#include<bits/stdc++.h>

using namespace std;

const int N=10;

int n;
int a[N];

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        scanf("%d",&n);int tot=0;
        for (int i=1;i<=7;i++)
            scanf("%d",&a[i]),tot+=a[i];

        int ans=1e3;
        for (int i=1;i<=7;i++)
        {
            int rem=n%tot+tot;
            int res=0,now=0;
            for (int j=i;;)
            {
                if(a[j]) res++;
                now++;j++;
                if(j==8) j=1;
                if(res==rem) break;
            }
            ans=min(ans,now);
        }

        printf("%d\n",ans+(n/tot-1)*7);
    }

    return 0;
}

E King Kog's Reception

题意：
国王的接待处会收到n个预约消息，第i个消息分为三种
1： + x y 表示第i个骑士在时刻 x 到来，国王处理这件事的持续时间为 y
2： - x 表示消息第 x 条预约作废
3：？ x 询问如果公主从时刻 x 到来，直到之前所有事情被处理完的等待时间
分析：
1. 这一道题的内容与国庆day7 C很类似，但是处理方法却不同。对于一个时间点来说，他有一个初始等待时间与最终结束时间之分。而他的最开始的等待时间明显就是他来的时间。于是我们考虑如何求得他的最终结束时间。
2. 一个点的最终结束时间是与他左边的预约有关的，因为只有左边的预约完成这个预约才会开始。也就是说我们的目的就是维护一个区间的最大的预约结束时间。
3. 维护方法：
  
  这一区间的预约结束时间就是 max (左区间的最终结束时间+右区间的预约处理时间，右区间的最终结束时间 )
  由此，就可以建立线段树维护区间的预约结束时间与处理预约的总时间，每次单点询问得到答案。
代码

//区间修改+单点查询 
#include<bits/stdc++.h>

#define ls now<<1
#define rs now<<1|1
#define ll long long

using namespace std;

const int N=1e6+10,M=1e6;

int q;ll ans;//加入的编号
int a[N],b[N];ll s[N<<2],w[N<<2];
char ins[5];

inline void upd(int now)
{
    s[now]=s[ls]+s[rs];
    w[now]=max(w[ls]+s[rs],w[rs]);
}

inline void build(int now,int l,int r)
{
    if(l==r)
    {
        w[now]=l;
        return ;
    }

    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    upd(now);
}

inline void add(int now,int l,int r,int x,int z)
{
    if(l==r)
    {
        w[now]+=z;s[now]+=z;
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,z);
    else add(rs,mid+1,r,x,z);

    upd(now);
}

inline ll find(int now,int l,int r,int x)
{
    if(r<=x)
    {
        ans=max(s[now]+ans,w[now]);
        return ans;
    }

    int mid=(l+r)>>1;
    find(ls,l,mid,x);
    if(x>mid) find(rs,mid+1,r,x);
    return ans;
}

int main()
{
    scanf("%d",&q);build(1,1,M);
    for (int i=1;i<=q;i++)
    {
        scanf("%s%d",ins,&a[i]);
        if(ins[0]=='+')
        {
            scanf("%d",&b[i]);
            add(1,1,M,a[i],b[i]);
        }
        else if(ins[0]=='?')
            ans=0,printf("%lld\n",find(1,1,M,a[i])-(ll)a[i]);
        else
            add(1,1,M,a[a[i]],-b[a[i]]);
    }

    return 0;
}

F Lazyland

题意：懒人国有n个乞丐，m份工作，每个人选择编号为 a [ i ] 的工作，然而有些工作没有人去做并且一份工作只能有一个人做。每一个乞丐都有一个 b [ i ] ，表示劝服其换一个工作的代价。问要使每一份工作有且只有一个人做的最小代价
分析：
1. 这是一个贪心问题。记录一下每一份工作的人数，以及还需要多少份工作(假设为 y )。那么这做这 y 份工作的人只能从那些参与了同一份工作的人中选。
代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+10;

int n,ned,k;ll ans;
int num[N],a[N],b[N];
bool vis[N];

struct nkl
{
    int id,per;
    bool operator < (const nkl &b)const
    {
        return per>b.per;
    }
    nkl (int x,int y):id(x),per(y){}
};
priority_queue<nkl>q;

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);num[a[i]]++;
        if(!vis[a[i]]) ned++,vis[a[i]]=1;
    }
    for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++)
        q.push(nkl(a[i],b[i]));

    ned=k-ned;
    while(ned)
    {
        nkl u=q.top();q.pop();
        if(num[u.id]==1) continue;
        num[u.id]--;ned--;
        ans+=u.per;
    }

    printf("%lld\n",ans);

    return 0;
}

H Archery Tournament

题意：现在有一个射箭比赛。由于靶场足够远，每一个靶子可以看做底面接触 y 轴的圆，像这样

一共有n个事件，分两种
1. 1 x y 表示出现了一个以(x,y)为圆心，y为半径的靶子
2. 2 x y 表示朝点(x,y)射，求会射中哪一个靶子，射中的靶子会消失。在任何时刻，靶子不会相交(不包括边缘接触)
分析
1. 第二次遇到这种题
2. 这样想，如果我朝(x，y)射，有哪些靶子可能被射中——圆心在 [ x - y , x + y ] ，也就是说，我需要维护一下圆心在 [ x - y , x + y ] 的圆。
3. 发现 x ， y 的范围较大，考虑动态开点线段树+vector。每当出现了一个靶子，便插入相应的节点中。如果要射箭，那就单点查询，对每一个节点中的圆都考虑一遍，如果找到了，就删除
代码：

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=2e5+10;
const int inf=1e9;

int n,cnt,rt,ans;
ll lx[N],ly[N];
int lc[N*30],rc[N*30];
vector<int>s[N*30];

inline void add(int &rt,int l,int r,int id,int x,int y)
{
    if(!rt) rt=++cnt;

    if(l>=x&&r<=y)
    {
        s[rt].push_back(id);
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) add(lc[rt],l,mid,id,x,y);
    if(mid<y) add(rc[rt],mid+1,r,id,x,y);
}

inline void upd(int rt,int l,int r,ll x,ll y)
{
    if(l>=x&&r<=y)
    {
        vector<int>tmp;int len=s[rt].size();
        for (int i=0;i<len;i++)
            if(s[rt][i]!=ans) tmp.push_back(s[rt][i]);
        s[rt]=tmp;
        return ;
    }

    int mid=(l+r)>>1;
    if(x<=mid) upd(lc[rt],l,mid,x,y);
    if(mid<y) upd(rc[rt],mid+1,r,x,y);
}

inline bool check(ll u,ll v,ll x,ll y)
{
    if((x-u)*(x-u)+(y-v)*(y-v)<v*v) return 1;
    return 0;
}

inline void find(int rt,int l,int r,ll x,ll y)
{
    if(!rt) return ;

    int len=s[rt].size();
    for (int i=0;i<len;i++)
        if(check(lx[s[rt][i]],ly[s[rt][i]],x,y))
            {ans=s[rt][i];break;}

    int mid=(l+r)>>1;
    if(x<=mid) find(lc[rt],l,mid,x,y);
    else find(rc[rt],mid+1,r,x,y);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int id;ll x,y;
        scanf("%d%lld%lld",&id,&x,&y);
        if(id==1)
        {
            lx[i]=x;ly[i]=y;
            add(rt,-inf,inf,i,x-y,x+y);
        }
        else
        {
            ans=-1;
            find(rt,-inf,inf,x,y);
            //抽象为单点查询
            printf("%d\n",ans);

            if(ans!=-1)
                upd(rt,-inf,inf,lx[ans]-ly[ans],lx[ans]+ly[ans]);
        }
    }

    return 0;
}

I Box

题意：能否用一个w*h的纸板制得大小为 a * b * c 的纸盒
分析：
1. 一开始我直接求出不同的剪切方法能否构成 a * b * c 的纸盒，但是情况之多，复杂之极
2. 换个方向，考虑这个 a * b * c 的纸盒能否以某种平铺方式放在这个纸板上面。发现题目下面给出了十一种平铺方式，没用他还给你放这里？于是我去把他列了下来(QwQ，中途还爆了)
  
  发现这些图形中的平铺下来的宽与长只有三种不同的形式,那就直接分类讨论就行
代码：

#include<bits/stdc++.h>

using namespace std;

int a,b,c,w,h;
int k,p;

inline bool check(int x,int y,int z)
{
    k=x+2*z,p=2*z+2*y;
    if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
    k=x+z,p=x+z+3*y;
    if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
    k=x+y+z,p=x+z+2*y;
    if((k<=w&&p<=h)||(k<=h&&p<=w)) return 1;
    return 0;
}

int main()
{
    scanf("%d%d%d%d%d",&a,&b,&c,&w,&h);

    if(check(a,b,c)||check(a,c,b)||check(b,a,c)||check(b,c,a)||check(c,a,b)||check(c,b,a)) puts("Yes");
    else puts("No");

    return 0;
}

J Connections

题意：有一个n个点m条有向边的强联通图，问能否删去(m-2n)条边(即只剩下2n条边)使得剩下的图仍然强联通
分析：
1. 既然涉及到联通图，那就试试从tarjan的方向考虑。
2. 首先回忆一下tarjan，在使用它的时候会形成一棵树，因为越先遍历到说明他的dfn越小。如果一条边能更新到一个点，说明他就是有用的。如果一条边能够使一个环闭合，他也是有用的。
  
  于是需要在跑tarjan的过程中找到这些有用边
- 代码：

/*
    在使用tarjan时会形成一棵搜索树,

越先遍历到说明dfn的值越小，因为节点

要相互到达，那么当找到一个环的时候

， 说明当前节点能到达下面所有的点，

那么这一条环的边也是需要的 
*/
#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int n,m,tot,cnt,tp;
int h[N],nex[N],ver[N],re[N];
int dfn[N],low[N],stk[N];
bool vis[N],yep[N];

inline void add(int x,int y)
{
    nex[tot]=h[x];
    ver[tot]=y;re[tot]=x;
    h[x]=tot++;
}

inline void tarjan(int u)
{
    dfn[u]=low[u]=++cnt;
    stk[++tp]=u;vis[u]=1;

    int rem=-1;//记录环边
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];

        if(!dfn[j])
        {
            tarjan(j);yep[i]=1;
            low[u]=min(low[u],low[j]);
        }
        else if(vis[j])
        {
            if(low[j]<low[u]) rem=i;
            low[u]=min(low[u],dfn[j]);
        }
    }

    if(rem!=-1) yep[rem]=1;
    if(low[u]==dfn[u])
    {
        int y;
        do
        {
            y=stk[tp--];
            vis[y]=1;
        }while(y!=u);
    }
}

inline void Pre()
{
    cnt=tot=0;
    memset(h,-1,sizeof(h));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(yep,0,sizeof(yep));
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        Pre();
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            add(x,y);
        }

        tarjan(1);

        int rem=m;
        for (int i=0;i<tot;i++)
        {
            if(rem<=2*n) break;
            if(!yep[i])
            {
                rem--;
                printf("%d %d\n",re[i],ver[i]);
            }
        }
    }

    return 0;
}