algorithm

ZSTUOJ 晚餐队列安排题目描述为了避免餐厅过分拥挤，FJ要求奶牛们分2批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第2批就餐的奶牛排在队尾，队伍的前半部分则由设定为第1批就餐的奶牛占据。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 2)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改 掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如112222或111122。有的时候，FJ会把整个队列弄得只有1组奶牛（比方 说，1111或222）。 你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。 输入 第1行: 1个整数：N 第2..N+1行: 第i+1行是1个整数 ...

ZSTUOJ 折线分割平面题目描述我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。 输入 多组测试数据每组输入数据的一个整数n(0<n<=10000),表示折线的数量。 输出 对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。 样例输入 12 样例输出 27 思路1先画出有3条折线的情况，发现是16 然后无头绪，4条折线很复杂，不想画 于是思考不是折线，而是直线的情况，容易找出规律： 1、2、3、4、5条直线分割平面，分别分割为2、4、7、11、16个 找到规律，每次增量+1，且2、7、16刚好对应折线情况 猜想折线也符合增量规律，即2，（+5）7，（+9）16，（+13）29 代码1#include <iostream>using namespace std;int ans[10010];int main() { ans[1] = 2; int d = 5; for (int i ...

ZSTUOJ 彼岸题目描述突破蝙蝠的包围，yifenfei来到一处悬崖面前，悬崖彼岸就是前进的方向，好在现在的yifenfei已经学过御剑术，可御剑轻松飞过悬崖。现在的问题是：悬崖中间飞着很多红，黄，蓝三种颜色的珠子，假设我们把悬崖看成一条长度为n的线段，线段上的每一单位长度空间都可能飞过红，黄，蓝三种珠子，而yifenfei必定会在该空间上碰到一种颜色的珠子。如果在连续3段单位空间碰到的珠子颜色都不一样，则yifenfei就会坠落。比如经过长度为3的悬崖，碰到的珠子先后为 “红黄蓝”，或者 “蓝红黄” 等类似情况就会坠落，而如果是 “红黄红” 或者 “红黄黄”等情况则可以安全到达。 现在请问：yifenfei安然抵达彼岸的方法有多少种？ 输入 输入一个正整数n (n<=40)。 输出 输出一个整数，表示yifenfei安然抵达彼岸的方法数。 样例输入 3 样例输出 21 思路公式推导定义 dp[j][k][l][i] 表示长度为i的，最后三段的颜色为j,k,l的线段的数量 状态转移dp[j][k][l][i] += dp[m][j][k][i - 1] 在满足不是（连续3段 ...

ZSTUOJ 宁宁的奥数路题目描述宁宁参加奥数班，他遇到的第一个问题是这样的：口口口+口口口=口口口，宁宁需要将1~9 九个数分别填进对应的空格内，使等式成立。现在宁宁填了一个算式，你能帮他验证是否正确么？ 输入 分别输入三个三位数，依次表示等式里的三个数。 输出 如果等式成立，输出：YES!，否则输出：NO! 样例输入 173 286 459 样例输出 YES! 代码注意：有一组测试数据疑似为多组测试，题目中未说明 传统做法#include <iostream>using namespace std;int bucket[10];int main() { int a, b, c; while (cin >> a >> b >> c) { bool ans = true; if (a + b != c) ans = false; for (int i = 0; i < 10; i++) { bucket[i] = 0; ...

ZSTUOJ 三只小猪题目描述这日，快码佳编四兄弟姐妹来到了一个山脚下，只听一个老奶奶给两个孙子讲故事。你听说过三只小猪的故事吗？这是一个经典的故事。很久很久以前，有三只小猪。第一只小猪用稻草建的房子，第二个小猪用木棍建的房子，第三个小猪则使用砖做为材料。一只大灰狼想吃掉它们并吹倒了稻草和木棍建的房子。但是砖盖的房子很结实，狼最终也没有破坏掉，最后小猪们战胜了大灰狼并把它尾巴烧掉了。为了自己的安全，小猪们又建造了一个新砖房。但是现在问题出现了，怎样把三个小猪分配到两个房子里呢？第三只小猪是三只小猪中最聪明的一只，为了不浪费任何一个房子，它总共考虑了三种方案，如下图 但是将来怎么办呢？”第三只小猪知道将来随着成员的增多，它们将会盖更多的房子。它想知道给定了房子和猪的数目后，房子的分配方案有多少，但这个问题对于它来说，很明显有点难了，你能帮小猪解决这个问题吗？ 输入 多组测试，每组仅有一行，包含两个整数n和m，分别表示小猪的数目和房间数（1≤n≤20，0≤m≤20） 输出 每组输出一行，仅一个整数，表示将n只小猪安置在m个房间且没有房间空闲的方案数。 样例输入 4 2 样例输出 7 思路 ...