D Link with Game Glitch

Link is developing a game. In this game, players can craft things using various types of resources, and things crafted can also be used to craft other things.

Formally speaking, there are nn types of items, numbered from 11 to nn, and mm recipes in the game. In the ii-th recipe, players can use ka_ik∗ai​ items of the b_ibi​-th type to craft kc_ik∗ci​ items of the d_idi​-th type, where kk can be any positive real number.

One day, he finds that one player owns more than 18,446,744,073,709,551,615 identical items, which causes a server crash. This is obviously impossible without using glitches.

Link soon finds out that there is something wrong with the crafting recipe. Players may get infinite resources by crafting some special things over and over again!

Link doesn’t want to adjust the recipes one by one, so he simply added an argument ww. Now players can use ka_ik∗ai​ items of the b_ibi​-th type to craft wk*c_iw∗k∗ci​ items of the d_idi​-th type.

Link wonders: What’s the maximum ww that he can set so that no player can get infinite items by crafting things over and over again?

在游戏中有n中物品和m种兑换规则，你可以用$k\ast a_i个b_i去兑换k\ast c_i个d_i$,k不一定是整数
但是这个规则出现了问题，即图中出现了边权积大于1的环
这里我们可以用二分求得答案
由于边权积过大，long long肯定是不够的，我们可以把边权转化为对数，再用bellman_ford算法（有负权边）求最短路，如果出现大于0的距离，即$logx>0$那么则有x大于1，说明二分的该答案有问题，继续向下二分得到结果
tags:二分 最短路(Bellman_Ford)

AC代码

/****************
 *@description:for the Escape Project
 *@author: Nebula_xuan
 * @Date: 2022-07-26 11:22:44
 *************************************************************************/

#include 

using namespace std;
const int N = 1e3 + 10, M = 2e3 + 10;
const double eps = 1e-9;
long long n, m, a[M], b[M], c[M], d[M];
double dist[N], w[M];
int Bellman_Ford()
{
    for (int i = 1; i <= n; i++)
        dist[i] = 0.0;
    bool flag = false;
    for (int i = 1; i < n; i++)
    {
        flag = false;
        for (int j = 1; j <= m; j++)
        {
            if (dist[b[j]] + w[j] < dist[d[j]])
            {
                flag = true;
                dist[d[j]] = dist[b[j]] + w[j];
            }
        }
        if (!flag)
            return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    double l = 0.0, r = 1.0;
    while (r - l > eps)
    {
        double mid = (l + r) / 2.0;
        for (int i = 1; i <= m; i++)
            w[i] = -log(1.0 * c[i] * mid / a[i]);
        if (!Bellman_Ford())
            l = mid;
        else
            r = mid;
    }
  	printf("%.10lf\n",l);
}
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

K Link with Bracket Sequence I

Link has a bracket sequence aa of length nn, which is a subsequence of a valid bracket sequence bb of length mm.

Link doesn’t remember bb, so he wonders the number of possible sequences bb.

A bracket sequence is valid if it satisfies any of the following conditions:

• Its length is 00.

• It can be represented as (A)(A), where AA is a valid bracket sequences.

• It can be represented as ABAB, where AA and BB are both valid bracket sequence.

A sequence aa is a subsequence of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements.

给你一个长度为n的括号序列，问你长度为m的原序列（且合法）的情况有多少种
这里我们用DP进行考虑，有$f[i][j][k]$,其中i表示原序列的长度
,j表示匹配的长度，k表示左括号比右括号多k的时的方案数
当我们选择添加一个左括号时，可以随意添加
但是如果我们添加的是一个右括号，当且仅当左括号数量大于右括号数量的时候匹配才成立

tags:DP

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-26 10:48:24

 *************************************************************************/

  

#include 

  

using namespace std;

  

const int N = 2e2 + 10;

long long  f[N][N][N];

const int MOD = 1e9 + 7;

int main()

{

    int t;

    cin >> t;

    while (t--)

    {

        int n, m;

        cin >> n >> m;

        string a;

        cin >> a;

        a=" "+a;

        for (int i = 0; i <= m; i++)

            for (int j = 0; j <= n; j++)

                for (int k = 0; k <= m; k++)

                    f[i][j][k] = 0;

        f[0][0][0] = 1;

        for (int i = 0; i < m; i++)

        {

            for (int j = 0; j <= n; j++)

            {

                for (int k = 0; k <= i; k++)

                {

                    if (a[j + 1] == '(')

                        f[i + 1][j + 1][k + 1] = (f[i + 1][j + 1][k + 1] + f[i][j][k]) % MOD;

                    else

                        f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % MOD;

                    if (k)

                    {

                        if (a[j + 1] == ')')

                            f[i + 1][j + 1][k - 1] = (f[i + 1][j + 1][k - 1] + f[i][j][k]) % MOD;

                        else

                            f[i + 1][j][k - 1] = (f[i + 1][j][k - 1] + f[i][j][k]) % MOD;

                    }

                }

            }

        }

        cout << f[m][n][0] << endl;

    }

}
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

G Link with Monotonic Subsequence

First, let’s review some definitions. Feel free to skip this part if you are familiar with them.

A sequence aa is an increasing (decreasing) subsequence of a sequence bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements and all elements are in increasing (decreasing) order from the beginning to the end.

A permutation is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array) and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

