简单题，给定密码替换的规则——比如把1换成@，把0换成％…… 问有多少个密码没改过。 还有注意输出有单数复数之分。 #include <cstdio> #include <cstring> #include <string> using namespace std; pair<string,string> a[1002]; char team[22],s[22],p[22]; void modify() {     strcpy(p, s);     for (int i = 0; p[i]; ++i) {         swit...

题目给了个很好的背景，就是人物之间打电话。人可以看作节点，边可以看作通话时间，图是无向的。定义一个连通分量可能就是一个团伙，还需要看 （1） 连通分量里的节点数 大于1 （2） 边总权值大于一个阈值K 这个都很简单，我们对于每个点，求连通分量，顺便打上标号（我写的where)就表示它在哪个分量里，按照联通分量标号排序，同一个连通分量的点在一起。求连通分量可以用dfs,顺便求出每个点连边权的总和，也能求出分量里所有边权值和——别忘记除以2和K比较。这样就能找到团伙。排序时同一个团伙把连边权和大的节点放在前面，就能找到每个团伙的头。 还要注意字符串到整数id之间使用map...

经典问题，汽车加油问题，从起点到终点，有若干个加油站，每个加油站油价不同，汽车油箱容积有限，问能否到终点，如何最便宜。 可以贪心， 我比较喜欢的做法。到当前加油站，就把油箱加满。 我们把油箱里的油看成是“分块”的，每块油有自己的价钱。我们使用油的时候从最便宜的开始用。加油的时候，如果当前加油站的油比邮箱里的还没用的油便宜，就把贵的油换掉。 所以油箱里的油可以存储为这样的pair, (价钱，油量) ，到达一个加油站，就把所有油价比它贵的油用这个加油站的油换掉，所以离开加油站的时候，油箱总是满的，使用的时候先用最便宜的油。注意：最后没有使用的油是不算钱的，可以理解为我...

很有意思的简单题——可以说也是模拟题吧，给定字符串按照指定格式输出。主要还是要细致，关键是计算两列之间空格的个数——如果总长度是n，空格个数大体就是(n + 4) / 3，但是如果n和这个数的差是奇数，还要多加一个空格，这样才能均分。然后就是直接循环输出了。 代码： #include <cstdio> #include <cstring> #include <string> using namespace std; char s[99]; int main() {     scanf("%s",s);     in...

