钟柯哲哲的博客
钟柯哲哲7.10总结
钟柯哲哲 LV2 金丹期 LV 6 @ 2024-7-10 20:23:48

Day03 7.10总结

第一类：暴力(T1)

T1.小田的01变换

对于本题，能够很容易发现答案只有 $-1, 0, 1, 2$ 四种情况，需要分类讨论。

$0$ 的情况。如果字符串本来就全是 $0$ 或 $1$ ，那么就不用操作了，直接输出 $0$ 。
$1$ 的情况。用两个变量 cnt0, cnt1 统计 $0$ 和 $1$ 的个数，如果 $0$ 的个数不等于 $1$ 的个数，那么就只要选择 $[1, n]$ 操作，只要一次，输出 $1$ 。
$-1$ 的情况。 $-1$ 只有一种情况：如果 $n = 2$ 并且 $s[0] \ne s[1]$ ，就无法变成全 $1$ 或全 $0$ ，输出 $-1$ 。
$2$ 的情况。如上面的情况都没有出现，则输出 $2$ ，也就是 cnt0 == cnt1 的情况且不符合上面任何一种情况，那么从中找到一个奇数段长， $0$ 个数与 $1$ 个数不同的 $01$ 串变换，再将全部元素变换即可。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int cnt1, cnt0;

int main ()
{
    freopen ("change.in", "r", stdin);
    freopen ("change.out", "w", stdout);
    cin >> n >> s;
    if (n == 2 && s[0] != s[1]) {cout << -1; return 0;}
    for (int i = 0; i < n; i ++)
        if (s[i] == '1') cnt1 ++;
        else cnt0 ++;
    if (cnt1 == n || cnt0 == n) {cout << 0; return 0;}
    if (cnt1 != cnt0) {cout << 1; return 0;}
    cout << 2;
    return 0;
}

感受与学习：本题我明白了在做思维题的时候经常有特判，需要对每一种情况做到刚好划分，不要重复判断，否则可能会画蛇添足。

错误原因：对本题的情况划分不清晰，本来写其他几个特判就能对了却画蛇添足加了一个 n % 2 == 1 的奇数判断导致错误，下次应该从这些方面去想：有什么需要的特判，又有哪些情况可以包含所有可能性，或是有什么能够化繁为简的思想。但切记一定要不重不漏，不要自作聪明加一些本来没有用的特判。

第二类：简单算法(T2, 模拟, T3, 排序)

T2.小田滑雪

题目传送门

本题首先可以看出是一道模拟题。本题最大的困难是有两种失误的表示方法：距离和时间。不过也可以想到，用一个变量 dist 表示现在到了多少距离， ans 表示已经过了多少时间(秒数) 。由于这里速度的分母是每次 $+ 1$ ，那么可以用一个 spd 变量记录分母，速度就是 1 / spd ( $\frac{1}{spd}$ ) ，在一个 while 循环中，如何每次更新两个变量呢？应该每次更新里当前位置近的距离，也就是当前失误时间对应的距离和当前失误距离来比较。哪个小就先更新哪个。

最后如果全部失误都走完了还没有到终点， ans 就要加上时间 (= 剩下的距离 / 速度) 。

伪代码：

$\operatorname{vectorArray}$ $\operatorname{pt[], pd[]}$

$\operatorname{var \ dist = 0, ans = 0, spd = 1 (double)}$

$\operatorname{var \ idt = 0, idd = 0 (integer)}$

$\operatorname{while (idt \le pt.size () \ or \ idd \le pd.size ())}$

$\operatorname{begin \rightarrow}$

$\operatorname{var \ tspd = 1 \div spd(double), inc(spd)}$

$\operatorname{var \ tdist = (pt[idt] - ans) \times tspd + dist (double)}$

$\operatorname{if (tdist < pd[idd]) \rightarrow dist = tdist, ans = pt[idt], inc (idt)}$

$\operatorname{else \rightarrow ans = ans + (pd[idd] - dist) \div tspd, dist = pd[idd], inc (idd)}$

$\operatorname{end;}$

最后的特判：

$\operatorname{if (dist < 1000) \rightarrow ans = ans + (1000 - dist) \div (1 \div spd)}$

