The Hand

— 摘自 Frank R Wilson 《The Hand》, 来自 Dynamicland 的推荐书单 “没有人在开始时知道他们参与的是什么；不知道需要多长时间，不知道会引向何方。&r

via 夜行人

The Educated Mind

— 摘自 Kieran Egan 《The Educated Mind》, 来自 Dynamicland 的推荐书单 在⼗六世纪，普通市民发现所有商品的价格开始迅速上涨。最明显的是他们不得不为⾐物等必需品⽀付更

via 夜行人

Simulation and Its Discontents

— 摘自 Sherry Turkle 《Simulation and Its Discontents》, 来自 Dynamicland 的推荐书单 没有什么⽐⼀个新鲜、未开发的机会更能吸引好奇者。 对于希望了解围

via 夜行人

【2019牛客暑期多校第一场】E题ABBA

题目链接

大致题意

有$(n + m)$个字母A和$(n + m)$个字母B，组成一个长度为 $2*(n + m)$的字符串，并且使得字符串中有$n$个“AB”和$m$个“BA”，求出可能的组合数（mod 1e9+7）
例如，n = 1 m = 2时，可以有这样的字符串（并不是全部的字符串）：
ABBABA
ABBBAA
BBABAA
上面三个字符串均满足条件

解题思路

考虑递推，假设已经有一个字符串满足一定的“先决条件”（此处应当理解为数学归纳法，及假设n - 1时满足）
下面考虑==在字符串最后加入一个字符==的情况。仅有两种可能：加A或者加B(这不是白说吗)
但是考虑一下极端情况，我们可以得到一些简单的且明显的条件（N~A~表示已经在字符串中的A个数，N~B~同理）
假如字符串的组成类似这样：

AAAAABBBBBBBB

则此字符串中，只能组合出 AB 而不可能组合出 BA
此时，我们假设 $n$ 为 5
而这个字符只能且必定要组合成 5 个AB，也就是说，我们接下来加入字符，只能加入 A 而不能加入 B
此时我们往前推，如果出现了这样一个字符串，则在之前，必定出现如下状态：

AAAAA

也即是 5 个A的情况，此时我们可以得到一个确定的关系式：

N~B~ = 0 and N~A~ <= n

推广到有B的情况，最优的情况就是所有的B都是用来组成BA，那么可以得到我们真正需要的关系式：

N~A~ - N~B~ <= n

同理，相对于 B 而言，我们可以得到

N~B~ - N~A~ <= m

合并上述两式

-n < N~A~ - N~B~ <= m

所以根据下标为 N~A~ - N~B~ 建立DP数组，下标范围为 -n 到 m （均包含）DP的内容为方案数量（mod 1e9 + 7），递推公式为
$dp[i] = dp[i - 1] + dp [i + 1]$
其中，dp[i - 1]指的是加入一个B（增加一个B使得N~A~ - N~B~变小）。而dp[i + 1]指的是加入一个A
当考虑到无论是正向dp还是逆向dp，均有值优先于dp[i]先更新（dp[i - 1]和dp[i + 1]会比dp[i]先更新），所以采用两个dp数组的方式，初始值dp[0]=1。每两次dp完后，dp[0]的值及为答案。

AC代码

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

#include &LTbits/stdc++.h>

using namespace std;

#define MAXN 2100
#define MOD (int)(1e9 + 7)
typedef long long ll;

ll dp[MAXN][2];

int trans(int x) {
return x + 1000;
}

int main() {
#ifdef ACM_LOCAL
freopen("debug.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
memset(dp, 0, sizeof(dp));
dp[n][1] = 1;
int cur = 0;
int last = 1;
for (int i = 0; i < 2 * (n + m); i++) {
for (int j = -n; j <= m; j++) {
if (j != -n) {
dp[j + n][cur] += dp[j - 1 + n][last];
dp[j + n][cur] %= MOD;
}
if (j != m) {
dp[j + n][cur] += dp[j + 1 + n][last];
dp[j + n][cur] %= MOD;
}
}
for (int j = -n; j <= m; j++) {
dp[j + n][last] = 0;
}
swap(cur, last);
}
cout << dp[n][last] << endl;
}
return 0;
}

via Shiroha白羽的博客

Educational Codeforces Round 80 D. Minimax Problem——二分+二进制处理

题目链接

题目大意

有n个维度为m的向量，取其中两个进行合并，合并时每个维度取两者之间的较大者，得到的新的向量中，维度值最小者最大为多少

分析

