526互联

AtCoder Grand Contest 021

发布时间 2023-09-27 19:06:23作者: Zhou_JK

A - Digit Sum 2

要么是 \(n\) 要么是 \(n\) 的第一位后面加上若干个 \(9\)。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n;
int calc(long long x)
{
    if(x==0) return 0;
    int sum=0;
    while(x)
        sum+=x%10,x/=10;
    return sum;
}
int count(long long x)
{
    if(x==0) return 1;
    int cnt=0;
    while(x)
        cnt++,x/=10;
    return cnt;
}
int main()
{
    scanf("%lld",&n);
    int len=count(n);
    if(len==1)
    {
        printf("%lld",n);
        return 0;
    }
    long long pw=1;
    for(int i=1;i<len;i++)
        pw*=10;
    int ans=max(calc(n),calc(n/pw*pw-1));
    printf("%d",ans);
    return 0;
}

B - Holes

因为范围很大，所有的点所形成的区域在整个平面中非常微不足道。

凸包内的点可以看做概率为 \(0\)，凸包上的点算下其所占圆心角比例即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
typedef pair<double,double> Point;
#define x first
#define y second
const int N=105;
const double PI=acos(-1);
int n;
Point p[N];
double slope(Point a,Point b)
{
    return (b.y-a.y)/(b.x-a.x);
}
double dis(Point a,Point b)
{
    return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x));
}
double ans[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        p[i]={x,y};
    }
    vector<int>t;
    static int id[N];
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,[=](const int &a,const int &b){return p[a].x<p[b].x;});
    static int s[N];
    int top=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&((p[s[top]].x==p[id[i]].x&&p[s[top]].y<p[id[i]].y)||slope(p[s[top-1]],p[s[top]])<slope(p[s[top]],p[id[i]]))) top--;
        s[++top]=id[i];
    }
    for(int i=1;i<=top;i++)
        t.emplace_back(s[i]);
    iota(id+1,id+n+1,1);
    sort(id+1,id+n+1,[=](const int &a,const int &b){return p[a].x<p[b].x;});
    top=0;
    for(int i=1;i<=n;i++)
    {
        while(top>1&&((p[s[top]].x==p[id[i]].x&&p[s[top]].y>p[id[i]].y)||slope(p[s[top-1]],p[s[top]])>slope(p[s[top]],p[id[i]]))) top--;
        s[++top]=id[i];
    }
    if(s[top]!=t.back()) t.emplace_back(s[top]);
    for(int i=top-1;i>=2;i--)
        t.emplace_back(s[i]);
    if(s[1]!=t.front()) t.emplace_back(s[1]);
    int m=t.size();
    for(int i=0;i<m;i++)
    {
        int l=i-1>=0?i-1:m-1,r=i+1<m?i+1:0;
        double a=dis(p[t[l]],p[t[i]]),b=dis(p[t[i]],p[t[r]]),c=dis(p[t[l]],p[t[r]]);
        ans[t[i]]=(PI-acos((a*a+b*b-c*c)/(2*a*b)))/(2*PI);
    }
    for(int i=1;i<=n;i++)
        printf("%.6lf\n",ans[i]);
    return 0;
}

C - Tiling

两个 \(1\times 2\) 或 \(2\times 1\) 的砖可以填满一个 \(2\times 2\) 的区域，将棋盘分成若干个 \(2\times 2\) 的区域，贪心的填就好了。

注意 \(n,m\) 都为奇数时可以将右下角一个 \(3\times 3\) 的区域这样填：

