记录洛谷刷题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
5
样例 #2
样例输入 #2
8
12 20 1 3 4 4 11 1
样例输出 #2
8
样例 #3
样例输入 #3
6
10 8 8 6 4 3
样例输出 #3
0
提示
数据规模与约定
对于 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<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
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);//输出
}
二、[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
36 37
样例 #2
样例输入 #2
1430 4862
样例输出 #2
6282 6292
样例 #3
样例输入 #3
16796 58786
样例输出 #3
74580 85582
提示
数据规模与约定
对于全部的测试点，保证 1 ≤ a , b ≤ 1 0 6 1 \leq a, b \leq 10^6 1≤a,b≤106。
说明
题目译自 COCI2010-2011 CONTEST #3 T2 ZBROJ。
代码如下：
#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
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;
}
三、[COCI2015-2016#1] KARTE
题目描述
这里有一堆牌，可惜它们似乎不全。
您需要找出每种花色缺失的张数。
如果有相同的扑克牌，请输出 GRESKA。
输入格式
您要读取的是一个字符串 s s s，每三个字符为一张扑克牌。
对于每一张扑克牌：
- 第一位为花色，用
P，K，H，T表示，且输出也是这个顺序。 - 接下来两位，为这张牌的点数，个位数会在十位补零。
输出格式
如果有相同的扑克牌，请输出 GRESKA。
否则按 P，K，H，T 的顺序，输出该花色缺的牌数。
样例 #1
样例输入 #1
P01K02H03H04
样例输出 #1
12 12 11 13
样例 #2
样例输入 #2
H02H10P11H02
样例输出 #2
GRESKA
样例 #3
样例输入 #3
P10K10H10T01
样例输出 #3
12 12 12 12
提示
【样例解释】
样例 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<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
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);
}
四、[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
mark
3
样例 #2
样例输入 #2
3
susan
sosososososos
jack
sossossossos
allen
soshelpsossossossossos
样例输出 #2
susan allen
6
提示
数据规模与约定
- 对于 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<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
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);
}
五、可持久化动态仙人掌的直径问题
题目背景
众所周知，一场考试需要一道签到题。
题目描述
给定 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
2
提示
对于 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<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int main()
{
long long n,m;
scanf("%lld%lld",&n,&m);
printf("%.0f",pow(n,1.0/m));
return 0;
}