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

题意：

首先题目定义了两个串的相似（串的构成是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<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 #include<iostream>

 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<w，那么我们肯定是先把s1这个个东西买完之后才会去买w1那个物品。那么对于一个人p，他最多能带走p/s个s1物品，又因为题目要我们要出来这两个人最多能拿出来多少件物品，那么可能p拿走p/s个s1物品就不是最优

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

代码：

 1 #include<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 #include<iostream>

 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<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 #include<iostream>

 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<len+10;++i)

21             w[i]='2';

22         ll flag = 1;

23         for(ll i = 0; i < len; i++)

24         {

25             if (s[i] == '0')

26             {

27                 ll temp;

28                 temp = i + x;

29                 if (temp < len)

30                 {

31                     w[i + x] = '0';

32                 }

33                 temp = i - x;

34                 if (temp >= 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<stdio.h>

 2 #include<string.h>

 3 #include<algorithm>

 4 #include<iostream>

 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 }

巴特西

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

最新文章

热门文章