首先最需要注意的是m的取值，m最大只有8，那么我们可以二分答案，对于每一个二分值，进行下面的操作，将整个矩阵的每一个元素，如果这个元素大于二分值，则变成1，反正则变成0，把每一个向量压缩为单个二进制数，这样我们最多只会得到$2^8 = 256$种不同的二进制数，然后暴力的遍历所有可能的二进制数的组合，得到是否满足当前二分值

AC code

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

#include &LTbits/stdc++.h>

using namespace std;

const int NUM = 3e5 + 100;

int data[NUM][10];

bool check(int value, int n, int m, pair<int, int> &ans) {
map<unsigned, int> s;
for (int i = 0; i < n; ++i) {
unsigned temp = 0;
for (int j = 0; j < m; ++j) {
temp <<= 1u;
temp |= data[i][j] > value;
}
s.insert({temp, i});
}
unsigned tar = -1u >> (sizeof(int) * 8 - m);
for (auto iter1 = s.begin(); iter1 != s.end(); ++iter1) {
for (auto iter2 = iter1; iter2 != s.end(); ++iter2) {
if ((iter1->first | iter2->first) == tar) {
ans.first = iter1->second;
ans.second = iter2->second;
return true;
}
}
}
return false;
}

void solve() {
int n, m;
cin >> n >> m;
int l = INT_MAX, r = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> data[i][j];
l = min(l, data[i][j]);
r = max(r, data[i][j]);
}
}
int mid, cnt = r - l;
pair<int, int> ans;
while (cnt > 0) {
int step = cnt / 2;
mid = l + step;
if (check(mid, n, m, ans)) {
l = mid + 1;
cnt -= step + 1;
} else
cnt /= 2;
}
cout << ans.first + 1 << " " << ans.second + 1 << endl;
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
long long test_index_for_debug = 1;
char acm_local_for_debug;
while (cin >> acm_local_for_debug) {
cin.putback(acm_local_for_debug);
if (test_index_for_debug > 20) {
throw runtime_error("Check the stdin!!!");
}
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
}
#else
solve();
#endif
return 0;
}

via Shiroha白羽的博客

我的ACM脚印

via Shiroha白羽的博客

记一次 Navicat 连接 MySQL 一直报认证错误(Access denied)

今天一时兴起，想在 WSL2 里下个 MySQL。方法也很简单，直接 sudo apt install mysql-server
本来以为顺风顺水，结果却在 Navicat 连接 MySQL 的操作上出事了

问题

Navicat 无法连接上 MySQL

配置情况

Navicat Premium 15.0.19
MySQL 8.0.22
WSL2(Ubuntu 20)

现状

终端可以通过sudo mysql连上 MySQL
终端不可以通过mysql -u root -p的方式连接，显示密码错误(Access denied for user 'root'@'localhost')
终端可以通过默认用户连接(默认用户为 /etc/mysql/debian.cnf 文件中的 debian-sys-maint，密码为安装MySQL时随机生成得到的)
Navicat不可以通过直接连接或者通过 ssh 的方式连接，显示密码错误(Access denied for user 'root'@'localhost')
Navicat可以通过默认用户连接

经过

尝试1

首先是尝试了百度的结果，重置 MySQL 的 root 账户的密码
因为可以通过sudo mysql直接进入数据库，也就不需要那么多百度出来的奇奇怪怪的操作了
直接进入数据库，然后尝试了下面几行代码

1
2
3

use mysql;
alter user 'root'@'localhost' identified by 'newPassword';
exit

然后，测试mysql -u root -p连接——失败

尝试2

后来在MySQL官网找到了重置root密码的方法，然后赶紧拿来测试
官网链接
其中的一点提到

B.3.3.2.2 Resetting the Root Password: Unix and Unix-Like Systems

大致操作就是先终止 MySQL，然后使用 MySQL 的附加参数来设置一个初始化文件，然后使得 MySQL 去运行此文件。

然后，测试mysql -u root -p连接——失败

其实觉得挺奇怪的，既然都能重启 MySQL 了，说明你已经拿到这个设备的 root 权限了，为什么不直接用 sudo mysql 进入直接run这条命令呢？

尝试3

最终我在一份不起眼的博客上找到了解决方案
博客连接
其中提到了一个很重要的命令

1

ALTER USER 'root'@'localhost' IDENTIFIED WITH mysql_native_password BY 'insert_password';

This command changes the password for the user root and sets the authentication method to mysql_native_password. This is a traditional method for authentication, and it is not as secure as auth_plugin.

其中的mysql_native_password是所谓的传统验证方案，也就是 Navicat 连接 MySQL 的解决方案

然后将方案1的命令稍作改正得到

1
2
3

use mysql;
alter user 'root'@'localhost' identified with mysql_native_password by 'newPassword';
exit

