root 的博客
Day3 题解
root LV27 至高道祖 LV 1 SU @ 2024-7-20 13:36:34

T1 - 小田的01变换

题目描述

小田有一个长度为 $n$ 的字符串 $S$ ，只包含 $0$ 和 $1$ 两种字符。小田每次可以选择两个索引 $i$ 和 $j$ ( $i < j$ 并且在字符串下标范围内)，并满足以下条件之一：

如果区间 [i, j] 中 $1$ 的数量大于 $0$ 的数量，可以把此区间的所有数字都变成 $1$ 。
如果区间 [i, j] 中 $0$ 的数量大于 $1$ 的数量，可以把此区间的所有数字都变成 $0$ 。
如果数量相等，则无法发生变换。

现在小田想知道把整个字符串变成全 $0$ 或者全 $1$ 的最少操作次数，如果无解则输出 $-1$ 。

输入描述

输入包含两行。第一行一个正整数 $n$ ，表示字符串长度。第二行输入一个长度为 $n$ 的字符串 $S$ ，保证输入只包含 $0$ 、 $1$ 。

输出描述

输出包含一行一个整数，表示最少操作次数，无解则输出 $-1$ 。

输入输出样例

输入 #1

3
011

输出 #1

输入 #2

4
1100

输出 #2

说明/提示

【样例 1 解释】 第一次： $i=0,j=2$ ，因为 $1$ 更多，所以全变成 $1$ 。 【样例 2 解释】 第一次： $i=0,j=2$ ，字符串变为 $1110$ 。第二次： $i=0,j=3$ ，字符串变为 $1111$ 。 【数据范围】 对于所有测试数据，有： $1 \le n \le 2 \times 10^{5}$ 。

题目分析

容易想到 0 的情况只有字符串全为 0 或者全为 1 时，答案为 0。

而当字符串中的 0和 1 的数量不相同时，只需要一次就可以。

当 0和 1 的数量相同时，对于通用情况，我们可以先选择一个子区间使得某一边更多，这样下一次就变成了数量不相同的情况，也就是需要 2 次。

但是有特例，就是当字符串长度为 $2$ 时，无法选择满足条件的子区间，所以答案是 -1。

#include <bits/stdc++.h>  
using namespace std;  
  
string s;  
  
int n, cnt1, cnt2;  
  
int main() {  
    freopen("change.in", "r", stdin);
    freopen("change.out", "w", stdout);
    cin >> n >> s;  
    if (s == "10" or s == "01") {  
        cout << -1;  
        return 0;  
    }  
    for (int i=0; i<n; i++) {  
        cnt1 += (s[i] == '0');  
        cnt2 += (s[i] == '1');  
    }  
    if (cnt1 == 0 or cnt2 == 0) cout << 0;  
    else if (cnt1 == cnt2) cout << 2;  
    else cout << 1;  
    return 0;  
}

T2 - 小田滑雪

题目描述

小田正在参加一场滑雪比赛。他从起点出发的时候，速度恒定为每秒 $1$ 米。然而，随着比赛进程的增加，他会犯很多失误，每次失误会使得他的速度下降。当他第一次失误后，速度会下降到每秒 $1/2$ 米，第二次失误后，速度会降到每秒 $1/3$ 米，第 $k$ 次失误后，速度会降到每秒 $1/(k+1)$ 米。你作为小田的好朋友，记录了他所有的失误，你有两种记录方式，一种是按比赛开始后的某个时间点来记录，另一种是按赛道的某个位置上记录。有时小田可能在某个时间点到达某个位置，且恰好在这个时间和这个位置都有一次失误的记录，这两个记录要算作不同的失误，都会对速度造成影响。比赛的终点距离和起点有 $1000$ 米，请问小田需要多少时间才能滑过终点？

输入描述

第一行输入一个整数 $n$ ，表示失误数量。接下来 $n$ 行，每行输入一个字符 $c$ 和一个整数 $x$ ，分别表示记录方式和对应的数据。当字符 $c$ 的值为 T 时，表示本次记录的方式为时间，表示比赛开始第 $x$ 秒发生了失误。当字符 $c$ 的值为 D 时，表示本次记录的方式为距离，表示在距离起点 $x$ 米处发生了失误。

输出描述

输出包含一行一个整数，表示最终的答案，若精确的时间不是整数，则用四舍五入的方式进行取整。

输入输出样例

输入 #1

