Lowlight's ACM Blog

一个蒟蒻的题解记录

0%

发表于 更新于
本文字数： 3.4k 阅读时长 ≈ 6 分钟

A Two Vessels

You have two vessels with water. The first vessel contains $a$ grams of water, and the second vessel contains $b$ grams of water. Both vessels are very large and can hold any amount of water.
You also have an empty cup that can hold up to $c$ grams of water.
In one move, you can scoop up to $c$ grams of water from any vessel and pour it into the other vessel. Note that the mass of water poured in one move does not have to be an integer.
What is the minimum number of moves required to make the masses of water in the vessels equal? Note that you cannot perform any actions other than the described moves.

思路

数学题，但是要注意数据类型均为小数

代码

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
#include<iostream>
#include<cmath>
using namespace std;
void solve()
{
    // 两个水管
    //第一个有a克水
    //第二个有b克水
    //你有一个可以放c克水的杯子
    //你每次可以从一个管子里拿出最多c克的水（不一定是整数）放进另一个管子
    int a,b,c;
    cin>>a>>b>>c;
    cout<<ceil(((abs(a-b)/2.0)/(c*1.0)))<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
	}
    return 0;

}

B 游游的字符重排

You are in a corridor that extends infinitely to the right, divided into square rooms. You start in room $1$, proceed to room $k$, and then return to room 1. You can choose the value of $k$. Moving to an adjacent room takes $1$ second.

Additionally, there are $n$ traps in the corridor: the i-th trap is located in room $d_i$ and will be activated $s_i$ seconds after you enter the room $d_i$. Once a trap is activated, you cannot enter or exit a room with that trap.

A schematic representation of a possible corridor and your path to room $k$ and back.
Determine the maximum value of $k$ that allows you to travel from room $1$ to room $k$ and then return to room $1$ safely.
For instance, if n=1 and $d_1=2,s_1=2$, you can proceed to room $k=2$ and return safely (the trap will activate at the moment $1+s_1=1+2=3$, it can’t prevent you to return back). But if you attempt to reach room $k=3$, the trap will activate at the moment $1+s_1=1+2=3$ preventing your return (you would attempt to enter room 2 on your way back at second 3, but the activated trap would block you). Any larger value for k is also not feasible. Thus, the answer is $k=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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct Trap{
    int activateSeconds;
    int roomNum;
};
int cmp(Trap a,Trap b)
{
    return a.roomNum<b.roomNum;
}
void solve()
{
    //模拟各个房间的状态
    //数据集很小，直接暴力
    //告诉你有n个陷阱，要求你求出最大可能到达的k房间并回来不会触发陷阱的k
    //你每次只能往右前进一格
    int trapsNum;
    int timestamp=0;
    int flag=0;
    cin>>trapsNum;
    int k=0;
    vector<Trap> traps(trapsNum);
    for(int i=0;i<trapsNum;i++)
    {
        cin>>traps[i].roomNum>>traps[i].activateSeconds;
    }
    sort(traps.begin(),traps.end(),cmp);
    //你到a房间的用时为a
    //你从k房间回到a房间的时间是k+k-a=2k-a
    //炸弹激活的时间是a+activateSeconds
    //如果炸弹激活时间比回到t房间时间早，则这个k无效，取k--
    for(;;k++)
    {
        for(Trap &t:traps){
            if(t.roomNum+t.activateSeconds<=2*k-t.roomNum)
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
            break;
    }
    cout<<k-1<<endl;
    
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}```
# C 游游开车出游
游游准备开车出游，她的车非常特殊，油越多则最高速度越快，即最高速度和油量是成正比的。另外，行驶过程中油是不会消耗的。
已知游游的车初始的最高速度为$v_0$，当游游花费了$t$时间加油时，车的最高速度会变成$v_0+t∗x$。
游游开车的总里程为$y$，假设游游始终以最高速度行驶（即忽略加速时间），游游想知道，自己最少花费多少时间可以完成出游？
## 思路
纯数学题？纯数学题？纯数学题？
对公式进行求导，然后得到导数的极值点，再代回原式
梦回高中
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    long double v0,x,y;
    cin >> v0 >> x >> y;
    if(v0 > sqrt(x*y)) printf("%.12llf",y/v0);
    else printf("%.12llf",2*sqrt(y/x) - v0/x);
}

int main() {
    solve();
    return 0;
}

发表于 更新于
本文字数： 2.2k 阅读时长 ≈ 4 分钟

A 游游的最长稳定数组

游游定义一个数组为“稳定的”，当且仅当数组相邻的两个元素之差的绝对值不超过1。例如$[2,3,2,2,1]$是稳定的，而$[1,3,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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,a[N];
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int res = 0;
    for(int i = 1; i <= n; i++)
    {
        int length = 1;
        for(int j = i + 1; j <= n; j++)
        {
            if(abs(a[j] - a[j - 1]) <= 1) length++;
            else
            {
                i = j - 1;
                break;
            }
        }
        res = max(length,res);
    }
    cout << res << '\n';
}

int main() {
    solve();
    return 0;
}

B 游游的字符重排

游游定义一个字符串是“好串”，当且仅当该字符串相邻的字符不相等。例如”arcaea”是好串，而”food”不是好串。
游游拿到了一个字符串，她可以将该字符串的各个字符顺序随意打乱。她想知道一共可以生产多少种不同的好串？

思路

全排列，直接将字符串视为一串ASCII的数字数组然后求这个数组的全排列就行。因为数据范围足够小（字符数小于等于10），所以可以直接暴力枚举

补充：next_permutation

和prev_permutation相对，作为获取全排列时可以使用的非常方便俩函数
next_permutation在使用的时候会自动获取传入的“上一个序列”，所以如果想要获取全排列，next_permutation要和sort连用，并且sort的规则为升序排序
基本用法：

1
2
3
4
5
6
7
8
9
int n=5;
int a[n];
for(int i=0;i<n;i++)
    cin>>a[i];
do{
    for(int i=0;i<n;i++)
        cout<<a[i]<<' ';//打印全排列
    cout<<endl;
}while(next_permutation(a,a+n,cmp));

同样的，struct和vector也可以使用这个函数，但是比较函数要自定义，并且在全排列之前也要升序

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
string s;
void solve()
{
    cin >> s;
    int n = s.size();
    for(int i = 0; i < s.size(); i++) a[i] = s[i] - 'a';
    sort(a,a + n);
    int result = 0;
    do
    {
        bool flag = true;
        for(int i = 1; i < n; i++)
        {
            if(a[i] == a[i - 1])
            {
                flag = false;
                break;
            }
        }
        if(flag) result++;
    }while(next_permutation(a,a + n));
    cout << result << endl;
}

int main() {
    solve();
    return 0;
}

C 游游开车出游

游游准备开车出游，她的车非常特殊，油越多则最高速度越快，即最高速度和油量是成正比的。另外，行驶过程中油是不会消耗的。
已知游游的车初始的最高速度为$v_0$，当游游花费了$t$时间加油时，车的最高速度会变成$v_0+t∗x$。
游游开车的总里程为$y$，假设游游始终以最高速度行驶（即忽略加速时间），游游想知道，自己最少花费多少时间可以完成出游？

思路

纯数学题？纯数学题？纯数学题？
对公式进行求导，然后得到导数的极值点，再代回原式
梦回高中

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    long double v0,x,y;
    cin >> v0 >> x >> y;
    if(v0 > sqrt(x*y)) printf("%.12llf",y/v0);
    else printf("%.12llf",2*sqrt(y/x) - v0/x);
}

int main() {
    solve();
    return 0;
}