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

AtCoder Grand Contest 048

时间：2023-09-27 18:56:52浏览次数：41  
标签：AtCoder const limits Contest int sum ans 048 include

A - atcoder < S

枚举操作完的串 \(s\) 和 atcoder 相同的前缀长度，算出前面的前缀相同的代价加上当前这位大于 atcoder 中对应的那一位的代价即为达到当前状态的代价，取个最小值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1005;
const int INF=1061109567;
int T;
int n;
char s[N];
char t[]={" atcoder`"};
void solve()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    int ans=INF;
    int now=0;
    for(int i=1;i<=min(n,8);i++)
    {
        for(int j=i+1;j<=n;j++)
            if(s[j]>t[i])
            {
                ans=min(ans,now+j-i);
                break;
            }
        if(s[i]<t[i])
        {
            for(int j=i+1;j<=n;j++)
                if(s[j]==t[i])
                {
                    now+=j-i;
                    for(int k=i;k<j;k++)
                        s[k]=s[k+1];
                    s[j]=t[i];
                    break;
                }
            break;
        }
        else if(s[i]>t[i])
        {
            ans=min(ans,now);
            break;
        }
    }
    if(ans>=INF) printf("-1\n");
    else printf("%d\n",ans);
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
        solve();
    return 0;
}

B - Bracket Score

最后 () 的位置一定为一半奇数一半偶数。先把所有 \(b_i\) 加入答案。把奇数位和偶数位的 \(a_i-b_i\) 从大到小排序，每次从奇数位和偶数位分别拿出一个，如果加入当前的两个数会使答案变大就加入。

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
int a[N],b[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    vector<int>odd,even;
    for(int i=1;i<=n;i++)
        if(i&1) odd.emplace_back(a[i]-b[i]);
        else even.emplace_back(a[i]-b[i]);
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans+=b[i];
    sort(odd.begin(),odd.end(),greater<int>());
    sort(even.begin(),even.end(),greater<int>());
    for(int i=0;i<n/2;i++)
        if(odd[i]+even[i]>=0) ans+=odd[i]+even[i];
    printf("%lld",ans);
    return 0;
}

C - Penguin Skating

每次操作相当于是将差分数组某个位置的值 \(-1\) 后加到相邻的一个位置上，然后再将这个位置的值置为 \(1\)，双指针搞搞就好了。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=100005;
int n,L;
int a[N],b[N];
int sa[N],sb[N];
int main()
{
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    a[0]=0,b[0]=0;
    n++,a[n]=L+1,b[n]=L+1;
    for(int i=1;i<=n;i++)
        sa[i]=a[i]-a[i-1]-1,sb[i]=b[i]-b[i-1]-1;
    long long ans=0;
    for(int i=1,j=1;i<=n;i++)
    {
        long long sum=0;
        int l=n+1,r=0;
        while(j<=n&&sum+sa[j]<=sb[i])
        {
            if(sa[j]) l=min(l,j),r=max(r,j);
            sum+=sa[j],j++;
        }
        if(l<=r)
        {
            if(i<l) ans+=r-i;
            else if(i>r) ans+=i-l;
            else ans+=r-l;
        }
        if(sum!=sb[i])
        {
            printf("-1");
            return 0;
        }
    }
    printf("%lld",ans);
    return 0;
}

D - Pocky Game

可以发现，一堆石子要么一个个取，要么一次性取完。

令 \(f_{l,r,0/1,x}\) 表示 \([l,r]\) 这段区间，左边/右边是 \(x\) 时谁能胜利。

\(x\) 的范围很大，考虑令 \(f_{l,r,0/1}\) 表示 \([l,r]\) 这段区间，第一个人/第二个人胜利 \(a_l\)/\(a_r\) 至少为多少。

考虑转移 \(f_{l,r,0}\)，\(f_{l,r,1}\) 同理。

  • 当 \(f_{l+1,r,1}\gt a_r\) 时，\(f_{l,r,0}=1\)，此时无论 \(a_l\) 取多少第一个人都必胜；
  • 当 \(f_{l+1,r,1}\le a_r\) 时，此时两个人肯定会轮流取一个，直到最右边的那一堆被取到 \(f_{l+1,r,1}\) 时，第二个人肯定只能将最右边那堆直接取完，否则第一个人直接将第一堆取完第二个人就输了，换句话说，就是：\(f_{l,r,0}-f_{l,r-1,0}\gt a_r-f_{l+1,r,1}\Leftrightarrow f_{l,r,0}=f_{l,r-1,0}-f_{l+1,r,1}+a_r+1\)。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int T;