2
T 30
D 10

输出 #1

说明/提示

【样例 1 解释】 前 $10$ 秒，小田的速度是每秒 $1$ 米，滑了 $10$ 米后发生第一次失误。在接下来 $20$ 秒内，他又滑了 $10$ 米，接着遭遇了第二次失误，速度变为每秒 $1/3$ 米，还剩下 $980$ 米，所以共计花了 $10 + 20 + 2940 = 2970$ 秒完成比赛。 【数据范围】 对于 $10 \%$ 的数据，保证所有的失误都是 T 类型的。对于另外 $10\%$ 的数据，保证所有的失误都是 D 类型的。对于所有测试数据，有： $1 \le n \le 10^{4}$ ，记录的时间小于等于 $10^7$ ，记录的距离小于等于 $10^3$ 。 请注意，不保证数据是按升序输入的。

题目分析

显然，分别存储时间和位置的失误信息，然后排序，然后双指针选择最先发生的失误即可。

难点在于如何比较 d[i] 和 t[j] 谁先发生，可以先算出当前速度在 t[j] 这个时间里能走到的距离，然后再用这个距离去和 d[i] 比较，如果 d[i]更小显然 d[i] 先发生，否则是 t[j] 先发生。

然后注意四舍五入的写法和数据范围即可。

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 1e4+5;  
  
int n;  
vector<int> d, t;  
  
int main() {  
    freopen("snow.in", "r", stdin);
    freopen("snow.out", "w", stdout);
    char op;  
    int x;  
    cin >> n;  
    while (n--) {  
        cin >> op >> x;  
        if (op == 'T') t.push_back(x);  
        else d.push_back(x);  
    }  
    sort(d.begin(), d.end());  
    sort(t.begin(), t.end());  
    d.push_back(2e9);  // 这样可以免去越界判断  
    t.push_back(2e9);  
    int i=0, j=0, v=1;  // v用来记录失误的次数，这样速度就是 1/v
    double s = 0, ti = 0, vi, tmps, tmpt;  // 当前路程 和 时间  
    while (i<d.size()-1 or j<t.size()-1) {  
        // 比较 d[i] 和 t[j] 谁在更前面  
        vi = 1.0 / v;  // 算出速度  
        v++;  // 减速
        tmps = s + (t[j]-ti) * vi;  // 在这段时间内可以走的路程  
        // cout << tmps << '\n';
        if (tmps < d[i]) {  
            s = tmps;  
            ti = t[j];  
            j++;  
        }  
        else {  
            ti += (d[i]-s) / vi;  // 走完这段路程需要的时间  
            s = d[i];  
            i++;  
        }  
    }  
    ti += (1000-s) / (1.0/v);  
    cout << (long long)(ti+0.5);  
    return 0;  
}

T3 - 小田赶牛

题目描述

有 $n$ 头奶牛跑到了小田的花园里去爽吃花儿了，它们现在分别在距离牛圈 $T_{i}$ （这里是指小田到那里需要 $T_{i}$ 分钟）处吃花，每分钟会吃掉 $D_{i}$ 朵花，小田现在要将它们弄回牛圈，但是他每次只能弄一头牛回去，来回用时总共为 $2 \times T_{i}$ 分钟，在这段时间内，其他的奶牛会继续吃小田的花，速度保持不变，当然正在被赶回牛圈的奶牛不能继续吃了。现在小田想让你帮他设计一个赶牛的顺序，使得奶牛总共吃掉的花最少。

输入描述

第一行输入一个整数 $n$ ，表示牛的数量。接下来 $n$ 行，每行输入两个数字 $T_{i}$ 和 $D_{i}$ ，表示第 $i$ 头牛的距离和每分钟吃的花。

输出描述

输出包含一行一个整数，表示最终的答案。

输入输出样例

输入 #1

输出 #1

说明/提示

【样例 1 解释】 赶牛的顺序为 $6, 2, 3, 4, 1, 5$ 。 【数据范围】 对于 $10\%$ 的数据，有：所有牛的 $T_i \times D_i$ 相等。对于另外 $10\%$ 的数据，有：所有牛的 $T_i$ 相等。对于另外 $10\%$ 的数据，有：所有牛的 $D_i$ 相等。对于所有测试数据，有： $1 \le n \le 10^{5}$ ， $1 \le T_{i} \le 2 \times 10^{6}$ ， $1 \le D_{i} \le 100$ 。