The problem starts from here.

Link has an array. He is currently learning the longest increasing subsequence algorithm. So he comes up with the following question.

Let the value of a permutation pp be \max({\rm lis}§,{\rm lds}§)max(lis§,lds§), where {\rm lis}§lis§ is the length of the longest increasing subsequence of pp and {\rm lds}§lds§ is the length of the longest decreasing subsequence of pp. For all permutations of length nn, which one has the minimum value?

给你一个数字n，你需要构造一个1-n的排列，排列的价值为
最长上升子序列长度和最长下降子序列长度的最大值，问你这个的最小值是多少
这里我们采取的方式是组内升序，组间降序，那么我们把它分成sqrt(n)个组，每个组内有sqrt(n)个数，那么答案就是
sqrt(n)

tags:思维

AC代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 550000
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t,n;
cin>>t;
while (t--){
    cin>>n;
    int u=sqrt(n-1)+1;
    int y=(n-1)/u+1,res=u;
    for(int i=1;i<=y;i++){
        if(i==y){
            //cout<<"??"<
            for(int j=n;j>res-u;j--){
                cout<<j<<" ";
            }
        }
        else{
            for(int j=res;j>res-u;j--){
                cout<<j<<" ";
            }
        }
        res+=u;
    }
    cout<<endl;
}
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

H Take the Elevator

There is a tall building called Arasaka Tower in the center of the Night City. People go up and down in the Arasaka Tower every day.

Arasaka Tower has kk floors. Today, there are nn people going to take the elevator, the ii-th person wants to go from the a_iai​-th floor to the b_ibi​-th floor. The elevator may carry up to mm people at a time, and it starts from the first floor. The elevator takes 11 unit of time to go up or down one floor. The time people enter and exit the elevator can be ignored.

However, there is something wrong with the elevator today. The running direction of the elevator can no longer be changed arbitrarily. When the elevator is going down, it can change its running direction if and only if it reaches the first floor.

What is the minimum time to carry all people to their destination and let the elevator back to the first floor?

现有一个k层楼的房子，电梯从一楼出发，最多承载m人，但是电梯向下运行时必须到达一楼才可改变方向
其中有m人希望从$a_i-b_i$，每向上或向下走需要花费1个单位的时间，问能满足要求的最小花费时间
因为限制了下降就必须到达最底层，所以我们应该贪心的选择先转移楼层高的，对于每个人的要求我们把他看成一个线段，即从$a_i+1到b_i$,用差分处理再使用前缀和就可以得到经过i层楼的总上行人数和总下行人数
我们不妨定义为c[i]为i趟电梯到达的最高楼层，然后我们取后缀最大值乘2即可得到答案
tags：思维 离散化 模拟

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-27 11:21:53

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

  

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

  