代码可以根据上面写出：

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <int> pt, pd;
double spd = 1, ans, dist;
int n;

signed main ()
{
    freopen ("snow.in", "r", stdin);
    freopen ("snow.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        char c; int a;
        cin >> c >> a;
        if (c == 'T') pt.push_back (a);
        else pd.push_back (a);
    }
    sort (pt.begin (), pt.end ());
    sort (pd.begin (), pd.end ());
    pt.push_back (2e9), pd.push_back (2e9);
    int i = 0, j = 0;
    while (i < pt.size () - 1 || j < pd.size () - 1)
    {
        double tspd = 1 / spd;
        spd ++;
        double xn = (pt[i] - ans) * tspd + dist;
        if (xn < pd[j]) dist = xn, ans = pt[i], i ++;
        else ans += (pd[j] - dist) / tspd, dist = pd[j], j ++;
    }
    ans += (1000 - dist) / (1 / spd);
    cout << (long long)(ans + 0.5);
    return 0;
}

感受与学习：本题我明白了对于一道大模拟，最应该找到的是你需要求什么(目标) ，接下来有几个步骤：

在做模拟题时应该先将思路、每一步的作用写出来。
把每个变量的作用和含义也要列得清清楚楚。
根据自己理出来的思路写代码，把每一步自己的变量、数组，和所有自己的思路对照。
愉快的提交。

错误原因：对于模拟，我的大忌就是不打草稿，然后一团乱糟糟的去写。但考试时太注意自己做的简单的题了，导致没有太过注意。下次再做题时，等简单的题写完了就会认真仔细的看题。

T3.小田赶牛

题目传送门

本题不需要保证牛的顺序，又要求求出让牛吃花最少的数量，那么肯定是在相同时间内吃花越多的牛越先走越好，那么很容易就看出来，这是一道排序题，使用 sort 对结构体中的“性价比”排序后，同时用一个 qsum[] 数组记录前缀和来计算在该走的牛走后所有牛每分钟吃花数的总和，再每次加上 (qsum[n] - qsum[i]) * cow[i].t * 2 也就是所有牛在本来要走的牛都走后，在这段时间里吃的花。

难点在于，怎么判定哪头牛先走最好呢？换句话说，就是怎么写 cmp ([cowJ], [cowJ]) 里面的判断排序条件呢？前面说过，可以根据“性价比”排序，所以有两种 cmp 写法：

真正的按性价比排序：用每头牛每分钟吃的花数(性)除以带这头牛回去的时间(价) ，根据此值排序。伪： $cow[i].xb = cow[i].d \div cow[i].t$
按每头牛在相同时间下吃的花数排序。可以假设现在只有两头牛 $A$ 和 $B$ ， $A$ 带回去的时间为 $t_A$ ，每分钟吃花数为 $d_A$ ， $B$ 带回去的时间为 $t_B$ ，每分钟吃花数为 $d_B$ 。那么我们可以思考带走 $A, B$ 两头牛的情况：如果带走 $A$ ， $B$ 在带走 $A$ 所花的 $2 \times t_A$ 时间中一共吃了 $2 \times t_A \times d_B$ 朵花，同理，带走 $B$ ， $A$ 就会吃掉 $2 \times t_B \times d_A$ 朵花。那我们只要判断 $2 \times t_A \times d_B$ 和 $2 \times t_B \times d_A$ 的大小，就知道应该带走 $A$ 还是 $B$ 了。伪：

$\operatorname{cmp ([cowJ] \ a, [cowJ] \ b) begin \rightarrow}$

$\operatorname{return \ a.t \times b.d < a.d \times b.t}$

$\operatorname{end;}$

$Code:$

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, st, qsum[N], ans;

struct cowJ
{
    int t, d;
    double xb;
} cow[N];

bool CmpC (cowJ a, cowJ b)
{
    return a.xb > b.xb;
}

