A. String Similarity
题目链接
题目原文
题目大意
定义两个字符串相似：两个字符串中至少有一个位置的值相同。
现在给出一个长度为2n−1的字符串s，现在让你构造一个长度为n的字符串，使得这个字符串与s的所有长度为n的子串都相似。
解题思路
可以发现，s的所有长度为n的子串都有一个公共位置s[n]
解法
直接输出n个s[n]就行，这个答案一定与所有子串都相似。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n;
char str[maxn];
int main()
{
#ifdef lemon
freopen("A.txt","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",str+1);
for(int i=1;i<=n;i++) printf("%c",str[n]);
printf("\n");
}
return 0;
}
|
B. RPG Protagonist
题目链接
题目原文
题目大意
现在有两个人，一个人可以带p单位的重量，另一个人可以带f单位的重量。现在有两种物品，给出两种物品单件的重量以及两种物品的数量，求这两个人最多一共带走多少物品（数量最多）。
解题思路
可以发现，我们一定是采取贪心的策略。
我们先考虑一个人，那一定是先尽可能地选重量小的装，这样一定能够装更多数量。
那其实我们只需要求出第一个人选剩下的数量，第二个人能装的数量可以直接O(1)算出来。
解法
直接枚举第一个人选了多少个第一种物品，然后我们根据贪心策略，我们一定是让第一个人尽可能地装满，然后这个时候我们就得到了两种物品剩下的数量，这个时候就按照前面说的直接先选小的的策略进行选择即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T;
long long p,f,cnts,cntw,s,w,ans;
int main()
{
#ifdef lemon
freopen("B.txt","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
ans=0;
scanf("%lld%lld",&p,&f);
scanf("%lld%lld",&cnts,&cntw);
scanf("%lld%lld",&s,&w);
for(long long i=0;i<=cnts;i++)
{
if(i*s>p) break;
long long resp=p-i*s;
long long t2=resp/w;
if(t2>cntw) t2=cntw;
long long t1=i+t2;
long long t3=cntw-t2;
if(s<=w)
{
long long t4=f/s;
if(t4>cnts-i) t4=cnts-i;
long long temp=f-t4*s;
long long t6=temp/w;
if(t6>t3) t6=t3;
long long t5=t4+t6;
ans=max(ans,t1+t5);
}
else
{
long long t4=f/w;
if(t4>t3) t4=t3;
long long temp=f-t4*w;
long long t6=temp/s;
if(t6>cnts-i) t6=cnts-i;
long long t5=t4+t6;
ans=max(ans,t1+t5);
}
}
printf("%lld\n",ans);
}
return 0;
}
|
C. Binary String Reconstruction
题目链接
题目原文
题目大意
对于一个原串s，现在通过以下规则构建串t。
对于一个位置i，如果s[i−x]存在并且s[i−x]=1或者s[i+x]存在并且s[i+x]=1，那么t[i]就为1，否则t[i]为0.
现在给出串t，让你还原原串s.
解题思路
直接从前往后依次贪心还原即可，如果有冲突的就无解。注意0是要求s前后两个位置都为0.
解法
如上。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,x;
char str[maxn];
int ans[maxn];
int main()
{
#ifdef lemon
freopen("C.txt","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%s%d",str+1,&x);
int n=strlen(str+1);
bool flag=false;
for(int i=1;i<=n;i++) ans[i]=-1;
for(int i=1;i<=n;i++)
{
if(str[i]=='1')
{
bool f=false;
if(i-x>=1)
{
if(ans[i-x]==1) f=true;
else if(ans[i-x]==-1) ans[i-x]=1,f=true;
}
if(!f&&i+x<=n)
{
if(ans[i+x]==1) f=true;
else if(ans[i+x]==-1) ans[i+x]=1,f=true;
}
if(!f) flag=true;
}
else
{
bool f=true;
if(i-x>=1)
{
if(ans[i-x]==-1) ans[i-x]=0;
if(ans[i-x]==1) f=false;
}
if(i+x<=n)
{
if(ans[i+x]==-1) ans[i+x]=0;
if(ans[i+x]==1) f=false;
}
if(!f) flag=true;
}
}
for(int i=1;i<=n;i++) if(ans[i]==-1)
{
int f=1;
if(i-x>=1&&str[i-x]=='0') f=0;
if(i+x<=n&&str[i+x]=='0') f=0;
ans[i]=f;
if(f==0)
{
if(i-x>=1&&str[i-x]=='1') flag=true;
if(i+x<=n&&str[i+x]=='1') flag=true;
}
if(f==1)
{
if(i-x>=1&&str[i-x]=='0') flag=true;;
if(i+x<=n&&str[i+x]=='0') flag=true;
}
}
if(flag) {printf("-1\n");continue;}
for(int i=1;i<=n;i++) printf("%d",ans[i]);printf("\n");
}
return 0;
}
|
D. Zigzags
题目链接
题目原文
题目大意
给出一个数组，求满足以下条件的四元组(i,j,k,l)的个数。
1⩽i<j<k<l⩽nai=akandaj=al
解题思路
先前缀和求出各数字出现的次数，再枚举j和k的位置，这时两个数字都是确定的，然后直接O(1)算出j前a[k]的数量与k后a[j]的数量，相乘累加答案即可。
解法
如上。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3005;
int T,n,a[maxn],cnt[maxn][maxn];
int main()
{
#ifdef lemon
freopen("D.txt","r",stdin);
#endif
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for(int j=1;j<=n;j++)
{
cnt[i][j]=cnt[i-1][j];
}
cnt[i][a[i]]++;
}
long long ans=0;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
ans+=(long long)cnt[i-1][a[j]]*(long long)(cnt[n][a[i]]-cnt[j][a[i]]);
}
}
printf("%lld\n",ans);
}
return 0;
}
|