题目分析

一道贪心题，关键在于如何对每头牛进行排序。

不管是单对 $T_i$ 排序还是单对 $D_i$ 进行排序，都是能轻松举出反例来体现出它是错误的。

如果是 $T_i \times D_i$ 呢？也不对，因为牛在被牵回去的时候是不会吃草的，这个算出来的数据压根就和题目没关系。

试想一下，如果只对牛 $a$ 和牛 $b$ 进行比较，如果先带走牛 $a$ ，那么牛 $b$ 吃的草是 $a.T \times b.D \times 2$ ；如果先带走牛 $b$ ，那么牛 $a$ 吃的草是 $b.T \times a.D \times 2$ ，显然当第一个式子更小时，先带走牛 $a$ ；否则先带走牛 $b$ 。

可以理解为当 $a.T / a.D < b.T / b.D$ 时，牛 $a$ 应该先被带走。

所以这样就得到了排序的规则，按照这个进行排序，然后遍历数组计算总和即可。

#include <bits/stdc++.h>  
using namespace std;  
  
const int N = 1e5+5;  
  
struct P {  
    int d, t;  
};  
  
long long n, sum[N], res;  
P a[N];  
  
bool cmp(P a1, P a2) {  
    return a1.t*a2.d < a1.d*a2.t;  
}  
  
int main() {  
    freopen("cow.in", "r", stdin);
    freopen("cow.out", "w", stdout);
    cin >> n;  
    for (int i=1; i<=n; i++) {  
        cin >> a[i].t >> a[i].d;  
    }  
    sort(a+1, a+1+n, cmp);  
    for (int i=n; i>=1; i--) {  
        sum[i] = sum[i+1] + a[i].d;  
    }  
    for (int i=1; i<=n; i++) {  
        res += 2 * a[i].t * sum[i+1];  
    }  
    cout << res;  
    return 0;  
}

T4 拼接最大数

题目描述

给定两个整数数组a和b，长度分别n和m。请你利用这两个数组中的数字创建一个长度为k的最大数，注意，你可以从a和b中任意挑选数字，但是要保证数字的相对顺序与原数组一致。请输出这个最大数。

输入描述

第一行三个数，n、m和k。第二行n个数，表示数组a的元素。第三行m个数，表示数组b的元素。

输出描述

输出一行，一个整数，表示长度为k的最大数。

输入输出样例

输入 #1

4 6 5
3 4 6 5
9 1 2 5 8 3

输出 #1

输入 #2

2 3 5
6 7
6 0 4

输出 #2

输入 #3

2 2 3
3 9
8 9

输出 #3

说明/提示

【数据范围】 20%数据： $k <= 2，1<=n,m<=5$ 50%数据： $1<=k<=n+m, 1<=n,m<=10$ 100%数据： $1<=k<=n+m, 1<=n,m<=500, 0<=a_i,b_i<=9$

【解析】

首先把问题简化一下，如果给定一个数组，要你找出这个数组中k个数组成一个最大数，要求找出的数保持原数组顺序，应该怎么做呢？比如：3 6 7 4 5 9 2 7 k=1 ans=9 k=2 ans=97 k=3 ans=927 k=4 ans=7927 k=5 ans=75927 ... 要解答这个问题，我们要借助一种数据结构——单调栈。首先我们要知道什么是单调栈：简单来说，单调栈就是一个内部元素有序的栈（大->小 or 小->大），可以把它理解为：选择一些元素丢弃，剩下的就是一个单调栈。下图就是一个降序单调栈，也是本题需要用到的单调栈类型； 为什么能使用单调栈？ 本题其实是一道贪心算法题，在两个数组中按序找最大组合，它的最优子结构就是在每个数组中都按序找到最大组合。所以我们可以从每个数组的局部最优，推到全局最优。所以能使用单调栈。 部分单调！！！ 普通的单调栈无论是正序或是逆序，都是保证单调栈内元素全部有序，但是本题却不需要保证全部，为什么？答案很简单，我们给定的数量K是确定的，同时我们在循环遍历数组1，2时，每个数组要返回的vector大小也是固定的。所以当我们的单调栈只满足单调性时，元素数很可能不够！这时，我们就需要一些其他操作：

n个元素的序列，找长度为k的最大子序列，最多可以丢弃n-k个数，我们可以设一个变量drop=n-k

每丢弃一个数，drop--，当drop为0时，剩余的数就不能再丢弃了。

