2021年度训练联盟热身训练赛第五场 F,G,H,I

比赛链接
https://ac.nowcoder.com/acm/contest/13926

F.Group Project

首先肯定可以划分成两个班级的，且班级内不会有冲突。那么肯定优先选择班级内配对，最后如果每个班都剩一个，且此时 cnta*cntb!=m，那么这两个人能配对，答案+1(cnta，cntb代表每个班级的人数，如果相乘不等于m，那么肯定存在当前班级的一个人可以和另一个班级的一个人配对)。然后用并查集实现即可。
这里把for循环换成while(m–)就过不了，

# include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int fa[N];
int enemy[N];
int find_fa(int x)
{
    if(x==fa[x])
        return x;
    else
        return fa[x]=find_fa(fa[x]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(enemy[x])
        {
            if(find_fa(enemy[x])!=find_fa(y))
                fa[fa[y]]=fa[enemy[x]];
        }
        else
            enemy[x]=y;
        if(enemy[y])
        {
            if(find_fa(enemy[y])!=find_fa(x))
                fa[fa[x]]=fa[enemy[y]];
        }
        else
            enemy[y]=x;
    }
    int root=find_fa(1);
    int cnta=0;
    int cntb=0;
    for(int i=1;i<=n;++i)
    {
        if(fa[i]==root)
            cnta++;
        else
            cntb++;
    }
    if(cnta%2==1&&cntb%2==1&&cnta*cntb!=m)
        printf("%d\n",cnta/2+cntb/2+1);
    else
        printf("%d\n",cnta/2+cntb/2);
}

G.Human Pyramid

思维+dp。strong的要不站在最底下，要不下面要有两个strong支撑。

我们换个方向看(按斜线方向看)，strong要不是连续的，要不就是单独在最下面。所以我们可以按斜线方向进行dp。dp[i][j][k]表示第i行至少有连续
k个strong，且前i行有j个strong的方案数。（这里的行数是看斜线方向）
状态转移方程如下：
dp[i][j][k]=dp[i-1][j-k][max(0,k-1)]+dp[i][j][k+1]
解释如下：
如果 i 行用k个strong，那么可由前一行 i-1行 转移到，那么前 i-1 行肯定是用 j-k个strong且第 i 行至少用 k-1个strong。(当然k=0时，前面也得至少用0个，所以和0取个max)
如果 i 行用大于 k 个strong，那么可由至少用 k+1 个strong转移到。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll dp[105][5305][105]; //dp[i][j][k]表示第i行至少选k个strong,且一共选j个strong的方案数
int main()
{
    int h,s;
    cin>>h>>s;
    dp[0][0][0]=1;
    for(int i=1;i<=h;++i)
        for(int j=0;j<=s;++j)
            for(int k=min(i,j);k>=0;k--)
                dp[i][j][k]=(dp[i][j][k+1]+dp[i-1][j-k][max(0,k-1)])%mod;
    cout<<dp[h][s][0]<<endl;
    return 0;
}

H.In-place Sorting

贪心的想法，如果当前第i个数a_i已经大于等于前面的了，要让他尽可能小，这样后面才能更容易满足条件。每次先把6全部改成9，看此时是否大于等于前面，如果不满足输出impossible，否则从高位向后依次，把9改为6，看是否满足，如果不满足改回9，如果满足继续向后重复此操作。因为如果当前能把9改为6，那么之后肯定不会出现情况，让前面的6重新改回9。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
string a[N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=0;a[1][i];++i)
    {
        if(a[1][i]=='9')
            a[1][i]='6';
    }
    for(int i=2;i<=n;++i)
    {
        if(a[i].size()<a[i-1].size())
        {
            puts("impossible");
            return 0;
        }
        if(a[i].size()>a[i-1].size())
        {
            for(int j=0;a[i][j];++j)
                if(a[i][j]=='9')
                    a[i][j]='6';
            continue;
        }
        for(int j=0;a[i][j];++j)
            if(a[i][j]=='6')
                a[i][j]='9';
        if(a[i]<a[i-1])
        {
            puts("impossible");
            return 0;
        }
        for(int j=0;a[i][j];++j)
        {
            if(a[i][j]=='9')
                a[i][j]='6';
            if(a[i]>=a[i-1])
                continue;
            a[i][j]='9';
        }
    }
    puts("possible");
    for(int i=1;i<=n;++i)
        cout<<a[i]<<endl;
    return 0;
}

I.Jam-packed

很简单的二分，首先想到最小数量具有单调性（因为如果当前情况满足的话，比当前情况小的肯定也满足check条件），因为箱子是无限个，所以最小数量多小都可以，所以 l=1，而最大数量也不可能超过上限 r=k。然后对于每个mid, 判断是否满足条件(先按每箱放mid个，那么最后会剩n%mid个，所以要将最后的n%mid个放到前面n/mid个箱子上，即判断 n%mid是否小于等于 (k-mid)*(n/mid)，如果满足就可以，不满足就不可以）PS:或者直接公式 n/(n/k + 1)

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
__int128 n,k;
bool check(__int128 x)
{
    if(n%x==0)
        return 1;
    __int128 res=n%x;
    __int128 num=n/x;
    return res<=num*(k-x);
}
int main()
{
    n=read();
    k=read();
    __int128 l=1;
    __int128 r=k;
    __int128 mid;
    __int128 ans=0;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid))
        {
            ans=max(ans,mid);
            l=mid+1;
        }
        else
            r=mid-1;
    }
    print(ans);
}