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;
}