signed main ()
{
    freopen ("cow.in", "r", stdin);
    freopen ("cow.out", "w", stdout);
    cin >> n; st = n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> cow[i].t >> cow[i].d;
        cow[i].xb = cow[i].d * 1.0 / cow[i].t;
    }
    sort (cow + 1, cow + n + 1, CmpC);
    for (int i = 1; i <= n; i ++) qsum[i] = qsum[i - 1] + cow[i].d;
    for (int i = 1; i <= n; i ++)
    {
        st --;
        ans += (qsum[n] - qsum[i]) * (2 * cow[i].t);
    }
    cout << ans;
    return 0;
}

感受与学习：本题我知道了在做一道简单算法的题时应该想好和模版题有什么区别，提取其中的思想。

错误原因：无

第三类：数据结构(T4, 栈 + 归并)

T4.合并最大数

题目传送门

本题一开始可以想到暴力解法：用双指针枚举两个数组中的元素并把每一种可能都写出来取最大值输出，但是时间复杂度极高，不能通过，要考虑优化。

解题步骤：

先想好我们需要求出什么：将两个数组 $a, b$ 分别要求截出一段长度为 $i$ 和 $k - i$ 的子序列要求字典序最大，再将两个序列合并，也是要求字典序最大，最后更新答案。
然后想到我们要写三个函数：一个函数可以获得在一个数组中长度为 $k$ 的字典序最大的子序列，这个函数仔细观察其功能可以发现字典序最大是要求元素单调非递增的，那么可以用单调栈来维护；还有一个函数用来将两个子序列合并为一个字典序最大的序列；最后一个是用来比较两个序列的字典序大小的，用来更新答案和比较后续子序列字典序。
重点在于第二个函数：合并两个子序列并保证字典序最大。首先当两个序列的同一位的值不同时，可以直接将大的那个加入新子序列中。但如果两个序列这一位的值一样，说明两个都可以选，但想到这一位后面的值可能不一样，如果选后面字典序小的，下一次字典序大的就会被压在下面不能取，所以要取后面子序列较大的那个对应的。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int n, m, k;

vector <int> GetSubArr (vector <int> tp, int cnt)
{
	if (tp.size () <= cnt) return tp;
	int n = tp.size () - cnt;
	vector <int> mts;
	for (int i = 0; i < tp.size (); i ++)
	{
		while (mts.size () && mts.back () < tp[i] && n)
		{
			mts.pop_back ();
			n --;
		}
		if (mts.size () < cnt) mts.push_back (tp[i]);
		else n --;
	}
	return mts;
}

bool CmpFrom (vector <int> tp1, int fr1, vector <int> tp2, int fr2)
{
	int tf1 = fr1, tf2 = fr2;
	while (tf1 < tp1.size () && tf2 < tp2.size ())
	{
		if (tp1[tf1] != tp2[tf2]) return tp1[tf1] > tp2[tf2];
		tf1 ++, tf2 ++;
	}
	return tf1 < tp1.size ();
}

vector <int> UniS (vector <int> tp1, vector <int> tp2)
{
	vector <int> res;
	int i = 0, j = 0;
	while (i < tp1.size () && j < tp2.size ())
	{
		if (tp1[i] > tp2[j]) res.push_back (tp1[i ++]);
		else if (tp1[i] < tp2[j]) res.push_back (tp2[j ++]);
		else
		{
			if (CmpFrom (tp1, i, tp2, j)) res.push_back (tp1[i ++]);
			else res.push_back (tp2[j ++]);
		}
	}
	while (i < tp1.size ()) res.push_back (tp1[i ++]);
	while (j < tp2.size ()) res.push_back (tp2[j ++]);
	return res;
}

int main ()
{
    freopen ("big.in", "r", stdin);
    freopen ("big.out", "w", stdout);
	cin >> n >> m >> k;
	vector <int> a, b;
	for (int i = 1; i <= n; i ++)
	{
		int tp; cin >> tp;
		a.push_back (tp);
	}
	for (int i = 1; i <= m; i ++)
	{
		int tp; cin >> tp;
		b.push_back (tp);
	}
	vector <int> ans (k);
	for (int i = 0; i <= k; i ++)
	{
		vector <int> ta = GetSubArr (a, i);
		vector <int> tb = GetSubArr (b, k - i);
		vector <int> t = UniS (ta, tb);
		if (t.size () == k && CmpFrom (t, 0, ans, 0)) ans = t;
	}
	for (auto itr : ans) cout << itr;
    return 0;
}

