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

AtCoder Grand Contest 022

时间：2023-09-27 19:15:42浏览次数：39  
标签：AtCoder Contest int res top -- 022 include MOD

A - Diverse Word

如果至少有一个字符没有出现过，只要在原字符串后面加入一个没有出现过的字符中最小的那个字符就好了。

如果所有字符都出现过，找到一个尽量靠后的位置 \(i\in [1,n)\)，使得 \(s_i\lt s_{i+1}\)，最优字符串将 \(s_i\) 换成 \([i+1,n]\) 里面比 \(s_i\) 大的最小的那个字符就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=26;
int n;
string s;
int cnt[N];
int main()
{
    cin>>s;
    n=s.size();
    for(int i=0;i<n;i++)
        cnt[s[i]-'a']++;
    if(n<26)
    {
        cout<<s;
        for(int i=0;i<26;i++)
            if(cnt[i]==0)
            {
                cout<<(char)(i+'a');
                break;
            }
    }
    else
    {
        for(int i=n-2;i>=0;i--)
        {
            if(s[i]<s[i+1])
            {
                cout<<s.substr(0,i);
                char now=s[i+1];
                for(int j=i+1;j<=n-1;j++)
                    if(s[j]>s[i]) now=min(now,s[j]);
                cout<<now;
                return 0;
            }
        }
        cout<<"-1";
    }
    return 0;
}

B - GCD Sequence

先填入 \(2,3\)，这样就可以满足 \(\gcd(a_1,a_2,\cdots,a_n)=1\) 的条件，再填入 \(2\) 的倍数和奇数且为 \(3\) 的倍数，我们需要保证总和是 \(6\) 的倍数，发现当 \(n=20000\) 时刚好满足。

考虑更一般的情况，我们不妨从小到大取，设 \(i\) 为取了 \(i\) 个奇数且为 \(3\) 的倍数，\(j\) 为取了 \(j\) 个 \(2\) 的倍数，那么 \(i\) 和 \(j\) 需要满足：

  • \(i+j = n\)；
  • \(i\le 5000\) 且 \(i\) 是偶数；
  • \(j\le 15000\) 且 \(j\bmod 3 \ne 1\)；

找出满足条件的 \(i,j\) 构造即可。

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int main()
{
    scanf("%d",&n);
    if(n==3)
    {
        printf("2 5 63");
        return 0;
    }
    for(int i=2;i<n&&i<=5000;i+=2)
    {
        int j=n-i;
        if(j<=15000&&j%3!=1)
        {
            for(int k=1,v=3;k<=i;k++,v+=6)
                printf("%d ",v);
            for(int k=1,v=2;k<=j;k++,v+=2)
                printf("%d ",v);
            return 0;
        }
    }
    return 0;
}

C - Remainder Game

显然不会重复使用一个相同的 \(k\) 操作两次。

考虑从大到小贪心考虑每一位 \(k\) 选不选，每次只需要判断是否能通过 \(1\sim k-1\) 和之前已经选过的模数将每个 \(a_i\) 变为 \(b_i\)，暴力 DP 一下就好了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N=55;
int n;
int a[N],b[N];
bool f[N][N];
vector<int>v;
int check(int m)
{
    memset(f,false,sizeof(f));
    for(int i=0;i<=50;i++)
    {
        f[i][i]=true;
        for(int j=0;j<=i;j++)
            for(int k=1;k<=m;k++)
                f[i][j]|=f[i%k][j];
        for(int j=0;j<=i;j++)
            for(int k:v)
                f[i][j]|=f[i%k][j];
    }
    for(int i=1;i<=n;i++)
        if(!f[a[i]][b[i]]) return false;
    return true;
}
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]);
    if(!check(50))
    {
        printf("-1");
        return 0;
    }
    for(int k=51;k>=1;k--)
        if(!check(k-1)) v.emplace_back(k);
    long long ans=0;
    for(int k:v)
        ans|=1LL<<k;
    printf("%lld",ans);
    return 0;
}

D - Shopping

可以发现，可以将 \(t\) 对 \(2L\) 取模，只需要在答案里加入 \(\lfloor \frac{t_i}{2L} \rfloor\)。相当于是求列车要跑几个来回。

对于第 \(i\) 个商场，令 \(l_i\) 表示从右边进入 \(i\)，列车从 \(i\to 0\to i\) 再次到达 \(i\) 的时候能不能上车；\(r_i\) 表示从左边进入 \(i\)，列车从 \(i\to L\to i\) 再次到达 \(i\) 的时候能不能上车。

