ARC163

A

显然划分两次最优,直接枚举即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2005;
int t;
int n;
char s[MAXN];
int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        scanf("%s",s+1);
        // for(int i=1;i<=n;i++)
        // {
        //     printf("%c",s[i]);
        // }
        // printf("\n");
        bool f=0;
        for(int i=2;i<=n;i++)
        {
            string S,T;
            S.clear();
            T.clear();
            for(int j=1;j<i;j++)
            {
                S+=s[j];
            }
            for(int j=i;j<=n;j++)
            {
                T+=s[j];
            }
            // cout<<T<<endl;
            // cout<<S<<' '<<T<<endl;
            if(S<T)
            {
                f=1;
            }
        }
        if(f)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
}

B

直接枚举\(a_1\),然后二分找到最小\(a_2\)的位置,线段树维护一下

两个\(log\)有点卡常

#include<bits/stdc++.h>
#define ls Tree[p].lc
#define rs Tree[p].rc
using namespace std;
const int MAXN=2e5+5;
int n;
int m;
int A[MAXN];
struct Seg{
    int date,lc,rc;
}Tree[MAXN*30];
int rt;
int cnt_node;
void Insert(int &p,int l,int r,int k)
{
    if(!p)
    {
        p=++cnt_node;
    }
    Tree[p].date++;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid){
        Insert(ls,l,mid,k);
    }
    else
    {
        Insert(rs,mid+1,r,k);
    }
}
int Query(int p,int l,int r,int ql,int qr)
{
    if(!p)
    {
        return 0;
    }
    if(l>=ql&&r<=qr)
    {
        return Tree[p].date;
    }
    int Res=0;
    int mid=(l+r)>>1;
    if(ql<=mid)
    {
        Res+=Query(ls,l,mid,ql,qr);
    }
    if(qr>mid)
    {
        Res+=Query(rs,mid+1,r,ql,qr);
    }
    return Res;
}

int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
    }
    for(int i=3;i<=n;i++)
    {
        Insert(rt,1,1e9,A[i]);
    }
    int Res=2e9;
    for(int i=1;i<=n;i++)
    {
        int l=A[i];
        int r=1e9;
        int Key=-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(Query(rt,1,1e9,A[i],mid)>=m)
            {
                r=mid-1;
                Key=mid;
            }
            else
            {
                l=mid+1;
            }
        }
        if(Key!=-1)
        {
            int Tot=max(0,A[1]-A[i])+max(0,Key-A[2]);
            Res=min(Res,Tot);
        }
    }
    printf("%d",Res);

}

C

首先有\(\dfrac{1}{n(n+1)}=\dfrac{1}{n}-\dfrac{1}{n+1}\)

有个比较显的思路,考虑\(a_i=\dfrac{1}{i(i+1)},a_n=\dfrac{1}{n}\)

唯一的问题在于\(n\)在之前被访问过

实际上直接整体\(\times\dfrac{1}{2}\)再用个\(\dfrac{1}{2}\)即可

#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
int T;
int n;
int Vis[MAXN*MAXN];
int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<n;i++)
        {
            Vis[i*(i+1)]=1;
        }
        if(n==2)
        {
            printf("No\n");
        }
        else if(!Vis[n])
        {
            printf("Yes\n");
            for(int i=1;i<n;i++)
            {
                printf("%d ",i*(i+1));
            }
            printf("%d\n",n);
        }
        else
        {
            printf("Yes\n2 ");
            for(int i=1;i<n-1;i++)
            {
                printf("%d ",2*i*(i+1));
            }
            printf("%d\n",2*(n-1));
        }
        for(int i=1;i<n;i++)
        {
            Vis[i*(i+1)]=0;
        }
    }
}

D

竞赛图有个性质是缩点后拓扑序已经确定了

考虑把拓扑序拉出来,\(s_1,s_2,s_3,s_4....s_k\)

对于\(s_i,s_{i+1}\),我们可以将\([1,i]\)化分为一个点集\(A\),\([i+1,k]\)划分成另一个点集\(B\),满足两点集之间的边都是\(A\rightarrow B\)

可以发现任意合法的点集划分对应这一个分割点\(i\)

于是直接考虑对点集划分计数,设\(dp_{i,j,k}\)表示前\(i+j\)个点,有\(i\)个点分到\(A\),\(j\)个点分到\(B\)其中有\(k\)对小指大的方案

转移就直接枚举\(A/B\)中的连边情况,注意一下\(i+j\)归到\(B\)时\(k\)要\(+i\)

// LUOGU_RID: 120168019
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
const int MAXN=55;
int n;
int m;
int dp[MAXN][MAXN][MAXN*MAXN];
int C[MAXN*MAXN][MAXN*MAXN];
int main()
{
    // freopen("date.in","r",stdin);
    // freopen("date.out","w",stdout);
    scanf("%d %d",&n,&m);
    C[0][0]=1;
    for(int i=1;i<=n*n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            C[i][j]=((long long)C[i-1][j]+C[i-1][j-1])%MOD;
        }
    }
    dp[0][0][0]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;(i+j)<=n;j++)
        {
            for(int k=0;k<=m;k++)
            {
                if(!dp[i][j][k])
                {   
                    continue;
                }
                for(int t=0;t<=i;t++)
                {
                    dp[i+1][j][k+t]=((long long)dp[i+1][j][k+t]+((long long)dp[i][j][k]*C[i][t])%MOD)%MOD;
                }
                for(int t=0;t<=j;t++)
                {
                    dp[i][j+1][k+t+i]=((long long)dp[i][j+1][k+t+i]+((long long)dp[i][j][k]*C[j][t])%MOD)%MOD;
                }
            }
        }
    }
    int Res=(MOD-C[(n*(n-1))/2][m]);
    for(int i=0;i<=n;i++)
    {
        Res=((long long)Res+dp[i][n-i][m])%MOD;
    }
    printf("%d\n",Res);
}