D-Link with Game Glitch

题目大意：
给定 m 个物品合成的方式，求一个最大的合成损耗参数 w ，使得所有物品都无法通过无限合成的方式无限获得。

思路：
就是一个SPFA的简单应用，二分答案，然后用spfa来判断图中是否有正环即可。double有可能溢出，因此要取log，算是一种计算技巧。

#include 
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 1e3 + 5;

using namespace std;

struct edge
{
    int to;
    double dis;
    int next;
} e[4005];
int head[N], idx = 0;
void addedge(int u, int v, double dis)
{
    e[++idx].to = v;
    e[idx].dis = dis;
    e[idx].next = head[u];
    head[u] = idx;
}

int n, m, a, b, c, d, cnt[N];
double dis[N], w;
bool inq[N];

bool check() //检查是否存在正环
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = 0;
        inq[i] = 1;
        cnt[i] = 0;
        q.push(i);
    }
    while (q.size())
    {
        int u = q.front();
        q.pop();
        inq[u] = 0;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            if (dis[u] + e[i].dis + w > dis[v])
            {
                dis[v] = dis[u] + e[i].dis + w;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = 1;
                }
                if (++cnt[v] >= n) return true;
            }
        }
    }
    return false;
}

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    mem(head, 0);
    cin >> n >> m;
    while (m--)
    {
        cin >> a >> b >> c >> d;
        addedge(b, d, log((double)c / (double)a));
    }
    double l = 0, r = 1, mid;
    while (r - l > 1e-8)
    {

        mid = (l + r) / 2;
        w = log(mid);
        if (check())
            r = mid;
        else
            l = mid;
    }
    printf("%.8lf", mid);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

G-Link with Monotonic Subsequence

题目大意：
构造一个排列，使其 max(lis(p), lds(p)) 最小。

思路：
结论是以√n的大小进行分组，然后输出。
猜到这个结论后进行反证即可，但是没猜到的话还是比较难想的。

H-Take the Elevator

题目大意：
n 个人坐电梯，楼高 m ，每个人有起始楼层和目标楼层。电梯有载客量限制 k ，上升时可以上升到任意层并随时下降，但是下降要一直下降到一层才能再上升。电梯每秒运行一层，换方向和上下人不占用时间，问电梯最短运行时间。

思路：
官方发的题解比较清楚，这里就不过多地写了。
每个人可以看作一条线段，本题就是一个线段覆盖问题，贪心地考虑，上升的时候尽量让上升楼层高的人先进入电梯，下降的时候尽量让下降楼层低的人进入电梯。上升时判断一个人是否还能进入电梯的条件是这个人出电梯的楼层是否不高于下一个人上电梯的楼层，下降的时候反之。然后用set来维护每个人出电梯和进入电梯的情况即可。

AC代码

#include 
#define inf 0x3f3f3f3f
using namespace std;

struct seg
{
    long long pos1, pos2;
};
bool operator<(seg a, seg b) { return a.pos2 > b.pos2; }

multiset<seg> up, down, upt, downt;

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    long long n, m, k, a, b;
    long long ans = 0;
    cin >> n >> m >> k;
    for (long long i = 0; i < n; i++)
    {
        cin >> a >> b;
        if (a > b) // down
            down.insert({b, a});
        else
            up.insert({a, b});
    }
    while (n)
    {
        long long maxh = -inf, nowpos;
        if (up.size()) maxh = up.begin()->pos2;
        if (down.size()) maxh = max(maxh, down.begin()->pos2);
        nowpos = up.begin()->pos2;
        ans += (maxh - 1) * 2;
        while (up.size())
        {
            while (upt.size() < m)
            {
                auto it = up.lower_bound({0, nowpos}); //找到小于nowpos的最大r
                if (it == up.end()) break;
                upt.insert({it->pos2, it->pos1});
                nowpos = it->pos2;
                up.erase(it);
                n--;
            }
            if (!upt.size()) break;
            auto it = upt.begin(); //找到最大的l
            nowpos = it->pos2;
            upt.erase(it);
        }
        nowpos = down.begin()->pos2;

        while (down.size()) //下降的时候操作和上升一样，因为前面在插入的时候将a和b的位置互换了
        {
            while (downt.size() < m)
            {
                auto it = down.lower_bound({0, nowpos}); //找到最大的l
                if (it == down.end()) break;
                downt.insert({it->pos2, it->pos1});
                nowpos = it->pos2;
                down.erase(it);
                n--;
            }
            if (!downt.size()) break;
            auto it = downt.begin(); //找到最大的r
            nowpos = it->pos2;
            downt.erase(it);
        }
    }
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

J-Link with Arithmetic Progression

直接套用线性回归的板子即可。

#include 
#define inf 0x3f3f3f3f
const long long N = 3e5 + 5;
using namespace std;

namespace GTI //快读模板
{
    char gc(void)
    {
        const long long S = 1 << 16;
        static char buf[S], *s = buf, *t = buf;
        if (s == t) t = buf + fread(s = buf, 1, S, stdin);
        if (s == t) return EOF;
        return *s++;
    }
    long long gti(void)
    {
        long long a = 0, b = 1, c = gc();
        for (; !isdigit(c); c = gc())
            b ^= (c == '-');
        for (; isdigit(c); c = gc())
            a = a * 10 + c - '0';
        return b ? a : -a;
    }
}
using GTI::gti;

long long num[N];

