2021级预备队周赛 (I) - STL, 枚举以及二分题目数7

目录

前言

一、做题顺序

二、不划水了好好做题

1.最长连号

         2.明明的随机数

3.奇怪的函数

4.第k小整数

5 .排队接水

6 拼数

7 字符串哈希

 总结



前言

题目跳转2021级预备队周赛 (I) - STL, 枚举以及二分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本蒟蒻听说今天下午要打周赛,再结合前一天晚上打卡记录,发现这周的我貌似有点水阿(打卡机制简直太欺负材料院天天都是专业课还兼职干班长的牛马

赛前还有一个小时,打开网易云,播放金刚经(金刚经yyds),果断听到还有一分钟开赛才意识到,手忙脚乱,,,

一、做题顺序

         因为没想好正文该写点啥于是决定先水一行为敬

          我好像又知道该写点啥了,补上补上:

蒟蒻的做题顺序是D E A B F G C(因为太菜了所以决定柿子先挑软的捏

其实做完E就打算回头往前做结果C那个奇怪的函数第一眼就觉得好奇怪吓的果断跳过

二、不划水了好好做题

1.最长连号

  题目跳转:P1420 最长连号 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

      签到题嘛,看我三分钟A了它,三分钟后GG送走

题目描述:在一堆数字中寻找一段连续最长上升序列输出这个最长数列的个数。

 第一眼:让我做最长上升子序列?这个简单,啪嗒啪嗒写出来了

第二眼:还需要数字是连续的(123或者234这种,135就是错的)也不难,稍加修改也能做

第三眼:为啥样例过不去,,等等我是不是看错题了,我勒个去(至此浪费了一堆时间)

(他急了他急了,数字规模不大,还浪费了一堆时间,看我大力出奇迹)

源代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=1050;
int a[maxn];
int b[maxn];
int n;
int main(){
    int ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		int js=1,w=i;
		for(int j=i+1;j<=n;j++)
		   if(a[j]!=a[w]+1)break;
		   else{
		   	w=j;
		   	js++;
		   }
		ans=max(ans,js);
	}
	
	printf("%d",ans);
}
	

大力出奇迹,看我暴力过他

如果数据规模可以借用差分约束的思想(本蒟蒻只会想大力出奇迹)

(求求下次一定要仔细读题不然咋挂掉的都,,,呜呜呜)


2.明明的随机数

题目跳转:P1059 [NOIP2006 普及组] 明明的随机数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:输入n个数字,将他们排序去重

直接借用函数解决(快乐到起飞)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int n;
vector <int> a;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	a.erase(unique(a.begin(),a.end() ),a.end());
	printf("%d",a.size());
	cout<<'\n';
	for(int i=0;i<a.size();i++)
	   printf("%d ",a[i]);
}
	

3.奇怪的函数

题目跳转P2759 奇怪的函数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

嗯,确实很奇怪,扫了一眼果断开溜,本蒟蒻多看一眼去思考的想法都没有

题目描述:输入一个二十亿以内数字n代表一个数字的位数,问如果数字x的x次方可以有这么多位,x是多少

x^x=10^(n-1)