#include<bits/stdc++.h>  
using namespace std;  
  
vector<int> a,b;  

//比较a和b两个vector从idx开始谁的字典序大，a大flag>0  
int cmp(vector<int> a, int idxa, vector<int> b, int idxb) 
{  
    int flag;  
    while(idxa < a.size() && idxb < b.size())  
    {  
        flag = a[idxa++]-b[idxb++];  
        if (flag != 0) return flag;  
    }  
    return (a.size()-idxa) - (b.size()-idxb);  
}  
  
vector<int> maxsq(vector<int> v, int k) // 求v的长度为k的最大子序列  
{  
    vector<int> res; // 模拟单调栈  
    int n = v.size();  
    if (n <= k) return v;  
    int drop = n-k; // 可以舍弃的元素个数，当为0时，剩余元素都要加入到res中  
    for (int i = 0; i < n; i++)  
    {  
        while (!res.empty() && v[i]>res.back() && drop > 0)  
        {  
            res.pop_back();  
            drop --;  
        }  
        if (res.size() < k) res.push_back(v[i]);  
        else drop --;  
    }  
    return res;  
}  
  
// 类似归并排序的操作，将两个最大子序列合并为一个最大的数  
vector<int> merge(vector<int> a, vector<int> b) {  
    int lena = a.size(), lenb = b.size();  
    if (lena == 0) return b;  
    if (lenb == 0) return a;  
    int i = 0, j = 0, k = 0;  
    vector<int> res;  
    while (k < lena + lenb)  
    {  
        if (cmp(a,i,b,j) > 0)  
            res.push_back(a[i++]);  
        else  
            res.push_back(b[j++]);  
        k++;  
    }  
    return res;  
}  

int main()  
{  
    int n, m, k;  
    cin >> n >> m >> k;  
    for (int i = 0; i < n; i++)  
    {  
        int x; cin >> x;  
        a.push_back(x);  
    }  
    for (int i = 0; i < m; i++)  
    {  
        int x; cin >> x;  
        b.push_back(x);  
    }  
    // 先求a，b的k最大子序列,这里需要枚举所有可能情况，k个元素分别来自a和b中  
    vector<int> ans(k,0);  
    for (int p = 0; p <= k; p++) // p个来自a，k-p个来自b  
    {  
        vector<int> stka, stkb, res;  
        stka = maxsq(a, p);      // 长为p的a最大子序列  
        stkb = maxsq(b, k-p);     // 长为k-p的b最大子序列  
        res = merge(stka, stkb); // 合并后k最大子序列  
        // 所有的res里面最大的即为答案  
        if (res.size() == k && cmp(res,0,ans,0)>0) ans = res;  
    }  
    for (int i = 0; i < k; i++)  
        cout << ans[i];  
    return 0;  
}

T5 小W运水

思路

标准的dijkstra求解,无向图可直接反向求解，反推走到每个点最少需要运出的水量, 但是要注意小数的问题.

#include<bits/stdc++.h>
using namespace std;

int g[2010][2010];//邻接矩阵
int n,m,s,e; //s,e表示起止点start，end. 
//反推要使得B得到100，那么每个点至少要运出多少水 
double dist[2010]; 
bool st[2010];
void dijkstra()
{
	for(int i = 1;i <= n;i++) dist[i] = 0x3f3f3f3f;//double数组初始化为正无穷 
	dist[e] = 100;//e的值为100 
	
	//无向图可直接反向求解，反推走到每个点最少需要运出的水量 
	for(int i = 1;i <= n;i++)
	{
		int t = -1;
		for(int j = 1;j <= n;j++)
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
				t = j;
		st[t] = true;
		//更新更短的路径
		for(int j = 1;j <= n;j++)//dist[j]*(1-g[t][j]*0.01)=dist[t]
			if(g[t][j]<200&&dist[t]/(1-g[t][j]*0.01)<dist[j])//存在路径才能更新，否则因为g[t][j]=0x3f3f3f3f导致更新 
				dist[j] = dist[t] / (1 - g[t][j]*0.01);
	}
}
int main(){
    freopen("water.in", "r", stdin);
    freopen("water.out", "w", stdout);
	cin>>n>>m;
	int x,y,z;
	memset(g,0x3f,sizeof(g));
	while(m--)
	{
		cin>>x>>y>>z;
		g[x][y] = z;
		g[y][x] = z;
	}
	cin>>s>>e;
	//dijkstra求解
	dijkstra();	
	printf("%.8lf",dist[s]);
    return 0;
     
}