signed main()
{
    long long T;
    T = gti();
    while (T--)
    {
        long long n = gti();
        long long sxy = 0, sx = 0, sy = 0, sx2 = 0;
        long double b, a, ans = 0;
        for (long long i = 1; i <= n; i++)
        {
            num[i] = gti();
            sxy += i * num[i];
            sx += i;
            sy += num[i];
            sx2 += i * i;
        }
        b = ((long double)n * sxy - (long double)sx * sy) / ((long double)n * sx2 - (long double)sx * sx);
        a = (long double)sy / n - b * sx / n;
        long double ai = a;
        for (long long i = 1; i <= n; i++)
        {
            ai += b;
            ans += (num[i] - ai) * (num[i] - ai);
        }
        printf("%.10lf\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

K-Link with Bracket Sequence I

题目大意：
给定两种操作（空序列也是合法序列）

• 给一个合法的括号序列的外部套上一层括号
• 将两个合法的括号序列拼接在一起

构造一个长为m的序列，使其子序列可以构成题目给定的序列，求出方案数。

思路：
一般这种问题都是用动规来解决，关键在于如何构造转移方程和状态表示。
根据提供的两种操作，任意取序列的前i个，不可能出现左括号少于右括号的情况，那么dp的一个维度可以是左括号比右括号多k个的情况。
于是将状态表示为：

dp[i][j][k]表示取序列的前i个，与给定序列的lcs为j，左括号比右括号多k个时的方案数
1

状态转移方程：
在每一个状态后面我们可以选择添加左括号或是右括号，根据给定序列的j+1位是否匹配来决定转移的方式，在添加右括号时需要注意右括号的数量不能超过左括号。

if (k) //在dp[i][j][k]的末尾加')'
{
    if (a[j + 1] == ')')
        dp[i + 1][j + 1][k - 1] = (dp[i + 1][j + 1][k - 1] + dp[i][j][k]) % mod;
    else
        dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % mod;
}
if (a[j + 1] == '(') //给定序列的j+1位是左括号
    dp[i + 1][j + 1][k + 1] = (dp[i + 1][j + 1][k + 1] + dp[i][j][k]) % mod;
else
    dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
1
2
3
4
5
6
7
8
9
10
11

AC代码：

#include 
const int N = 205;
using namespace std;
const long long mod = 1e9 + 7;
long long dp[N][N][N]; // dp[i][j][k]表示b的前i个,与a的lcs为j,左括号比右括号多k个

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    char a[N];
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        cin >> a + 1;
        for (int i = 0; i <= m; i++)
            for (int j = 0; j <= min(i, n); j++)
                for (int k = 0; k <= i; k++)
                    dp[i][j][k] = 0;
        dp[0][0][0] = 1;
        //为了防止出现重复的计算，用小的情况更新大的情况
        //由于加括号的方式限制，不可能出现左括号少于右括号的情况
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j <= min(i, n); j++)
            {
                for (int k = 0; k <= i; k++)
                {
                    if (k) //在dp[i][j][k]的末尾加')'
                    {
                        if (a[j + 1] == ')')
                            dp[i + 1][j + 1][k - 1] = (dp[i + 1][j + 1][k - 1] + dp[i][j][k]) % mod;
                        else
                            dp[i + 1][j][k - 1] = (dp[i + 1][j][k - 1] + dp[i][j][k]) % mod;
                    }
                    if (a[j + 1] == '(') //在dp[i][j][k]的末尾加'('
                        dp[i + 1][j + 1][k + 1] = (dp[i + 1][j + 1][k + 1] + dp[i][j][k]) % mod;
                    else
                        dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod;
                }
            }
        }
        printf("%lld\n", dp[m][n][0]);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

L-Link with Bracket Sequence I

题目大意：
有 n 个世界，每个世界是一张简单有向图。从这些世界中选择一个子段进行游戏，规则为从 1 出发，每个世界可以原地不动或经过一条边，到达点 m 即为胜利。要求选出一个尽可能短的子段，使得存在至少一种方案可以胜利。

思路：
还是一道动态规划的题目，因为要选取最短的子段，需要知道要从一个世界到达另一个世界，最晚可以从哪个世界出发。
于是将状态设置为：

dp[i][j]表示从第i个世界到第j个世界，最晚可以从哪个世界出发
状态转移方程为：
在一个世界可以选择不动，那么dp[i][j]=dp[k][i]; //k是在i之前的所有世界
在一个世界进行移动，那么dp[i][j]=max(dp[i][j], dp[k][i]); //k是在i之前且能够到达i的世界
1
2
3
4

AC代码

#include 
#define inf 0x3f3f3f3f
const int N = 1e4 + 5;
const int M = 2e3 + 5;
using namespace std;

int dp[2][M], ans = inf;
vector<pair<int, int>> world[N];

signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, l, u, v;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> l;
        while (l--)
        {
            cin >> u >> v;
            world[i].push_back({u, v});
        }
    }
    if (m == 1)
        cout << "0";
    else
    {
        for (int i = 0; i < M; i++)
            dp[0][i] = -inf;
        dp[0][1] = 0;
        int idx = 0;
        for (int i = 1; i <= n; i++)
        {
            idx ^= 1;
            dp[idx][1] = i;
            for (int j = 2; j <= m; j++) //在当前世界不进行移动
                dp[idx][j] = dp[idx ^ 1][j];
            for (auto e : world[i]) //在当前世界进行移动
            {
                dp[idx][e.second] = max(dp[idx ^ 1][e.first], dp[idx][e.second]);
                if (e.second == m)
                    ans = min(ans, i - dp[idx][m]);
            }
        }
        if (ans <= 1e4)
            cout << ans;
        else
            cout << "-1";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51