题目链接:https://codeforc.es/contest/1702

这次比赛赛题比较简单,很多题感觉可以用stl巧做。另外感觉有必要学习一下stl容器的一些设置的规则 ,stl是有必要深入学习一下的。这次比赛A了四个题,有两个题用map巧做的,一个题是用了set。map嘛很多时候是可以当哈希来用的,而且还可以设置key值对应结构体val。

A题:就是给出个数,然后让求出不超过这个数的10的幂次方。刚开始想用log来O(1)做,但是其实可以直接循环。

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		long long x;
		cin>>x;
		long long f=1;
		while(f<=x)
			f*=10;
		f/=10;
		cout<<x-f<<endl;
	} 
}

B题:给出一个字符串,每天可以学习连续的字母,字母类别不超过三个。多少天能学完

#include<bits/stdc++.h>
using namespace std;
map<char,int>mapt;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string a,b;
		cin>>a;
		b=a;
		sort(b.begin(),b.end());// nlogn
		int p,sum=0;
		scanf("%d",&p);
		int i=0;
		while(sum<=p&&i!=a.size())//nlogn
		{
			sum+=b[i]-96;
			mapt[b[i]]++;
			i++;
		}
		if(sum>p)
		{
			i--; 
			mapt[b[i]]--;//消除一个 
		}
		for(int j=0;j<a.size();j++)
		{
			if(mapt[a[j]]>0)
			{
				printf("%c",a[j]);
				mapt[a[j]]--;
			}
		}
		printf("\n");
	} 
}

解决方法:可以用指针指向来控制学习的元素,循环内巧用set来对每天的进行判重。贪心思想学到第四个之前为止。

code:

#include<bits/stdc++.h>
using namespace std;
set<char>se;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		se.clear();
		string a;
		cin>>a;
		int i=0;
		int day =0;
		while(i!=a.size())
		{
			se.clear();
			while(1)
			{
				se.insert(a[i++]);
				if(i==a.size()||se.size()==3&&se.count(a[i])==0)
					break;
			}
			day++;
		}
		cout<<day<<endl;
	} 
}


 C题:给出一堆数(可能有重复),询问两个数a b,问a能否到达b,只能顺序到达。

解决方案:用map做伪哈希,存储一个数的最低位次和最高位次,当这个数为a时,用最低位次来判断到b的最高位次。这个有个贪心的思想在里面。

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 2*1e5+20;
struct posison{
	int mint=nn;
	int maxt=0;
};
map<int,posison>mp;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		mp.clear();
		int n,k,x;
		scanf("%d%d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x);
			if(mp[x].mint>i)
				mp[x].mint=i;
			if(mp[x].maxt<i)
				mp[x].maxt=i;
		}
		int a,b;
		while(k--)
		{
			scanf("%d%d",&a,&b);
			if(mp[a].mint>mp[b].maxt)
				printf("NO\n");
			else
				printf("YES\n");
		}
	} 
}


D题:大意就是给出个字符串,令a=1,b=2,直到z,给出一个数p,我们可以删除某些字符,使得字符串的sum<=p,求最少操作数。

解决方法:排序,然后map记录保留字符的数量。

code:

 

#include<bits/stdc++.h>
using namespace std;
map<char,int>mapt;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string a,b;
		cin>>a;
		b=a;
		sort(b.begin(),b.end());// nlogn
		int p,sum=0;
		scanf("%d",&p);
		int i=0;
		while(sum<=p&&i!=a.size())//nlogn
		{
			sum+=b[i]-96;
			mapt[b[i]]++;
			i++;
		}
		if(sum>p)
		{
			i--; 
			mapt[b[i]]--;//消除一个 
		}
		for(int j=0;j<a.size();j++)
		{
			if(mapt[a[j]]>0)
			{
				printf("%c",a[j]);
				mapt[a[j]]--;
			}
		}
		printf("\n");
	} 
}