然后，测试mysql -u root -p连接——成功！

后续

mysql5.8开始将caching_sha2_password作为默认的身份验证插件，该caching_sha2_password和 sha256_password认证插件提供比mysql_native_password插件更安全的密码加密 ，并 caching_sha2_password提供了比更好的性能sha256_password。由于这些优越的安全性和性能特性 caching_sha2_password它是MySQL 8.0首选的身份验证插件，而且也是默认的身份验证插件而不是 mysql_native_password。此更改会影响服务器和libmysqlclient 客户端库；目前来说和经常使用的客户端软件兼容性不好。

这也是导致目前 Navicat 无法连接到 MySQL 5.8及以后版本的原因。当然如此操作后的影响便是无法直接使用sudo mysql的方式连接到数据库，只能通过 mysql -u root -p的传统密码验证的方式来登陆

via Shiroha白羽的博客

Codeforces Round#697 (Div. 3)

via Shiroha白羽的博客

面试复习（操作系统）

用户态和内核态

● 什么时候从用户态转为内核态 ● 程序在用户态执行时，当需要进行系统调用的时候，或者遇到异常，或者外围设备引发的中断，如文件读取与写入，程序报错，键盘输入，网络操作等行为时，程序会从用户态转为内核态，直到执行此行为结束时，再返回用户态
● 为什么要转至内核态 ● 通过限制用户态的权利，使得有限的系统资源能够受到系统的控制与管理，由系统进行资源的分配
● 用户态和内核态的切换原理 ● 实质上就是中断，保存当前用户态的所有寄存器信息等，然后将代码指针指向中断处理程序

进程和线程

● 区别 ● 进程是相对于操作系统的最小单位，每个进程都有唯一一个 PID 与之对应，每个进程都有独立的内存空间，代码段，数据段。进程之间相互独立且不会相互影响，一个进程可以包含多个线程。CPU在多个进程之间切换时会带来较大的开销。进程可以由CPU单独启动 ● 线程是相对于处理器的最小单位，单个CPU只能同时处理一个线程，相同进程的线程之间共用内存空间，共用代码段和数据段，线程不可以单独执行，线程没有 PID 用于区别，线程出现错误或者异常时会影响此进程内的所有线程，CPU在同一个进程的线程内切换所带来的开销相对较小
● 进程之间的通信 ● 管道（无名和有名管道） ● 消息队列 ● 共享内存 ● 不同的进程可以同时将同一个内存页面映射到自己的地址空间中 ● 信号 ● 套接口（网络）
● 线程之间的通信 ● 锁机制（互斥锁、读写锁） ● wait 和 notify ● violate
● 进程切换代价 ● 切换页目录 ● 切换内核栈 ● 切换上下文
● 线程切换代价 ● 切换内核栈 ● 切换上下文

内存

● 内存寻址是如何实现的 ● 段页式，程序进行分段，包括代码段，数据段等等，每一段再分页，并由 MMU 保存页表 ● MMU 通过页表将逻辑地址转为物理地址

缓存

● 缓存列 ● 每次计算机读取数据放入缓存的单位长度

文件系统

● iNode 结构 ● 文件树结构保存了一个目录的子文件/目录的名称以及对应的 iNode 号码 ● 需要访问文件内容时，需要通过 iNode 号码来获取文件的详细信息 ● iNode 不包含文件名信息，指包含文件的 “元信息”

中断

via Shiroha白羽的博客

Codeforces Round#789(Div. 2)

B2. Tokitsukaze and Good 01-String (hard version)

大致题意

有一段 01 组成的字符串，保证长度为偶数

你可以选择一个 0 或者 1，将其变为 1 或者 0

问至少需要操作几次，可以使得所有的 0 或者 1 段都为偶数长度。同时，此时，最少有多少段单独段 0 或 1 段

分析

首先，因为总长度为偶数，所以奇数段一定是成对出现的，可以简单讨论五种情况

● 改变一个奇数段内部，可以生成两个偶数段一个奇数段
● 改变一个偶数段内部，可以生成两个奇数段和一个偶数段
● 改变两个偶数段边缘，可以生成两个奇数段
● 改变两个奇数段边缘，可以生成两个偶数段
● 改变奇偶段边缘，可以交换奇偶关系

这几种方法中，只有改变两个奇数段边缘是有意义的，但是并不一定每次都那么好运。所以必须选择一种方法去将两个离得很远的奇数段靠近

明显只有第一个和最后一个可选，在不产生新的奇数段的前提下改变位置。但是第一个明显有点蠢……因为生成的奇数段在原奇数段内部（仅一个 0 或者 1），所以只能选最后一种方案

