常用经典算法和经典程序

有n个学生. 每个学生都有自己的宗教信仰，可能相同，也可能不同。一个调查机构想弄清楚宗教信仰的总数。但是，直接询问可能会使人不快，于是，调查机构决定询问m对学生，问他们是否具有相同的宗教信仰。（如果相同，则他们会参加同一教会，彼此会认识）。要求计算最大可能的宗教数。 函数原型 int Religions(int n,int m,int* record); n 人数 1<=n<=50000 m 抽查的学生对数，record中有2m个学生编号。 0<=m<=n*(n-1)/2 且 m<=500000 record[] 编号record[i*2]与record[i*2+1]的两个学生，他们之间有相同的信仰。0<=i<m,学生编号1～n 返回值：最大可能的宗教数。 内存限制：256M 时间限制：10S 样例： n=10 m=9 record[]= {1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10} 返回值：1 n=10 m=4 record[]= {2 3 4 5 4 8 5 8} 返回值：7 取石子游戏的变种：有两堆石子，两个人轮流对这些石子进行操作。在每一次操作中，操作者需要拿走其中一堆石子，并且把另一堆石子分成两堆（可以不相等）留给对方操作。游戏如此进行下去，石子数会越来越少，最后必将出现这样一种情况：某人拿走一堆石子后发现另一堆里只剩1个石子不能再分了。游戏规定此时该操作者取胜。 　　这个游戏是不公平的。对于任意一种初始状态，总有一方有必胜策略。所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。现在给出两堆石子的数量，要求计算先操作的人是否存在必胜策略。 函数原型 bool Stone(char* a,char* b); a，b是两堆数字的数目，用字符串保存。字符串长度不大于30，并且没有非法字符，没有前导0。 返回值：如果先操作的人存在必胜策略，返回true，否则返回false 内存限制：256M 时间限制：10S 样例： a="1" b="1" true a="100" b="1" true a="2" b="1" true a="2" b="3" false a="5" b="2" true 【问题描述】 陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。 现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。 【输入文件】 输入文件apple.in包括两行数据。第一行包含10个100到200之间（包括100和200）的整数（以厘米为单位）分别表示10个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。第二行只包括一个100到120之间（包含100和120）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。 【输出文件】 输出文件apple.out包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。 【样例输入】 100 200 150 140 129 134 167 198 200 111 110 【样例输出】 5 Problem Statement &nbsp;&nbsp;&nbsp;&nbsp; You want to send a group of salespeople from location 0 to location 1, but no two of them can travel through the same location (other than 0 and 1). This removes the possibility of trying to sell a customer the same product twice. Character j of element i (both 0-based) of adj denotes whether locations i and j are connected by a symmetric link ('1' for connected, '0' otherwise). Return the greatest number of salespeople that can be sent. The constraints will guarantee that locations 0 and 1 do not share a link. Definition &nbsp;&nbsp;&nbsp;&nbsp; Class: SalesRouting Method: howMany Parameters: vector <string> Returns: int Method signature: int howMany(vector <string> adj) (be sure your method is public) &nbsp;&nbsp;&nbsp;&nbsp; Constraints - adj will contain between 3 and 12 elements, inclusive. - Each element of adj will contain exactly N characters, where N is the number of elements in adj. - Each character in adj will be '0' (zero) or '1' (one). - Character i of element j of adj will be the same as character j of element i. - Character i of element i of adj will be '0'. - Character 1 of element 0 of adj will be '0'. Examples 0) &nbsp;&nbsp;&nbsp;&nbsp; { "001", "001", "110" } Returns: 1 We can send a single salesperson from location 0 to location 2, and finally to location 1. 1) &nbsp;&nbsp;&nbsp;&nbsp; { "0010", "0010", "1100", "0000" } Returns: 1 Same as before, but now there is an isolated location 3. 2) &nbsp;&nbsp;&nbsp;&nbsp; { "001100", "000001", "100010", "100010", "001101", "010010" } Returns: 1 The only location that is directly connected to location 1 is 5, so only 1 salesperson can be sent. 3) &nbsp;&nbsp;&nbsp;&nbsp; { "001111", "001111", "110000", "110000", "110000", "110000" } Returns: 4 4) &nbsp;&nbsp;&nbsp;&nbsp; { "00000", "00000", "00000", "00000", "00000" } Returns: 0 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. 为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛， 负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。 由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自由分组。 不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。 比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如果是1，2，3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4，2 vs 4，3 vs 4。 很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，通过上面这种比赛规则， 总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。 但是无论怎么分都不可能恰需要1场比赛。 相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。 输入要求： 每行为一组数据，包含两个数字 N, K(0<N<=500, K>=0)。例： 2 0 2 1 3 1 3 2 样例：in.txt 输出要求： 对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"（请全部使用大写字母）， 每组数据占一行。例： YES YES NO YES 样例：out.txt 评分规则： 1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试数据集上运行不能超过10秒，否则该用例不得分； 2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。 如果不能正确读入数据和输出数据，该题将不得分； 3．该题目共有3个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为30%，30%，40%； 4．该题目20分。