杭电多校第四场

August 2, 2020 · 算法 · 1214次阅读

小结

说实在的没啥可总结的,因为太菜了。这次比赛虽然没有跟着打,但是从赛后补题来看,我在数论、搜索的变形、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;
}

杭电补题算法

最后编辑于4年前

添加新评论