感受与学习：本题是一道非常非常好的数据结构题。考察对单调栈的应用，同时在"合并"这个操作中也运用了归并的思想(每次将大的放在前) ，但是有改进。

错误原因：根本没有头绪 (~~甚至想到了DP~~) ，只骗了 20 分，然后就去做其他题去了 (~~其实我根本不对这种题抱有希望~~) ，下次如果在做完简单题后，应该对这种题进行深入思考， 千万不要摆烂!

第四类：图论(T5, 最短路Dijkstra)

T5.小W运水

题目传送门

本题初一看，是一道最短路问题，而且数据范围较小、只有正权边，说明可以用朴素版 Dijkstra 来做。

但是本题有要求：要求的是初始水量，所以要从终点开始跑，跑到起点；由于权值(水量)有可能是小数，所以要将 dist 的类型改为 double 。而且要运到 $B$ 城市的水量要有 100吨 。所以初始化时要将 dist[终点] 设为 100 。

那么本题就很简单了。

$Code:$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n, m, g[N][N], st, ed;
double dist[N];
bool vis[N];

void Dijkstra ()
{
    for (int i = 1; i <= n; i ++) dist[i] = 0x3f3f3f3f;
    dist[ed] = 100.0;
    for (int i = 1; i < n; i ++)
    {
        int x = -1;
        for (int j = 1; j <= n; j ++)
            if (! vis[j] && (dist[j] < dist[x] || x == -1)) x = j;
        vis[x] = true;
        for (int y = 1; y <= n; y ++)
        {
            if (g[x][y] < 100 && dist[y] > (dist[x] / (1 - g[x][y] * 0.01)))
                dist[y] = dist[x] / (1 - g[x][y] * 0.01);
        }
    }
}

int main ()
{
    freopen ("water.in", "r", stdin);
    freopen ("water.out", "w", stdout);
    cin >> n >> m;
    memset (g, 0x3f, sizeof (g));
    for (int i = 1; i <= n; i ++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x][y] = min (g[x][y], z);
        g[y][x] = min (g[y][x], z);
    }
    cin >> st >> ed;
    Dijkstra ();
    printf ("%.8lf", dist[st]);
    return 0;
}

感受与学习：本题我知道了对于一道模版裸题，先注意与原题的区别(如：题面复杂看不出是裸题、或有些许改变) ，然后想办法消除这些区别。比如这道题要求我们运到终点时有 100 吨水，那么我们就从终点开始倒着求。

错误原因：看出来了是 Dijkstra 裸题，但没有想到怎么在模板上改，特别是扫描出边的循环中的判断条件，应该对模版题多加深刻记忆，遇到这种题时灵活变通，看题目要求什么，再根据模版去改。

第五类：DP(T6, 线性DP)

T6.WOW

题目传送门

本题一开始可以想到暴力解法：用三重循环，两个枚举相邻的 v ，一个枚举 o ，时间复杂度 $O(n^3)$ ，只能过前 2 个点，考虑优化。

优化后有两种方法，前后缀和 + DP 。

做法1.前后缀和

思路：对于每一个 o ，我们只要统计这个 o 前面 vv 的数量和后面 vv 的数量，那么这个 o 能组成 vvovv 的数量就是前面的 vv 数 $\times$ 后面的 vv 数。

那么我们用一个 frt 和 bak 数组， frt[i] 代表第 $i$ 个字符前面有多少个 vv ， bak[i] 则是后面的。那么第 $i$ 个字符 $(s[i] = o)$ 能组成的 wow 数就是 frt[i] * bak[i] 。

那么， frt[i](或bak[i]) 究竟怎么算呢？当当前 s[i] == 'v' 时，如果 s[i - 1] == 'v' ，说明多了一个新的 "vv" ， frt[i] = frt[i - 1] + 1 。bak 数组同理。

做法2.DP

设一个 $f[][3]$ 数组，有：