所以我们需要选择两个奇数段，然后通过方法五将它们贴近到相邻，然后再用方法四消灭它们，所需要的数量也就是奇数段之间的偶数段个数 + 1

数量解决了，接下来就是分配如何变化使得数量最少了。因为对于每一个奇数段而言，只会改变一个，而对于偶数段而言，两侧边缘都需要发生变化，所以

当奇数段的长度为 1 的时候，变化此奇数段，当偶数段长度为 2 的时候，左右两侧都变化此偶数段。然后再统计不同的奇偶段数量即可

AC Code

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

#include "bits/stdc++.h"

using namespace std;

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n;
cin >> n;
string str;
str.resize(n);
cin >> str;
vector<int> st;
char last = -1;
for (int i = 0; i < n; ++i) {
if (str[i] == last) {
st.back()++;
} else {
st.push_back(1);
last = str[i];
}
}
int isOdd = 0, ans = 0;
for (int i = 0; i < st.size(); ++i) {
if (st[i] % 2) {
isOdd = !isOdd;
if (st[i] == 1) st[i] = 0;
} else if (isOdd) {
if (st[i] == 2) st[i] = 0;
}
ans += isOdd;
}
int ls = -1, cnt = 0;
for (int i = 0; i < st.size(); ++i) {
if (st[i] == 0) continue;
if (ls != (i % 2)) {
ls = i % 2;
cnt++;
}
}
cout << ans << ' ' << max(1LL, cnt) << endl;
}
}

signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed localTestCount = 1, localReadPos = (signed) cin.tellg();
char localTryReadChar;
do {
if (localTestCount > 20)
throw runtime_error("Check the std input!!!");
auto startClockForDebug = clock();
solve();
auto endClockForDebug = clock();
cerr << "Test " << localTestCount++ << " Run Time: "
<< double(endClockForDebug - startClockForDebug) / CLOCKS_PER_SEC << "s" << endl;
//        cout << "Test " << localTestCount << " successful" << endl;
//        cout << "--------------------------------------------------" << endl;
} while (localReadPos != cin.tellg() && cin >> localTryReadChar && localTryReadChar != '$' &&
cin.putback(localTryReadChar));
#else
solve();
#endif
return 0;
}

via Shiroha白羽的博客

Java Script 的 null 和 undefined 随想

有些时候感觉一些语言里看起来很蠢的设计，实际上却能解决一些很有意思的场景。比如 JavaScript 的 null 和 undefined，虽然看起来都是表示空的意思，但是实际上却解决了“没有这个值”，“这个值为空”这样两种语义。在缓存穿透的问题上，如果 redis、memcached 等数据库也有这样一层设计等话，是不是就能解决 null 穿透问题了呢

via Shiroha白羽的博客

Codeforces Round 890 (Div. 2)

via Shiroha白羽的博客

Educational Codeforces Round#153 (Div. 2)

A. Not a Substring

大致题意

需要构建一个只有小括号构成的字符串，既满足括号匹配，同时不存在一个子串等同于给出的一个字符串

思路

实际上很简单，只需要取 ()()()() 模式 和 (((()))) 这两种即可，因为这两种模式的唯一相同的子串就只有一对 ()，而若需要一个满足括号匹配的字符串，那么必然存在 ()，故这两种模式就可以应对所有情况

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
string str, ans;
cin >> str;
ans.resize(str.size() << 1);
for (int i = 0; i < str.size(); ++i) ans[i] = '(';
for (int i = 0; i < str.size(); ++i) ans[i + str.size()] = ')';
if (strstr(ans.c_str(), str.c_str()) == nullptr) {
cout << "YES" << endl;
cout << ans << endl;
continue;
}
for (int i = 0; i < str.size(); ++i) ans[i * 2] = '(';
for (int i = 0; i < str.size(); ++i) ans[i * 2 + 1] = ')';
if (strstr(ans.c_str(), str.c_str()) == nullptr) {
cout << "YES" << endl;
cout << ans << endl;
continue;
}
cout << "NO" << endl;
}
}

B. Fancy Coins

大致题意

有 $a1$ 个 $1$ 元，$a2$ 个 $k$ 元，同时你可以“借来”无限量的 $1$ 元和 $k$ 元，问组成 $m$ 元最多需要借多少硬币

思路

简单卡一下边界，多一个 $k$ 元和少一个 $k$ 元的两种情况考虑一下即可，比较简单

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int m, k, a1, a2;
cin >> m >> k >> a2 >> a1;
m -= min(m / k, a1) * k;
if (m <= a2) {
cout << 0 << endl;
continue;
}

