2022寒假每日一题笔记（三）

第三周

2022.1.16—1934. 贝茜放慢脚步

奶牛贝茜正在参加冬季哞林匹克运动会的越野滑雪比赛。
她以每秒 1 米的速度出发。
但是，随着时间的推移，她变得越来越疲倦，她开始放慢脚步。
每次放慢脚步，贝茜的速度都会降低：减速一次后，她以每秒 1/2 米的速度移动，减速两次后，则以每秒 1/3 米的速度移动，依此类推。
你将被告知何时何地贝茜会减速。
当减速信息格式为：
T 17
意味着，贝茜在某个时间点减速，本例表示比赛开始第 17 秒贝茜减速。
当减速信息格式为：
D 10
意味着，贝茜在某个地点减速，本例表示在行进 10 米处减速。
给定 N 个减速信息，请计算贝茜滑完一千米需要多少秒。
将你的答案四舍五入到最接近的整数（ 0.5 向上舍入为 1）。

输入格式
第一行包含整数 N。
接下来 N 行，每行描述一个减速信息，格式为 T x 或 D x。
无论哪种情况，x 都是一个整数，保证所有减速都在贝茜滑完一千米前发生。
可能同时发生多次减速，那么这会使得贝茜的速度一下子变慢很多。
所有减速信息不一定按顺序给出。

输出格式
输出贝茜滑完一千米所需的总时间。

数据范围
1≤N≤10000
输入样例：
2
T 30
D 10
输出样例：
2970
样例解释
贝茜以每秒 1 米的速度跑完前 10 米，耗时 10 秒。
然后她减速到每秒 1/2 米，接下来的 10 米要花 20 秒。
然后她在第 30 秒时，再次减速到每秒 1/3 米。
滑完剩下的 980 米需要 980×3=2940 秒。
因此，总时间是 10+20+2940=2970 秒。

本题麻烦的地方就在时间和距离信息都有，是乱序给出的。

所以需要将时间和距离信息统一起来。

核心思路是：二路归并。

从时间和距离两组事件中，找到最早发生的事件。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4+5;
int n;
int t[N],d[N];

int main(){
    cin >> n;
    
    char op;
    int a = 0,b = 0,x;
    while (n--){
        cin >> op >> x;
        if (op == 'T') t[a++] = x; // 开vector存方便一点
        else d[b++] = x;
    }
    d[b++] = 1000; // 保证走到1000米

    sort(t,t + a);
    sort(d,d + b);
    
    int i = 0,j = 0;
    double T = 0,D = 0,V = 1;
    while (i < a || j < b){ // 二路归并，y总写法，不用单独写两个循环
        double x = t[i] - T,y = V*(d[j] - D);
        if (j == b || i < a && x <= y){
            // 注意更新顺序
            D += x / V; // 时间事件更早发生，先更新距离，然后时间和速度更新
            T = t[i++];
            V ++;
        }
        else{
            T += y; // 距离事件更早发生，先更新时间，然后距离和速度更新
            D = d[j++];
            V ++;
        }
    }
    
    printf("%.0lf\n",T); // 保留整数
    return 0;
}

2022.1.17—1929. 镜子田地

农夫约翰在屋子外面放了一些旧镜子，他的奶牛们像往常一样调皮地偷走了它们！
奶牛们将镜子放置在了一个矩形田地中，该田地可被划分为 N×M 个方格区域。
在每个方格区域中，奶牛在其某对对角之间放置一个双面镜，因此，共有两种放法，一种为 / 放置（镜子连接方格左下角和右上角），另一种为 \ 放置（镜子连接方格左上角和右下角）。
一天晚上，奶牛贝茜将激光发射器带到了该田地中。
她站在田地外面，沿着田地的行或列水平或垂直照射光束，使光束反射一定数量的镜子。
由于镜子都是沿对角线摆放，因此经反射镜反射的水平光束最终将垂直传播，反之亦然。
贝茜想知道从田地之外射入的水平或垂直光束最多可以在田地中被反射多少次。
给定镜子田地的布局，请帮助贝茜计算这个数字。

输入格式
第一行包含 N 和 M。
接下来 N 行，每行包含 M 个 / 或 \ 字符，表示田地中镜子的具体摆放方式。

输出格式
输出田地之外的水平或垂直光束能够被反射的最大次数。

如果可以无限反射，则输出 −1。

