Codeforces 589A Email Aliases

题意

给出了一堆电子邮件地址,要你按照一定的规则分类,然后一类一类地输出。

思路

模拟。

只要正确地理解了题意基本不会有问题,在实现方面,可以考虑使用map的迭代器轻松地完成分类操作,令map的key为邮件地址的Hash(其实就是按照题目规则把等价但不同的邮件地址处理成同一个字符串),value为set<string>用来当作不同形态的邮件地址的容器。

代码

 

UVA 12946 Peanoland contacting Gaussland

题意

给出了一个从整数到复数的映射,你要求出给你的整数映射成的复数的实部和虚部。

思路

STL complex裸题。

直接模拟就好,当然自己写一个complex结构体也不是难事。

代码

 

CodeForces 484B Maximum Value

题意

给你一串数,让你找出一组(i,j),使得在保证第i项大于等于第j项的同时,第i项mod第j项最大,求这个最大值。

思路

要有一种转换的思维,余数最大的话,可以另一个方向进行考虑,a%b=c的话,a可以看成是kb+c,这个里面b,c是已知的,这个k可以枚举,这样就把求余数这个事情转换成了枚举/搜索,换一个思路问题可能就突破了。

对给出的数列sort一下,unique一下,erase一下,这样就有效的避免了重复数据的干扰(如果你不unique可能会被这个题的某组坑数据给弄T),而且sort完才能做。sort好之后,我们挨个数枚举,对于每个数k,我们考虑这个数列上0~k,k~2k,2k~3k,…这些个小区段,每个小区段中最大的那个数 mod k可能是最大的,我们挨个数挨个区段去枚举就可以了。
但是暴力枚举是过不了的,我们就把在数列中找k,2k,…这个过程改成二分搜索,这样复杂度降为nlogn就行了。

代码

 

 

CodeForces 484B Maximum Value

在lower_bound之后如果加入了多余的判断(判断pos的位置等等),就会T,如果没有用unique来压缩输入,就会T。

总觉得很寸,应该是数据做的有漏洞。

解法的思路就是先从小到大排序,然后从第一项开始,借用素数筛法的思路,对于每个数检查以这个数的倍数为终点的各个区间,然后找出每个区间之内离终点最近的数,更新答案。找终点的过程使用了二分搜索,STL自带的lower_bound和upper_bound就能很好地工作,使用upper_bound的话还有一个小窍门就是把搜索目标设成目标-1,这样的话搜索完落在的点就和lower_bound是一样的了。

如何给priority_queue写比较函数

下面是转的:

注:

  1. less<class T>这是大顶堆,按值大的优先,值大的在最上面。greater<class T>这是小顶堆,按值小的优先,值小的在最上面。
  2. 自定义cmp如果还有不明白的看这里:
  3. 还是自定义cmp函数,注意,一般ACM中用结构体内含“bool operator()(const int &a,const int &b)”。这其实等价于Class cmp,不过更省事,当然也不规范(不需要规范)。
  4. return就是希望如何排列为true。如果希望由大到小,就将大到小的情况return;反则亦然。和sort的自定义cmp是一样的。

HDU 1015 Safecracker

用STL,next_permutation把所有可能性搞出来注意检验就可以爆过去了。

HDU 1540 Tunnel Warfare

这个是用STL水过去的啊,可不是什么正规做法。

POJ 2503 Babelfish

这个是拿map水过去的版本,其实应该自己手写一个的。。。

HDU 1908 Double Queue

那帮老逼太机智了,双端优先队列他们居然用map实现也是diao。。。

HDU 1702 ACboy needs your help again!

STL小练习

其实手写应该会很带感

Scroll to top