int ls = (m - a2) / k;
int ans = ls + (m - a2 - ls * k);
if (m - (ls + 1) * k >= 0) ans = min(ans, ls + 1);
cout << ans << endl;
}
}

C. Game on Permutation

大致题意

有一个数组，开始位置可以是任意的一个下标，每次可以移动到当前位置左边的任意一个值小于当前的位置。

两个人依次操作，谁最后无法进行操作了，谁胜利，问放在哪些位置，可以保证第二个开始操作的胜利

思路

假如说我摆放在一个位置，然后可以通过 $3$ 个依次操作达到最终无法移动（例如 $a \rightarrow b \rightarrow c \rightarrow d$），那么此时应该说第二个移动的人胜利

但是这个操作是可跳过的，因为你可以移动 $3$ 次，那么就必然可以一次移动到底，因为一定也符合题意，那么第一个移动的人为什么要遵循一个个移动呢，他完全可以直接 $a \rightarrow c$，然后第二个操作的人只能移动到 $d$，然后输了游戏

所以必须卡在一些只能移动一次的地方，否则就有可乘之机。

那么就必须保证选择的点满足

● 大于左边最小的值
● 小于左边之前确认的满足条件的点

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, ans = 0, curMin = INT_MAX, curMax = INT_MAX;
cin >> n;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
if (tmp < curMin) curMin = tmp;
else if (tmp > curMin && tmp < curMax) {
ans++;
curMax = tmp;
}
}
cout << ans << endl;
}
}

via Shiroha白羽的博客

Codeforces Round 894 (Div. 3)

via Shiroha白羽的博客

Codeforces Round 895 (Div. 3)

via Shiroha白羽的博客

CodeTON Round 6 (Div. 2)

A. MEXanized Array

大致题意

构造一个数组，其长度为 $n$，最大值为 $x$，$MEX$ 为 $k$，问这个数组的所有值的和最大是多少

思路

简单题，在 $k > x + 1$ 或 $n < k$ 的场景下无解（不可能构造一个 $MEX$ 不可达的数组），然后就随便构造就行了，保证 $MEX$ 之后，剩下所有值取最大就行

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, k, x;
cin >> n >> k >> x;
if (k > x + 1 || n < k) {
cout << -1 << endl;
continue;
}
int sum = 0;
for (int i = 0; i < k; ++i) sum += i;
for (int i = k; i < n; ++i) sum += (x == k ? x - 1 : x);
cout << sum << endl;
}
}

B. Friendly Arrays

大致题意

给出两个数组 $a, b$，允许选择任意次的 $b$ 数组中的任意一个 $b_j$，然后让 $\forall i \in [1, len(a)], a_i = a_i | b_j$，问最终得到的数组 $a$ 中所有的异或和最大和最小的可能

思路

某个比特为是 $1$ 的情况下，在奇数个值异或和的结果则也是 $1$，而偶数个则为 $0$。而或运算可以让 $a$ 数组的每一个值的某些个位都变成 $1$。基于此，只需要关心 $a$ 的长度即可，若 $a$ 为奇数，那么选尽可能多的 $b$ 使得每个位都尽可能是 $1$，反之则尽可能不选，这样才能达到最大，同理可以得到最小的方案

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, m;
cin >> n >> m;
int sa = 0, sb = 0, tmp;
for (int i = 0; i < n; ++i) {
cin >> tmp;
sa ^= tmp;
}
for (int i = 0; i < m; ++i) {
cin >> tmp;
sb |= tmp;
}
cout << (n % 2 ? sa : sa & ~sb) << ' ' << (n % 2 ? sa | sb : sa) << endl;
}
}

C. Colorful Table

大致题意

有一个数组 $a$，长度为 $n$，然后有一个对应的矩阵 $b$，为 $n \times n$，其每一个位置的值 $b_{i,j}=min(a_i, a_j)$

问对于每个数字 $x$，在矩阵 $b$，中能够找到对应一个最小的矩形，此矩形包含了所有出现 $x$ 的位置，求出这个矩形的大小

思路

对于任意一个值，假定其第一次在 $a$ 中出现的位置为 $i$，它第一次出现在 $b$ 地点一定是 $b_{i,i}$，同时其最后一次在矩阵中的位置一定是 $b_{j,j}$，其中 $j$ 是在数组 $a$，中出现的，最后一个比当前值更大的下标

