A

题意

给一个长为n的数组，每次可以对其中某个数做+1或-1的操作。求最小的操作次数，使得可以从数组中选出三个相同的数。

思路

很容易可以想到选三个最接近的数然后操作。也可以很容易证明，对于a<b<c，一定是将a，c操作到b距离最短。

所以排序后遍历中间的b，然后求a与c的差距即可。

代码

#include<bits/stdc++.h>
 
using namespace std;
 
int a[305];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,minn=2e9+7;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=1;i<n-1;i++)
            minn=min(minn,a[i+1]-a[i-1]);
        printf("%d\n",minn);
    }
}

B

题意

乱七八糟一大堆，最后只要找规律构造就行了。

思路

找规律

代码

#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        printf("1\n");
        for(int i=2;i<=n;i++)
        {
            printf("1 ");
            for(int j=0;j<i-2;j++)
                printf("0 ");
            printf("1\n");
        }
    }
}

C

题意

给一个包含1-n整数的集合S，每次可以花费代价k进行一次操作：选择S中k的最小倍数，然后移除该数。

然后给一个S的子集T，求通过上述操作把S变成T的最小代价。

思路

思路很明显是要贪心的。对于一个待移除的数A，一定是选择他的最小因子来移除最优。如果从因子k的角度考虑，那么一个更小的k能移除的数越多越好。所以可以想到从1-n遍历因子，尽可能移除更多的数。然后很容易可以想到，只要移除到一个不需要移除的数，那么就可以停止了。然后实现一下，已经移除的数打标记，不计入答案就好了。总体复杂度为n+n/2+n/3+....+n/(n-1)+1，可以算一下时间复杂度大约为O(n*logn)

代码

#include<bits/stdc++.h>
 
using namespace std;
using ll=long long;
 
const int MAX=1e6+6;
 
char s[MAX];
bool vis[MAX];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        ll sum=0;
        scanf("%d%s",&n,s+1);
        for(int i=1;i<=n;i++)
            vis[i]=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='0')
            {
                if(!vis[i])
                    sum+=i,vis[i]=1;
                for(int j=i+i;j<=n;j+=i)
                {
                    if(s[j]=='1')break;
                    if(!vis[j])
                        sum+=i,vis[j]=1;
                }
            }
        }
        printf("%I64d\n",sum);
    }
}

D

题意

给一个数组a，初始位于i位置，初始分数为ai，每次可以任意左右移动，每移动到一个新的位置j，就将分数加上aj，如果分数为负，则失败，如果最后可以移动到数组头或尾且保持分数非负，则获胜。求最后能否获胜。

思路

如果某一段和为非负，那么一定可以移动到它的边界，将和吸收掉，分数一定不降。但是过程中要保持分数非负，所以要想吸收某一段，当前分数必须大于abs（该段的最小前缀和）。如果左右两侧都不能吸收了，那一定会失败，如果存在一段可以吸收的，那吸收一定保持分数不降。所以只需要从起点处预处理出左右分段，然后左右尝试能否吸收就能得出答案了。实现可以用队列加pair方便一点。

代码

#include<bits/stdc++.h>
 
using namespace std;
using ll=long long;
using pll=pair<ll,ll>;
 
const int MAX=2e5+5;
 
int a[MAX];
 
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int L=k,R=k;
        queue<pll> QL,QR;
        while(!QL.empty())QL.pop();
        while(!QR.empty())QR.pop();
        while(R<n)
        {
            int r=R+1;
            ll sumr=a[r],minr=a[r];
            while(sumr<0&&r<n)
            {
                r++;
                sumr+=a[r];
                minr=min(minr,sumr);
            }
            QR.push({sumr,-minr});
            R=r;
        }
        while(L>1)
        {
            int l=L-1;
            ll suml=a[l],minl=a[l];
            while(suml<0&&l>1)
            {
                l--;
                suml+=a[l];
                minl=min(minl,suml);
            }
            QL.push({suml,-minl});
            L=l;
        }
        ll cur=a[k];
        QL.push({0,0});
        QR.push({0,0});
        while(!QL.empty()&&!QR.empty())
        {
            int fail=0;
            if(cur<0)break;
            pll p=QL.front();
            if(cur>=p.second)
            {
                QL.pop();
                cur+=p.first;
            }
            else fail++;
            p=QR.front();
            if(cur>=p.second)
            {
                QR.pop();
                cur+=p.first;
            }
            else fail++;
            if(fail==2)break;
        }
        if(QL.empty()||QR.empty())printf("YES\n");
        else printf("NO\n");
    }
}