提高组比赛分析(1)

停更n个月，我又来了！

今天打了场模拟赛，差点就AK IOI了

废话不多说

正片开始

题目一：#1751. 第 T 个数

Description

给定一个 n(0质数。(0

Format

Input

第一行为 22 个数 n,T（含义如上题） 第二行为 n 个数，表示这个序列。

Output

如果 x 为质数，则第一行为 YES，第二行为这个数 x；

否则，第一行为 NO，第二行为这个数 x。

Samples

输入数据 1

5 2 
1 2 3 4 5

输出数据 1

YES
2

Hint

对于第 T 大的详细解释: 如果一个序列为 1 2 2 2 2 3，第 1 大为 3，第 2 大为 2，第 3 大为 2，第 4 大为 2，第 5 大为 1……第 K 小与上例相反。

另外需要注意的是，最小的质数是 2，如果小于 2 的话，请直接输出 NO。

Limitation

1s, 1024KiB for each test case.

题解：

这道题十分的简单，约等于签到题，只要排序然后计算出差值并判断它是否为质数就行了。排序用sort，判断质数函数是冲击一等奖必备技能，其他没什么难点了。

思路难度：★☆☆☆☆

程序难度：★☆☆☆☆

程序：

#include<bits/stdc++.h>
using namespace std;
long long n,k,x,a[10010];
bool p(int x){
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
			return false;
	return true;
} 
int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	x=a[n-k]-a[k-1];
	if(x>2&&p(x))
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	cout<<x; 
	return 0;
}

题目二：#1752. 聂小倩

Background

为了能逃脱姥姥的魔爪，尽快找到宁采臣，小倩在一条山路上开始了她的训练。

Description

小倩希望能在每次训练中跑得尽可能远，不过她也知道姥姥的一条规定：

女子独自进山的时间不得超过 M 秒 (1≤M≤10,000,000)。

整条山路被小倩划分成 T 个长度相同的小段(1≤T≤100,000)，并且，小倩用 Si​ 表示第 i 个小段的路况。Si​ 为 u,f,d 这3个字母之一，它们分别表示第i 个小段是上坡、平地，或是下坡。

小倩要花 U 秒(1≤U≤100) 才能跑完一段上坡路，跑完一段平地的耗时是 F 秒(1≤F≤100)，跑完一段下坡路要花 D 秒(1≤D≤100)。

注意，沿山路原路返回的时候，原本是上坡路的路段变成了下坡路，原本是下坡路的路段变成了上坡路。

小倩想知道，在能按时返回的前提下，她最多能在这条山路上跑多远。

Format

Input

第 1 行，5 个用空格隔开的整数：M,T,U,F,D。

第 2...T+1 行中，第 i+1 行为 1 个字母 Si​，描述了第 i 段山路的路况。

Output

输出一个整数，为小倩在按时回到的前提下，最多能跑到多远。

Samples

输入数据 1

13 5 3 2 1 
u 
f 
u 
d 
f

输出数据 1

3

Hint

输入说明:

小倩跑步的最大耗时为 13 秒（这么短...），她跑步的山路一共被划成 5 段。 小倩跑完一段上坡路的耗时为 3 秒，平地为 2 秒，下坡路为 1 秒。山路各段的走向如下图所示：

输出说明:

小倩跑完山路的前 3 段，然后返回，总耗时为 3+2+3+1+2+1=12 秒，只比她能在外面呆的时限少 1 秒。如果她跑得更远，就无法按时返回。

Limitation

1s, 1024KiB for each test case.

题解：

这题也比较简单，因为题目中提到了如果原来是下坡路回来时则会变成上坡路且出行要来回且相同路况(上坡，平地，下坡)的通过时间是相同的，所以就可以得出一个思路，把每一个路段来回一次的时间计入数组里并根据最多时间判断出最多能跑到哪里。虽然我这思路有些清奇，不过想到了这思路应该很容易就能写出代码了。

思路难度：★★☆☆☆

程序难度：★☆☆☆☆

程序：

#include<bits/stdc++.h>
using namespace std;
int m,t,u,f,d,a[100010],k,ans=1;
char c;
int main(){
	cin>>m>>t>>u>>f>>d;
	for(int i=1;i<=t;i++){
		cin>>c;
		if(c=='f')
			a[i]=2*f;
		else
			a[i]=u+d;
	}
	k=a[1];
	while(k<=m){
		ans++;
		k+=a[ans];
	}
	cout<<ans-1;
	return 0;
}

前两题写完了，后两题晚些更，肝作业去喽~