根据上面的规律，可以求出实际上每个值的位置，一定可以包裹比他大的那个值对应的矩阵，所以只需要根据值的大小排序一下他们在数组中第一次出现的位置，和最后一次出现的位置，然后从大到小遍历，保证小的值的区间能够覆盖到大的值的区间即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, k;
cin >> n >> k;
vector<bool> flag(k, false);
vector&LTpair<int, int>> data(k, {-1, -1});
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
data[tmp - 1].first == -1 ? data[tmp - 1].first = data[tmp - 1].second = i : data[tmp - 1].second = i;
flag[tmp - 1] = true;
}
for (int i = k - 2; i >= 0; --i) {
data[i].first = !flag[i] ? data[i + 1].first : (data[i + 1].first != -1 ? min(data[i].first, data[i + 1].first) : data[i].first);
data[i].second = !flag[i] ? data[i + 1].second : (data[i + 1].first != -1 ? max(data[i].second, data[i + 1].second) : data[i].second);
}
for (int i = 0; i < k; ++i)
cout << (!flag[i] ? 0 : (data[i].second - data[i].first + 1) + (data[i].second - data[i].first + 1)) << ' ';

cout << endl;
}
}

D. Prefix Purchase

大致题意

有一个初始数组，每一个值都是 $0$，每次你可以选择花费 $c_i$ 元，使得这个数组前 $i$ 个元素加一，最多只能花费 $k$ 元，问能够得到最大字典序的数组是什么

思路

首先需把 $c$ 的值进行单调递增栈处理一下，毕竟价格相同或更低的同时 $i$ 更大肯定有优势

回到题目中的字典序，意味着只有越前面的值越大即可，所以要尽可能满足最前面的值最大，所以直接把 $k$ 丢给处理后的第一个值，看看最多第一个值可以到多少

处理完成第一个值后，那就意味着后面无论怎么贪心，第一个值一定要达到这个，否则肯定不如现在更好。另外，对于字典序而言，约前面的值价值越高，所以要尽可能让前面的值大，贪心一下即可

AC code

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

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, k;
cin >> n;
vector&LTpair<int, int>> data;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
while (!data.empty() && data.back().first >= tmp) data.pop_back();
data.emplace_back(tmp, i);
}
data.emplace_back(INT_MAX, n - 1);
cin >> k;
vector<int> ans(data.size());
ans[0] = k / data.front().first;
k %= data.front().first;
for (int i = 1; i < data.size(); ++i) {
int diff = data[i].first - data[i - 1].first;
if (k < diff) {
break;
}
ans[i] = min(ans[i - 1], k / diff);
k -= diff * ans[i];
}
int cur = 0;
for (int i = 0; i < n; ++i) {
while (data[cur].second < i) cur++;
cout << ans[cur] << " \n"[i == n - 1];
}
}
}

via Shiroha白羽的博客

Codeforces Round 898 (Div. 4)

via Shiroha白羽的博客

Codeforces Round 901 (Div. 2)

最近双十一加班严重，难得有一个完整的周末假期，来写点题稍微恢复一下脑子吧

A. Jellyfish and Undertale

大致题意

有一个炸弹，有倒计时在缓慢减少，你有 $n$ 个道具，每次你可以花费 1s 的时间来使用，使得倒计时增加 $v_i$
秒，但是由于一些故障，每次加完后，不能超过上限 $a$，否则就会变成 $a$。问最多可以让炸弹坚持到几秒

思路

注意操作可以是任何时候进行的，所以当每次只剩下 1s 的时候操作就是最好的，不然就炸了，因为是先完成加时间，再扣除当前操作的
1s，故只需要考虑每个都在 1s 的时候操作即可，即对每个值取 $min(v_i, a - 1)$ 然后求和就行了

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int a, b, n;
cin >> a >> b >> n;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
b += min(tmp, a - 1);
}
cout << b << endl;
}
}

B. Jellyfish and Game

大致题意

A 有 $n$ 个苹果，每个都有重量，B 有 $m$ 个，每次交换，A 或者 B 可以选择自己的一个苹果给对方，同时从对方那边拿来一个苹果，两人都希望自己的苹果重量之和最大，问依次交换
$x$ 次后，$A$ 的苹果重量之和是多少

思路

模拟就行了，说白了交换了两次之后，就是纯粹的互换相同的那两个苹果，只需要考虑最开始的两次即可

AC code

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

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
for (auto &i: a) cin >> i;
for (auto &i: b) cin >> i;
auto sort_all = [&]() {
sort(a.begin(), a.end());
sort(b.begin(), b.end());
};
sort_all();
if (a.front() < b.back()) {
swap(a.front(), b.back());
}
if (k >= 2) {
sort_all();
if (b.front() < a.back()) {
swap(b.front(), a.back());
}
if (k % 2) {
sort_all();
if (a.front() < b.back()) {
swap(a.front(), b.back());
}
}
}
int tot = 0;
for (auto &i : a) tot += i;
cout << tot << endl;
}
}