<>^
^.v
v<>

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1005;
int n,m,a,b;
char s[N][N];
int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s[i][j]='.';
    if(n&1)
    {
        for(int j=1;j<=m;j++)
            if(s[n][j]=='.'&&s[n][j+1]=='.'&&a>0) s[n][j]='<',s[n][j+1]='>',a--;
    }
    if(m&1)
    {
        for(int i=1;i<=n;i++)
            if(s[i][m]=='.'&&s[i+1][m]=='.'&&b>0) s[i][m]='^',s[i+1][m]='v',b--;
    }
    for(int i=1;i<=n;i+=2)
        for(int j=1;j<=m;j+=2)
            if(s[i][j]=='.'&&s[i+1][j]=='.'&&s[i][j+1]=='.'&&s[i+1][j+1]=='.')
            {
                if(a==0&&b==0) continue;
                if(a==1&&b==1) s[i][j]='<',s[i][j+1]='>',a--;
                else if(a==1&&b==0) s[i][j]='<',s[i][j+1]='>',a--;
                else if(a==0&&b==1) s[i][j]='^',s[i+1][j]='v',b--;
                else
                {
                    if(a>=b) s[i][j]='<',s[i][j+1]='>',s[i+1][j]='<',s[i+1][j+1]='>',a-=2;
                    else s[i][j]='^',s[i+1][j]='v',s[i][j+1]='^',s[i+1][j+1]='v',b-=2;
                }
            }
    if(n%2==1&&m%2==1)
    {
        if(a==1&&b==0&&s[n-2][m-2]=='^'&&(s[n-2][m]=='.'||s[n-2][m-1]=='.'||s[n-2][m-2]=='.')) s[n-2][m-2]='^',s[n-1][m-2]='v',s[n][m-2]='<',s[n][m-1]='>',s[n][m]='v',s[n-1][m]='^',s[n-2][m]='>',s[n-2][m-1]='<',s[n-1][m-1]='.',a--;
        if(a==0&&b==1&&s[n-2][m-2]=='<'&&(s[n][m-2]=='.'||s[n-1][m-2]=='.'||s[n-2][m-2]=='.')) s[n-2][m-2]='^',s[n-1][m-2]='v',s[n][m-2]='<',s[n][m-1]='>',s[n][m]='v',s[n-1][m]='^',s[n-2][m]='>',s[n-2][m-1]='<',s[n-1][m-1]='.',b--;
    }
    if(a==0&&b==0)
    {
        printf("YES\n");
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
                printf("%c",s[i][j]);
            printf("\n");
        }
    }
    else printf("NO\n");
    return 0;
}

D - Reversed LCS

字符串的最长回文子序列长度等于其自身与反转的最长公共子序列长度。

令 \(f_{l,r,k}\) 表示 \([l,r]\) 这个区间操作了 \(k\) 次的最长回文子序列长度。

转移为：

\[f_{l,r,k}= \max\begin{cases}f_{l+1,r,k} & \\ f_{l,r-1,k} & \\ f_{l+1,r-1,k}+2\ &(S_l=S_r) \\ f_{l+1,r-1,k-1}+2\ &(k\ge 1)\end{cases} \]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=305;
int n,k;
char s[N];
int f[N][N][N];
int dfs(int l,int r,int k)
{
    if(l==r) return f[l][r][k]=1;
    if(l+1==r)
    {
        if(s[l]==s[r]||k>=1) f[l][r][k]=2;
        else f[l][r][k]=1;
        return f[l][r][k];
    }
    if(f[l][r][k]!=-1) return f[l][r][k];
    f[l][r][k]=max(dfs(l+1,r,k),dfs(l,r-1,k));
    if(s[l]==s[r]) f[l][r][k]=max(f[l][r][k],dfs(l+1,r-1,k)+2);
    if(k>=1) f[l][r][k]=max(f[l][r][k],dfs(l+1,r-1,k-1)+2);
    return f[l][r][k];
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%d",&k);
    memset(f,-1,sizeof(f));
    printf("%d",dfs(1,n,k));
    return 0;
}

E - Ball Eat Chameleons

枚举喂了 \(R\) 个红球，\(B\) 个蓝球，其中 \(R+B=K\)。

一只变色龙只有当吃的红球比蓝球多，或吃的红球和蓝球一样多且吃的最后一个是蓝球。

  • 如果 \(R\lt B\)，显然无解。
  • 如果 \(R\ge B+N\)，可以让所有变色龙的红球都比蓝球多，显然合法。

如果 \(R=B\)，最后一个肯定是蓝球，将最后一个蓝球删去，这样就至少会有一只变色龙吃的红球数比蓝球多。这样变色龙的状态一定就是一些吃的红球和蓝球一样多，另一些吃的红球多。

