BestCoder 2nd Anniversary A,B,C解题报告

【A题】

【题意】给一个数字构成的字符串，可以任意交换这个字符串里面的任意位置！在交换之后，要把这个字符串拆成两个数，使得它们的和，最大，并且输出这个拆掉之后的字符串！

【解题方法】水题，先记录 $0 - 9$ 这 $10$ 个数字分别有多少个。不难看出，最小的一个存在的数字和其余的数字降序排列的相加就是答案，但是最小的那个数字不能是 $0$ ，因为题面上说明是正整数。将这两个数加起来时，注意处理进位问题。考虑无解的情况，即一串数字中仅存在 $1$ 个非 $0$ 数字或不存在。

【AC code】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
char s[20000000];
int a[10];
string ans;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof(a));
        ans="";
        scanf("%s",s);
        int len=strlen(s);
        int p=0;
        for(int i=0; i<len; i++)
        {
            if(s[i]!='0') p++;
        }
        if(p<2)
        {
            puts("Uncertain");
            continue;
        }
        for(int i=0; i<len; i++)
        {
            a[s[i]-'0']++;
        }
        int x=0;
        ans="";
        for(int i=1; i<=9; i++)
        {
            if(a[i])
            {
                x=i;
                a[i]--;
                break;
            }
        }
        for(int i=9; i>=0; i--)
        {
            if(a[i])
            {
                while(a[i])
                {
                    ans+=char(i+'0');
                    a[i]--;
                }
            }
        }
        int l=ans.size();
        int zz=x;
        //cout<<ans<<endl;
        bool flag=0;
        for(int i=l-1; i>=0; i--)
        {
            if(ans[i]-'0'+zz>=10)
            {
                ans[i]=(ans[i]-'0'+zz-10)+'0';
                flag=1;
                zz=1;
            }
            else
            {
                ans[i]=(ans[i]-'0'+zz)+'0';
                zz=0;
            }
        }
        if(flag) printf("%c",ans[0]-'0'+zz+'0');
        for(int i=0; i<=l-1; i++)
        {
            printf("%c",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

【B】

【题意】给了n个数B[i]和n个数C[i]。B[i]代表在【1--i】里面的最小值为B【i】，C【i】代表在【1--i】里面的最大值为C【i】，现在要求一个1--n的排列，使得这个排列满足上述条件，问有多少个这样的排列？

【解题方法】规律题！

可以发现 $A_1 = B_1 = C_1$ ，所以如果 $B_1 \neq C_1$ 无解。

进一步，我们发现如果 $B_i < B_{i-1}$ ， $A_i = B_i$ ；如果 $C_i > C_{i-1}$ ， $A_i = C_i$ 。但是如果 $B_i < B_{i-1}$ 和 $C_i > C_{i-1}$ 同时满足，就会产生冲突导致无解。

考虑 $B_i = B_{i-1}$ 和 $C_i = C_{i-1}$ 同时满足的情况，此时应有 $A_i \in (B_i,C_i)$ 且 $A_i$ 没有在之前使用过。因为 $B_i,C_i)$ 是不断变大的，我们只需维护一下这个区间内有多少值已经被使用过了，用乘法原理统计答案即可。注意到如果某时刻 $A_i$ 没有值可以使用，也会导致无解。

时间复杂度 $O (T n)$ 。

【AC代码】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const int maxn=1e5+5;
int B[maxn],C[maxn];
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) scanf("%d",&B[i]);
        for(int i=1; i<=n; i++) scanf("%d",&C[i]);
        if(B[1]!=C[1])
        {
            puts("0");
            continue;
        }
        ll ans=1;
        for(int i=2; i<=n; i++)
        {
            if(B[i]<B[i-1]&&C[i]>C[i-1])
            {
                ans=0;
                break;
            }
            if(B[i]!=B[i-1]&&C[i]!=C[i-1])
            {
                ans=0;
                break;
            }
            if(B[i]==B[i-1]&&C[i]==C[i-1])
            {
                ans=ans*max(C[i]-B[i]+1-(i-1),0)%mod;
            }
        }
        printf("%I64d\n",ans);
    }
}

【Ｃ】

【题意】

首先给出n,L,R，表示地上现在有n根树枝，你手里现有[L,R]长度的树枝各一根要求选择一根树枝，不能与地上任意两根树枝构成三角形，问有多少种选法。

【解题方法】

考虑三角形三条边 $a, b, c$ $\ge b)$ 的关系 $a - b < c, a + b > c$ ，即 $\in (a-b,a+b)$ 。

令加入的边为 $c$ ，枚举所有边作为 $a$ 的情况。对于所有可行的 $b$ ，显然与 $a$ 相差最小的可以让 $(a - b, a + b)$ 覆盖范围最大，所以可以贪心地选择不大于 $a$ 的最大的 $b$ 。

于是我们可以先将边按长度排序，然后 $a_i$ 和 $a_{i + 1}$ 建一条线段。线段并是不合法的部分。

将所有线段按左端点排序，按序扫描一遍，过程中统计答案即可。

时间复杂度 $O(Tn\ \log n)$ 。

【AC code】

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
ll a[maxn];
pair<ll,ll>p[maxn];
ll ans;
ll L,R;
int n;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%I64d%I64d",&n,&L,&R);
        for(int i=1; i<=n; i++) scanf("%I64d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1; i<n; i++)
        {
            p[i].first=a[i+1]-a[i];
            p[i].second=a[i+1]+a[i];
        }
        sort(p+1,p+n);
        ll mx=L;
        ll ans=0;
        for(int i=1; i<n&&p[i].first<=R; i++)
        {
            if(p[i].first>=mx) ans+=(p[i].first-mx+1);
            mx=max(mx,p[i].second);
        }
        ans+=max((ll)0,R+1-mx);
        printf("%I64d\n",ans);
    }
}