typedef pair<int, int> PII;

typedef long long ll;

const int N =4e5 + 10;

ll a[N], b[N], c[N], up[N], down[N];

vector<int> A;

signed main()

{

    ios::sync_with_stdio(false);

    int n, m, k;

    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++)

    {

        cin >> a[i] >> b[i];

        A.push_back(a[i]);

        A.push_back(b[i]);

    }

    sort(A.begin(), A.end());

    A.erase(unique(A.begin(), A.end()), A.end());

    int sz = A.size();

    rep(i, 1, n)

    {

        int x = lower_bound(A.begin(), A.end(), a[i]) - A.begin();

        int y = lower_bound(A.begin(), A.end(), b[i]) - A.begin();

        if (x < y)

            up[x + 1]++, up[y + 1]--;

        else

            down[y + 1]++, down[x + 1]--;

    }

    int cnt1 = 0, cnt2 = 0;

    rep(i, 0, sz)

    {

        cnt1 += up[i];

        cnt2 += down[i];

        int idx = max((cnt1 - 1) / m + 1, (cnt2 - 1) / m + 1);

        c[idx] = max(c[idx], A[i] - 1);

    }

    int ans = 0;

    dep(i, n, 1)

    {

        c[i] = max(c[i], c[i + 1]);

        ans += c[i];

    }

    cout << ans * 2;

}
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

J Link with Arithmetic Progression

题目描述

The input size for this problem is huge, you may refer to the code in notes for faster input.

Be aware of the error caused by using floating point numbers.

Link has an array aaa of length nnn. NIO wants it to be an arithmetic progression(i.e., ai=a1+(i−1)da_i = a_1+(i-1)dai​=a1​+(i−1)d).

Link can arbitrarily modify the value of aia_iai​. For each iii, he can modify at most once. Suppose Link changed the value from aia_iai​ to ai′a_i’ai′​, the cost is ∑i=1n(ai−ai′)2\sum_{i=1}^{n(a_i-a_i’)}2∑i=1n​(ai​−ai′​)2.

What is the minimum cost to make aaa an arithmetic progression?

输入描述:

Each test contains multiple test cases. The first line contains the number of test cases TTT (1≤T≤10001 \le T \le 10001≤T≤1000). Description of the test cases follows.

The first line contains an integer nnn (3≤n≤1053 \leq n \leq 10^53≤n≤105).

The second line contains nnn integers a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​ (∣ai∣≤109|a_i| \leq 10^9∣ai​∣≤109).

It is guaranteed that the sum of nnn over all test cases does not exceed 10610^6106.

输出描述:

For each case, output your answer in one line.

Your answer is considered correct if its absolute or relative error does not exceed 10−610^{-6}10−6.

Formally, let your answer be aaa, and the jury’s answer be bbb. Your answer is accepted if and only if ∣a−b∣max⁡(1,∣b∣)≤10−6\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}max(1,∣b∣)∣a−b∣​≤10−6.

输入

3
3
-1 0 1
3
0 0 1
13
1 1 4 5 1 4 1 9 1 9 8 1 0

输出

0.000000000000000
0.166666666666667
129.225274725274716

说明

In the second example, you may change aaa to [−16,13,56][-\frac{1}{6},\frac{1}{3},\frac{5}{6}][−61​,31​,65​] to minimize the cost.

给你一个n长的数组，改变这些数字使得该数组变为一个等差数组，问修改的代价最小为多少
用线性回归方程进行求解即可，注意精度问题

AC代码

/****************
 *@description:for the Escape Project
 *@author: Nebula_xuan
 * @Date: 2022-07-23 15:50:13
 *************************************************************************/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#include 