C. Jellyfish and Green Apple

大致题意

有 $n$ 个苹果，要平均分给 $m$ 个人，每次可以把一片苹果平均切成两份，问至少要切几刀才能平分

思路

其实是一个小数二进制问题，根据小数二进制方式去解决，从高位开始，一步步减去需要的苹果块，每一步减完之后，就可以将剩下来的苹果块全部对切开，因为不会再用到更大的苹果块了

AC code

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

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, m;
cin >> n >> m;
n %= m;
if (n == 0) {
cout << 0 << endl;
continue;
}
// check m is or not the power of 2
int tmp = gcd(m, n);
tmp = m / tmp;
bool flag = true;
while (tmp != 1) {
if (tmp % 2 == 1) {
flag = false;
break;
}
tmp >>= 1;
}
if (!flag) {
cout << -1 << endl;
continue;
}

int ans = n;
n <<= 1;
while (n) {
n %= m;
ans += n;
n <<= 1;
}

cout << ans << endl;
}
}

D. Jellyfish and Mex

大致题意

有一个数组，每次可以从中删除一个值，然后得到对应的 $mex$，问直到整个数组被完整删除后，所有得到的 $mex$，相加最小可能是多少

思路

举个例子来看

0 0 0 1 1 2 3 3 3 4 4 4 5 5 5

首先要让 $mex$ 尽可能小，那么就应该尽量挑小的开始删除，显然，如果我把 $0$ 删除完那就会使得后面所有的操作都是无代价的，即随便删的
$mex$ 都是 $0$。但是直接删除 $0$ 的代价非常大，因为前两次删除都会导致代价为 $6$ 的 $mex$。这是因为 $0$ 出现了 $3$ 次。如果我们先删除
$2$，然后再删除 $0$ 那么就会发现，只需要额外增加 $2$ 的代价，就能让后面删除 $0$ 的两次操作的代价从 $6$ 减少到 $2$。

所以可以得到，我们尽量应该删除越少越小的值，即如果值增加的情况下，数量还不减少，那么肯定没有必要优先做删除了，可以等 $mex$ 变成
$0$ 之后再动手。而对于这些值，当然也应该从较大者开始删除，这样可以尽快减小 $mex$
的值（因为在上面的前提下，最大值的出现次数一定比较小值少）但是不能每个值都要操作，例如例子中的 $1$
就是不需要操作的，即使其恰好在这条单调栈上，即需要从一个序列中取出最优的子序列

我们考虑最多会出现多少个这样的需要考虑的数字，假设刚好递减的情况，且数量为 $n$，那么总占用的数字数量就是 $n * (n + 1) /
2$。故对于长度为 $5000$ 的数组，实际上 $n < 100$。即 $n^2$ 暴力去找子序列是可以的

AC code

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

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; ++i) {
int tmp;
cin >> tmp;
mp[tmp]++;
}

int mex = 0;
while (mp.count(mex)) mex++;

if (mex == 0) {
cout << 0 << endl;
continue;
}

vector&LTpair<int, int>> data;
for (auto &iter: mp) {
if (iter.first > mex) break;
if (data.empty() || data.back().second > iter.second)
data.emplace_back(iter);
}
reverse(data.begin(), data.end());
vector<int> dp(data.size());
for (int i = 0; i < data.size(); ++i) {
dp[i] = (data[i].second - 1) * mex + data[i].first;
for (int j = 0; j < i; ++j)
dp[i] = min(dp[i], (data[i].second - 1) * data[j].first + data[i].first + dp[j]);
}

cout << dp.back() << endl;
}
}

via Shiroha白羽的博客

Codeforces Round 916 (Div. 3)

via Shiroha白羽的博客

Codeforces Round 907 (Div. 2)

A. Sorting with Twos

大致题意

每次可以从前往后选择 $2^x$ 个值，每个值减少一，问进行无数次操作后，是否可能让整个数组变成无递减

思路

简单题，只要原数组中，那些盲区仍然保持非递减即可。例如 $[3, 4]$ 这种区间，要么一起减少要么一起不减少

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n;
cin >> n;
vector<int> data(n);
for (auto& i: data) cin >> i;
bool flag = true;
pair<int, int> arr[4] = {{2, 3}, {4, 7}, {8, 15}, {16, 31}};
for (auto [l, r]: arr) {
for (; l < min(r, n - 1); ++l) {
if (data[l] > data[l + 1]) {
flag = false;
break;
}
}
}

cout << (flag ? "YES" : "NO") << endl;
}
}

B. Deja Vu

大致题意

