首页 > 其他分享 >AtCoder Grand Contest 021

AtCoder Grand Contest 021

时间：2023-09-27 19:14:23浏览次数：33  
标签：AtCoder return Contest int top 021 const include MOD

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;
}

标签：AtCoder,return,Contest,int,top,021,const,include,MOD
From： https://www.cnblogs.com/zhou-jk/p/17733479.html

相关文章

  • AtCoder Regular Contest 102
    C-TriangularRelationship枚举\(a\bmodk\)的值，\(b\bmodk,c\bmodk\)的值也就确定了，算下贡献就好了。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); longlongans=0; for(inta=0;......
  • ACL Contest 1
    A-ReachableTowns现把城市按照\(x_i\)排序将第一维去掉。对于每个联通块，将单调栈将每个联通块中\(y_i\)最小的那个存下来。每次新加入一个点\(i\)相当于前面的\(\lty_i\)的位置合并成一个联通块。具体地，将单调栈中所有\(\lty_i\)的点弹出，并查集合并一下，加入弹出......
  • AtCoder Regular Contest 103
    C-////如果奇数和偶数出现的颜色的最大值相同一边取最大值和一边取次大值，否则两边都选最大值即可。#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=100005;intn,m;intv[N];intc[N];intmain(){ scanf("%d",&n); for(in......
  • DISCO Presents Discovery Channel Code Contest 2020 Qual
    A-DDCCFinals直接模拟即可。#include<iostream>#include<cstdio>usingnamespacestd;intx,y;intmain(){ scanf("%d%d",&x,&y); intans=0; if(x==1)ans+=30; elseif(x==2)ans+=20; elseif(x==3)ans+=10; if(y==1)ans+=30; ......
  • diverta 2019 Programming Contest
    A-ConsecutiveIntegers答案为\(n-k+1\)。#include<iostream>#include<cstdio>usingnamespacestd;intn,k;intmain(){ scanf("%d%d",&n,&k); printf("%d",n-k+1); return0;}B-RGBBoxes枚举\(r,g\)，判断一下对应的......
  • AtCoder Grand Contest 048
    A-atcoder<S枚举操作完的串\(s\)和atcoder相同的前缀长度，算出前面的前缀相同的代价加上当前这位大于atcoder中对应的那一位的代价即为达到当前状态的代价，取个最小值即可。#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=1......
  • AtCoder Grand Contest 046
    A-Takahashikun,TheStrider问题就是要你求\(ax\equiv0\pmod{360}\)中\(a\)的最小值。答案就是\(a=\frac{360}{\gcd(x,360)}\)。代码：#include<iostream>#include<cstdio>usingnamespacestd;intx;intgcd(inta,intb){ returnb==0?a:gcd(b,a%b);......
  • AtCoder Grand Contest 047
    A-IntegerProduct考虑将原来的数全部化为整数，乘上\(10^9\)，那么问题就变成了是否有两个数的乘积是\(10^{18}\)的倍数。考虑如果是\(10^{18}\)的倍数的话必然是\(2^{18}\)和\(5^{18}\)的倍数，那么分解出每个数的\(2,5\)因子数量，然后再看看有多少个数与它\(2,5\)的因......
  • AtCoder Grand Contest 043
    A-RangeFlipFindRoute可以发现，一条路径的最小操作数等于路径上有多少#的块，令\(f_{i,j}\)表示到\((i,j)\)的最小操作次数，直接DP就行了。注意路径上一个\(1\)的块会被算两次，需要除以\(2\)。#include<iostream>#include<cstdio>#include<cstring>usingnamesp......
  • AtCoder Grand Contest 044
    A-PaytoWin不妨将操作倒过来考虑，问题就变成了每次除以\(2,3,5\)或者\(+1,-1\)，令\(f_n\)表示将\(n\)变成\(0\)的最小花费，然后记忆化搜索即可，可以证明复杂度是对的。代码：#include<iostream>#include<cstdio>#include<map>usingnamespacestd;intT;longlong......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99