对于刚上大学的牛牛来说，他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中，有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i$ （$1 \leq i \leq n$）个时间段上，两节内容相同的课程同时在不同的地点进行，其中，牛牛预先被安排在教室 $c_i$ 上课，而另一节课程在教室 $d_i$ 进行。

在不提交任何申请的情况下，学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第i节课程的教室，则需要提出申请。若申请通过，学生就可以在第 $i$ 个时间段去教室 $d_i$ 上课，否则仍然在教室 $c_i$ 上课。

由于更换教室的需求太多，申请不一定能获得通过。通过计算，牛牛发现申请更换第 $i$ 节课程的教室时，申请被通过的概率是一个已知的实数 $k_i$，并且对于不同课程的申请，被通过的概率是互相独立的。

学校规定，所有的申请只能在学期开始前一次性提交，并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室，而不能根据某些课程的申请结果来决定其他课程是否申请；牛牛可以申请白己最希望更换教室的 $m$ 门课程，也可以不用完这 $m$ 个申请的机会，甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行，所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 $v$ 个教室，有 $e$ 条道路。每条道路连接两间教室，并且是可以双向通行的。由于道路的长度和拥堵程度不同，通过不同的道路耗费的体力可能会有所不同。当第 $i$（$1 \leq i \leq n - 1$）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

现在牛牛想知道，申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小，请你帮他求出这个最小值。

小南有一套可爱的玩具小人，它们各有不同的职业。

有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。

这时 singer 告诉小南一个谜题：「眼镜藏在我左数第 3 3 个玩具小人的右数第 $1$ 个玩具小人的左数第 $2$ 个玩具小人那里。」

小南发现，这个谜题中玩具小人的朝向非常关键， 因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。

小南一边艰难地辨认着玩具小人，一边数着：

singer 朝内，左数第 $3$ 个是 archer。 archer 朝外，右数第 $1$ 个是 thinker。 thinker 朝外，左数第 $2$ 个是 writer。

所以眼镜藏在 writer 这里！

虽然成功找回了眼镜，但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜，或是谜题的长度更长，他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为：

有$n$个玩具小人围成一圈，已知它们的职业和朝向。现在第 $1$ 个玩具小人告诉小南一个包含 $m$ 条指令的谜题。其中第 $i$ 条指令形如「左数/右数第 $s_i$ 个玩具小人」。你需要输出依次数完这些指令后，到达的玩具小人的职业。

有$n$堆石子排成一列，每堆石子有一个重量$w_i$, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和$w_i+w_{i+1}$，求怎样合并能使合并代价最小，输出最小代价。

给定两个数列 $a, b$，每个数列中相邻两个数可以交换，求使得 $\sum\limits_{i = 1}^{n}(a_i - b_i) ^ 2$ 最小的交换次数，答案对 $99999997$ 取模

给定一个序列，求其中最长波动子序列

题解

据说这题可以动归，然而感觉动归爆炸，就贪了个心

正解是枚举所有的拐点，将拐点加入子序列中一定比加入其他点更优，因为拐点比可以容纳更多的点在其中波动，最后特判起点和终点是否可以加入序列中即可

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
const int MAXN = 100000;
int height[MAXN + 1];
int main () {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &height[i]);
    }
    
    bool isUping = true; int ans = 0;
    if (height[1] >= height[2]) isUping = false;
    else isUping = true;
    for (int i = 2; i <= n - 1; i++) {
        if (isUping && height[i] > height[i + 1]) {
            isUping = false;
            ans++;
        } else if (!isUping && height[i] < height[i + 1]) {
            isUping = true;
            ans++;
        }
    }
    if (height[1] == height[2]) ans--;
    if (height[n - 1] == height[n]) ans--;
    ans += 2;
    printf("%d\n", ans);
    return 0;
}

• 给定一个长为$n$，高为$m$的二位平面，其中有$k$个管道（不计宽度）
• 小鸟从平面最左边出发，到达平面最右边时游戏完成
• 小鸟每单位时间沿横坐标方向右移距离为1，竖直移动距离由玩家控制，如果点击屏幕，小鸟会上升一定高度$X$，每单位时间内可以点击多次，效果叠加，如果不点击屏幕，小鸟会下降一定高度$Y$
• 小鸟位于不同的横坐标位置时，上升高度$X$和下降高度$Y$可能互不相同
• 小鸟高度为$m$时，无法再上升
• 小鸟高度等于$0$或小鸟碰到管道时，游戏失败
• 要求：
  • 如果能完成游戏，输出最少点击屏幕次数
  • 如果不能，输出最多能通过的水管

• 有$m+1$个星球，从$0$到$m$编号，yqy最初在$0$号星球
• 有$n$处矿体，第$i$出矿体有$a_i$单位原矿，在编号为$b_i$的星球上
• 飞船每次只能从$x$号星球移动到$x+4$或$x+7$号星球，每到一个星球yqy会采走该星球上所有的原矿
• 求yqy最多能采走多少原矿
• 注意：
  • yqy不必最终到达$m$号星球
  • 对于$100\%$的数据，$n\leq 10^5, m\leq 10^9$

• 有两个仅包含小写英文字母的字符串A和B
• 现在要从字符串A中取出k个互不重叠的非空子串，然后把这k个子串按照其在字符串A中出现的顺序依次连接起来得到一个新的字符串
• 求使得新串与B串相同的方案数
• 子串取出的位置不同，认为是不同的方案。

• 给定$N$门课，每门课有自己的学分，可能有一门先修课
• 不同的课程可能有共同的先修课
• 求在学习课程项目限制$M$内，可能获得的最大学分

• 制作一个体积为$N\pi$，共$M$层的蛋糕
• 从上往下数第$i,(1\leq i\leq M)$的蛋糕是半径为$R_i$，高度为$H_i$的圆柱
• 当$i<M$时，要求$R_i>R_{i+1}$且$H_i>H_{i+1}$
• 使得蛋糕的表面积最小

在这里本题需要输出的答案并不是最小的表面积，而是最小表面积除以$\pi$之后的结果