时间限制 1000 ms 内存限制 65536 KB
题目描述
Given an array with N integers where all elements appear three times except for one. Find out the one which appears only once.输入格式
Several test cases are given, terminated by EOF.Each test case consists of two lines. The first line gives the length of array N(1≤N≤105), and the other line describes the N elements. All elements are ranged in [0,2^63−1].
输出格式
Output the answer for each test case, one per line.输入样例
4 1 1 1 3 10 1 2 3 1 2 3 1 2 3 4输出样例
3 4
这道题，超时超的我不要不要的，明明O(n)的时间复杂度还是超时。就找了一些别人的答案看了看，觉得应该是卡常数（学了新词）。因此换用另一种算法，虽然还是O(n)但是不再超时。 之前的思路：把每个数转化成二进制，逐位相加，放在数组（数组大小定为64）里，最后逐位模3，得到的二进制数转化为十进制即为结果。 AC的思路：定义一个二维数组，2^63 大约 10^19，所以数组为20*10。num[i][j]表示第i位出现过数字j的次数，然后从第一列遍历数组，若模3得1则直接输出j。 可见，同为O(n)也是存在差别的。（代码参照了别的博主，就不贴了） 遇到这种题上来就想换成二进制算，也不知道什么毛病。换来换去还挺耗时间的。
时间限制 1000 ms 内存限制 65536 KB
题目描述
给出一棵有向树，一共有N(1 小于N≤1000)个节点，如果一个节点的度（入度+出度）不小于它所有儿子以及它父亲的度(如果存在父亲或儿子)，那么我们称这个节点为p节点，现在你的任务是统计p节点的个数。如样例，第一组的p节点为1,2,3；第二组的p节点为0。
输入格式
第一行为数据组数T(1≤T≤100)。 每组数据第一行为N表示树的节点数。后面为N−1行，每行两个数x,y(0≤x,y小于N)，代表y是x的儿子节点。输出格式
每组数据输出一行，为一个整数，代表这棵树上p节点的个数。输入样例
2 5 0 1 1 2 2 3 3 4 3 0 2 0 1输出样例
3 1
这道题，WA也不知道为啥，找不到错在哪里，用的结构体。后来发现用邻接矩阵的方法比较优秀，而且以前没有这么用过，就换用这种方法，学习学习。 思路：定义一个二组数组作为邻接矩阵，每次输入一组节点i，j，就分别在matrix[i][j]和val[i],val[j]加一。 学习使用邻接矩阵处理两点相关的问题。代码不贴。
新闻热点
疑难解答
