Educational Codeforces Round 94 (Rated for Div. 2) String Similarity、RPG Protagonist、Binary String Reconstruction、Zigzags 思维

阅读原文时间：2023年07月08日阅读：2

题意：

首先题目定义了两个串的相似（串的构成是0、1），如果两个串存在对于一个下标k，它们的值一样，那么这两个串就相似

然后题目给你一个长度为2n-1的串，我们设下标从1开始，那么[1,n],[2,n+1],[3,n+2]…[n,2n-1]每一个都是一个长度为n的串，你需要找出来长度为n的串，使得这个串和[1,n],[2,n+1],[3,n+2]…[n,2n-1]这些串都相似****

题解：

你会发现，只需要输出原长度为2n-1串的下标1，3，5，7….（我们设串的下标从1开始），因为这样输出的话，那么我们构成的这个新串的第i位就和第i个串的第i位相同

代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 const int maxn=2e3+10;
7 double dp[maxn];
8 int main()
9 {
10 int t;
11 scanf("%d",&t);
12 while(t--)
13 {
14 int n;
15 char s[maxn];
16 scanf("%d",&n);
17 scanf("%s",s);
18 for(int i=0;i<2*n-1;i+=2)
19 {
20 printf("%c",s[i]);
21 }
22 printf("\n");
23 }
24 return 0;
25 }

题目链接：RPG Protagonist

题意：

两个人中一个人可以带p单位的东西，另一个可以带f单位的东西。一共有两种东西，一种物品s1占用s单位空间，这种物品有cnts个；另一种物品w1占用w单位空间，这种物品有cntw个。你需要找出来这两个人一共最多能带出来多少个东西

题解：

我们假设s

我们可以枚举p/s，枚举p拿走多少件s1物品，那么p剩下的空间就去拿w1物品。然后f肯定是拿走剩下的s1物品，然后剩余空间才去拿w1物品

代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int maxn=2e3+10;
8 int main()
9 {
10 ll t;
11 scanf("%lld", &t);
12 while (t--)
13 {
14 ll p, f, cnts, cntw, s, w;
15 scanf("%lld%lld",&p,&f);
16 scanf("%lld%lld",&cnts,&cntw);
17 scanf("%lld%lld",&s,&w);
18 ll maxx = min(p / s, cnts), ans = 0;
19 for (ll i = 0; i <= maxx; i++)
20 {
21 //��һ��
22 ll cntss = cnts - i;
23 ll sum=i;
24 ll getw = min(cntw, (p - i * s) / w);
25 ll cntww = cntw;
26 cntww -= getw;
27 sum += getw;
28
29
30 if (s <= w) //�ڶ��
31 {
32 ll ans = min(cntss, f / s);
33 ll temp = f - ans * s;
34 ll ans2 = min(cntww, temp / w);
35 sum += ans + ans2;
36 }
37 else
38 {
39 ll ans = min(cntww, f / w);
40 ll temp = f - ans * w;
41 ll ans2 = min(cntss, temp / s);
42 sum += ans + ans2;
43 }
44 ans = max(sum, ans);
45 }
46 printf("%lld\n", ans);
47 }
48 return 0;
49 }
50

题目链接：Binary String Reconstruction

题意：

给你一个数组w，由0/1构成，你有一个数组v，对于位置i，如果w[i+x]这个存在且w[i+x]==1，那么v[i]=1

或者对于位置i，如果w[i-x]这个存在且w[i-x]==1，那么v[i]=1

否则，v[i]=0

现在给你v数组，让你求出来w数组并输出，如果w数组不存在输出-1

题解：

先通过v数组中值为0的位置，然后确定w数组的一些位置的值，然后再去判断1。没什么说的，模拟

代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int maxn=2e3+10;
8 char s[100010];
9 char w[100010];
10 int main()
11 {
12 ll t;
13 scanf("%lld",&t);
14 while(t--)
15 {
16 ll x;
17 scanf("%s", s);
18 scanf("%lld", &x);
19 ll len=strlen(s);
20 for(ll i=0;i= 0)
35 {
36 w[i - x] = '0';
37 }
38 }
39 }
40 for(ll i = 0; i < len; i++) 41 { 42 ll pos,flagg=0; 43 if (s[i] == '1') 44 { 45 flagg=0; 46 pos = i + x; 47 if (pos < len) 48 { 49 if (w[i + x] == '1' || w[i + x] == '2') 50 flagg++; 51 } 52 pos = i - x; 53 if(pos >= 0)
54 {
55 if(w[i - x] == '1' || w[i - x] == '2')
56 flagg++;
57 }
58 }
59 else
60 flagg=1;
61 if(!flagg)
62 {
63 flag=0;
64 break;
65 }
66 }
67 if(flag)
68 {
69 for (ll i = 0; i < len; i++)
70 {
71 if (w[i] == '2')
72 printf("1");
73 else printf("%c",w[i]);
74 }
75 printf("\n");
76 }
77 else
78 printf("-1\n");
79 }
80 return 0;
81 }

题目链接：Zigzags

题意：

给你一个长度为n的数组v，你需要找出来i,j,k,l这四个下标，他们要满足v[i]==v[k]且v[j]==v[l]

找出i，j，k，l四元组的四元组的数量输出

题解：

我们可以枚举k，然后k的位置确定了之后我们先记录一下[k+1,n]这些下标对应元素出现数量。然后再去枚举i元素在k之前出现的位置。并进行记录

具体看代码

代码：

1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef long long ll;
7 const int maxn=3e3+10;
8 int v[maxn],num[maxn];
9 int main()
10 {
11 int t;
12 scanf("%d", &t);
13 while (t--)
14 {
15 int n;
16 scanf("%d",&n);
17 for(int i=1;i<=n;++i) 18 { 19 scanf("%d",&v[i]); 20 } 21 int sum=0; 22 for(int i=1;i<=n;++i) //枚举k的位置 23 { 24 int ans=0; 25 memset(num,0,sizeof(num)); 26 for(int j=i+1;j<=n;++j) 27 { 28 num[v[j]]++; 29 } 30 for(int j=i-1;j>=1;--j)
31 {
32 if(v[j]==v[i])
33 {
34 sum+=ans;
35 }
36 ans+=num[v[j]];
37 }
38 }
39 printf("%d\n",sum);
40 }
41 return 0;
42 }