Znzryb's Blog
0%

Posted on Edited on

题目大意

题目： C. 带有分数的游戏

题意：
Alice 和 Bob 玩一个游戏，初始有两个整数 pp 和 qq。Alice 先手，两人轮流进行操作。
每回合玩家可以执行以下操作之一：

  1. 将 pp 减少 1（需满足 p>0p > 0）。

  2. 将 qq 减少 1（需满足 q>1q > 1）。

游戏在 p=0p=0 且 q=1q=1 时结束。

胜负判定：

  • Bob 获胜：如果在游戏过程中的任意时刻（包括初始状态），分数 pq\frac{p}{q} 的值等于 23\frac{2}{3}。

  • Alice 获胜：如果游戏结束时 Bob 仍未获胜。
    假设双方都采取最优策略，判断谁是赢家。

样例解释：

  • 输入 4 6：初始 46=23\frac{4}{6} = \frac{2}{3}，Bob 立即获胜。

  • 输入 10 14：双方博弈过程中，可能会到达状态 p=8,q=12p=8, q=12，此时 812=23\frac{8}{12} = \frac{2}{3}，Bob 获胜。

  • 输入 15 15：Alice 存在必胜策略，使得游戏过程中分数永远不等于 23\frac{2}{3}，最终 Alice 获胜。

思路讲解

不难推出，3P 小于2Q 时无答案。（糖水不等式就是把，这个糖水不等式就是把糖从溶液里面抠出来，溶液质量和糖的质量它都会减。按照实际生活常识，我们知道此时溶液浓度肯定是下降的，因为你少加点糖，那溶液浓度总归是减的呀，不会增呀，对吧？）

image

那么 P 除以 Q 大于2/3是比较棘手的这个情况。然后我们又进行了一下分类讨论，然后说明了 P 除以 Q 大于等于一的时候，一定是没有解的。这是根据糖水不等式，其实就是颠倒个个嘛，就是颠倒个，就是水和糖不一样了，那么这个结果 也也是自然是不一样的。然后是 p 除以 q 大于2/3小于一的时候，那么就是这个时候是 Bob 一定是赢的，因为 我们写在这个图片里面了，它一定有一个合法解。

image

image

AC代码

AC

https://codeforces.com/contest/2197/submission/362464859

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

这是一道交互题，你的程序会对每个测试用例被运行两次。

编码阶段（Encode）：给你一个长度为 nn 的二进制串 ss（仅含 0 和 1），你需要输出一个长度同为 nn 的三进制串（可使用 0、1、2）。

解码阶段（Decode）：你在编码阶段输出的三进制串会被做一次循环旋转（即取某个后缀拼上对应的前缀，也可能不旋转），然后作为输入给你。你需要根据这个被旋转过的三进制串，还原出编码阶段的原始二进制串。

换句话说，你需要设计一种编码方案，使得即使编码后的串被任意循环旋转，你仍然能唯一地解码出原始二进制串。编码串长度必须和原串相同，且只能使用三种字符。

数据范围：1≤n≤1051 \le n \le 10^5。

样例 1：编码阶段，原始串为 001，编码输出 002。解码阶段，收到的是 002 循环旋转后的 200，需要还原出 001。

1
2
3
4
5
6
7
输入（编码阶段）：
Encode
3
001

输出：
002
1
2
3
4
5
6
7
输入（解码阶段）：
Decode
3
200

输出：
001

样例 2：编码阶段，原始串为 0100，编码输出 2100。解码阶段，收到的恰好没有旋转，仍为 2100，需要还原出 0100。

1
2
3
4
5
6
7
输入（编码阶段）：
Encode
4
0100

输出：
2100
1
2
3
4
5
6
7
输入（解码阶段）：
Decode
4
2100

输出：
0100

思路讲解

使用二二作为分隔符。其他地方不允许出现二二为分隔符的这个情况。

长度大于8位的时候，使用二二作为分隔符，把这个字符串，把二进制字符串的前8位转化为6位，然后前面添上二二。然后转换的这6位三进制字符串要求第一位 不能为二，最后一位不能为二，然后其中不能有二二这样子的字符。然后这样子转好以后，然后就好了。这样子转好以后呢，在解码的时候，我们就能够看到这个22的地方，然后我们知道我们的22都是放在开头的，我们就知道这个字符串它到底被循环移动了几位。

之所以不用二作为分隔符，就是不用一个二作为分隔符，是因为只用一个二的话，那么相当于你后面的就是二进制的字符串了，你后面就是一个二进制的字符串了，它造成了非常大量的信息的损失，所以我们就选用二二作为分隔符。当然你也可以用三个二，用四个二作为分隔符，但是那个可能会更加复杂。谢谢，但是意思反正是这个意思。