T6 WOW

本题需要使用文件输入输出，文件名为 wow.in 和 wow.out。

题目描述

小z最近对字符串十分的痴迷，特别是让人不禁大叫一声wow的字符串，说到wow，小z瞬间想到自己键盘的w键坏了！作为对字符串的痴迷爱好者，小z自然有小z的办法，他决定利用vv来代替w。现在，小z利用计算机生成了一段只有v和o组成的字符串，需要你找到有多少个wow存在，当然，如果找连续的子串这个问题过于简单，所以他加了一点难度，只需要子串即可。举个例子： vvvovvv 一共有 $4$ 个wow

"vvvovvv"
"vvvovvv"
"vvvovvv"
"vvvovvv"

如果找连续的子串，则答案会是 $1$ （只有第三种满足）

输入描述

输入包含一个非空字符串 $s$ ，仅由字符 "v "和 "o "组成。 $s$ 的长度最多为 $10^6$ 。

输出描述

输出一个整数，即 $s$ 的所有子串中wow的个数。

输入输出样例

输入 #1

vvvovvv

输出 #1

输入 #2

vvovooovovvovoovoovvvvovovvvov

输出 #2

说明/提示

【数据范围】 对于 $20 \%$ 的数据，有：字符串长度不超过 $10$ 。对于所有测试数据，如上文所描述。

做法一：前后缀分解预处理每个 $o$ 左右的 $vv$ 个数，分别记作 $pre$ 和 $suf$ 然后枚举每一个 $o$ ，根据乘法原理，该 $o$ 提供的答案个数为： $pre*suf$

#include<bits/stdc++.h>  
using namespace std;  
  
const int N = 1;  
  
int main()  
{  
    freopen("wow.in","r",stdin);  
    freopen("wow.out","w",stdout);  
    string s;  
    cin >> s;  
    long long pre = 0, suf = 0, ans = 0;  
    int len = s.size();  
    for(int i = 0; i < len; i++) {  
        if(s[i] == 'v' && s[i + 1] == 'v' )             suf ++;  
    }  
    //cout << suf << endl;  
    for(int i = 0; i < len - 1; i++) {  
        if(s[i] == 'o') ans += pre * suf;  
        else {  
            if(s[i - 1] == 'v') pre ++;  
            if(s[i + 1] == 'v') suf --;  
        }  
    }  
    cout << ans;  
    return 0;  
}

方法二：状态机DP

$f_{i,0}$ 表示考虑前 $i$ 个字母，能得到的 $w$ 子序列的个数
$f_{i,1}$ 表示考虑前 $i$ 个字母，能得到的 $wo$ 子序列的个数
$f_{i,2}$ 表示考虑前 $i$ 个字母，能得到 $wow$ 子序列的个数

分类讨论：

如果 $s_i = o$ 那么 $f_{i, 1} = f_{i-1,1} + f_{i-1,0}$ ，分别表示不选和选 $s_i$
如果 $s_i=v$ 且 $s_{i-1} = v$ ，那么 $f_{i,0} = f_{i-1,0} + 1$ ， $f_{i,2}=f_{i-1,2} + f_{i-1,1}$ ，理由同上
其余情况 $f_{i,j} = f_{i-1,j}$

答案为： $f_{n,2}$ 代码实现时，可以利用滚动数组。

#include<bits/stdc++.h>  
using namespace std;  
  
const int N = 1;  
  
int main()  
{  
    freopen("wow.in","r",stdin);      
    freopen("wow.out","w",stdout);     
    string s;  
    cin >> s;  
    long long f0 = 0, f1 = 0, f2 = 0;  
    for(int i = 0; i < s.size(); i++)  
    {  
        if(s[i] == 'o') f1 += f0;  
        else if(s[i - 1] == 'v') {  
            f2 += f1;  
            f0 ++;  
        }  
    }  
    cout << f2;  
    return 0;  
}

Day3 题解

T1 - 小田的01变换

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目分析

T2 - 小田滑雪

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

说明/提示

题目分析

T3 - 小田赶牛

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

说明/提示

题目分析

T4 拼接最大数

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

输入 #3

输出 #3

说明/提示

【解析】

T5 小W运水

思路

T6 WOW

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

状态

开发

支持

关于

登录