数据范围
1≤N,M≤1000
输入样例：
3 3
/\\
\\\
/\/
输出样例：
3
样例解释
贝茜可以从上向下沿中间列上方发射激光。
共可以反射 3 次。

考察数据范围，时间复杂度最好控制为：O(n*m)。

有一定难度。

将每片镜子分为两个节点，边就是一条光线经过两条点。

节点又可以分为内部节点和边界节点两类，内部节点的度都是2，边界节点的度为1或0。

可以证明穿过矩阵的路径中只有不相交的环和链。

从边界节点出发的路径一定是链，从内部节点出发的路径一定是环。

证明参考题解： https://www.acwing.com/solution/content/85067/。

环图：只含有环和链的图，链和环不相交。（第一次见，下次记住）

题目要求的就是最长的一条链。所以遍历从边界节点出发的所有路径（链）就行。

异或代码解释：

看二进制形式：2(10) = 10(2),10(2) ^ 1(2) = 11(2) = 3(10)，异或1将个位数字取反。

同理，异或3将个位和十位数字都取反。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
int n,m;
char g[N][N];
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1}; // 注意按照顺时针方向，如图所示

int dfs(int x,int y,int d){ // 根据坐标和方向dfs
    if (x < 0 || x >= n || y < 0 || y >= m) return 0; // 出界，找到一条链
    
    if (g[x][y] == '/') d ^= 1; // 根据方向编号进行反射，改变方向
    else d ^= 3;
    
    return dfs(x + dx[d],y + dy[d],d) + 1;
}

int main(){
    cin >> n >> m;
    
    for (int i = 0;i < n;i ++)
        for (int j = 0;j < m;j ++)
            cin >> g[i][j];
            
    int res = 0;
    for (int i = 0;i < m;i ++){ // 光线从上面和下面入射
        res = max(res,dfs(0,i,2));
        res = max(res,dfs(n-1,i,0));
    }
    
    for (int i = 0;i < n;i ++){ // 光线从左面和右面入射
        res = max(res,dfs(i,0,1));
        res = max(res,dfs(i,m-1,3));
    }
    
    cout << res;
    return 0;
}

2022.1.18—1922. 懒惰的牛

这是一个炎热的夏日。
懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置，以便可以在短距离内尽可能多地吃到美味的草。
贝茜所在的田野中共有 N 片草地，我们可以将田野视作一个一维数轴。
第 i 片草地中包含 gi 单位的青草，位置坐标为 xi。
不同草地的位置不同。
贝茜想选取田野中的某个点作为她的初始位置（可能是某片草地所在的点）。
只有一片草地与她的初始位置的距离不超过 K 时，贝茜才能吃到那片草地上的草。
如果贝茜选择最佳初始位置，请确定她可以吃到的青草最大数量。

输入格式
第一行包含两个整数 N 和 K。
接下来 N 行，每行描述一片草地，包含两个整数 gi 和 xi。

输出格式
输出如果贝茜选择最佳初始位置，则她可以吃到的青草最大数量。

数据范围
1≤N≤10^5,
1≤gi≤10000,
0≤xi≤10^6,
1≤K≤2×10^6
输入样例：
4 3
4 7
10 15
2 2
5 1
输出样例：
11
样例解释
最佳初始位置选择为 x=4，可以吃到 x=1,x=2,x=7 处的青草。

本题挺简单的，经典差分例题。数据比较分散的话可以用map处理。

也可以用前缀和求差分，原理是一样的。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
int n,k;
int b[N];

int main(){
    cin >> n >> k;
    
    int g,x;
    while (n--){
        cin >> g >> x;
        int l = max(x-k,0);
        int r = min(x+k,(int)1e6);
        b[l] += g,b[r + 1] -= g;
    }
    
    int ans = 0,sum = 0;
    for (int i = 0;i <= 1e6;i ++){
        sum += b[i];
        ans = max(ans,sum);
    }
    
    cout << ans;
    return 0;
}

2022.1.19—1913. 公平摄影

农夫约翰的 N 头奶牛站在一维长围栏的不同位置。
第 i 头牛位于位置 xi，其所属品种为 bi（根西岛牛或荷斯坦牛）。
所有奶牛的位置各不相同。
约翰想给一段连续区间内的奶牛拍摄一张照片，用来在乡村集市上展览。
但是我们希望他所有品种的奶牛都能在照片中得到公平的展示。
因此，他希望确保无论照片中出些哪些品种的奶牛，每种品种的奶牛在照片中的数量都必须相等。
例如，一张照片中只包含荷斯坦牛是可以的，包含荷斯坦牛和根西岛牛各 27 头也没问题，但是包含 10 头荷斯坦牛和 9 头根西岛牛则不可以。
请确定，约翰可以拍下的满足以上条件的照片的最大尺寸。
照片的尺寸是指照片中奶牛最大和最小位置之间的差。
约翰最终可能只拍下一头奶牛，这种情况下，照片尺寸为 0。