考虑第 \(i\) 个商场的贡献。如果 \(t_i=0\)，或者是 \(l_i=r_i=0\)，肯定不能匹配，直接加入答案。否则如果 \(i \lt j,l_i=r_j=1\)，则可以把它们匹配起来，然后少跑一个来回。由于所有 \(l_i=1,r_i=0\) 的点一定在所有 \(l_i=0,r_i=1\) 的点的右边，可以单独考虑两边的匹配。

可能需要特判下 \(n\) 的位置。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
int n,L;
int x[N],t[N];
bool l[N],r[N];
bool del[N];
int main()
{
    scanf("%d%d",&n,&L);
    for(int i=1;i<=n;i++)
        scanf("%d",&x[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&t[i]);
    int res=1;
    for(int i=1;i<=n;i++)
    {
        res+=t[i]/(2*L),t[i]%=(2*L);
        if(t[i]==0)
        {
            del[i]=true;
            continue;
        }
        l[i]=2*(L-x[i])>=t[i];
        r[i]=2*x[i]>=t[i];
        del[i]=!(l[i]|r[i]);
        res++;
    }
    if(l[n]) res--;
    int sum=0,top=0;
    int pos=n;
    for(int i=1;i<n;i++)
        if(!del[i])
        {
            if(!l[i])
            {
                pos=i;
                break;
            }
            else if(r[i]) top++;
            else if(top>=1) top--,res--;
        }
    sum+=top,top=0;
    for(int i=n-1;i>=pos;i--)
        if(!del[i])
        {
            if(!r[i]) break;
            else if(l[i]) top++;
            else if(top>=1) top--,res--;
        }
    sum+=top,top=0;
    res-=sum/2;
    printf("%lld",2LL*L*res);
    return 0;
}

E - Median Replace

考虑判断一个串是否合法。

从前往后扫，记下当前 \(1\) 的个数 \(c_1\) 和 \(0\) 的个数 \(c_0\)，每次新加入一个数。

如果加入的数为 \(0\)，将 \(c_0\) 加一。如果 \(c_0\ge 3\)，可以通过操作将 \(3\) 个 \(0\) 变为 \(1\) 个零。

如果加入的数为 \(1\)，如果当前 \(c_0\gt 0\)，那么可以将这个 \(1\) 和一个 \(0\) 配对，这样是没有影响的，因为这个组的权值取决于后面第三个数的权值。否则将 \(c_1\) 加 \(1\)。

可以发现 \(c_0\) 取值只可能为 \(0,1,2\)，\(c_1\ge 3\) 时跟 \(c_1=2\) 是等价的，即 \(0\le c_0,c_1\le 2\)。

那么就可以 DP 了，令 \(f_{i,j,k}\) 表示到 \(i\) 个位置，\(c_0=j,c_1=k\) 的方案数，填 \(0\) 或填 \(1\) 转移即可。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=300005;
const int MOD=1000000007;
int n;
char s[N];
int f[N][3][3];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    f[0][0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
            {
                if(s[i+1]=='1')
                {
                    if(k>=1) f[i+1][j][k-1]=(f[i+1][j][k-1]+f[i][j][k])%MOD;
                    else if(j+1<3) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
                    else f[i+1][2][k]=(f[i+1][2][k]+f[i][j][k])%MOD;
                }
                if(s[i+1]=='0')
                {
                    if(k>=2) f[i+1][j][1]=(f[i+1][j][1]+f[i][j][k])%MOD;
                    else f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;
                }
                if(s[i+1]=='?')
                {
                    if(k>=1) f[i+1][j][k-1]=(f[i+1][j][k-1]+f[i][j][k])%MOD;
                    else if(j+1<3) f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
                    else f[i+1][2][k]=(f[i+1][2][k]+f[i][j][k])%MOD;
                    if(k>=2) f[i+1][j][1]=(f[i+1][j][1]+f[i][j][k])%MOD;
                    else f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;
                }
            }
    int ans=0;
    for(int j=0;j<3;j++)
        for(int k=0;k<=j;k++)
            ans=(ans+f[n][j][k])%MOD;
    printf("%d",ans);
    return 0;
}

F - Checkers

考虑一个过程中所在位置，肯定是若干个 \(X^k\) 所组成。我们可以用 \(S=\{a_i\}\) 来表示这个位置，其中 \(a_i\) 表示某个 \(X^k\) 的系数。

我们令初始时令第 \(i\) 个位置 \(s_{i,i}=1,s_{i,j}=0\,(j\ne i)\)。

每次将 \(i\) 移到关于 \(j\) 的对称位置，相当于是将 \(s_i=2s_j-s_i\)，这里的减法为每个位置依次相减。

因为 \(X\) 很大，我们只需要计算最后操作留下的那个位置的 \(S\) 的方案数。

考虑 \(S\) 需要满足的条件：

  • 由 \(\pm 2^k\) 组成，这个可以归纳证明。

  • 所有元素之和为 \(1\)，这个也可以归纳。

  • 如果存在绝对值为 \(2^k\) 的元素，必然存在绝对值为 \(2^{k-1}\) 的元素。

  • 恰有一个元素的绝对值为 \(1\)。

  • 对于 \(i\ge 1\) ，存在一种调整绝对值为 \(2^i\) 的项的符号的方式使得绝对值不超过 \(2^i\) 的项和为 \(1\)。

    证明的话可以考虑归纳。

    \(A\) 分裂为两个集合 \(B,C\)，\(B,C\) 也是能被表示出来的，满足 \(A=2B-C\)。不妨令 \(-1\in A\)，\(1\in A\) 时同理。

    令 \(A\) 中最小的正元素为 \(2^i\)。

    • 如果 \(-2,-4,\cdots,-2^{i-1}\) 出现至少两次，令 \(B=\{-1,-2,\cdots ,-2^{i-2},2^{i-1}\}\)，\(2B=\{-2,-4,\cdots ,-2^{i-1},2^i\}\)，其余元素构成 \(C\)，这显然是满足条件的。

    • 否则 \(-2,-4,\cdots,-2^{i-1}\) 一定存在某个元素 \(-2^j\) 只出现了一次：

      • 如果 \(j=1\)，令 \(B=\frac{A/\{-1\}}{2}\)，\(C=\{1\}\)，显然满足条件。
      • 否则不满足假设条件。

这样的 \(S\) 肯定和最后的位置一一对应，考虑计算这个 \(S\) 的方案数，注意这个 \(a_i\) 所对应的 \(X^k\) 是可以互换的，所以要乘以一个可重集排列数。

令 \(f_{i,j,k}\) 表示当前已经填了绝对值 \(2^{i-1}\) 的数，填了 \(j\) 个位置，当前权值和为 \(k\cdot 2^i+1\) 的方案数，每次枚举填入 \(x\) 个 \(2^i\) 和 \(y\) 个 \(-2^i\) 转移即可。

#include<iostream>
#include<cstdio>
#include<cassert>
using namespace std;
const int N=55;
const int MOD=1000000007;
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 n;
int fac[N],inv[N];
void init(int n=50)
{
    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 f[N][N][N+N];
int main()
{
    init();
    scanf("%d",&n);
    f[1][1][-1+n]=f[1][1][0+n]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=-n;k<=n;k++)
                if(f[i][j][k+n])
                {
                    for(int x=0;x<=n;x++)
                        for(int y=0;y<=n;y++)
                            if(x+y>0&&j+x+y<=n&&k+x+y>=0&&k-x-y<=0&&(k+x-y)%2==0)
                                if((k+x-y)/2>=-n&&(k+x-y)/2<=n) f[i+1][j+x+y][(k+x-y)/2+n]=(f[i+1][j+x+y][(k+x-y)/2+n]+1LL*f[i][j][k+n]*inv[x]%MOD*inv[y]%MOD)%MOD;
                }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+f[i][n][n])%MOD;
    ans=1LL*ans*fac[n]%MOD;
    printf("%d",ans);
    return 0;
}

标签：AtCoder,Contest,int,res,top,--,022,include,MOD
From： https://www.cnblogs.com/zhou-jk/p/17733478.html

相关文章

  • AtCoder Grand Contest 023
    A-Zero-SumRanges令\(s_n=\sum\limits_{i=1}^na_i\)，相当于找满足\(l\ler,s_r-s_{l-1}\)的点对\((l,r)\)的个数，直接搞就完事了。#include<iostream>#include<cstdio>#include<unordered_map>usingnamespacestd;constintN=200005;intn;inta[N]......
  • AtCoder Grand Contest 024
    A-Fairness每次操作后\(a_i-b_i=b_{i-1}-a_{i-1}\)，对\(k\)的奇偶性讨论一下即可。#include<iostream>#include<cstdio>usingnamespacestd;inta,b,c;longlongk;intmain(){scanf("%d%d%d%lld",&a,&b,&c,&k);if(k%2==0)......
  • AtCoder Grand Contest 021
    A-DigitSum2要么是\(n\)要么是\(n\)的第一位后面加上若干个\(9\)。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;longlongn;intcalc(longlongx){if(x==0)return0;intsum=0;while(x)sum+=x......
  • 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);......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99