C2020寒假训练赛2

信息学——模拟赛

C2020寒假练习赛2 & G2020寒假练习赛1

T1. BERRY PICKING

由于自己要拿的最多，则$Elsie$得拿的最少。

考虑$Elsie$拿的篮子中最少的一个为$m$

则最优情况为她所拿的所有篮子均为$m$

由此，考虑枚举共有$l$个篮子为$m$

则有两种特殊情况。

$1^o$ $l<\frac{k}{2}$:

不满足条件，$break$。

$2^o$ $l>=k$:

此时答案为$\frac{mk}{2}$

$3^o$ $default$:

除这两种情况外，考虑每颗果树上剩余的果子

发现为$b_i \bmod m$

所以我们可以对$b$数组按$b_i \bmod m$为关键字排序。

则答案为：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k;
struct node{
    int x,mod;
}a[1005];
int maxx,ans;
inline bool operator <(node x,node y)
{
    return x.mod>y.mod;
}
int main(){
    n=read(),k=read();
    for (register int i=1;i<=n;++i)
        a[i].x=read(),maxx=max(maxx,a[i].x);
    for (register int i=1;i<=maxx;++i)
        {
        int l=0;
        for (register int j=1;j<=n;++j)
            l+=a[j].x/i,a[j].mod=a[j].x%i;
        if (l<(k>>1))
           break;
        if (l>=k)
           {
           ans=max(ans,i*(k>>1));
           continue;           
           }
        sort(a+1,a+n+1);
        int cnt=i*(l-(k>>1));
        for (register int j=1;j<=k-l&&j<=n;++j)
            cnt+=a[j].mod;  
        ans=max(ans,cnt);
        }
    printf("%d",ans);
    return 0;
}

T2. LOAN REPAYMENT

首先不难想到二分答案$x$，那么本题的困难便是$check$部分。

直接模拟时间复杂度肯定是$O(k)$的，无法通过。

观察发现此形式为$\lfloor{\frac{i}{n}}\rfloor$，所以考虑类似整除分块的做法。

则可以用根号复杂度解决$check$。

至于整除分块是啥请看G2020寒假集训Day4的整除分块部分。

//The code is from dxbdly
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,k,m;
inline bool check(int x)
{
    int tot=0,day=k;
    while (tot<n&&day>0)
          {
          int cnt=(n-tot)/x;
          if (cnt<m)
             return (n-tot+m-1)/m<=day;
          int num=min(day,(n-cnt*x-tot)/cnt+1);
          tot+=cnt*num,day-=num;
          }
    return tot>=n;
}
inline void erfen()
{
    int l=1,r=1e12;
    while (l<r)
          {
          int mid=(l+r+1)>>1;
          if (check(mid))
             l=mid;
          else
             r=mid-1;
          }
    printf("%lld",l);
}
signed main(){
    n=read(),k=read(),m=read();
    erfen();
    return 0;
}

T3. WORMHOLE SORT

将位置抽象成点，虫洞抽象成边，则可构建一张图。

则题目要求选一些边使所有$i$与$p_i$联通。

且所选边边权的最小值最大。

由于需要最小值最大，我们先将所有边按边权从大到小排序。

然后不断选边使得所有$i$与$p_i$联通。

至于怎么维护联通，自然是用并查集了。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int x,y,w;
}a[100005];
int father[100005],p[100005],now,ans;
inline int Find(int x)
{
    if (father[x]!=x)
       return father[x]=Find(father[x]);
    return father[x];
}
inline void unnion(int f1,int f2)
{
    father[f2]=f1;
}
inline bool operator <(node x,node y)
{
    return x.w>y.w;
}
inline bool check()
{
    while (Find(now)==Find(p[now]))
          {
          now++;
          if (now>n)
             {
             printf("%d",ans);
             return 0;
             }
          }
    return 1;
}
int main(){
    n=read(),m=read();
    for (register int i=1;i<=n;++i)
        p[i]=read(),father[i]=i;
    for (register int i=1;i<=m;++i)
        a[i].x=read(),a[i].y=read(),a[i].w=read();
    sort(a+1,a+m+1);
    now=1,ans=-1;
    for (register int i=1;i<=m;++i)
        {
        if (!check())
           return 0;
        int f1=Find(a[i].x),f2=Find(a[i].y);
        if (f1!=f2)
           unnion(f1,f2),ans=a[i].w;
        }
    printf("%d",ans);
    return 0;
}