输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个整数 xi 和一个字符 bi（H 表示荷斯坦牛，G 表示根西岛牛）。

输出格式
输出照片的最大尺寸。

数据范围
1≤N≤10^5,
0≤xi≤10^9
输入样例：
6
4 G
10 H
7 G
16 G
1 G
3 H
输出样例：
7
样例解释
共 6 头牛，从左到右排列顺序为 G,H,G,G,H,G。
最佳摄影方案是拍中间四头奶牛，恰好荷斯坦牛和根西岛牛各两头。

注意审题，题目有坑。

每种品种的奶牛在照片中的数量都必须相等。

一张照片中只包含荷斯坦牛是可以的。（只包含一种牛的序列也是合法的）

两句话都很重要。

参考题解： https://www.acwing.com/solution/content/85577/。

本题首先要按距离从小到大排序。

然后就到了这个题目最有意思的点，也是我说这是一道 括号序列 题的原因。

我们做这样的处理：

1. 假如是一头荷斯坦牛 H，那么就把它的权值当成是 1
2. 假如是一头根西岛牛 G，那么就把它的权值当成是 -1

假设没有 一张照片中只包含荷斯坦牛是可以的 这句话，那么就是两种牛的数量都相同的时候，此时若干头牛的 权值和 就是 0。 而这个特点就能帮助我们在 O(1) 的判断这是否是一个合法答案。

比方说有牛 G G H H H G G 对应的权值就分别是 -1 -1 1 1 1 -1 -1 ，那么我们需要 快速知道某一段区间的和，不难想到其实需要用到 前缀和 思想。

对序列求前缀和之后就有 -1 -2 -1 0 1 0 -1 ；

此时意思就是假如 s[r]=s[l] 那么意味着 l+1 头牛开始到第 r 头牛 中，两种牛的数量是相等的。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef pair<int,int> PII;
#define fi first
#define se second
const int N = 1e5+5;
PII p[N]; // 存放牛的距离和品种
int s[N];
unordered_map<int,int> m; // 记录s[i]出现的下标i

int main(){
    int n;
    cin >> n;
    m[0] = 0; // 细节，s[0] = 0，s[0]在下标为0时出现一次
    int x;char c;
    for (int i = 1;i <= n;i ++){
        cin >> x >> c;
        p[i] = {x,(c == 'G' ? 1 : -1)};
    }
    
    sort(p + 1,p + n + 1);
    
    int ans = 0,pos = p[1].fi,val = p[1].se;
    for (int i = 1;i <= n;i ++){
        s[i] = s[i-1] + p[i].se; // 前缀和
        
        if (p[i].se == val) ans = max(ans,p[i].fi - pos); // 求连续的同一种牛的nas
        else pos = p[i].fi,val = p[i].se;
        // 包含多种牛的同数量的ans
        if (m.count(s[i])) ans = max(ans,p[i].fi - p[m[s[i]] + 1].fi);
        else m[s[i]] = i;
    }
    
    cout << ans;
    return 0;
}

2022.1.20—1904. 奶牛慢跑

奶牛们又出去锻炼蹄子去了！
有 N 头奶牛在无限长的单行道上慢跑。
每头奶牛在跑道上开始奔跑的位置都不相同，一些奶牛的奔跑速度也可能不同。
由于跑道是单行道，十分狭窄，奶牛们无法相互超越。
当一头速度很快的牛追上另一头牛时，她必须减速至与另一头牛速度相同以免发生碰撞，并成为同一跑步小组的一员。
最终，再也没有奶牛会撞到（追上）其他奶牛了。
约翰想知道在这种情况下，会剩下多少个跑步小组。

输入格式
第一行包含整数 N.
接下来 N 行，每行包含一头奶牛的初始位置和跑步速度。
所有奶牛的初始位置各不相同，且是按照递增顺序给出的。

输出格式
输出一个整数，表示最终剩下的小组数量。