那么如果说长度小于8位的时候呢？长度小于8位的时候，我们是这样子做，就是直接暴力的进行双射就可以了。

包括长度大于8位，怎么把那6位给转回8位，我们也是用双设，就是直接我们下面放一个这个代码吧，就是非常暴力的。

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
const ll len2=8,len3=6;
vector<string> two_s;
// 生成该长度的二进制串
for (ll status=0;status<(1<<len2);++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+(op_status&1));
        op_status/=2;
    }
    sta.resize(len2,'0');
    two_s.push_back(sta);
}
ll idx=0;
for (ll status=0;status<pow_three[len3];++status) {
    string sta;
    ll op_status=status;
    while (true) {
        if (op_status==0) {
            break;
        }
        sta.push_back('0'+op_status%3);
        op_status/=3;
    }
    sta.resize(len3,'0');
    // 不允许开头为 2 ,这个是因为如果说开头为二的话，会造成一些问题。就是开头二如果连着前面那个二，然后就就，它会造成一个连接，能相当于又造出来一个二二，这个是会造成混乱的。
    if (!(sta.find("22")==-1 && sta.front()!='2')) {
        continue;
    }
    three_to_two[sta]=two_s[idx];
    two_to_three[two_s[idx]]=sta;
    ++idx;
    if (idx>=two_s.size()) {
        break;
    }
}

AC代码

AC
https://qoj.ac/submission/2031795
AC
https://codeforces.com/gym/106129/submission/362719223

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目名称：Around the Table

题意总结：
公园里有一张乒乓球桌，初始时左边队列有 ℓ\ell 个人，右边队列有 rr 个人。左边队首的人先持球。
游戏规则如下：

  1. 持球者将球打到对面，然后立刻跑到对面队列的队尾。

  2. 对面队首的人接球后成为新的持球者，重复上述过程。
    假设游戏进行无限次（101010010^{10^{100}} 次击球），你需要计算总共会出现多少对不同的“对决组合”。
    注意：两个人面对面即为一次对决，A 对战 B 与 B 对战 A 被视为同一种组合，不重复计算。

输入格式：
一行包含两个整数 ℓ\ell 和 rr （2≤ℓ≤109,1≤r≤1092 \le \ell \le 10^9, 1 \le r \le 10^9），分别表示初始时左侧和右侧的人数。

输出格式：
输出一个整数，表示会出现的不同对决组合的数量。

样例 1 解释：
输入：2 2
输出：6
假设左边初始为 A, B，右边初始为 D, E。
流程推演：

注意啊，题目实际上求的是面对面情况，就是面对面过的这个 pair 的数量。当然，这 Pair 是一个无序对。

image

  1. A 对 D（记录组合 {A, D}）。A 击球后去右边队尾。局面变更为：左 [B]，右 [D, E, A]。

  2. B 对 D（记录组合 {B, D}）。D 击球后去左边队尾。局面变更为：左 [B, D]，右 [E, A]。

  3. B 对 E（记录组合 {B, E}）。B 击球后去右边队尾。局面变更为：左 [D]，右 [E, A, B]。

  4. D 对 E（记录组合 {D, E}）。E 击球后去左边队尾。局面变更为：左 [D, E]，右 [A, B]。

  5. D 对 A（组合 {A, D} 已存在）。D 击球后去右边队尾。局面变更为：左 [E]，右 [A, B, D]。

  6. E 对 A（记录组合 {E, A}）。A 击球后去左边队尾。局面变更为：左 [E, A]，右 [B, D]。

  7. E 对 B（组合 {B, E} 已存在）。E 击球后去右边队尾。局面变更为：左 [A]，右 [B, D, E]。

  8. A 对 B（记录组合 {A, B}）。B 击球后去左边队尾。局面变更为：左 [A, B]，右 [D, E]。
    此时回到初始局面（A 对 D），循环结束。
    总共出现的不重复组合为：{A, D}, {B, D}, {B, E}, {D, E}, {E, A}, {A, B}，共 6 种。

