今天还是水一点题吧。
题1：P2249 【深基13.例1】查找https://www.luogu.com.cn/problem/P2249
输入?�n?个不超过?109109?的单调不减的（就是后面的数字不小于前面的数字）非负整数?�1,�2,…,��a1?,a2?,…,an?，然后进行?�m?次询问。对于每次询问，给出一个整数?�q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出??1?1?。
第一行?22?个整数?�n?和?�m，表示数字个数和询问次数。
第二行?�n?个整数，表示这些待查询的数字。
第三行?�m?个整数，表示询问这些数字的编号，从?11?开始编号。
输出一行，�m?个整数，以空格隔开，表示答案。
输入 #1复制
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6
输出 #1复制
1 2 -1
数据保证，1≤�≤1061≤n≤106，0≤��,�≤1090≤ai?,q≤109，1≤�≤1051≤m≤105
本题输入输出量较大，请使用较快的 IO 方式。
思路：普通二分就可以解决，这边可以先记住二分的模版，然后套用就可以了。
int binarySearch(vector<int>& nums, int target){
if(nums.size() == 0)
return -1;
int left = 0, right = nums.size() - 1;
while(left <= right){
// Prevent (left + right) overflow
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else { right = mid - 1; }
}
return -1;
}
#include<stdio.h>
#include <stdlib.h>
int a[1000005];
int b[1000005];
int n,m;
int erfen(int k,int a[])
{
int l=0,r=n-1;
while (l<r)
{
int mid=l+(r-l)/2;
if (a[mid]>=k)
{
r=mid;
}
else
{
l=mid+1;
}
}
if (a[l]==k) return l+1;
else return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;++i)
{
scanf("%d",&a[i]);
}
for (int i=0;i<m;++i)
{
scanf("%d",&b[i]);
}
for (int i=0;i<m;++i)
{
int pos=erfen(b[i],a);
printf("%d ",pos);
}
}题2：B3627 立方根https://www.luogu.com.cn/problem/B3627
给定正整数?�n，求?�33n?。答案向下取整。
仅一行，一个正整数?�n。
仅一行，一个正整数，表示?�33n?。向下取整输出。
输入 #1复制
27
输出 #1复制
3
输入 #2复制
100000
输出 #2复制
46
输入 #3复制
1000000000000000
输出 #3复制
100000
对于?100%100%?的数据，有?�≤1015n≤1015。
思路：挺离谱的一个题，用一个cbrt函数就好
#include<stdio.h>
#include <stdlib.h>
#include<math.h>
long long n;
int main()
{
scanf("%lld",&n);
long long pos=cbrt(n);
printf("%lld",pos);
}题3：P1068 [NOIP2009 普及组] 分数线划定https://www.luogu.com.cn/problem/P1068
世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A 市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的?150%150%?划定，即如果计划录取?�m?名志愿者，则面试分数线为排名第?�×150%m×150%（向下取整）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。
现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。
第一行，两个整数?�,�(5≤�≤5000,3≤�≤�)n,m(5≤n≤5000,3≤m≤n)，中间用一个空格隔开，其中?�n?表示报名参加笔试的选手总数，�m?表示计划录取的志愿者人数。输入数据保证?�×150%m×150%?向下取整后小于等于?�n。
第二行到第?�+1n+1?行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号?�(1000≤�≤9999)k(1000≤k≤9999)和该选手的笔试成绩?�(1≤�≤100)s(1≤s≤100)。数据保证选手的报名号各不相同。
第一行，有?22?个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。
从第二行开始，每行包含?22?个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。
输入 #1复制
6 3 1000 90 3239 88 2390 95 7231 84 1005 95 1001 88
输出 #1复制
88 5 1005 95 2390 95 1000 90 1001 88 3239 88
【样例说明】
�×150%=3×150%=4.5m×150%=3×150%=4.5，向下取整后为?44。保证?44?个人进入面试的分数线为?8888，但因为?8888?有重分，所以所有成绩大于等于?8888?的选手都可以进入面试，故最终有?55?个人进入面试。
思路：很简单的结构体排序，但是这里需要注意一下排序函数（cmp）的定义，其他没有含金量
#include<bits/stdc++.h>
using namespace std;
struct Number{
int paiming;
int grade;
};
bool cmp(const Number& a,const Number& b)
{
if (a.grade==b.grade)
{
return a.paiming<b.paiming;
}
else return a.grade>b.grade;
}
int main()
{
int n,m;
cin>>n>>m;
Number number[10000];
for (int i=0;i<n;++i)
{
cin>>number[i].paiming>>number[i].grade;
}
sort(number,number+n,cmp);
int numbers = min(n, int(m * 1.5));
for (int i=0;i<numbers;++i)
{
if (number[i].grade==number[i+1].grade && i==numbers-1)
{
numbers++;
}
}
cout<<number[numbers-1].grade<<" "<<numbers<<endl;;
for (int i=0;i<numbers;++i)
{
cout<<number[i].paiming<<" "<<number[i].grade<<endl;
}
}题4：P5143 攀爬者https://www.luogu.com.cn/problem/P5143
他在地形图上标记了?�N?个点，每个点?��Pi??都有一个坐标?(��,��,��)(xi?,yi?,zi?)。所有点对中，高度值?�z?不会相等。HKE 准备从最低的点爬到最高的点，他的攀爬满足以下条件：
(1) 经过他标记的每一个点；
(2) 从第二个点开始，他经过的每一个点高度?�z?都比上一个点高；
(3) HKE 会飞，他从一个点?��Pi??爬到?��Pj??的距离为两个点的欧几里得距离。即，(��?��)2+(��?��)2+(��?��)2(Xi??Xj?)2+(Yi??Yj?)2+(Zi??Zj?)2?
现在，HKE 希望你能求出他攀爬的总距离。
第一行，一个整数?�N?表示地图上的点数。
接下来?�N?行，三个整数?��,��,��xi?,yi?,zi??表示第?�i?个点的坐标。
一个实数，表示 HKE 需要攀爬的总距离（保留三位小数）
输入 #1复制
5 2 2 2 1 1 1 4 4 4 3 3 3 5 5 5
输出 #1复制
6.928
对于100%的数据，1≤�≤500001≤N≤50000，答案的范围在 double 范围内。
思路：也同样用结构体写，直接按照高度排序完，然后以此遍历相加就完事了
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
struct Weizhi{
int x;
int y;
int z;
};
bool cmp(const Weizhi &a,const Weizhi &b)
{
return a.z>b.z;
}
int main()
{
int n;
cin>>n;
Weizhi weizhi[50005];
for (int i=0;i<n;++i)
{
cin>>weizhi[i].x>>weizhi[i].y>>weizhi[i].z;
}
sort(weizhi,weizhi+n,cmp);
double dis=0.0;
for (int i=1;i<n;++i)
{
dis+=sqrt(pow((weizhi[i-1].x-weizhi[i].x),2)+pow((weizhi[i-1].y-weizhi[i].y),2)+pow((weizhi[i-1].z-weizhi[i].z),2));
}
printf("%.3lf",dis);
}题5：P1012 [NOIP1998 提高组] 拼数https://www.luogu.com.cn/problem/P1012
设有?�n?个正整数?�1…��a1?…an?，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。
第一行有一个整数，表示数字个数?�n。
第二行有?�n?个整数，表示给出的?�n?个整数?��ai?。
一个正整数，表示最大的整数
输入 #1复制
3 13 312 343
输出 #1复制
34331213
输入 #2复制
4 7 13 4 246
输出 #2复制
7424613
对于全部的测试点，保证?1≤�≤201≤n≤20，1≤��≤1091≤ai?≤109。
思路：这题主要是考虑到字符串相接最大的情况，一开始只是想到，先把字符串按从大到小排序相接就是最大，结果是错误的，应该直接用比较函数比较相接的大小，这个函数的定义第一次用
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
bool cmp(const string &a,const string &b)
{
return a+b>b+a;
}
int main()
{
int n;
cin>>n;
string s[25];
for (int i=0;i<n;++i)
{
cin>>s[i];
}
sort(s,s+n,cmp);
string sum="";
for(int i=0;i<n;++i)
{
sum+=s[i];
}
cout<<sum;
}题6：P1255 数楼梯https://www.luogu.com.cn/problem/P1255
楼梯有?�N?阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
一个数字，楼梯数。
输出走的方式总数。
输入 #1复制
4
输出 #1复制
5
思路：今天遇到的最烦的一个问题了，考虑到数据比较大，就需要用到递推和高精度一起完成，好久没写高精度，又有点忘记了，现在来重新回顾一下这里只是简单的高精度加法
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stack>//添加栈
#include<ctype.h>
#include<cstdlib>
#define pritnf printf
#define itn int
#define INF 10234567111
#define MAX 2000000
using namespace std;
#define str string
#define ll long long int
#define f float
#define ff double
//字符串类型是string ceil()向上取整，C++的正常逻辑是向下取整
int main() {
//高精度加法
//把数放到数组里面加法
// 12
// 39
// 51
// 50
// 60
// 110
string n, m; //输入两个值
cin >> n >> m;
//按照倒数放到两个数组里
int a[100] = { 0 }, b[100] = { 0 }, c[100] = { 0 };
//倒序放入
int len1 = n.size(), len2 = m.size();
for (int i = 0; i < len1; ++i) a[i] = n[len1 - 1 - i] - '0';
for (int i = 0; i < len2; ++i) b[i] = m[len2 - 1 - i] - '0';
//相加放到结果数组c中
int maxn = max(len1, len2);
for (int i = 0; i < maxn; ++i) {
c[i] += a[i] + b[i];//各个位相加 11,4
c[i + 1] = c[i] / 10;
c[i] %= 10;//如果有位置上大于10，就进位
}
//去掉前置0
maxn++;
while (c[maxn-1] == 0 && maxn > 1) maxn--;
//因为是逆序，所以需要倒着输出
for (int i = maxn - 1; i >= 0; --i) cout << c[i];
return 0;
}这一个加法是在接受到数据后，把数据翻转相加，在翻转输出得到的
而这个递推的不同，我们可以直接模拟加法的运算
a[1]=1,b[1]=2;
for (int i=3;i<=n;++i)
{
for (int j=1;j<=ns;++j)c[j]=a[j]+b[j];
for (int j=1;j<=ns;++j)
{
if (c[j]>=10)
{
c[j+1]+=c[j]/10;
c[j]%=10;
if (j+1>ns)ns++;
}
}
for (int i=1;i<=ns;++i)a[i]=b[i];
for (int i=1;i<=ns;++i)b[i]=c[i];
}直接从最小的开始加，进位就判断最大长度与当前位数，如果小了，ns就加1，后面就是简单的递推了
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int n,ns=1;
int a[5010],b[5010],c[5010];
void fibonaci()
{
a[1]=1,b[1]=2;
for (int i=3;i<=n;++i)
{
for (int j=1;j<=ns;++j)c[j]=a[j]+b[j];
for (int j=1;j<=ns;++j)
{
if (c[j]>=10)
{
c[j+1]+=c[j]/10;
c[j]%=10;
if (j+1>ns)ns++;
}
}
for (int i=1;i<=ns;++i)a[i]=b[i];
for (int i=1;i<=ns;++i)b[i]=c[i];
}
}
int main()
{
memset(a,0,sizeof (a));
memset(b,0,sizeof (b));
memset(c,0,sizeof (c));
cin>>n;
if (n<3)
{
cout<<n;
return 0;
}
fibonaci();
int idx=ns;
while (b[idx]==0 && idx>0) idx--;
for (int i=idx;i>0;--i)cout<<b[i];
return 0;
}