【总结】2019.6.1模拟赛

T1

题目内容

传送门

解法

记忆化搜索,卡空间需要float,并且floor()函数返回类型是浮点,位数多了cout会科学计数法,需要转一下。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <map>

using namespace std;

const int MAXN = 45;
const float EPS = 1e-5;

int n;
int a[MAXN], s[MAXN];
float dp[MAXN][MAXN * MAXN][MAXN * MAXN];
//map<int, map<int, map<int, float> > > dp;

bool Judge(float a, float b, float c) {
    return a + b - c > EPS && a + c - b > EPS && b + c - a > EPS;
}

float Area(float a, float b, float c) {
    if (!Judge(a, b, c)) return -0.010000;
    float m = (a + b + c) / 2.000000;
    return sqrt(m * (m - a) * (m - b) * (m - c));
}

float Dfs(int pos, int l1, int l2) {
    if (dp[pos][l1][l2] < -EPS || dp[pos][l1][l2] > EPS) return dp[pos][l1][l2];
    if (pos == n) {
        int l3 = s[pos - 1] - l1 - l2;
        return dp[pos][l1][l2] = max(Area(l1, l2, l3 + a[pos]), max(Area(l1, l2 + a[pos], l3), Area(l1 + a[pos], l2, l3)));
    }
    return dp[pos][l1][l2] = max(Dfs(pos + 1, l1 + a[pos], l2), max(Dfs(pos + 1, l1, l2 + a[pos]), Dfs(pos + 1, l1, l2)));
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = a[i] + s[i - 1];
    cout << fixed<< setprecision(0) << floor(Dfs(0, 0, 0) * 100.000000) << endl;
    return 0;
}

T2

题目内容

传送门

解法

暴搜,然后改成记忆化,没想到A了。。

// luogu-judger-enable-o2
#include <iostream>
#include <utility>
#include <cstring>

using namespace std;

const int MAXN = 205;
const int MAXK = 205;
const int MAXT = 4e4 + 5;
const int X[] = {0, -1, 1, 0, 0};
const int Y[] = {0, 0, 0, -1, 1};

int n, m, k, xx, yy;
int l[MAXN], r[MAXN], dir[MAXN];
char ch[MAXN][MAXN];
int dp[MAXK][MAXN][MAXN];

int Dfs(int pos, int x, int y) {
    if (pos > k) return 0;
    if (dp[pos][x][y] != -1) return dp[pos][x][y];
    int len = r[pos] - l[pos] + 1;
    int nowx = x, nowy = y;
    int ret = Dfs(pos + 1, x, y);
    for (int i = 1; i <= len; i++) {
        nowx += X[dir[pos]];
        nowy += Y[dir[pos]];
        if (ch[nowx][nowy] == 'x') break;
        if (nowx > n || nowy > m || nowx < 1 || nowy < 1) break;
        ret = max(ret, i + Dfs(pos + 1, nowx, nowy));
    }
    return dp[pos][x][y] = ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m >> xx >> yy >> k;
    for (int i = 1; i <= n; i++) {
        cin >> ch[i] + 1;
    }
    for (int i = 1; i <= k; i++) {
        cin >> l[i] >> r[i] >> dir[i];
    }
    cout << Dfs(1, xx, yy) << endl;
    return 0;
}

T3

题目内容

传送门

解法

太难了,记忆化乱搞85分

#pragma GCC diagnostic error "-std=c++11"
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 3e4 + 5;
const int INF = 1e9;

using namespace std;

int n, m, s, t;
vector<int> q[MAXN];
int dp[MAXN], b[MAXN], p[MAXN];

int Dfs(int pos) {
    if (pos == t) return 0;
    if (dp[pos] != -1) return dp[pos];
    int ret = INF; dp[pos] = ret;
    for (auto tmp : q[pos]) {
        for (int i = pos % tmp; i < n; i += tmp) {
            ret = min(ret, Dfs(i) + abs(pos - i) / tmp);
        }
    }
    return dp[pos] = ret;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        q[b[i]].push_back(p[i]);
    }
    s = b[0]; t = b[1];
    int ans = Dfs(s);
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

正解:分块最短路

#pragma GCC optimize(3)
#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 3e4 + 5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int to, val;
    Edge *nxt;

    Edge() {}

    Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
};

Edge *head[MAXN];
int n, m, b[MAXN], p[MAXN], blank;
int dis[MAXN * 200];
queue<int> q;
bool vis[MAXN * 200];

inline void AddEdge(int u, int v, int w) {
    head[u] = new Edge(v, w, head[u]);
}

int Spfa(int s, int t) {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    q.push(s); vis[s] = true; dis[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (auto e = head[u]; e; e = e->nxt) {
            int v = e->to;
            if (dis[v] > dis[u] + e->val) {
                dis[v] = dis[u] + e->val;
                if (!vis[v]) q.push(v);
            }
        }
    }
    return dis[t];
}

int Id(int i, int k) {
    return n * k + i;
}

int main() {
    cin >> n >> m;
    blank = min(100, (int)sqrt(n));
    for (int i = 1; i <= blank; i++) {
        for (int j = 0; j + i < n; j++) {
            AddEdge(Id(j, i), Id(j + i, i), 1);
            AddEdge(Id(j + i, i), Id(j, i), 1);
        }
        for (int j = 0; j < n; j++) AddEdge(Id(j, i), j, 0);
    }
    for (int i = 0; i <= m - 1; i++) {
        cin >> b[i] >> p[i];
        if (p[i] <= blank) {
            AddEdge(b[i], Id(b[i], p[i]), 0);
        } else {
            for (int j = b[i] - p[i]; j >= 0; j -= p[i]) {
                AddEdge(b[i], j, (b[i] - j) / p[i]);
            }
            for (int j = b[i] + p[i]; j < n; j += p[i]) {
                AddEdge(b[i], j, (j - b[i]) / p[i]);
            }
        }
    }
    int ans = Spfa(b[0], b[1]);
    cout << (ans != INF ? ans : -1) << endl;
    return 0;
}