AtCoder Beginner Contest 145


第一次AtCoder体验

A.Circle

开场送温暖

int main()
{
    int r;cin>>r;
    cout<<r*r<<endl; 
    return 0;
}

B.Echo

直接判断前一半后一半是否相等即可

int main()
{
    cin>>n>>s;
    if(s.size()%2==1) puts("No");
    else
    {
        for(int i=0;i<s.size()/2;i++)
        {
            if(s[i]!=s[i+(s.size()/2)])
            {
                puts("No");
                return 0;
            }
        }
        puts("Yes");
    }
    return 0;
}

C.Average Length

题解:

emmm这题我现场浪费了好多时间 算错了分母结果1,2样例都很巧对了然后第三个样例数字很小让我一度以为哪里精度炸了…

我们可以这样考虑 对于两个点之间的路径计算这个路径的贡献 剩下$n-2$个点 有$(n-2)!$种路线 然后我们可以把这条路径插空插到这$n-2$条路里 所以一共有$(n-2)!(n-1)=(n-1)!$种情况都会有这条路径 那么总贡献就是$d\cdot (n-1)!$而一共有$n!$种路径 所以平均长度就是$\frac{d}{n}$

我们直接去枚举所有路径$(i,j)$然后计算贡献即可

AC代码:

ll n;
double x[15],y[15];
double calc(int a,int b)
{
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int main()
{
    cin>>n;
    double res=1.0;
    double ans=0.0;
    res=n;
    for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            ans+=calc(i,j)/res;
        }
    }
    printf("%.10Lf\n",ans);
    return 0;
}

D.Knight

一道还算是比较简单的数学题?

题解

既然最后要从$(0,0)$到$(X,Y)$而且只有两种走法 那我们可以假设第一种走了$a$次 第二种走了$b$次 那么可得方程$a+2b=X,2a+b=Y$解得$a= \frac{2y-x}{3},b= \frac{2x-y}{3}$

那么剩下就是一个组合数学问题 总共走$a+b$次其中需要$a$次走第一种情况 那么答案就是$C_{a+b}^{a}\mod p$然后就是比较套路的组合数计算 可以$O(n)$处理乘阶和逆元 不过我就随便写了个快速幂反正题目要求不高

AC代码:

const int p=1e9+7;
ll x,y;
ll calc(ll n)
{
    ll res=1;
    for(ll i=1;i<=n;i++) res=res*i%p;
    return res%p;
}
ll ksm(ll a,ll b)
{
    ll res=1%p;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
int main()
{
    cin>>x>>y;
    if(2*x-y<0||(2*x-y)%3!=0) puts("0");
    else if(2*y-x<0||(2*y-x)%3!=0) puts("0");
    else
    {
        ll a=(2*y-x)/3;
        ll b=(2*x-y)/3;
        ll temp=(x+y)/3;
        temp=calc(temp);
        a=calc(a),b=calc(b);
        ll ans=temp%p*ksm(a,p-2)%p*ksm(b,p-2)%p;
        cout<<ans%p<<endl;
    }
    return 0;
}

E.All-you-can-eat

题解:

这题感觉还是挺有趣的 让我想起在hdoj上做的一题 我大概看了眼题解感觉好像做法不太一样 我是一种贪心的思想

首先这道题肯定需要跑一个01背包 但是它也只能跑一个01背包 数据范围不允许我们去做一些枚举的操作 所以自然想到贪心 因为到了$T$以后就不能再吃了而之前吃的还可以继续 我们可以想到在$T-1$处做点什么

那应该把什么东西放进去呢 其实这里我卡了蛮久的还WA了一发放之前体积最大的进去 不太行 放价值最大的也不太行 其实关键在于我们需要放一个最合适的进去

所以我们可以跑完01背包以后把具体情况跑出来(背包体积是$T-1$) 之后对于没有选到的我们按价值排序 选一个最大的放进去即可

const int maxn=3050;
int n,m;
int v[maxn],w[maxn],f[maxn][maxn];
int p[maxn],num;
int main()
{
    cin>>n>>m;
    int maxx=0,pos=0;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m-1;j++)
        {
            f[i][j]=f[i-1][j];
            if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
        }
    }
    int temp=m-1;
    for(int i=n;i>=1;i--)
    {
        if(temp-v[i]>=0&&f[i][temp]==f[i-1][temp-v[i]]+w[i])
        {
            temp-=v[i];
        }
        else p[++num]=w[i];
    }
    sort(p+1,p+num+1);
    cout<<f[n][m-1]+p[num]<<endl;
    return 0;
}

F.Laminate

待补 比赛时候没高兴看


文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1262C Messy CF1262C Messy
题意简述:给定一个长度为$n$的括号序列 保证一半左括号一半右括号 每次可以指定一个区间反转 假设进过若干次反转以后 对于括号序列的每一个前缀 一共用$k$个合法(包含序列本身)那么符合题意 求一个长度任意的操作序列(长度小于等于$n$)在
2019-11-25
下一篇 
P2312 解方程 P2312 解方程
题意简述:已知方程:$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$求该方程在$[1,m]$内的正整数解 $(0<n\leq100,m\leq10^6,|a_i|\leq10^{10000})$ 题解:首先看到那么
2019-11-16
  目录