int n;
int a[N];
long long f[N][N][2];
long long dfs(int l,int r,int k)
{
    if(l==r) return f[l][r][k]=1;
    if(f[l][r][k]!=-1) return f[l][r][k];
    if(k==0)
    {
        if(dfs(l+1,r,k^1)>a[r]) f[l][r][k]=1;
        else f[l][r][k]=a[r]-dfs(l+1,r,k^1)+dfs(l,r-1,k)+1;
    }
    else
    {
        if(dfs(l,r-1,k^1)>a[l]) f[l][r][k]=1;
        else f[l][r][k]=a[l]-dfs(l,r-1,k^1)+dfs(l+1,r,k)+1;
    }
    return f[l][r][k];
}
void solve()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(f,-1,sizeof(f));
    if(dfs(1,n,0)<=a[1]) printf("First\n");
    else printf("Second\n");
    return;
}
int main()
{
    scanf("%d",&T);
    while(T--)
        solve();
    return 0;
}

E - Strange Relation

我们从后往前插入每个数，对于 \(a_i\) 放到 \(a_{i+1},\cdots ,a_n\) 前面对 \(x_i\cdots x_n\) 的影响：

  • \(x_i=0\)
  • \(a_i \lt a_j+T\times (x_j+1)\)，令 \(x_j=x_j+1\)（不加肯定字典序比加字典序小）。
  • \(a_i \ge a_j+T\times (x_j+1)\)，\(x_j\) 不变。

可以发现对于每个 \(j\) 是独立的。

对于每个位置 \(p\) 的每一个取值分别 DP，设 \(f_{i,j}\) 表示考虑 \(1\sim i\) 的影响时 \(x_p=j\) 的方案数。

因为 \(i+1\sim n\) 可以随便选，答案还要乘上 \(k^{n-p}\)，贡献即为 \(k^{n-p}\sum\limits_{i=0}^n i\cdot f_{1,i}\)。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
const int MOD=1000000007;
int n,m,t;
int b[N][N];
int f[N][N];
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[i][j]);
    for(int i=1;i<=n;i++)
    {
        int ans=0;
        for(int j=1;j<=m;j++)
        {
            f[i][0]=1;
            for(int k=i;k>1;k--)
                for(int l=0;l<n;l++)
                    for(int x=1;x<=m;x++)
                        if(b[i][j]+t*(l+1)>b[k-1][x]) f[k-1][l+1]=(f[k-1][l+1]+f[k][l])%MOD;
                        else f[k-1][l]=(f[k-1][l]+f[k][l])%MOD;
            for(int k=1;k<n;k++)
                ans=(ans+1LL*k*f[1][k])%MOD;
            for(int k=1;k<=i;k++)
                for(int l=0;l<=n;l++)
                    f[k][l]=0;
        }
        for(int j=i+1;j<=n;j++)
            ans=1LL*ans*m%MOD;
        printf("%d\n",ans);
    }
    return 0;
}

F - 01 Record

可以发现，对一个数连续操作一定是 \(01\) 交错排列，结尾一定是 \(1\)。

考虑将整个序列翻转后，相当于是每次删去一个 \(101010\cdots\) 的子序列。

我们贪心的每次能删尽量删，令每次删除的字符串长度为 \(l_1,l_2,\cdots ,l_n\)。

令 \(S\) 中的元素从大到小分别为 \(x_1,x_2,\cdots ,x_m\)，其中 \(m\ge n\)，则一组 \(x\)合法当且仅当：

  • \(L=\sum\limits_{i=1}^n l_i=\sum\limits_{i=1}^m x_i\)
  • \(\forall 1\le i\le n,\sum\limits_{j=1}^i \lfloor \frac{l_j}{2}\rfloor\ge \sum\limits_{j=1}^i \lfloor \frac{x_j}{2}\rfloor\)
  • \(\forall 1\le i\le n,\sum\limits_{j=1}^i \lceil \frac{l_j}{2} \rceil \ge \sum\limits_{j=1}^i \lceil \frac{x_j}{2} \rceil\)

具体证明可以看官方题解。

令 \(f_{i,j,k,t}\) 表示当前填到第 \(i\) 位，且 \(\sum\limits_{l=1}^i \lfloor \frac{x_l}{2}\rfloor=j\) 且 \(\sum\limits_{l=1}^i \lceil \frac{x_l}{2}\rceil=k\) 且 \(x_i=t\) 的方案数。因为 \(x_1\ge x_2\ge\cdots\ge x_i\)，且 \(\sum\limits_{j=1}^i x_i\le L\)，所以 \(t\le \lfloor \frac{L}{i}\rfloor\)。直接转移即可。

答案即为：

