Educational Codeforces Round 94

A – String Similarity

题意

如果有两个字符串，若他们存在有相同的以为，那么我们称这两个字符串是相似的。

给定一个长度为$2n-1$的字符串$S$，要求构造出一个字符串使得长度为$n$的$S$的任意子串都与该字符串相似。

解题思路

长度为$2n-1$的字符串它的长度为$n$的子串数量刚好是$n$，所以我们考虑使得每个子串都影响到答案的一位。

我的构造思路是令$ans_i=s_{2i}^{}$

参考代码

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
using namespace std;
const int MAXN=(int)1e5+5;
char buf[MAXN];
int main()
{
    int T,n;
    cin>>T;
    while (T--)
    {
        cin>>n>>buf;
        rep(i,0,n)cout<<buf[i*2];
        cout<<endl;
    }
    return 0;
}

B – RPG Protagonist

题意

$p$和$f$分别代表你和你的同伴的背包的容量值
$cnt_s$和$cnt_w$分别代表$s$物品的数量和$w$物品的数量
$s$和$w$分别代表这两件物品的体积
求两个人一共能携带的物品的最大值是多少

解题思路

我本来考虑是否有$O(1)$的贪心思路的，但是那些看似没有问题的贪心思路都是有问题的。

正确的思路是枚举一个人的$s$的物品的数量，然后剩下的贪心解决，此处的$s<w$如果不是交换就好了。

时间复杂度为$O(cnt_s)$

参考代码

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
using namespace std;

int main()
{
    int T;
    int p,f;
    int cs,cw;
    int s,w;
    cin>>T;
    while(T--)
    {
        cin>>p>>f;
        cin>>cs>>cw;
        cin>>s>>w;
        if(s>w){swap(s,w);swap(cs,cw);}
        int ans=0;
        rep(i,0,cs+1)
        {
            if(i*s>p)break;
            int tmp=i;
            int k=min(cw,(p-i*s)/w);
            tmp+=k;
            int j=min(cs-i,f/s);
            tmp+=j;
            tmp+=min(cw-k,(f-s*j)/w);
            ans=max(ans,tmp);
        }
        cout<<ans<<endl;
    }
    return 0;
}

C – Binary String Reconstruction

题意

给定一个长度为$n$的由0和1构成的字符串$w$，和一个整数$x$。

字符串$w$和字符串$s$存在这如下的变换

• 如果$w_{i+x}^{}=1$那么$s_i=1$
• 如果$w_{i-x}^{}=1$那么$s_i=1$
• 否者就为0

已知字符串$s$和$n$求字符串$w$

解题思路

我们可以从字符串$s$中的0来推测出字符串$w$中的0的位置。
然后我们还需要检验一下生成的字符串是否是答案。

时间复杂度为$O(n)$

PS：我发现有些时候用离散数学化简条件真的爽

参考代码

#include <bits/stdc++.h>
#define MEM(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,n) for (int i=a;i<n;i++)
using namespace std;
const int MAXN=(int)1e5+5;
char buf[MAXN];
int n,x;
bool ans[MAXN];
bool check()
{
    rep(i,0,n)if(buf[i]=='1'&&(i-x<0||ans[i-x])&&(i+x>=n||ans[i+x]))return false;
    return true;
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>buf;
        cin>>x;
        n=strlen(buf);
        MEM(ans,0);
        for (int i = 0; i < n; i++)
        {
            if(buf[i]=='0')
            {
                if(i+x<n)ans[i+x]=true;
                if(i-x>=0)ans[i-x]=true;
            }
        }
        if(check())rep(i,0,n){if(ans[i])cout<<'0';else cout<<'1';}
        else cout<<-1;
        cout<<endl;
    }
    return 0;
}

D – Zigzags

题意

给定一个长度为$n$的数组$a_n$。求有多少组$i,j,k,l$满足

• $1\le i<j<k<l \le n$
• $a_i=a_k$且$a_j=a_l$

解题思路

我们可以枚举$j$和$k$，然后统计$k$之后有多少个与$a_j$相同的数，$j$之前有多少个与$a_k$相同的数，然后乘起来就好了。

参考代码

#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
typedef long long ll;
using namespace std;
const int MAXN=(int)3e3+5;
ll f[MAXN][MAXN];
int a[MAXN];
int main()
{
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        rep(i,1,n+1)cin>>a[i];
        rep(i,1,n+1)
        {
            memcpy(f[i],f[i-1],sizeof(f[i]));
            f[i][a[i]]++;
        }
        ll ans=0;
        rep(i,1,n+1)rep(j,i+1,n+1)ans+=f[i-1][a[j]]*(f[n][a[i]]-f[j][a[i]]);
        cout<<ans<<endl;
    }
    return 0;
}