A. DIY Wooden Ladder

先找出数组中最大的两个元素a和b，b是第二大的数。答案是min(b-1，n-2)

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int arr[N];
#define min(a,b) ((a)<(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
    freopen("in.txt","r",stdin);
#endif
    int t;
    cin>>t;
    for(int ti=0; ti<t; ti++)
    {
        int n;
        cin>>n;
        int a=-1,b=-1;
        for(int i=0; i<n; i++)
        {
            cin>>arr[i];
            if(arr[i]>a)
            {
                b=a;
                a= arr[i];
            }
            else if(arr[i]>b)
            {
                b=arr[i];
            }
        }
        int ret = min(b-1,n-2);
        if(ret<0)
            ret = 0;
        cout<<ret<<endl;
    }
    return 0;
}

B. Pillars

首先找出最大的元素，目标是将所有盘子移到处。如果对于，那么盘子将无法移到柱子。同理如果也会导致所有盘子无法移到处。找到最大元素后向左向右遍历一遍即可。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2*100010;
int n;
int arr[N];
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
bool solve()
{
    int ti = -1;
    int t = -1;
    for(int i=0;i<n;i++)
    {
        if(arr[i] > t)
        {
            t = arr[i];
            ti = i;
        }
    }
    int a = t;
    for(int i=ti-1;i>=0;i--)
    {
        int x = arr[i];
        if(x>=a)
        {
            return false;
        }
        a = min(x, a);
    }
    a = t;
    for(int i=ti+1;i<n;i++)
    {
        int x = arr[i];
        if(x>=a)
        {
            return false;
        }
        a=min(x,a);
    }
    return true;
 
}
int main()
{
    #ifdef CODEBLOCKS
    freopen("in.txt","r",stdin);
    #endif
    while(cin>>n)
    {
 
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
        }
 
        if(solve())
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
 
    return 0;
}

C. Array Splitting

对于分好后的第个连续子数组，。

当k=1时，所求答案为。

当k=2时，假设分区是1~i，i+1~n，则答案是

以此类推，答案应该为减去k-1个最大的

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 3*100010;
int arr[N];
int q[N];
int n,k;
 
#define min(a,b) ((a)<(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
    freopen("in.txt","r",stdin);
#endif
    while(cin>>n>>k)
    {
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            if(i>0)
            {
                q[i-1]=arr[i]-arr[i-1];
            }
        }
        sort(q,q+n-1);
        long long sum = 0;
        for(int i=0;i<n-k;i++)
        {
            sum+=q[i];
        }
        cout<<sum<<endl;
    }
    return 0;
}

D. Yet Another Subarray Problem

设为子数组以第个元素结尾所能得到的最佳答案。
分两种情况。考虑j>i-m，j~i的子数组的花费为best[i-m]+ \Sigma_{t=i-m+1}^i a_t - k。best[i]取两者答案的最小值。算法时间复杂度为O(nm)

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int N = 3*100010;
int arr[N];
long long best[N];
int n,m,k;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
int main()
{
#ifdef CODEBLOCKS
    freopen("in.txt","r",stdin);
#endif
    while(cin>>n>>m>>k)
    {
        long long ret = 0;
        for(int i=0;i<n;i++)
        {
            cin>>arr[i];
            best[i] = max(0, arr[i]-k);
            ret = max(ret,best[i]);
        }

        for(int i=1;i<n;i++)
        {
            long long t = 0;
            for(int j=0;j<m &&i-j>= 0;j++)
            {
                t += arr[i-j];
                best[i] = max(best[i], t-k);
            }
            if(i>=m)
            {
                best[i] = max(best[i], t-k+best[i-m]);
            }
            ret = max(best[i], ret);
        }
        cout<<ret<<endl;
    }
    return 0;
}

E. Culture

对所有数据以排序。
设，其中表示以所有套娃构造所能组成的最小extraspace，表示以所有套娃构造所能组成的满足条件的套娃数目。

倒序遍历数据，对于，找到恰好大于的位置，那么对于套娃应该能装在pos-n中的某些套娃中，其extraspace应该等于。

那么对于的计算，分三种情况。
a. 时，说明第i个套娃无法与其他套娃构造成最小extraspace，不纳入计算，

b. 时，第i个套娃应该可以构造出个满足条件的套娃。

c. 时，

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int n;
const int N = 2*1e5+10;
pair<int, int> p[N];
pair<int, long long> dp[N];
const int mod = 1e9+7;
int main()
{
#ifdef CODEBLOCKS
    freopen("in.txt", "r", stdin);
#endif // CODEBLOCKS
    while(cin>>n)
    {
        int min_out = 0x7fffffff;
        for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            p[i] = make_pair(b,a);
        }
        sort(p, p+n);
        for(int i=n-1;i>=0;i--)
        {
            int in = p[i].first;
            int out = p[i].second;
            auto iter = lower_bound(p, p+n, make_pair(out,0));
            int space, cnt;
            if((iter-p) == n)
            {
                space = in;
                cnt = 1;
            }
            else
            {
                space = dp[iter - p].first - out + in;
                cnt = dp[iter-p].second;
            }
 
            if(i<n-1)
            {
                if(space > dp[i+1].first)
                {
                    space = dp[i+1].first;
                    cnt = dp[i+1].second;
                }
                else if(space == dp[i+1].first)
                {
                    cnt = (cnt + dp[i+1].second)%mod;
                }
            }
            dp[i] = make_pair(space, cnt);
        }
        cout<<dp[0].second<<endl;
    }
    return 0;
}