您的位置: 首页  >  IT文章  >  Educational Codeforces Round 94 (Rated for Div. 2) 赛后总结及题解

Educational Codeforces Round 94 (Rated for Div. 2) 赛后总结及题解

分类: IT文章 • 2023-11-07 18:07:05

A    String Similarity

题意：定义若两个长度相同的01串中，存在某一个位置，使得两字符串在该位置的字符相同（a[i]=b[i]），则称这两个字符串相似。现在给一个长度为2*n-1的01字符串s，要求构造一个长度为n的字符串，使得该字符串与给出字符串中的s[1..n]，s[2..n+1]，s[3..n+2]，......，s[n..2*n-1]均相似。

思路：对于每一对相似字符串，只要有一个位置上的字符相同即可。

于是对于s[1..n]取出第一位，对于s[2..n+1]取出第二位......即s[1]，s[3]，s[5]，......，s[2*n-1]组合起来，就可构造出答案。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 55
#define mod 100000000
typedef long long ll;
using namespace std;
char s[maxn];
int main()
{
    int T,i,n,len;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%s",&n,s);
        len=2*n-1;
        for (i=0;i<len;i+=2)
        {
            printf("%c",s[i]);
        }
        printf("
");
    }
    return 0;
}
View Code

B    RPG Protagonist

题意：有两个容量分别为p、f的背包，有两种质量分别为s、w，数量分别为cnts，cntw的物品，要求输出背包能够装入的最大物品数。

思路：贪心思想，先枚举p背包装入的s物品数（这里假设s<w），剩余的容量尽可能装入f物品；对于f背包先尽可能装入s物品，剩余的容量尽可能装入f物品。

在每次枚举后得到的最大物品数中取最大值就是答案。

比赛的时候我思维混乱，一度想到背包，二分等等 _(:_」∠)_就这么个题卡了半天。。

其实想到二分验证的时候有想到贪心思路了，然而想得不够，贪错了。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 55
#define mod 100000000
typedef long long ll;
using namespace std;
int p,f,s,w,cnts,cntw;
int cnt,ans,lim;
int main()
{
    int T,i,j,k,t;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&p,&f);
        scanf("%d%d",&cnts,&cntw);
        scanf("%d%d",&s,&w);
        if (s>w) 
        {
            swap(s,w); 
            swap(cnts,cntw);
        }
        ans=0;
        lim=p/s;
        lim=min(cnts,lim);
        for (i=0;i<=lim;i++)
        {
            k=min((p-i*s)/w,cntw);
            cnt=i+k;
            j=min(cnts-i,f/s);
            t=min((f-j*s)/w,cntw-k);
            cnt+=j+t;
            if (cnt>ans) ans=cnt; 
        }
        printf("%d
",ans);
    }
    return 0;
}
View Code

C    Binary String Reconstruction

题意：给一个01串s，要求输出它对应的01串w，若不存在符合条件的w串则输出-1。其中若w[i-x]==1或w[i+x]==1时，s[i]为1；若不满足则s[i]=0。

思路：对于s串中每一个0，都有w[i-x]==0且w[i+x]==0（若存在）。

因此预处理将w的每一位赋值为1，先将s中的所有0对应的w[i-x]和w[i+x]标记为0，再处理s中的每一位1，若对应的w[i-x]与w[i+x]均被标记为0，说明不存在符合条件的w串，输出-1。

最后直接输出w串就可以了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100010
typedef long long ll;
using namespace std;
int ans[maxn];
char s[maxn];
int main()
{
    int T,i,x,len,flag,cnt;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s%d",s,&x);
        len=strlen(s);
        flag=0;
        for (i=0;i<len;i++) ans[i]=1;
        for (i=0;i<len;i++)
        {
            if (s[i]=='0') 
            {
                if (i-x>=0) ans[i-x]=0;
                if (i+x<len) ans[i+x]=0;
            }
        }
        for (i=0;i<len;i++)
        {
            if (s[i]=='1')
            {
                cnt=0;
                if (i-x<0 || ans[i-x]==0) cnt++;
                if (i+x>=len || ans[i+x]==0) cnt++;
                if (cnt==2) 
                {
                    flag=1;break;
                }
             }
        }
        if (flag) 
        {
            printf("-1
");
            continue;
        }
        else 
        {
            for (i=0;i<len;i++) printf("%d",ans[i]);
            printf("
");
        }
    }
    return 0;
}
View Code

D    Zigzags

题意：给定一个数组a，问存在几种i,j,k,l的组合，使得i<j<k<l且a[i]==a[k],a[j]==a[l]。

思路：枚举j，用cnt数组统计j之前a[i]出现的次数，再从j+1开始寻找l，在寻找l的过程中，统计j与l之间每个k对应的i的数量（就是cnt[a[k]]），累加起来记作tot（即符合i<j<k且a[i]==a[k]的ik的对数），每当找到一个对应的l，就将答案加上tot。

想起来可能有点绕，手动模拟一下过程会好理解一点。(代码极短)

比赛时完全没想到这么写。。感觉这个代码还是挺巧妙的。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 3005
typedef long long ll;
using namespace std;
int n,a[maxn],cnt[maxn];
ll ans,tot;
int main()
{
    int T,i,j,l;
    scanf("%d",&T);
    while (T--)
    {
        ans=0;
        memset(cnt,0,sizeof(cnt));
        scanf("%d",&n);
        for (i=1;i<=n;i++) scanf("%d",&a[i]); 
        for (j=1;j<n;j++)
        {
            tot=0;
            for (l=j+1;l<=n;l++)
            {
                if (a[j]==a[l]) ans+=tot;
                tot+=cnt[a[l]];
            }
            cnt[a[j]]++;
        }
        printf("%lld
",ans);
    }
    return 0;
}
View Code

E    Clear the Multiset

F    x-prime Substrings

G    Mercenaries

相关推荐