数据范围
1≤N≤10^5,
初始位置范围 [0,10^9]，
跑步速度范围 [1,10^9]
输入样例：
5
0 1
1 2
2 3
3 2
6 1
输出样例：
2

思维题，不考察算法。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int n,v[N];

int main(){
    cin >> n;
    
    int x;
    for (int i = 0;i < n;i ++) cin >> x >> v[i];
    
    int res = 0,vmin = 2e9;
    for (int i = n-1;i >= 0;i --){
        if (v[i] <= vmin){ // 取等号
            res ++; // 找队长，队长一定不能追尾
            vmin = v[i];
        }
    }
    
    cout << res;
    return 0;
}

补充一种解法。参考题解。

#include<iostream>
#include<stack>
using namespace std;
int main(){
    stack<int>s;
    int n;
    cin>>n;
    while(n--){
        int p,v;//因为题目说位置是有序的所以这里位置不用管
        cin>>p>>v;
        while(!s.empty()&&v<s.top())s.pop();
        s.push(v);
    }
	cout<<s.size()<<endl;

    return 0;
}

2022.1.21—1884. COW

奶牛贝茜在她最喜欢的牧场中发现了一块石碑，上面刻有神秘的碑文。
碑文的文字似乎来自一种神秘的古代语言，可看作一个只包含 C,O,W 三种字符的字符串。
尽管贝茜无法解密该文字，但是她很欣赏 C,O,W 按顺序构成她最喜欢的单词 COW。
她想知道 COW 在碑文中一共出现了多少次。
她不介意 C,O,W 之间是否存在其他字符，只要这三个字符按正确的顺序出现即可。
她也不介意多个不同的 COW 是否共享了一些字符。
例如，COW 在 CWOW 中只出现一次，在 CCOW 中出现两次，在 CCOOWW 中出现八次。
给定碑文中的文字，请帮助贝茜计算 COW 出现的次数。

输入格式
第一行包含 N。
第二行包含一个长度为 N 的字符串，其中只包含字符 C,O,W。

输出格式
输出给定字符串中 COW 作为子序列（不一定连续）的出现次数。

数据范围
1≤N≤10^5
输入样例：
6
COOWWW
输出样例：
6

又不会。

题解：状态机模型。

对于类似背包问题的DP很容易定义每一维的状态，但对于类似本题的DP不好定义第二维的状态。

本题理论看似复杂，代码很简短。

每一条状态机的转移路径都对应一种COW的子序列，两者是一一对应的。

所以问题就转化为了求有多少种状态机的转移路径。

状态计算：考虑当前第i个字符，分为不含Si和含Si两类计算。

当s[i] = 'c'时， f[i,0] = f[i-1,0] + 1：解释，前i个字符走到0状态有多少种走法？

1.前i-1个字符是0状态的走法，以及选择s[i]作为第一个字符的一种状态。

当s[i] = 'c'时， f[i,1] = f[i-1,1]：解释，前i个字符走到1状态有多少种走法？

1状态是CO的路径，当前第i个字符为C，肯定不能选。

---

另一种理解角度。

从前往后遍历：

如果遍历到‘O’，它只会与前面的‘C’组成”CO“，所以不需要管后面的‘C’的数量

同理如果遍历到‘W’，它只会与前面的‘CO’组成”COW“，所以不需要管后面的‘CO’的数量

记录当前‘C’，“CO”，“COW”的个数

#include <iostream>
using namespace std;
typedef long long LL;

int main(){
    int n;
    string str;
    cin >> n >> str;
    
    LL a = 0,b = 0,c = 0;
    for (auto &t : str){
        if (t == 'C') a ++;
        else if (t == 'O') b += a;
        else c += b;
    }
    
    cout << c;
    return 0;
}

也可以写成类似这位佬的“正规”DP代码。

#include <bits/stdc++.h>  // 万能头文件
using namespace std;

const int n = 100010;
char str[n];
int dp[n][2];  // 分别对应 C CO

int N;

int main(void) {
    cin >> N;
    cin >> str + 1;

    long long ans = 0;

    dp[0][0] = 0, dp[0][1] = 0;
    for (int i = 1; i <= N; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        if (str[i] == 'C') {
            dp[i][0] += 1;
        } else if (str[i] == 'O') {
            dp[i][1] += dp[i - 1][0];
        } else {  // str[i] == 'W'
            ans += dp[i - 1][1];
        }
    }

    cout << ans << endl;

    return 0;
}