小结

说实在的没啥可总结的，因为太菜了。这次比赛虽然没有跟着打，但是从赛后补题来看，我在数论、搜索的变形、dp等知识点上仍有很大的坑要填，尤其是搜索这一个本来以为有一点熟练的知识点直接在1004跪了（太菜了太菜了）。
说啥都没用，好好补题，改过自新。
下面开始放题目

1004 Deliver the Cake

题目描述

原题传送门：点我直达

人话翻译：张三过生日要拿蛋糕，需要经过一些村庄和一些连接村庄的路。现在给出三种类型的村庄：L M R，分别代表只能用左手提蛋糕，不限制，用右手提蛋糕。在经过这三种类型的村庄时如果需要换手（有必要的话），需要花费额外的时间，从而保证换后的手符合该村庄的类型。现给出村庄之间路的起点终点和代价、每个村庄的类型，以及换手需要的代价。问从村庄s到村庄t花费的最小代价。

样例输入

1
3 3 1 3 100
LRM
1 2 10
2 3 10
1 3 100

样例输出

100

题目分析

看标答才会的，本来是挺简单的一个单源最短路径，结果硬给被换手搞复杂了，正解是拆点搜索。因为直接分析左右手不好分析，因此将每一个村庄（下面都叫他节点）拆成两个节点，一个节点代表换左手（1号），一个表示换右手（2号），这样就可以将左右手的不确定性解决。举例：如果当前节点类型给出L，则只保留1号节点，也就是只将1号节点加入到搜索的图中。通过这样的方法遍历点就可以构造出一个图，再用Djikstra解决。
但有坑！M类型没有要求，因此可以换也可以不换手，这是两种情况！！！必须分开讨论哪一种情况更优，而不是直观以为不换就行，换了也许更好。（比如刚好和下一个节点类型一致，下一个节点甚至下面所有的节点都有可能不用换）

代码（还是有点问题的代码）

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;
typedef long long ll;

typedef pair<int, int> pi;
const int maxn = 200000 + 10;
const ll inf = 1e18;
int T;
int n, m, s, t, x;
ll dis[maxn][2];
char type[maxn];
struct Edge { int v, w; };
vector<Edge> vc[maxn];
struct Node {
    ll d;//该节点的代价
    int u, t;//u是节点编号 t是节点类型（L/R）

    bool operator<(const Node &b) const { //重载运算符用于对pair排序，优先队列从小到大
        return d > b.d; //这里的符号和优先队列最终排序的顺序是相反的
    }
};

priority_queue<Node> pq;

void solve() {
    cin >> n >> m >> s >> t >> x;
    cin >> (type+1);
    for (int i = 1; i <= m; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        vc[u].push_back(Edge{v, d});
        vc[v].push_back(Edge{u, d});
    }
    for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = inf;
    if (type[s] != 'R') pq.push(Node{dis[s][0] = 0, s, 0});//将出发节点加入队列 同时判断出发节点左右手
    if (type[s] != 'L') pq.push(Node{dis[s][1] = 0, s, 1});//这里用!=是因为要把M这个类型搞进去
    while (!pq.empty()) {
        Node now = pq.top();
        pq.pop();
        if (dis[now.u][now.t] < now.d) continue;//如果这个点已经被更新过了就不用管了
        if (now.u == t) break;//到达终点
        for (const Edge &e:vc[now.u]) {
            ll w = e.w + now.d;//总代价等于现在选的路的代价+目前为止的总代价
            int tt = type[e.v] == 'R' ? 1 : (type[e.v] == 'L' ? 0 : now.t);//如果不是左边也不是右边。就和上一个点保持一致
            if (tt == now.t && w < dis[e.v][tt]) {//若走这条路不需要换手
                pq.push(Node{dis[e.v][tt] = w, e.v, tt});
            }
            w += x;
            if (type[e.v] == 'M') t = !t;//M这个可以换手也可以不换，不换的上一个if考虑到了，现在考虑换手
            if (tt != now.t && w < dis[e.v][tt]) {
                pq.push(Node{dis[e.v][tt] = w, e.v, tt});
            }
        }
    }
    cout << min(dis[t][0], dis[t][1]) << endl;
    while (!pq.empty()) pq.pop();
    for (int i = 1; i <= n; i++) vc[i].clear();//init
}

int main() {
    for (cin >> T; T--;) solve();
    return 0;
}

1005 Equal Sentences

题目描述

原题传送门：点我直达

人话翻译：给出一串若干单词组成的语句，每个单词可能同也可能不同。如果相邻两个单词不同，则可以交换。交换过后的语句称为原语句的几乎相等语句（也就是换一下语序，语句意思仍然不变的语句）。现在给出一串语句，问这串语句有多少个几乎相等语句。

样例输入

2
6
he he zhou is watching you
13
yi yi si wu yi si yi jiu yi jiu ba yao ling

样例输出

8
233

题目分析

这题刚开始被我理解复杂了，我一度以为需要一个个数相同和不同的单词数量，重组语句。实际上前面的人话翻译我已经给简化了题意，这题就是问如果相邻两个不同的单词（注意必须不同）交换顺序后算不同的语句，最后能交换出多少种不同语句出来。（这里注意交换后要交换回来，每次只能进行一次交换操作）最后这题可以直接递推解决（虽然std说用dp？？）

AC代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int maxn = 100000 + 10;
const int mod = 1e9 + 7;
int t;
int f[maxn];
string s[maxn];

int solve() {
    int n;
    memset(f, 0, sizeof(f));
    f[0] = 1;//加上其本身
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i];
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1];//继承上一单词为止的相似总数
        if (i >= 2 && s[i] != s[i - 1]) {
            f[i] += f[i - 2];//i-2是因为要加上上一阶段（上一次交换）前的字符串结果
            f[i] %= mod;
        }
    }
    return f[n];
}

int main() {
    for (cin >> t; t--;) cout << solve() << endl;
    return 0;
}

1011 Kindergarten Physics

题目描述

原题传送门：点我直达

人话翻译：两个小球同时下落，只由万有引力牵引，问指定时间时相距的距离。

样例输入

3
1 2 3 4
7 73 7 68
100 100 1 100

样例输出

2.99999999999999999982
6.99999999999999974807
0.99999999999993325700

题目分析

因为最后要求误差在1e6之内，发现不管怎么样，只要在题设数据量内都不会超这个误差，直接输出就行（迷惑输出）

AC代码（STD）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(void) {
  int T;
  scanf("%d", &T);
  while (T--) {
    int d;
    scanf("%*d%*d%d%*d", &d);
    printf("%d\n", d);
  }
  return 0;
}