给定自然数n，不超过105，再给定d, 问n是否是质数,并且把n化成d进制后，把数字倒过来（123变成321）还是不是质数。 注意1不是质数。 分析： 不难。主要有两个考点： （1） 把n化成d进制，再翻转数字。 这个我们不断地除以d就好了，而且先得到的是低位数字，我们直接用x = x * d + n % d，最终x就是翻转后的结果了，很方便， O(logn) （2） 判断x是否是质数，一个数的最小的约数不超过sqrt(x)，所以循环没有必要到x，但从本题的数据范围似乎循环到x也没大问题，不过还是推荐sqrt(x)吧, O(sqrt(x)) = O(x0.5...

这种题目叫做模拟题——意思是说，没什么算法，题目给定规则，让你模拟一个事件。规则很细致，往往很容易出错。 例如本题，有如下几条规则： （1） 所有人是按照顺序到来的，可以认为他们都在等候，每个人要办的服务的时间给定，是p[i]。 （2） 有n个窗口队列，每个队列长度不能超过m。多余的人只能在外面等候——还不能选择窗口。 （3） 如果允许，每个人会选择最短的队列进入，如果很多队列都是最短的，选取编号较小的。 （4） 真正服务开始的时间是8点，结束时间是17点。 输出的是一些人最终业务办理完成的时间。 解决： 我们直接模拟，对每个队列记录入队的人的id。 ...

简单题，题目给了个买彩票的背景。本质就是给一个3 ＊ 3的矩阵，找每一行的最大值出来，3个数相乘再乘以65%,再减去1，最终乘以2，表示一个人可以获得的最大利润，题目就是这么描述的，让计算的就是这个公式。直接做就可以，顺便说一下double里x > y，最好写成x >= y + eps, 而eps一般取1e-8或者1e-10之类的小正数，因为double比较大小不准确。还有读入单一字符最好也别用"%c",因为这个会读空格，我建议使用"%s"。 代码： #include <cstdio> #include &lt...

两个有序数组的中位数是个经典的问题，但是本题对时间要求不高，所以可以用归并排序的方法来做，所以就很简单了。归并排序找到第k个元素就可以了。时间复杂度是O(k)其中k是(na + nb)  / 2。还有题目里说的long，我还是用了long long。 代码： #include <cstdio> #include <string> #include <cstring> using namespace std; long long a[1000006], b[1000006]; int main() { int na,nb;     s...

简单题，把3个数变成13进制，而且每个数要求变成两位13进制数。 对于x，变为13进制，高位“数字”是(x / 13)，低位数字是(x % 13)，然后直接输出就可以了。感觉比1001那种要处理的A + B还简单。 代码： #include <cstdio> #include <cstring> #include <string> using namespace std; const char *s = "0123456789ABC"; void print(int x) {     printf(&quo...

这个题和1002类似，1002是多项式加法，这个是多项式乘法。输入输出格式完全一样，数据范围也一样。我还是同样的建议：用数组存多项式的系数，而不要用链表——因为链表容易错。不过要注意两个1000次的多项式相乘，结果可能到2000次——注意数组别开小了。还有就是注意0的判断，这一点和1002一样。相乘采取的就是两重循环。 c[i + j] += a[i] * b[j]这样了。 代码： #include <cstdio> #include <string> #include <cstring> #include <cmath> ...

简单题，电梯问题。开始在0层，上一层需要6秒，下一层需要4秒，知道每个人想到的楼层数，必须按顺序送这些人。可以理解为现在所有的人都在电梯里，每下一个人要停5秒，问电梯总共运行多长时间可以运送所有人——电梯最终不需要回到0层。 分析： 简单模拟。因为送人是按顺序送的，就看一下之前所在的层数last和现在要到达的楼层数相比是应该往上还是往下（或者不动），进而就算出了时间，累加起来就好了，当然每个人还要停5秒也算上去。我们没有必要存每个人的楼层，读一个计算一个就行了。 #include <cstdio> #include <cstring> #include &l...

           最大子数组和问题，给定一个数组，求一个子数组和最大。要输出子数组的起点和终点对应的数，输出起点终点对应下标字典序最小的，如果全是负数输出0，并且起点是第一个数，终点是最后一个数。            分析：还是那个经典算法：             以第i项结尾的最大子数组有两种可能： （1） 以(i - 1)项结尾的最大子数组加上a[i] （2） a[i]本身 我们要同时更新当前解的开头和结尾，注意第（2）种情况，当前解的开头变化了，变成a[i]了。我们用endi表示当前解的开头，用end表示当前解的和。我们来看看如何更新...

输入一个非负整数n，求这个数各个数字的和，并输出英文（每一位输出一个数字），比如15，最终输出one five. 分析： n有10100那么大。显然用int, long long都是不够的，java当然可以用自带的BigInteger，对于C/C++，我们可以用字符串读入这些数。求各个数字之和也很简单，直接加即可——对于C/C++，字符c - '0'就得到了对应的整数。这个和显然不会太大——不超过900，因为最大就是100个9。然后我们把这个和的各个数字截出来，输出即可。截取各个数字，可以像1001那样用除法，不断除以10即可。更简单的方法是使用sprintf，再把结果写回到...

题目给了一个图，代表若干个城市，每个城市里有若干人，城市靠道路相连——总体来说是一个无向图，每个节点有一个权值，边也有权值，代表路径长度。然后给定一个起点，是你所在的城市，再给定一个终点——表示目的城市，一旦遇到紧急情况，你需要以最快的速度把尽可能多的人放到目的城市。求两个值 （1） 从起点到终点有多少条最短路径 （2） 走最短路的前提下，你最多能运送多少人到终点？ 分析： 这是一个典型的最短路问题。后面还会看到其实PAT最短路的问题还挺多的，但都不是直接求最短路那么简单。比如本题，还要求最短路的长度。我们考虑一下Dijkstra算法的核心步骤: if (d[i]...