\[\sum_{i=n}^L \sum_{t=1}^L f_{i,\sum\limits_{j=1}^n \lfloor \frac{l_j}{2}\rfloor,\sum\limits_{k=1}^n \lceil \frac{l_k}{2} \rceil,t} \]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=305;
const int MOD=1000000007;
int n,m,L;
string s;
int a[N];
int s1[N],s2[N];
int f[2][N][N][N],g[2][N][N][N];
int main()
{
    cin>>s;
    L=s.size();
    reverse(s.begin(),s.end());
    while((int)s.size()>0)
    {
        if(s[0]!='1')
        {
            cout<<0;
            return 0;
        }
        string t="";
        int c=1;
        n++;
        for(int i=0;i<(int)s.size();i++)
            if(s[i]-'0'==c) a[n]++,c^=1;
            else t+=s[i];
        s=t;
    }
    for(int i=1;i<=L;i++)
        s1[i]=s1[i-1]+a[i]/2;
    for(int i=1;i<=L;i++)
        s2[i]=s2[i-1]+(a[i]+1)/2;
    int cur=0;
    f[0][0][0][L]=g[0][0][0][L]=1;
    int ans=0;
    for(int i=1;i<=L;i++)
    {
        cur^=1;
        if(i-2>=0)
        {
            for(int j=0;j<=s1[i-2];j++)
                for(int k=0;k<=s2[i-2];k++)
                    for(int t=0;t<=L/max(i-2,1);t++)
                        f[cur][j][k][t]=g[cur][j][k][t]=0;
        }
        for(int j=0;j<=s1[i];j++)
            for(int k=0;k<=s2[i];k++)
            {
                for(int t=0;t<=L/i;t++)
                    if(j-t/2>=0&&k-(t+1)/2>=0) f[cur][j][k][t]=(g[cur^1][j-t/2][k-(t+1)/2][L/max(i-1,1)]-(t-1>=0?g[cur^1][j-t/2][k-(t+1)/2][t-1]:0))%MOD;
                g[cur][j][k][0]=f[cur][j][k][0];
                for(int t=1;t<=L/i;t++)
                    g[cur][j][k][t]=(g[cur][j][k][t-1]+f[cur][j][k][t])%MOD;
            }
        if(i>=n)
            for(int t=1;t<=L/i;t++)
                ans=(ans+f[cur][s1[n]][s2[n]][t])%MOD;
    }
    ans=(ans+MOD)%MOD;
    printf("%d",ans);
    return 0;
}

标签：AtCoder,const,limits,Contest,int,sum,ans,048,include
From： https://www.cnblogs.com/zhou-jk/p/17733440.html

相关文章

  • 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......
  • AtCoder Grand Contest 045
    A-XorBattle可以发现，从后往前扫，遇到一个\(1\)找后面是否有若干个\(0\)的位置的\(a_i\)与当前位置的异或和相等，用线性基维护一下就好了。代码：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;constintN=205;intT;intn;longlong......
  • AtCoder Beginner Contest 318
    AtCoderBeginnerContest318A-FullMoon(atcoder.jp)以\(M\)为首项,\(P\)为公差,看\(1\simN\)里包含了多少项的个数#include<bits/stdc++.h>usingi64=longlong;usingnamespacestd;typedefpair<i64,i64>PII;intmain(){ios::sync_with_stdio......
  • AtCoder Regular Contest 165
    Preface这场前三题是上周四写的，今天课有点多本来想着把最近两场CF的博客先写下的但后面发现还有CCLCC的杂谈没写，写完发现由于晚上要上课没时间了，只能先把这场先写一下A-SumequalsLCM设\(n=\prod_{i=1}^kp_i^{c_i}\)，不难发现令\(A_1=p_1^{c_1},A_2=p_2^{c_2},\cdots\)，然......
  • The 2023 ICPC Asia Regionals Online Contest (2) MDIELK
    The2023ICPCAsiaRegionalsOnlineContest(2)MDIELKMDirtyWork题意：总共有\(n\)个问题，对于第\(i\)个问题需要\(a_i\)分钟。你可以随便选择一个没过的题去写，写完以后马上交，你有\(p_i\)的概率会错，错了不能跳题，你要花额外\(b_i\)的时间去\(debug\)。问你以最佳策略的最小罚......
  • The 2023 ICPC Asia Regionals Online Contest (2)
    Preface这场打的有点捞说实话，两个小时出头的时候写完6个题就开始坐牢了K题由于我习惯性地不写数论就扔给徐神了，徐神也是很有思路写了个看着就很对的东西，但不知道为什么过不去赛后发现K其实是个很傻逼的题，类似的思路我最近补CF的时候还遇到过，但就是没细想虽然当时下机的时候和......
  • 100048.美丽塔 2 - 364
    美丽塔2给你一个长度为n下标从0开始的整数数组maxHeights。你的任务是在坐标轴上建n座塔。第i座塔的下标为i，高度为heights[i]。如果以下条件满足，我们称这些塔是美丽的：1<=heights[i]<=maxHeights[i]heights是一个山状数组。如果存在下标i满足以下条......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99