namespace GTI
{
    char gc(void)
    {
        const int 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++;
    }
    int gti(void)
    {
        int 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;
#define rep(i, h, t) for (int i = h; i <= t; i++)
#define dep(i, t, h) for (int i = t; i >= h; i--)
#define endl char(10)
const int N = 1e5 + 10;
double w[N];
signed main()
{
    int t;
    t = gti();
    while (t--)
    {
        int n;
        n = gti();
        double sum = 0;
        for (int i = 1; i <= n; i++)
        {
            w[i] = gti();
            sum += w[i];
            //  printf("%lf", w[i]);
        }

        double y_ = 1.0 * sum / (n * 1.0);
        double x_ = 1.0 * (1 + n) / (2 * 1.0);

        double temp1 = 0, temp2 = 0;
        for (int i = 1; i <= n; i++)
        {
            temp1 += (i - x_) * (w[i] - y_);
            temp2 += (i - x_) * (i - x_);
        }
       // printf("%lf--%lf", temp1, temp2);
        double b = temp1 / temp2;
        double a = y_ - b * x_;
        double ans = 0;
        for (int i = 1; i <= n; i++)
        {
            long double y1 = b * i + a;
            ans += (y1 - w[i]) * (y1 - w[i]);
        }
        printf("%.15lf\n", ans);
    }
}
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
83
84

L Link with Level Editor I

Please pay attention to the unusual memory limit.

Link is playing a game, called NIO’s Game.

In this game, a level consists of several worlds. Each world consists of mm nodes and some directed roads. The player starts on node 11 of the first world. In each world, the player can either stay at current node or go through exactly one road that exists in that world. After that, the player will be teleported to the next world without changing the ID of the node where he stays. If there is no next world, the game ends. The player wins if he ends on node mm.

Link is editing a new level, he has already made nn worlds (numbered from 11 to nn) and wants to choose a continuous subsegment of them to form a new level. The only limit is that there should be at least one way to win.

Link doesn’t want to use too many worlds. What is the minimum number of worlds Link needs to use in the new level?

给你n个世界（平面），每个世界都有m个结点和一些有向道路
每次移动你可以不动掉到下一个世界或者沿着有向边走一格
问到达m的最小需要的世界数
这题玩糖豆人的应该很好理解hh),
不妨设$f[i][j]$为在第i个世界到达点j需要的最小世界数，但是看数据范围发现明显不够用，考虑到当前状态只和上一个世界有关，所以我们用滚动数组来优化DP
因为我们可以从任一世界开始，所以f[1]=0
然后我们设g[i]为走有向边，f[i]为不走的状态

tags:线性DP 滚动数组优化

AC代码

/****************

 *@description:for the Escape Project

 *@author: Nebula_xuan

 * @Date: 2022-07-26 22:09:57

 *************************************************************************/

  

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

  

using namespace std;

  

#define xx first

#define yy second

#define rep(i, h, t) for (int i = h; i <= t; i++)

#define dep(i, t, h) for (int i = t; i >= h; i--)

#define endl char(10)

#define int long long

//记得%d应该写成%lld

  

typedef pair<int, int> PII;

typedef long long ll;

const int N = 1e4 + 10;

int f[N], g[N];

signed main()

{

    ios::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

    int ans = 0x3f3f3f3f;

    memset(f, 0x3f, sizeof f);

  

    rep(j, 1, n)

    {

        f[1] = 0;

        int l;

        cin >> l;

        memset(g, 0x3f, sizeof g);

        while (l--)

        {

            int u, v;

            cin >> u >> v;

            g[v] = min(g[v], f[u] + 1);

        }

        for (int i = 1; i <= m; i++)

            f[i] = min(f[i] + 1, g[i]);

        ans = min(ans, f[m]);

    }

    if (ans == 0x3f3f3f3f)

        cout << -1;

    else

        cout << ans;

}
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117