====== Codeforces Round #643 (Div. 2) ======

===== A. Sequence with Digits =====

大致题意：$a_{n+1}=a_n+\min \{D_{a_n}\}+max\{D_{a_n}\}$，$D_n$是n的各位数字组成的集合。求$a_n$。

盲猜多求几个就会带有数字0

代码:

<code cpp>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    auto f=[](long long now){
        vector<long long> vec;
    while (now!=0)
    {
        vec.push_back(now%10);
        now/=10;
    }
    return vec;
    }; 
    auto minn=[&](long long now)
    {
        auto &&vec=f(now);
        return *min_element(vec.begin(),vec.end());
        
    };
    auto maxn=[&](long long now)
    {
        auto &&vec=f(now);
        return *max_element(vec.begin(),vec.end());
    };
    while (T--)
    {
        long long a1,k;
        scanf("%lld%lld",&a1,&k);
        long long ans=a1;
        for (int i=2;i<=k&&minn(ans);i++)
            ans=ans+minn(ans)*maxn(ans);
        printf("%lld\n",ans);
    }
    return 0;
}
</code>
===== B. Young Explorers =====

排序，贪心即可

代码:

<code cpp>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
int a[200001];
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        sort(a+1,a+n+1,[](int a,int b){
            return a>b;
        });
        stack<int> s;
        for (int i=1;i<=n;i++)
                s.push(a[i]);
        int ans=0;
        while (s.size()>0)
        {
            int top=s.top();
            int i;
            for (i=1;i<=top&&s.size()>0;i++)
            {
            s.pop();
            if (i!=top&&s.size()>0)
            top=max(top,s.top());
            }
            if (i==top+1)
            ans++;
        }
        printf("%d\n",ans);
    }
}
</code>
===== C. Count Triangles =====

题意：求集合$\{(x,y,z)|a\le x\le b\le y\le c\le z\le d且x+y<z\}$中元素的个数

枚举x，然后计算即可

<code cpp>
#include <stdio.h>
#include <iostream>
#include <algorithm> 
using namespace std;
int main()
{
    long long a,b,c,d;
    long long ans=0;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    for (long long i=a;i<=b;i++)
    {
        long long mid=c;
        if (d-i+1<=c)
        {
            mid=d-i;
            ans+=(long long)(c-max((d-i+1),b)+1)*(d-c+1);
            if (d-i<b)
            continue;
        }
        long long l=max(b,c-i+1);
        ans+=(mid-l+1)*(i-c)+(mid+l)*(mid-l+1)/2;
    }
    printf("%lld",ans);
}
</code>
===== D. Game With Array =====

构造题，前面n-1个全是1

代码：

<code cpp>
#include <stdio.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    if (m<2*n)
    {
    printf("no");
    return 0;
    }
    printf("yes\n");
    for (int i=1;i<n;i++)
    printf("1 ");
    printf("%d\n%d",m-n+1,n);
}
</code>