我们要让吃的红球多的那些变色龙尽可能多，这样吃的红球多的那些变色龙一定就是吃的红球比蓝球多了一个。对于吃的红球和蓝球一样多的那些变色龙，它吃的球一定是 RB，否则我们可以拿出一对 RB 到红球多的那些变色龙那里，这样一定不会更劣。

那么就可以知道，一个序列合法当且仅当能取出 \(N-(R-B)\) 对 RB，也就是说如果将 R 看做 \(+1\)，B 看做 \(-1\)，那么每个位置的前缀和都要大于 \(-(R-N)\)，这个可以按照折线计数那样做，方案数即为：

合问题，类似于卡特兰数的计算方法（翻转第一次碰到直线上方的部分），可以得到答案：

\[C_R^{R+B}-C_{R+B}^{2R-N+1} \]

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000005;
const int MOD=998244353;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int getinv(int x)
{
    return ksm(x,MOD-2);
}
int fac[N],inv[N];
void init(int n=1000000)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1LL*fac[i-1]*i%MOD;
    inv[n]=getinv(fac[n]);
    for(int i=n;i>=1;i--)
        inv[i-1]=1LL*inv[i]*i%MOD;
    return;
}
int C(int n,int m)
{
    if(m>n) return 0;
    else return 1LL*fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int n,k;
int main()
{
    init();
    scanf("%d%d",&n,&k);
    if(k<n)
    {
        printf("0");
        return 0;
    }
    int ans=0;
    for(int r=1;r<=k;r++)
    {
        int b=k-r;
        if(r<b) continue;
        if(r>=b+n) ans=(ans+C(k,r))%MOD;
        else
        {
            if(r==b) b--;
            if(2*r-n+1>=0) ans=((long long)ans+C(r+b,r)-C(r+b,2*r-n+1)+MOD)%MOD;
        }
    }
    printf("%d",ans);
    return 0;
}

F - Trinity

令 \(f_{i,j}\) 为每行都有黑格子的 \(i\) 行 \(j\) 列矩阵的方案数, 答案即为 \(\sum\limits_{i=1}^nC_n^if_{i,m}\)。

考虑转移，每次加一列，然后枚举新增的行数 \(k\)，转移到 \(f_{i+k,j+1}\)。这些行满足 \(A_i=j+1\)。

如果 \(k=0\)，相当于在第 \(j+1\) 列选 \(0,1,2\) 个端点，转移即为 \(\left(1+i+\frac{i(i-1)}{2}\right)f_{i,j}\to f_{i+k,j+1}\)

如果 \(k\gt 0\)，\(b_{j+1}\) 可能是新加入的 \(k\) 行编号的最小值，也可能是原有的某一行，\(c_{j+1}\) 同理。\(b_{j+1},c_{j+1}\) 的方案数可以看做是在 \(i+k+2\) 行选出 \(k+2\) 行，这 \(k+2\) 表示 \(b_{j+1}-1,c_{j+1}+1\) 和新加入 \(k\) 行的位置，转移即为 \(C_{i+k+2}^{k+2}f_{i,j}\to f_{i+k,j+1}\)。

\[\begin{aligned}f_{i,j}&=\left(1+i+\frac{i(i-1)}{2}\right)f_{i,j-1}+\sum\limits_{k=0}^{i-1}C_{i+2}^k f_{k,j-1} \\ &=\left(1+i+\frac{i(i-1)}{2}\right)f_{i,j-1}+(i+2)!\sum\limits_{k=0}^{i-1}\frac{f_{k,j-1}}{k!} \cdot \frac{1}{(i+2-k)!} \end{aligned} \]

直接 NTT 优化即可。

#include<iostream>
#include<cstdio>
#include<vector>
#include<functional>
using namespace std;
const int N=8005;
const int g=3;
const int MOD=998244353;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1LL*res*a%MOD;
        a=1LL*a*a%MOD,b>>=1;
    }
    return res;
}
int getinv(int x)
{
    return ksm(x,MOD-2);
}
std::vector<int>W[2];
void init_omega(int n)
{
    for(int len=1;len<=n;len<<=1)
    {
        int w=ksm(g,(MOD-1)/len),iw=getinv(w);
        W[0][len]=W[1][len]=1;
        for(int k=1;k<len;k++)
            W[0][len+k]=1LL*W[0][len+k-1]*w%MOD,W[1][len+k]=1LL*W[1][len+k-1]*iw%MOD;
    }
    return;
}
void init_poly(int _n)
{
    int n=1;
    while(n<=_n) n<<=1;
    W[0].resize(n*4+1);
    W[1].resize(n*4+1);
    init_omega(n*2);
    return;
}
typedef std::vector<int> Poly;
Poly ntt(const Poly &F,const Poly &G,const std::function<int(int,int)> &mul)
{
    Poly f=F,g=G;
    int n=f.size()-1,m=g.size()-1;
    m+=n,n=1;
    while(n<=m) n<<=1;
    f.resize(n);
    g.resize(n);
    std::vector<int>rev(n);
    for(int i=0;i<n;i++)
    {
        rev[i]=rev[i>>1]>>1;
        if(i&1) rev[i]|=n>>1;
    }
    static const int BIT=15;
    std::function<void(Poly &)> dft=[=](Poly &F)
    {
        int n=F.size();
        std::vector<unsigned long long>f(n);
        for(int i=0;i<n;i++)
            f[i]=F[rev[i]];
        for(int len=2;len<=n;len<<=1)
        {
            if(len&(1<<BIT))
            {
                for(int i=0;i<n;i++)
                    f[i]%=MOD;
            }
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+len/2;k++)
                {
                    unsigned long long l=f[k];
                    int r=W[0][len+k-i]*f[k+len/2]%MOD;
                    f[k]=l+r;
                    f[k+len/2]=l+MOD-r;
                }
        }
        for(int i=0;i<n;i++)
            F[i]=f[i]%MOD;
        return;
    };
    dft(f);
    dft(g);
    for(int i=0;i<n;i++)
        f[i]=mul(f[i],g[i]);
    std::function<void(Poly &)> idft=[=](Poly &F)
    {
        int n=F.size();
        std::vector<unsigned long long>f(n);
        for(int i=0;i<n;i++)
            f[i]=F[rev[i]];
        for(int len=2;len<=n;len<<=1)
        {
            if(len&(1<<BIT))
            {
                for(int i=0;i<n;i++)
                    f[i]%=MOD;
            }
            for(int i=0;i<n;i+=len)
                for(int k=i;k<i+len/2;k++)
                {
                    unsigned long long l=f[k];
                    int r=W[1][len+k-i]*f[k+len/2]%MOD;
                    f[k]=l+r;
                    f[k+len/2]=l+MOD-r;
                }
        }
        for(int i=0;i<n;i++)
            F[i]=f[i]%MOD;
        int invn=getinv(n);
        for(int i=0;i<n;i++)
            F[i]=1LL*F[i]*invn%MOD;
        return;
    };
    idft(f);
    f.resize(m+1);
    return f;
}
Poly operator*(const Poly &F,const Poly &G)
{
    return ntt(F,G,[=](const int &x,const int &y){return 1LL*x*y%MOD;});
}
int fac[N],ifac[N];
void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1LL*fac[i-1]*i%MOD;
    ifac[n]=getinv(fac[n]);
    for(int i=n;i>=1;i--)
        ifac[i-1]=1LL*ifac[i]*i%MOD;
    return;
}
int C(int n,int m)
{
    if(m>n) return 0;
    else return 1LL*fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}
int n,m;
int dp[N][N];
int main()
{
    init(8003);
    init_poly(8000);
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        dp[i][1]=1;
    for(int j=2;j<=m;j++)
    {
        Poly f(n),g(n);
        for(int k=0;k<n;k++)
            f[k]=1LL*dp[k][j-1]*ifac[k]%MOD;
        for(int k=0;k<n;k++)
            g[k]=ifac[k+3];
        Poly res=f*g;
        for(int i=0;i<=n;i++)
        {
            dp[i][j]=1LL*(1+i+i*(i-1)/2)*dp[i][j-1]%MOD;
            if(i-1>=0) dp[i][j]=(dp[i][j]+1LL*res[i-1]*fac[i+2])%MOD;
        }
    }
    int ans=0;
    for(int i=0;i<=n;i++)
        ans=(ans+1LL*dp[i][m]*C(n,i))%MOD;
    printf("%d",ans);
    return 0;
}