思路讲解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
_______________[ Sample Testcase #1 INPUT ]_______________
2 2

_______________[ Sample Testcase #1 OUTPUT]_______________
6


[-] FAILURE: RUNTIME ERROR
2 3
1 3
1 4
3 4
3 2
4 2
4 1
2 1
2 3
1 3
1 4

我们还是把第一个数字给反转一下吧，把第一个数字反转一下更加符更加符合我们人类的这个直觉。

你会发现一二三四五，这样子是轮流出现的，是轮流出现的，就像模运算一样。

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
_______________[ Sample Testcase #1 INPUT ]_______________
2 2

_______________[ Sample Testcase #1 OUTPUT]_______________
6


[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 1
4 1
4 2
1 2
1 3
2 3
2 4

_______________[ Sample Testcase #2 INPUT ]_______________
2 3

_______________[ Sample Testcase #2 OUTPUT]_______________
10


[-] FAILURE: RUNTIME ERROR
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3
2 3
2 4
3 4
3 5
4 5
4 1
5 1
5 2
1 2
1 3

image

规律大概是这样的，不过还是不是特别清楚呢。我们使用零 base 的下标再注释一下。

image

这下子这个规律就非常清楚了。不过注意啊，其实就是第奇数个加 gap ，第偶数个加 gap-1，它不会加 gap 加二什么之类的。

image

那么奇数位，(i,(i+gap)mod  n)(i,(i+gap)\mod n)，这个东西内部，有没有可能重复呢？不难写出：

i≡i′+gapi+gap≡i′i\equiv i'+gap \\ i+gap\equiv i' \\

art
1
2
3
4
5
i      ≡ i' + gap  (mod n)    ①
i + gap ≡ i'        (mod n)    ②

① - ②:  -gap ≡ gap  (mod n)
即:      2 * gap ≡ 0  (mod n)

注意啊，处理这种同余式子可以加减乘，但是不能除。如果除的话，必须确保逆元存在。逆元存在条件就是你要除的数字和和这个 mod n 的这个 n 是互质的。

注意啊，处理各种各样的式子，这个都是先要把这个变量给消掉，对吧？这个 i 和 i’ 都是变量，它们这个式子非常优美，可以直接消掉。

我们接下来看，就是说i 加 gap 和 i 加 gap 减一这两个环是否会有相同的情况。

image

如上图所示，无非其实就是两种相同的情况嘛。

image

那么另外一种情况就是有可能成立的了。也就是二 gap 减一，和百分之 n，mod n 是零。

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Solve() {
    ll L,R;
    cin >> L >> R;
    ll N=L+R;
    // 就是 L
    ll gap1=(L+1)-1;
    ll ans1=N;
    // 如果是这个重复了，由于与这个 i 无关，因此所有 i 都有相同，总个数就是 N/2
    if (2*gap1%N==0) {
        ans1=N/2;
    }
    ll gap2=gap1-1;
    ll ans2=N;
    if (2*gap2%N==0) {
        ans2=N/2;
    }
    // 相同情况处理
    if ((gap1+gap2)%N==0) {
        ans2=0;
    }
    cout<<ans1+ans2<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2027025

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述
你需要构造一个包含整数 11 到 nn 的排列（即长度为 nn 的序列，其中 1∼n1 \sim n 每个数字出现且仅出现一次）。
在这个序列中，我们将数字视为楼房的高度。定义“可见性”规则如下：

  • 从某一侧观察，如果一个数字严格大于它和观察点之间的所有数字，则该数字是可见的（即较高的楼会挡住后面较矮的楼）。

请构造一个排列，同时满足以下两个条件：

  1. 从左向右看，恰好有 aa 个数字是可见的。

  2. 从右向左看，恰好有 bb 个数字是可见的。

输入格式
输入包含一行三个整数 n,a,bn, a, b。
数据范围：2≤n≤10002 \le n \le 1000，1≤a,b≤n1 \le a, b \le n。

输出格式

  • 如果存在满足条件的排列，首先输出一行 yes，随后输出 nn 个整数，表示构造出的排列。如果有多个解，输出任意一个即可。

  • 如果不存在满足条件的排列，输出 no。

样例解释

样例 1
输入：5 2 2
输出：yes 1 5 2 3 4
解释：

  • 左侧视角：看到 1，接着看到 5（5 > 1）。后面的 2, 3, 4 都比 5 小，被 5 挡住。共看见 2 个，满足 a=2a=2。

  • 右侧视角：看到 4，3 和 2 被 4 挡住。接着看到 5（5 > 4）。1 被 5 挡住。共看见 2 个（4 和 5），满足 b=2b=2。

image

样例 2
输入：5 3 4
输出：no
解释：在 n=5n=5 的情况下，无法构造出左看 3 个、右看 4 个的排列。

样例 4
输入：4 1 4
输出：yes 4 3 2 1
解释：

  • 左侧视角：第一个是 4（最大值），挡住了后面所有的数。共看见 1 个，满足 a=1a=1。

  • 右侧视角：从右往左依次是 1, 2, 3, 4，每一个都比右边的前序数字大。共看见 4 个，满足 b=4b=4。

思路讲解

这个这道题目还是很简单的。这个无解的情况已经高亮出来了。A 等于等于一，B 等于等于一，肯定是不可能的。因为你一定能够看到一个次高的和一个最高的。所以说你你是不可能你是不可能就是只看到一个建筑的。那么 A 加 B 大于 N 加一的话也是不可能的。因为两边看，从一边看过去，再从另外一边看过去的总和加在一起，不可能超过 N 加一。因为一定有一个最高的建筑会把你给挡住的。所以两边的总和其实就是两边，这边就是，两边它加起来最大就是 N 加一。

后面构造也是比较简单，反正就是要注意这个顺序的，就是要注意一下顺序，就是要注意一下顺序。然后还有最高的建筑一定能被看到这个限制。就是记住这个，然后你用一个 DQ 去构造会简单一点。

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
void Solve() {
    ll N,a,b;
    cin >> N >> a >> b;
    //  无解的情况
    if (a==1 && b==1) {
        cout<<"no\n";
        return;
    }
    if (a+b>N+1) {
        cout<<"no\n";
        return;
    }
    vector<ll> ans_ls(N+2);
    deque<ll> q;
    for (int i=1;i<=N-2;++i) {
        q.push_back(i);
    }
    if (a==1) {
        ans_ls[1]=N;
        for (ll i=N;i>=2;--i) {
            if (i==N-b+2) {
                ans_ls[i]=N-1;
            }else {
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else if (b==1){
        // ll cnt=0;
        ans_ls[N]=N;
        for (int i=1;i<=N-1;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else {
                // ++cnt;
                ans_ls[i]=q.front();
                q.pop_front();
            }
        }
    }else {
        ll cnt=0;
        for (int i=1;i<=N;++i) {
            if (i==a-1) {
                ans_ls[i]=N-1;
            }else if (i==N-b+1) {
                ans_ls[i]=N;
            }else if (i<a-1){
                ans_ls[i]=q.front();
                q.pop_front();
            }else {
                ans_ls[i]=q.back();
                q.pop_back();
            }
        }
    }
    cout<<"yes\n";
    for (int i=1;i<=N;++i) {
        cout<<ans_ls[i]<<" ";
    }
    cout<<"\n";
}

AC代码

AC
https://qoj.ac/submission/2026555

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目描述

根据德国《工作时间法》（ArbZG），员工的工作与休息时间需遵守以下规定：

  1. 如果单日实际工作时间超过 6 小时，必须至少休息 30 分钟。

  2. 如果单日实际工作时间超过 9 小时，必须至少休息 45 分钟。

  3. 单日工作时间严禁超过 10 小时。

定义“在岗总时间”为：

在岗总时间=实际工作时间+休息时间在岗总时间 = 实际工作时间 + 休息时间

给定一名员工当天的在岗总时间 tt（分钟），因为忘记了具体的打卡记录，为了确保不违反法律，请计算该员工为了使工作时间合法，其中最少必须包含多少分钟的休息时间。

输入格式

包含一行一个整数 tt (0≤t≤14400 \le t \le 1440)，表示当天的在岗总时间（分钟）。

输出格式

输出一个非负整数，表示使该工作时长合法的最小休息时间（分钟）。

样例解释

  • 样例 1
    输入：495
    输出：30
    解释：总时间 495 分钟。如果休息 30 分钟，实际工作时间为 495−30=465495 - 30 = 465 分钟（7 小时 45 分）。因为 465>360465 > 360（6 小时），法律要求至少休息 30 分钟。当前休息时间 30 分钟满足要求。

  • 样例 2
    输入：360
    输出：0
    解释：总时间 360 分钟。如果休息 0 分钟，实际工作时间为 360 分钟（6 小时）。未超过 6 小时，法律不强制要求休息。

  • 样例 3
    输入：540
    输出：30
    解释：总时间 540 分钟。如果休息 0 分钟，实际工作 540>360540 > 360，违规。如果休息 30 分钟，实际工作 510510 分钟（8.5 小时），超过 6 小时但不超过 9 小时，需休息 30 分钟，满足要求。

  • 样例 4
    输入：0
    输出：0
    解释：没上班，不需要休息。

思路讲解

之所以这道题目它有点阴啊，就是因为它计算的是这个实际工作时间，然后它会有一些空隙。

我们这个 min max 指的是什么呢？就是要么把工作时间降到360分钟以下，接受0小时休息，要么把工作时间降到540分钟以下接受30分钟休息，要么把工作时间降到600分钟以下，结束45分钟休息。

1
2
3
4
5
void Solve() {
    ll N;
    cin >> N;
    cout << min({max(0ll, N - 360), max(30ll, N - 540), max(45ll, N - 600)}) << "\n";
}

AC代码

AC
https://qoj.ac/submission/2026351

心路历程（WA，TLE，MLE……）