那很容易想到同时取对数(容易到我完全没想到

于是乎就有 xlogx=n-1

logx=(n-1)/x

x=10^((n-1)/x)

就变成了算10的多少次方

再然后,奇怪的东西登场了

pow!!!

可以直接计算次方的函数(不需要for循环算喽

pow(数字x,(多少次方));    (中间逗号好不要忘了)

写一个函数判断

那剩下的问题就是在二十亿里面找一个数字就行,我们很容易想到二分

#include <iostream>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
int n;
bool check(int x)
{
    return x>=floor(pow(10,(n-1)*1.0/x)+0.5);
}

int main()
{
    
    cin>>n;
    int l=1,r=0x3f3f3f3f;
    int mid;
    while (l<r)
    {
        mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
    
}

注意比较需要四舍五入不能用int粗暴 ,不然会全WA掉

写到这里忽然意识到其实这题我也能做,,,但怂怂子一个比赛时间内没想那么多只想着打表混分,,,汝呀,破釜沉舟的勇气呢


4.第k小整数

题目跳转P1138 第k小整数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:有n个数将他们排序,除去相同的输出第k小的作为答案

和ACwing上面的有差别,多了一个去重环节。于是乎排序去重输出就有答案了,如果不需要去重的话,priority也是一个不错的选择(其实这题也可以这么做应该时间效率可以更高)

另外千万别忘了写如果没有答案的情况,不然只会有七十分,别问我怎么知道的 qwq

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
int n,k;
vector <int> a;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		a.push_back(x);
	}
	sort(a.begin(),a.end());
	a.erase(unique(a.begin(),a.end() ),a.end());
	if(k>a.size())
	   cout<<"NO RESULT";
	else
	   cout<<a[k-1];
}
	

 

5 .排队接水

题目跳转P1223 排队接水 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:n个人接水,一个人接水其他人都要等,问平均等待时间最短是多少

直接贪心就行,速度麻溜的先接,速度慢的后接,大家等的时间都少

这么说的好像很简单,但是,sort比较一定要注意

虽然说每个数字可以是小于等于前一个数字,但是如果存在等于的情况的话,两个接水时间相同的同学可能会互换位置,于是乎就会有一个点WA掉(也别问我是怎么知道的)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=1050;
struct node{
	int x,y;//时间 编号 
}a[maxn];
int n;
bool cop(node X,node Y){
	if(X.x<Y.x)return true;
	 return false;
}
double ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
	   scanf("%d",&a[i].x);
	   a[i].y=i;
    }
	sort(a+1,a+n+1,cop);
	int z=n-1;
	for(int i=1;i<=n;i++){
		printf("%d ",a[i].y);
		ans+=a[i].x*z;
		z--;
	}
	cout<<'\n';
	printf("%.2f",ans/n);
	
}

 

6 拼数

题目跳转:P1012 [NOIP1998 提高组] 拼数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:有n个数字,将他们按照字典序的顺序输出(如果我第一遍就想到了何至于,,)

数字的排序,,我的第一反应,也不是不能做,看我纯暴力模拟过他(二*想法

于是乎,吭哧吭哧写了一个函数用来判断两个数字的大小

感觉不靠谱又判断数字长度等等等

two thousand years later,,,

卡在bug里面自闭了

本来想要不干脆重构代码,然后灵光一闪

等等,字典序?

我丢,string直接比较不久拉倒了

很快就,,A了 (天知道我砸了多少时间在里面)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
const int maxn=200;
int n;
string a[maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
	    cin>>a[i];
	}
    for(int i=1;i<=n;i++)
       for(int j=i+1;j<=n;j++){
            if(a[j]+a[i]>a[i]+a[j]){
                swap(a[j],a[i]);
            }
        }
    for(int i=1;i<=n;i++)
      cout<<a[i];
}

7 字符串哈希

题目跳转:P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述:找出有多少个不一样的字符串

这题有手就行(其实是题解写烦了不想写了要划水)

一个map函数一对应,轻松搞定

其实解决方案还有很多,但不得不说map是真的香(暴力模拟是一种愚蠢至极的做法会超时的·)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
map<string,int> M;
int n;
int main(){
	scanf("%d",&n);
	int ans=0;
	string s;
	int m=0;
	for(int i=1;i<=n;i++){
		cin>>s;
		if(M.find(s)==M.end()){
			m++;
			M[s]=m;
		}
	}
	cout<<m;
}

 总结

    就跟去做工作报告一样,感觉没什么好说的,要真的总结的话就是,有点丢人,很不满意。

很多问题都是以前接触过的,数据结构也是会用的,可实操起来却发现大脑一片空白。很无语就,明明有更好的解决方法却总是后知后觉,状态很不好,心态也,,拉跨。锐进和头铁不知道丢到哪去了。希望后续能好好调整一下吧,麻了麻了。

上一篇:C++ STL基本组成


下一篇:C++STL标准库容器