一、题意 递归输入天平的wl, dl, wr, dr，分别表示天平的左重量、距离和右重量、距离。要求判断是否所有天平都力矩平衡。 二、解析 递归输入时顺便判断即可。由于父天平的判断显然需要子天平的总重量，因此可以考虑将总重量作为递归返回值。不平衡时返回-1即可。 三、代码 #include <iostream> using namespace std; int input() { int wl, dl, wr, dr; cin >> wl >> dl >> wr >> dr; if(wl == 0) wl = input(); if(...

一、题意 每组数据一棵树。给出树的中序遍历和后序遍历，求这棵树的叶子节点中，到根节点的权值和最小的那个结点的权值。 二、解析 由中序遍历和后续遍历就可以恢复出完整的树。然后再对树做dfs求出答案。 三、代码 #include <iostream> #include <string> #include <sstream> #include <vector> using namespace std; const int maxn = 10000 + 5, INF = 1 << 30; struct node { int val; node...

一、题意 在每组数据中有一棵树，给出每个结点的val和从根节点到它的位置的路径path（由L和R组成）要求输出树的层次遍历。 二、解析 构造树需要用到指针操作，递归生成。层次遍历用bfs即可，bfs一般通过队列实现。 三、代码 #include <iostream> #include <string> #include <sstream> #include <vector> #include <queue> using namespace std; struct node { int has_val = 0; int val; nod...

一、题意 每组数组为一棵树，给出这个数的深度D，以及小球数量I。每个球从一个二叉树根开始沿着树干下落，每经过一个结点会改变结点的开闭状态。所有结点的默认状态为关闭。关闭时小球往左走，否则往右走。求每组数据中，第I个小球会落在那个叶子结点中。结点编号按层次遍历1到2^D-1。 二、解析 考察二进制的概念。假设是第I个小球，I从0开始算起的话，则I的二进制末位为0则往左走，1则往右走，每下一层I往右移一位。然后根据树结点编号的计算方法即可算出答案。 三、代码 #include <iostream> using namespace std; int main() { int n, D, ...

一、题意 一个1...n的序列。（n<=100000）有4中指令：1 X Y 表示把X移动到Y的左边2 X Y 表示把X移动到Y的右边3 X Y 表示交换X和Y的位置4 表示反转序列输出最终序列的奇数位上的数字和，下标从1开始计算。 二、解析 用列表list模拟。主要是要维护每个元素所在的位置，因此需要维护一个存放迭代器的pos[maxn]数组。反转序列不需要真的反转，只需要用一个bool变量标记即可，同时注意左右的含义要根据这个标记进行变换。 三、代码 #include <iostream> #include <list> #include <iterat...

一、题意 输入若干行字符串。表示键盘输入的字符序列。其中'['表示光标移至开头，']'表示把光标移至末尾。要求输出最终的字符串。 二、解析 需要插入操作，因此考虑用list。移动光标通过维护list的一个迭代器即可，用来表示插入的位置。 三、代码 #include <iostream> #include <string> #include <list> using namespace std; int main() { string str; while(cin >> str) { list<char> lst; auto pos =...

一、题意 一列火车车厢号从1...n，问能否依靠一个中转站将车厢顺便变为指定的排序。有若干组数据，每组数据第一行一个n,之后若干行每行为一询问。 二、解析 显然用栈模拟中转站。车厢从1...n首先必然进栈，然后根据执行排序来判断是否需要出栈。 三、代码 #include <iostream> #include <stack> using namespace std; const int maxn = 1000 + 5; int n, a[maxn]; int main() { while(cin >> n && n) { while(cin ...

一、题意 有kase组数据。每组第一行一个n表示有n个点。接下来n行输入这些点(x, y)。要你判断每组点是否左右对称。 二、解析 先用vector存点，然后sort一下找到中心对称轴。然后用map法来判断是否对称：具体而言，将对称轴左侧的点视为正标记，右侧的点视为负抵消，维护这样一个flag在map中，最后看是否所有点能恰好完全抵消，是的话说明对称，否则不对称。 三、代码 #include <iostream> #include <algorithm> #include <vector> #include <map> #define mp ma...

