• 洛谷刷题C语言：USPON、ZBROJ、KARTE、最急救助、可持久化动态仙人掌的直径问题

    记录洛谷刷题C语言

    一、[COCI2010-2011#6] USPON

    题目背景

    Tomislav 去爬山。

    题目描述

    他所走的山路可以看做一个长度为 n n n 的数字序列 P i P_i Pi​， P i P_i Pi​ 表示位置 i i i 的高度为 P i P_i Pi​。

    从低处往高处走一段连续的高度严格递增的山路称为一次爬升。

    为了锻炼身体，他想走一段落差尽量大的爬升。

    一段山路的落差定义为这段山路的结束点与起始点的差。

    你需要求出他走一段山路所能达到最大的落差是多少。

    输入格式

    输入第一行一个整数 n n n，表示山路的长度。

    第二行 n n n 个整数 P i P_i Pi​，表示位置 i i i 的高度为 P i P_i Pi​。

    输出格式

    输出一行一个整数，表示最大的落差。

    如果整条山路不包含任何的爬升，则输出 0。

    样例 #1

    样例输入 #1

    5
1 2 1 4 6

    • 1
    • 2

    样例输出 #1

    5

    • 1

    样例 #2

    样例输入 #2

    8
12 20 1 3 4 4 11 1

    • 1
    • 2

    样例输出 #2

    8

    • 1

    样例 #3

    样例输入 #3

    6
10 8 8 6 4 3

    • 1
    • 2

    样例输出 #3

    0

    • 1

    提示

    数据规模与约定

    对于 100 % 100\% 100% 的数据，保证 1 ≤ n ≤ 1000 1\le n\le 1000 1≤n≤1000， 1 ≤ P i ≤ 1000 1\le P_i\le 1000 1≤Pi​≤1000。

    说明

    题目译自 COCI2010-2011 CONTEST #6 T2 USPON。

    代码如下：

    
#include
#include
#include
#include 

int MAXN=1010;
int n;
int a[1010],ans;
int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}
int main()
{
	scanf("%d",&n);//输入n 
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入高度 
	for(int left=1;left<=n;left++)//枚举左端点 
		for(int right=left+1;right<=n;right++)//枚举右端点 
		{
			if(a[right]<=a[right-1]){ans=max(ans,a[right-1]-a[left]);break;}
			//如果不是严格大于a[right-1]，那么更新答案并break 
			if(right==n){ans=max(ans,a[right]-a[left]);break;}
			//特判如果已经枚举到n，那么更新答案 
		}	
	printf("%d\n",ans);//输出 
}




    • 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

    二、[COCI2010-2011#3] ZBROJ

    题目描述

    老师给了 Perica 两个数 a , b a, b a,b，Perica 将他们抄在了笔记本上，并要算出他们的和。

    在抄写过程中，Perica 可能会将 a , b a, b a,b 中的数字 6 6 6 错抄成数字 5 5 5，也可能将数字 5 5 5 错抄成数字 6 6 6，当然也可能不抄错。

    给定 a , b a, b a,b，请求出 Perica 算出的和最小和最大分别是多少。

    输入格式

    输入只有一行两个整数，分别表示 a a a 和 b b b。

    输出格式

    输出一行两个整数，表示最小可能的和以及最大可能的和。

    样例 #1

    样例输入 #1

    11 25

    • 1

    样例输出 #1

    36 37

    • 1

    样例 #2

    样例输入 #2

    1430 4862

    • 1

    样例输出 #2

    6282 6292

    • 1

    样例 #3

    样例输入 #3

    16796 58786

    • 1

    样例输出 #3

    74580 85582

    • 1

    提示

    数据规模与约定

    对于全部的测试点，保证 1 ≤ a , b ≤ 1 0 6 1 \leq a, b \leq 10^6 1≤a,b≤106。

    说明

    题目译自 COCI2010-2011 CONTEST #3 T2 ZBROJ。

    代码如下：

    #include
#include
#include
#include 

int main()
{
    int a,b,s1,s2;
    scanf("%d%d",&a,&b); 
    int value=a+b,minvalue=a+b,maxvalue=a+b;
    int cnt=1;//cnt是枚举当前位,1表示个位
	while(a)//当a!=0时
	{
		int x=a%10;//取a的最末位
		if(x==5) maxvalue+=cnt;//如果是5就把maxvalue加当前位数
		if(x==6) minvalue-=cnt;//如果是6就把minvalue减当前位数
		a/=10;//去掉a的最末位
		cnt*=10;//进位
	}
	cnt=1;
	while(b)
	{
		int x=b%10;
		if(x==5) maxvalue+=cnt;
		if(x==6) minvalue-=cnt;
		b/=10;
		cnt*=10;
	}
	printf("%d %d",minvalue,maxvalue);
    return 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

    三、[COCI2015-2016#1] KARTE

    题目描述

    这里有一堆牌，可惜它们似乎不全。

    您需要找出每种花色缺失的张数。

    如果有相同的扑克牌，请输出 GRESKA。

    输入格式

    您要读取的是一个字符串 s s s，每三个字符为一张扑克牌。

    对于每一张扑克牌：

    • 第一位为花色，用 P，K，H，T 表示，且输出也是这个顺序。
    • 接下来两位，为这张牌的点数，个位数会在十位补零。

    输出格式

    如果有相同的扑克牌，请输出 GRESKA。

    否则按 P，K，H，T 的顺序，输出该花色缺的牌数。

    样例 #1

    样例输入 #1

    P01K02H03H04

    • 1

    样例输出 #1

    12 12 11 13

    • 1

    样例 #2

    样例输入 #2

    H02H10P11H02

    • 1

    样例输出 #2

    GRESKA

    • 1

    样例 #3

    样例输入 #3

    P10K10H10T01

    • 1

    样例输出 #3

    12 12 12 12

    • 1

    提示

    【样例解释】

    样例 1 解释

    有一张花色为 P 的牌，一张花色为 K 的牌，两张花色为 H 的牌。

    样例 2 解释

    这里有两张 H02 ，所以输出 GRESKA。

    【数据范围及限制】

    对于 100 % 100\% 100% 的数据，保证 1 ≤ ∣ s ∣ ≤ 1 0 3 1\le \lvert s\rvert\le 10^3 1≤∣s∣≤103 且 s s s 中仅含有数字与 P，K，H，T，每张牌的点数 ∈ [ 1 , 13 ] \in [1,13] ∈[1,13] 。

    【说明】

    本题满分 50 50 50 分。

    本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T1 KARTE。

    代码如下：

    #include
#include
#include
#include 

int main()
{
    char num[10001];
    scanf("%s",&num);
    
    int len = strlen(num);
    int P[14], K[14],H[14],T[14];
    for(int i = 1;i < 14;i++)
    {
    	P[i] = 0;
    	K[i] = 0;
		H[i] = 0;
    	T[i] = 0;
	}
	int j = 0;
	while(j != len)
	{
		if(num[j] == 'P')
		{
			int a = ((int)num[j+1]-48)*10 + (int)num[j+2] -48;
	
			P[a]++;
			j= j+3;
		}
		else if(num[j] == 'K')
		{
			int b = ((int)num[j+1]-48)*10 + (int)num[j+2] -48;
	
			K[b]++;
			j= j+3;
		}
		else if(num[j] == 'H')
		{
			int c = ((int)num[j+1]-48)*10 + (int)num[j+2] -48;
	
			H[c]++;
			j= j+3;
		}
		else if(num[j] == 'T')
		{
			int d = ((int)num[j+1]-48)*10 + (int)num[j+2] -48;
			T[d]++;
			j= j+3;
		}
	}
	int n1 = 0,n2 =0,n3 = 0,n4 = 0;
	for(int i = 1;i < 14;i++)
	{
		if(P[i] > 1||K[i] > 1||H[i] > 1||T[i] > 1)
		{
			printf("GRESKA\n");
			return 0;
		}

		if(P[i] == 0)
		{
			n1++;
		}
		if(K[i] == 0)
		{
			n2++;
		}
		if(H[i] == 0)
		{
			n3++;
		}
		if(T[i]== 0)
		{
			n4++;
		}
		
		
	}
	
	printf("%d %d %d %d\n",n1,n2,n3,n4);
	
}




    • 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
    • 83
    • 84
    • 85

    四、[NOI Online #3 入门组] 最急救助

    题目描述

    救助中心每天都要收到很多求救信号。收到求救信号后，救助中心会分析求救信号，找出最紧急的求救者给予救助。

    求救信号是一个由小写英文字母组成的字符串，字符串中连续三个字符依次组成sos的情况越多（即包含子串sos的数目越多），代表着求救者情况越紧急。

    现在请你帮助救助中心找出最紧急的求救者。注意字符串中包含的sos可以有重叠，例如sosos算作包含 2 2 2 个sos。

    输入格式

    从标准输入读入数据。

    第一行一个整数 n n n，表示求救者的数目。

    接下来有 2 × n 2\times n 2×n 行，每行一个由小写英文字母组成的字符串。这 2 × n 2\times n 2×n 行中，第 2 × i − 1 2\times i-1 2×i−1（ 1 ≤ i ≤ n 1\le i\le n 1≤i≤n）行的字符串表示第 i i i 个求救者的名字，第 2 × i 2\times i 2×i 行的字符串表示第 i i i 个求救者的求救信号。

    输出格式

    输出到标准输出。

    输出共两行，第一行是最紧急求救者的名字。如果最紧急求救者有多个，则按照输入的顺序将他们的名字依次输出，相邻两个名字间用空格分隔。

    第二行一个整数，表示最紧急求救者的求救信号中包含有多少个sos子串。

    样例 #1

    样例输入 #1

    2
adam
ineedhelpsosineedhelpsos
mark
ineedmorehelpsoshelpmesossoshelpme

    • 1
    • 2
    • 3
    • 4
    • 5

    样例输出 #1

    mark
3

    • 1
    • 2

    样例 #2

    样例输入 #2

    3
susan
sosososososos
jack
sossossossos
allen
soshelpsossossossossos

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    样例输出 #2

    susan allen
6

    • 1
    • 2

    提示

    数据规模与约定

    • 对于 10 % 10\% 10% 的数据， n = 1 n=1 n=1。
    • 对于所有数据， 1 ≤ n ≤ 100 1 \leq n\le 100 1≤n≤100，求救者名字长度不超过 20 20 20，求救信号长度不超过 200 200 200。

    代码如下：

    #include
#include
#include
#include 

int max(int x,int y)
{
	return (x>y)?x:y; 
} 
struct 
{
	char name[30];//求救者名字 
	char ql[220];//求救信号长度
	int qm;//这个人的求救信号长度 
	int lgh;//这个人的求救信号中含有几个'sos' 
}a[110];

int N;
int main()
{
	//freopen("save.in","r",stdin);
	//freopen("save.out","w",stdout);
	scanf("%d%d",&N);
	int i,j,t;
	t=0;
	for(i=1;i<=N;i++)//读入数据 
	{
		scanf("%s",a[i].name);
		scanf("%s",a[i].ql);
		a[i].qm=strlen(a[i].ql);
		a[i].lgh=0;
	} 
	for(i=1;i<=N;i++) 
	{
		for(j=2;j<=a[i].qm;j++)
		{
			if(a[i].ql[j]=='s'&&a[i].ql[j-1]=='o'&&a[i].ql[j-2]=='s')
			{
				a[i].lgh++;
			}
		}
	} 
	for(i=1;i<=N;i++)
	{
		t=max(a[i].lgh,t);
	}
	for(i=1;i<=N;i++)
	{
		if(a[i].lgh==t)
		{
			printf("%s ",a[i].name);
		}
	}
	printf("\n%d\n",t);
}

    • 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

    五、可持久化动态仙人掌的直径问题

    题目背景

    众所周知，一场考试需要一道签到题。

    题目描述

    给定 n , m n,m n,m，求有多少个正整数 x x x，使得 x m ≤ n x^m\le n xm≤n。

    输入格式

    一行两个正整数 n , m n,m n,m。

    输出格式

    一个整数表示正整数 x x x 的个数。

    样例 #1

    样例输入 #1

    5 2

    • 1

    样例输出 #1

    2

    • 1

    提示

    对于 25 % 25\% 25% 的数据满足 m = 1 m=1 m=1；
    对于 50 % 50\% 50% 的数据满足 n ≤ 1 0 6 n\le 10^6 n≤106；
    对于 100 % 100\% 100% 的数据满足 1 ≤ n , m ≤ 1 0 9 1\leq n,m\le 10^9 1≤n,m≤109。

    upd 2022.7.24 \text{upd 2022.7.24} upd 2022.7.24：新增加一组 Hack 数据。

    代码如下：

    #include
#include
#include
#include 

int main()
{
	long long n,m;
	scanf("%lld%lld",&n,&m);
	
    printf("%.0f",pow(n,1.0/m));
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    SpringCloud Alibaba之Sentinel流量治理组件学习笔记
    Java面试——并发问题（sleep、synchronized、volatile等）
    Linux- 由映射文件I/O问题引出的SIGBUS & 空洞文件（Sparse File）
    Linux 安装Harbor镜像仓库私服
    腾讯云数据库TDSQL-大咖论道 | 基础软件的过去、现在、未来
    Intel RealSense D435i与IMU标定用于vins-fusion
    kubernetes-Service详解
    dble安装zk及配置mysql主从模式，在已有mysql存在数据升级mysql配置
    nodejs 简介
    第一个Mybatis程序
  • 原文地址：https://blog.csdn.net/weixin_62529383/article/details/126335435