$f[i][0]$ 表示字符串中子串 vv 的数量。
$f[i][1]$ 表示字符串中子串 vvo 的数量。
$f[i][2]$ 表示字符串中子串 vvovv 的数量。

很显然，最后答案为 $f[n][2]$ 。

那么我们根据 s[i] 当前的值来分类讨论。

s[i] == 'o' 。这种情况我们只可能更新 $f[i][1]$ 的值。多了一个 o ，那么之前所有 vv 都可以变成子串 vvo (加上这个 o) ，所以 $f[i][1] = f[i][1] + f[i][0]$ 。
s[i] == 'v' ，但必须要 s[i - 1] == 'v'。这种情况我们既能更新 $f[i][0]$ ，也可以更新 $f[i][2]$ 。 $f[i][0]$ 的情况也很简单，和第一种做法类似， $f[i][0]$ 可以直接 $+ 1$ 。而 $f[i][2]$ 如果也满足这两个条件，说明 $s[i]$ 之前的所有子串 vvo 都可以和这两个 v 组成 vvovv ，也就是满足 $f[i][2]$ 的更新条件。又因为 vvo 的数量就是 f[i][1] ，所以可以让 $f[i][2] = f[i - 1][2] + f[i][1]$ ，就被更新了。
最后，由于题中的数组第一维只用到了 $i, i - 1$ 两个下标，所以可以仿照 01背包的写法，用三个变量 $f0, f1, f2$ ，代表 $f[i][0], f[i][1], f[i][2]$ ，当需要用上一维的下标时直接调用，用到的直接就是上一维对应的了。

$Code:$

#include <bits/stdc++.h>
using namespace std;
long long f0, f1, f2;
string s;

int main ()
{
	freopen ("wow.in", "r", stdin);
	freopen ("wow.out", "w", stdout);
    cin >> s;
    for (int i = 0; i < s.size (); i ++)
    {
        if (s[i] == 'o') f1 += f0;
        else if (s[i - 1] == 'v' && s[i] == 'v') f0 ++, f2 += f1;
    }
    cout << f2;
    return 0;
}

感受与学习：本题我们明白了在一个题目中，要细致的对每一种情况进行深入讨论，如对于本题，我们就要对 s[i] == 'o' 和 s[i] == 'v' 的情况去分析。特别是对于 DP题 ，要做到以下3点。

不重(也许不一定)不漏。
将大问题分解成许多子问题
初始化。

错误原因：最大问题懒，不愿意多想。在考试时认为自己对于剩下的时间已经不够做出这道题了，所以没有仔细去想，下次应该从这些方面去想：

对一道题目，它的题面描述是怎么样的，是什么意思。
先想暴力 (有些题目用暴力也能过) ，不能过则跳到下一步
这道题目想做出来应该 用什么算法 (!!!!!!!)。
这道题和模版题 (或没有，通用格式) 有什么区别，区别在于哪里，应该干什么才能将这个区别消掉或是应该在简单 / 做过的题上做什么修改才可能过。
打草稿 (1.有条理 2.目标明确 3.精神集中) 。
注意细节并 Debug (freopen, 范围或特判) 。
愉快的提交，下一题。

钟柯哲哲7.10总结

Day03 7.10总结

第一类：暴力(T1)

T1.小田的01变换

第二类：简单算法(T2, 模拟, T3, 排序)

T2.小田滑雪

T3.小田赶牛

第三类：数据结构(T4, 栈 + 归并)

T4.合并最大数

第四类：图论(T5, 最短路Dijkstra)

T5.小W运水

第五类：DP(T6, 线性DP)

T6.WOW

做法1.前后缀和

做法2.DP

状态

开发

支持

关于

钟柯哲哲7.10总结

Day03 7.10总结

第一类：暴力(T1)

T1.小田的01变换

第二类：简单算法(T2, 模拟, T3, 排序)

T2.小田滑雪

T3.小田赶牛

第三类：数据结构(T4, 栈 + 归并)

T4.合并最大数

第四类：图论(T5, 最短路Dijkstra)

T5.小W运水

第五类：DP(T6, 线性DP)

T6.WOW

做法1.前后缀和

做法2.DP

状态

开发

支持

关于

登录