一、题意 一堆学生要申请换学院。有若干组数据。每组第一行表示申请个数。之后每一行为两个数(A, B)，表示这个人想从A换到B学院。如果同时存在一对(A,B)和(B,A)则这两个人可以交换。求最终所有人能否交换成功。 二、解析 用一个map来存储信息，比如当有(A，B)申请时， 将(A, B)在map中+1，然后当有一个(B，A)申请时，再将(A, B)在map中-1，表示抵消。最终看是否能完全抵消即可。可用A,B的大小关系来区分是正标记还是负抵消。 三、代码 #include <iostream> #include <map> #define mp make_pair ...

一、题意 有kase组数据(kase<=200)。每组数据一个字符串（长度<=1000），要求列出该字符串中，包含i个循环节的循环子串的最大长度。输出列出的答案数组max_cir_len[i]. 二、解析 循环节问题考虑使用KMP。用KMP的Next数组只能求出前缀子串的循环节，而此题要求的是所有子串，因此需要枚举起始点。考虑时间复杂度O(n^2)，不会超时。 三、代码 #include <iostream> #include <string> #include <cmath> using namespace std; const int max...

一、题意 每组数据第一行一个n,第二行给一个长度为n的字符串。要求列出所有的(i, k)满足该字符串的前i个字符组成的前缀子串是由k个子串循环而成的。 二、解析 中心问题就是求出某个字符串的循环节。求循环节应该马上想到KMP算法。求出Next数组后，根据Next数组的定义，Next[i]=j表示j为s[i]匹配失败后需要跳回的位置，也即是i和j之前可能为相同的串。对于一个循环串来说，它的Next数组“跳回”的长度正好就是一个循环节。因此通过i-Next[i]即可计算出s[1..i)的循环节长度，但注意可能字符串不是循环字符串，因此还要判定字符串长度i是否能被循环节长度i-Next[i]整除。 ...

紫薯 例题5-9 一、题意 输入一个n行m列的数据库（1<=n<=10000, 1<=m<=10），列用','隔开表示。要求找到两个不同的行r1, r2和两个不同的列c1, c2使得元素(r1, c1) ==(r2, c1)且(r1, c2) == (r2, c2)，即在某两列上下相等的两行。找到则输出NO，并依次输出r1, r2, c1, c2；否则输出YES。 二、解析 暴力4重遍历显然会超时。注意到列数最大为10，因此列数可以枚举。行最多只能用复杂度为O(nlgn)的算法找出相等的两行。这里很快能想到map。遍历行时，用map存储已经遍历过的行的两行字符串的值（存...

紫薯 例题5-7 一、题意 输出从小到大排列的第1500个丑数。丑数定义：不能被2，3，5以外的其它素数整除的数。 二、解析 不能被其它素数整除，也就是说丑数质因子分解后只有2，3，5,所以丑数就是有这三个数的乘积组成的。用一个优先队列维护已经求出的最小丑数。从1开始，每次从优先队列中取出当前最小的丑数，然后将它的2，3，5倍放入队列中，来扩充丑数序列，注意队列中已经存在的数就不要重复放了，因此还需要用一个set来记录队列中是否已经存在某个数了。 三、代码 #include <iostream> #include <queue> #include <vector&...

紫薯P108 例题5-1 一、题意 若干组数据。每组第一行n、q分别表示石头数和询问数。之后列出n个石头分别代表的数字。之后q次询问每次一个数x，要求你输出x在这个石头序列排列后的第几个（或者找不到）。 二、解析 排序后用lower_bound 三、代码 #include <iostream> #include <algorithm> using namespace std; const int maxn = 10000 + 5; int n, q, a[maxn], kase = 1; int main() { while(cin >> n >&gt...