欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

牛客多校第三场 A-Clam and Fish【贪心】+ B-Classical String Problem【思维】

程序员文章站 2022-04-23 13:45:32
目录A-Clam and Fish题意解题思路代码B-Classical String Problem题意解题思路代码A-Clam and Fish题意链接:Clam and Fish给出 n 单位的时间,每个单位时间有四种状态,有蛤蜊/没蛤蜊, 有鱼/没鱼。0没蛤蜊没鱼1有蛤蜊没鱼2没蛤蜊有鱼3有蛤蜊有鱼事先知道这 n 个时间点的状态。每个时间点有四种可能的动作:若该时间点有鱼,则可以直接钓鱼。若该时间点有蛤蜊,则可以用该蛤蛎制作一个鱼饵。若该时间点身上有至少一个鱼...

A-Clam and Fish

题意

  • 链接Clam and Fish
  • 给出 n 单位的时间,每个单位时间有四种状态,有蛤蜊/没蛤蜊, 有鱼/没鱼。
    0没蛤蜊没鱼
    1有蛤蜊没鱼
    2没蛤蜊有鱼
    3有蛤蜊有鱼
    事先知道这 n 个时间点的状态。每个时间点有四种可能的动作:
  1. 若该时间点有鱼,则可以直接钓鱼。

  2. 若该时间点有蛤蜊,则可以用该蛤蛎制作一个鱼饵。

  3. 若该时间点身上有至少一个鱼饵,则可以用一个鱼饵钓一条鱼,钓完后就少
    了一个鱼饵。

  4. 什么事都不做。

    请问最多可以钓多少条鱼。

解题思路

  • 贪心:只要有鱼就空手抓鱼 没有鱼有鱼饵就用鱼饵抓鱼 没有鱼没有鱼饵有蛤蜊就做鱼饵
  • 重点(现场没考虑到):最后若鱼饵有剩余x,x>=2,就要花一半的做鱼饵的时间来钓鱼,可得x/2条鱼

代码

#include<stdio.h>
const int N=2e6+6;
int t,n;
char s[N];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d\n%s",&n,s);
		int fish=0,er=0;
		for(int i=0;i<n;i++)
		{
			if(s[i]=='2'||s[i]=='3')fish++;
			else if(s[i]=='1')er++;
			else if(s[i]=='0'&&er>0)
			{
				fish++;er--;
			}
		}
		if(er>1)fish+=er/2;
		printf("%d\n",fish);
	}
	return 0;
}

B-Classical String Problem

题意

  1. ‘A’ : 询问第 x 个字符。
  2. ‘M’ : x>0,把最左边的 x 个字符搬到最右边;x<0,把最右边 x 个字符搬到最左边。

解题思路

  • 想像成字符串是头尾接在一起的 ,只需维护一个指针指向当前第一个字符的位置,就能以 O(1) 的时间复杂度进行每个操作。
  • 以 Sample 为例
    • 初始时指针在 n 的前面 |nowcoder
    • 操作 1 询问指针右边第 1 个字符,答案是 n • 操作 2 把 4 个字符搬到右边,相当于把指针向右移 4 个字符 nowc|oder
    • 操作 3 询问指针右边第 6 个字符,答案是 o • 操作 4 把右边 3 个字符搬到右边,相当于把指针向左移 3 个字符 n|owcoder

代码

#include<stdio.h>
#include<string.h>
using namespace std;
const int N=2e6+6;
int n,pos;
char s[N],ch;
int main()
{
	scanf("%s\n",s);
	int len=strlen(s),head=0;
	scanf("%d\n",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%c %d\n",&ch,&pos);
		if(ch=='M')
		{
			if(pos>0)head=(head+pos)%len;
			else if(pos<=0)head=(head+len+pos)%len;
		}
		else if(ch=='A') printf("%c\n",s[(head+pos-1)%len]);
	}
	return 0;
}

本文地址:https://blog.csdn.net/zjllll123/article/details/107606334

相关标签: # 7.18第三场