给出两个数组，对于第一个数组 $a$ 的每一个值，进行如下操作：

● 从前往后遍历数组 $b$
● 若 $a_i \space mod \space 2^{b_i} = 0$ 则 $a_i \leftarrow a_i + 2^{b_i - 1}$

求最终数组

思路

数据量很大，但是有技巧

因为一旦满足 $a_i \space mod \space 2^{b_i} = 0$ 之后，会加上的是 $2^{b_i - 1}$。
这也就意味着，如此操作之后，其必然可以被 $2^{b_i - 1}$ 整除，且最大只能被它整除了。
也就是说，每次能够加上的值一定是不断变小的

题目中给出的 $b_i \in [1, 30]$ 所以其实第二个数组最多只能有 30 个有效值。处理之后暴力即可

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n, q;
cin >> n >> q;
vector<int> data(n), query;
query.reserve(30);
for (auto& i: data) cin >> i;
for (int i = 0; i < q; ++i) {
int tmp;
cin >> tmp;
if (i == 0 || tmp < query.back()) query.push_back(tmp);
}

for (auto& i: data) for (long long j: query) if (i % (1 << j) == 0) i += 1 << j - 1;
for (int i = 0; i < n; ++i) cout << data[i] << " \n"[i == n - 1];
}
}

C. Smilo and Monsters

大致题意

有一堆怪物窝，每个怪物窝里有一定数量的怪物。你有一个累计的技能点数，初始值为 0，每次可以选择不同的技能

● 找一个怪物窝，打死里面的一只怪物，积累一点技能点数
● 找一个怪物窝，里面的怪物数量不大于你的技能点数，消耗全部的技能点数释放大招，消灭这个窝里的全部怪物

问最少需要几次操作

思路

对于一个窝而言，只需要打死里面的一半的怪物，再加上一次使用技能，就可以实现打败这个窝了，此时成本为 $\left \lceil \frac{x}{2} \right \rceil + 1$

如果有两个窝，假设都这样操作，那么代价就是 $\left \lceil \frac{x}{2} \right \rceil + \left \lceil \frac{y}{2} \right \rceil + 2$

假如我将小一点的那个窝全部一只只打死，然后打几只大窝里的怪，再对大一点对窝释放大招，也就是只使用一次技能，代价就是 $x + (\left \lceil \frac{y+x}{2} \right \rceil - x) + 1 = \left \lceil \frac{y+x}{2} \right \rceil + 1$

显然，后者价值更高，所以要考虑按照后者的操作进行，即多用小窝的怪刷技能点，然后对大窝放技能。用双指针做就行了

AC code

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

#define int long long

void solve() {
int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int n;
cin >> n;
vector<int> data(n);
for (auto& i: data) cin >> i;
sort(data.begin(), data.end());
int l = 0, r = n - 1, x = 0, ans = 0;
while (l <= r) {
if (x >= data[r]) {
data[r] = 0;
x = 0;
--r;
++ans;
} else {
const int tmp = l == r ? (x + data[l] + 1) / 2 - x : min(data[l], data[r] - x);
x += tmp;
ans += tmp;
data[l] -= tmp;
if (!data[l]) ++l;
}
}

cout << ans << endl;
}
}

D. Suspicious logarithms

大致题意

定义两个函数，$f(x) = y, g(x) = z$，满足 $2^y \leq x, y^z \leq z$，且 $y, z$ 都尽可能大

给出一个区间，求 $\sum_{i=l}^{r} g(i)$

思路

虽然看起来很难，但是观察可以发现，$y \in [1, 64]$，而 $z \in [0, 10]$，所以只需要枚举所有的 $y, z$ 即可

AC code

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

#define int long long

void solve() {
map&LTpair<int, int>, int> mp;
for (int i = 2; i < 60; ++i) {
const __int128 ml = 1ll << i, mr = 1ll << i + 1;
__int128 base = 1;
for (int j = 0; j <= 10; ++j) {
if (base >= mr) break;
if (base * i <= ml) {
base *= i;
continue;
}
mp.insert({{max(ml, base), min(mr, base * i) - 1}, j});
base *= i;
}
}

constexpr int mod = 1e9 + 7;

int _;
cin >> _;
for (int ts = 0; ts < _; ++ts) {
int l, r;
cin >> l >> r;
int ans = 0;
for (auto& [fst, snd]: mp) {
const int len = min(fst.second, r) - max(fst.first, l) + 1;
if (len <= 0) continue;
ans = (ans + len * snd % mod) % mod;
}
cout << ans << endl;
}
}

via Shiroha白羽的博客

Codeforces Round 912 (Div. 2)

via Shiroha白羽的博客