Day02 7.9总结

第一类：暴力(T1)

T1.小田的消消乐游戏

题目传送门

这题初一看似乎十分困难—— aia_i 的取值如果范围很大就麻烦了。但是再一看， 0≤ai≤10 \le a_i \le 1 ，也就是 aia_i 只可能是 00 或者 11 。所以答案的取值就只有三种可能了： 0,10, 1 或 22 ，00 是不可能，而 11 是首尾都相同的时候， 22 是可以在 aa 数组中找到两个不同的分割点，使其一个与左边配对，一个与右边配对，如下：

对于一个 i(1<i<n−1)i (1 < i < n - 1) ， 如果 a[1]=a[i]a[1] = a[i] 并且 a[i+1]=a[n]a[i + 1] = a[n] 那么 ii 就是一个可行的分割点，输出 22

实现：

for (int i = 2; i < n - 1; i ++)
    if (a[1] == a[i] && a[i + 1] == a[n])
    {
        cout << 2;
        return 0;
    }

Code:Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, a[N];

int main ()
{
    freopen ("num.in", "r", stdin);
    freopen ("num.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    if (n == 1) {cout << -1; return 0;}
    if (a[1] == a[n]) {cout << 1; return 0;}
    for (int i = 2; i < n - 1; i ++)
        if (a[1] == a[i] && a[i + 1] == a[n]) {cout << 2; return 0;}
    cout << -1;
    return 0;
}

感受与学习：在本题中，我知道了要对每一种情况都要考虑清楚。

错误原因：

  1. 在本题的代码中，我虽然已经把思路完全理解并写好了，却没有仔细检查，将一个情况 n == 1 时的操作从正确的 cout << -1 粗心大意写成了 cout << 1 导致错了一个点。
  2. 我在以后的代码中要再多检查并核查草稿，清晰自己的思路，以防止像这种情况粗心大意写错再发生。

第二类：简单算法(T2, 分类讨论)

T2.小田的气球爆炸啦

题目传送门

本题思考方向在于对各种情况的分类讨论(四种情况) 。

暴力做法：每次对于各种气球，看有几种方案可以消除，每种情况可能一共有 nn 种，最坏时间复杂度 O(n2−3)O (n^{2-3}) 。会超时。

进一步思考，可以很容易想到第一个情况： n=2n = 2 并且 a[1]=a[2]a[1] = a[2] ，则说明这 2 种气球一定会互相抵消，输出 00 。 (伪) →\rightarrow

if(n=2⁡\operatorname{if (n = 2} and⁡\operatorname{and} $\operatorname{a[1] =a[2]) \rightarrow OutPut (0), exit.}$

再想，有什么时候一定会抵消掉所有的，只剩一种颜色呢？当然是有一种颜色的气球比其他所有气球的和都大，抵消了其他气球，输出 11 。 (伪) →\rightarrow

var⁡\operatorname{var} $\operatorname{mxi \leftarrow \max \{a_1, a_2, a_3...a_n\}}$

var⁡\operatorname{var} sum←∑ana1⁡\operatorname{sum \leftarrow \sum^{a_1}_{a_n}}

$\operatorname{if (mxi \ \ge \ sum \ - \ mxi) \rightarrow OutPut (1), exit.}$

最后两种情况(最 难 也最 重要 的)： 在上面，我们写了一个变量 sumsum 代表 a1a_1 至 ana_n 的和，那么可以思考：如果 sumsum 是奇数，说明我们可以从所有气球中任意抽出一个来，让剩下的偶数个气球两两配对消掉，这样每种气球都有可能剩下一个，输出 nn 。而如果 sumsum 为偶数，那么我们可以将每种气球拿出两个，将剩下的配对。但由于只有 11 个的拿不出两个，所以我们统计 aa 中个数为 11 的气球，剩下的非 11 数就是答案，由于 sumsum 要么为奇要么为偶，所以所有情况都考虑完了。 (伪) →\rightarrow

var⁡\operatorname{var} $\operatorname{cnt} \leftarrow \operatorname{Count (1)}$ in⁡\operatorname{in} array⁡\operatorname{array} a⁡\operatorname{a}

var⁡\operatorname{var} sum⁡...\operatorname{sum}... (见上)

if(sum⁡\operatorname{if (sum}  mod \bmod $2 = 1) \rightarrow \operatorname{OutPut (n), exit.}$

$\operatorname{else \rightarrow OutPut (n-cnt), exit.}$

现在 44 种情况都分析完了。

Code:Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, a[N], cnt, sum, mxi;

signed main ()
{
    freopen ("balloon.in", "r", stdin);
    freopen ("balloon.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        sum += a[i];
        mxi = max (mxi, a[i]);
        if (a[i] == 1) cnt ++;
    }
    if (n == 2 && a[1] == a[2]) {cout << 0; return 0;}
    else if (mxi >= sum - mxi) {cout << 1; return 0;}
    else if (sum % 2) {cout << n; return 0;}
    else if (sum % 2 == 0) {cout << n - cnt; return 0;}
    return 0;
}

感受与学习：我明白了学习时要多从各种角度分析，如本题就是从气球数各种不同的极值，再到奇偶性来分析的。

错误原因：本题我由于自己 懒 ，加上时间原因，只骗了 15 分，实属没有好好考虑，当我下次明白要分类讨论时，我会做到先考虑极值(特判) ，在思考概括除特殊情况外的大部分情况(如奇偶性) 。

第三类：搜索(T3, 深搜DFS[或贪心])

T3.小k的加减游戏

题目传送门

做法1.贪心

本题第一个思路是使用贪心。使用字符转换和数组达到便捷的效果。每次判断输入的字符串，比较参加运算的两个数，如果都是 00 则说明不能持续 nn 轮，输出 No 并 return 0 。否则将大的那个数 −1- 1 ，小的那个数 +1 + 1 并加入答案字符串中，最后如果没有提前 return 0 那么输出 Yes 并将答案字符串输出。

Code:Code:

#include <bits/stdc++.h>
using namespace std;
int n, a[5];
string s;

int main ()
{
	freopen ("game.in", "r", stdin);
	freopen ("game.out", "w", stdout);
	cin >> n >> a[1] >> a[2] >> a[3];
	for (int i = 1; i <= n; i ++)
	{
		char cx, cy; int tx, ty;
		cin >> cx >> cy;
		tx = cx - 'A' + 1, ty = cy - 'A' + 1;
		if (a[tx] <= 0 && a[ty] <= 0)
		{
			cout << "No";
			return 0;
		}
		if (a[tx] > a[ty])
		{
			s += char (ty + 'A' - 1);
			a[tx] -= 1, a[ty] += 1;
		}
		else
		{
			s += char (tx + 'A' - 1);
			a[tx] += 1, a[ty] -= 1;
		}
	}
	cout << "Yes" << '\n';
	for (int i = 0; i < n; i ++) cout << s[i] << '\n';
	return 0;
}
做法2.深搜(接近暴力)

另一个写法使用深搜(纯练手)

具体思路见代码。

Code2:Code2:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, a, b, c;
string s[N];

void DFSgm (int idx, int a, int b, int c)  
{
    if (idx == n + 1)
    {
        cout << "Yes\n";
        for (int i = 1; i <= n; i ++) cout << s[i] << '\n';
        exit (0); 
    }  
    if (s[idx] == "AB")
    {  
        if (a) s[idx] = 'B', DFSgm (idx + 1, a - 1, b + 1, c);  
        if (b) s[idx] = 'A', DFSgm (idx + 1, a + 1, b - 1, c);  
    }
    else if (s[idx] == "AC")
    {  
        if (a) s[idx] = 'C', DFSgm (idx + 1, a - 1, b, c + 1);  
        if (c) s[idx] = 'A', DFSgm (idx + 1, a + 1, b, c - 1);  
    }
    else if (s[idx] == "BC")
    {  
        if (b) s[idx] = 'C', DFSgm (idx + 1, a, b - 1, c + 1);
        if (c) s[idx] = 'B', DFSgm (idx + 1, a, b + 1, c - 1);
    }
}

int main ()
{
    freopen ("game.in", "r", stdin);
    freopen ("game.out", "w", stdout);
    cin >> n >> a >> b >> c;
    for (int i = 1; i <= n; i ++)
        cin >> s[i];
    DFSgm (1, a, b, c);
    cout << "No";
    return 0;
}

感受与学习：本题虽然可以使用贪心写，但代码 2 中搜索的思想也很重要，并且通过以前的做题，我发现我最大知识薄弱面都在搜索题上，所以需要多加练习😕😕 😕 😕 (表情意味着还没有练习的搜索题，目前1/5)

upd:2024.7.12 Day05 小W去冒险

错误原因：无

第四类：图论(T4, 非常简单版)

T4.蓬莱山仙峰台

题目传送门

本题既可以通过邻接表来写，也可以直接在输入时统计边连接的两个观景台高度来表示，下面展示了三份代码，还有一份代码是我自己的思想(理论空间复杂度最坏过不了，但可能由于数据太水而AC了，为严谨此处也贴在这里) 。

做法1.邻接表(图论)

做法1就是在读入邻接表后遍历每个表 ii ，如果 ii 为空或是沿途的所有点高度都小于 h[i]h[i] 则 cnt ++ ，最后输出 cnt 。

Code:Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, hd[N], h[N], idx = 1, cnt;
int vn[N], nid[N];

void AddList (int x, int y)
{
    vn[idx] = y, nid[idx] = hd[x];
    hd[x] = idx ++;
}

void CntXFT (int x)
{
    bool isXFT = true;
    for (int i = hd[x]; i != -1; i = nid[i])
        if (h[vn[i]] >= h[x]) {isXFT = false; break;}
    if (isXFT) cnt ++;
}

int main ()
{
    freopen ("penglai.in", "r", stdin);
    freopen ("penglai.out", "w", stdout);
    cin >> n >> m;
    memset (hd, -1, sizeof (hd));
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i <= m; i ++)
    {
        int f, t;
        cin >> f >> t;
        AddList (f, t), AddList (t, f);
    }
    for (int i = 1; i <= n; i ++) CntXFT (i);
    cout << cnt;
    return 0;
}
做法2.遍历标记(偏暴力)

本做法思路十分简单，就是在输入边时看两个观景台之间高度的大小，如果对于一个观景台 uu ，与它相连的一个观景台是 vv ，那么如果 h[v]>=h[u]h[v] >= h[u] ，那么 uu 就不是"仙峰台"了，同理，如果 h[u]>=h[v]h[u] >= h[v] ，则 vv 也不是了，最后统计 cnt 输出。

Code:Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m, h[N], cnt;
bool sta[N];

signed main ()
{
    freopen ("penglai.in", "r", stdin);
    freopen ("penglai.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {cin >> h[i]; sta[i] = true;}
    for (int i = 1; i <= m; i ++)
    {
        int f, t;
        cin >> f >> t;
        if (h[f] >= h[t]) sta[t] = false;
        if (h[t] >= h[f]) sta[f] = false;
    }
    for (int i = 1; i <= n; i ++) if (sta[i]) cnt ++;
    cout << cnt;
    return 0;
}
做法3.自己做法

就是用 vector 存储每个点能去的所有其他点，然后遍历，用一个 edg 数组储存当前点有没有与其他点有联系，不推荐使用(理论上会爆空间)。

Code:Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, h[N], edg[N], cnt;

struct edgeJ
{
    vector <int> cgo;
} rd[N];

void CntXFT ()
{
    for (int i = 1; i <= n; i ++)
    {
        if (! edg[i]) cnt ++;
        else
        {
            bool isXFT = true;
            for (int j = 0; j < rd[i].cgo.size (); j ++)
                if (h[rd[i].cgo[j]] >= h[i]) {isXFT = false; break;}
            if (isXFT) cnt ++;
        }
    }
}

int main ()
{
    freopen ("penglai.in", "r", stdin);
    freopen ("penglai.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    for (int i = 1; i <= m; i ++)
    {
        int f, t;
        cin >> f >> t;
        rd[f].cgo.push_back (t);
        rd[t].cgo.push_back (f);
        edg[f] ++, edg[t] ++;
    }
    CntXFT ();
    cout << cnt;
    return 0;
}

感受与学习：我在本题明白了邻接表是一切图论题的核心基础之一，需要好好掌握。

错误原因：第一次用自己写的代码 (vector) 觉得会爆空间所以改了(这个想法没错) ，但在改了之后因为自己对每个部分如标记数组和统计边的数组定义不清晰，所以多此一举(有了标记数组就不需要边数组了) ，一定要在题目中(特别是图论这种有些复杂的题) 对每个变量、数组的定义都要清晰。

第五类：数学(T5)

T5.数学题1

题目传送门

本题题面十分直白，就是求一个在 1−n,1−m1 - n, 1 - m 之间能够任意选两个数 a,ba, b 使 a+ba + b 是 b⋅gcd⁡(a,b)b \cdot \gcd ({a, b}) 的倍数。

先不急着写，在题解中我先给出结论： a+ba + b 是 b2b ^ 2 的倍数。为什么呢？看下面证明。

证明 (a+b)(a + b) modmod (b×gcd⁡(a,b))=0(b \times \gcd (a, b)) = 0 时， a+ba + b modmod b2=0b ^ 2 = 0

首先， gcd⁡(a,b)×b\gcd (a, b) \times b 一定是 bb 的倍数，因为乘上了一个 bb 。而如果想让 a+ba + b 成为 gcd⁡(a,b)×b\gcd (a, b) \times b 的倍数，那么我们先知道， gcd⁡(a,b)\gcd (a, b) 肯定是 aa 的因数，那么， aa 只要是 bb 的倍数就可以了。

aa 是 bb 的倍数，那么 gcd⁡(a,b)=b\gcd (a, b) = b ，两者公因数为 bb 。我们可以设 q=a÷bq = a \div b ，也就是 a=bqa = bq 。那么 a+b=bq+b→(q+1)×ba + b = bq + b \rightarrow (q + 1) \times b

然后我们发现， a+ba + b ，变成了 b2b ^ 2 的倍数 →gcd⁡(a,b)\rightarrow \gcd (a, b) 是 aa 的因数，bb 也是 aa 的因数，那么 gcd⁡(a,b)⋅b\gcd (a, b) \cdot b 是 a+ba + b 的因数， b2b ^ 2 也就是 a+ba + b 的因数 。

设 xx 为 (a+b)÷b2(a + b) \div b^2 ，也就是 a+ba + b 中有 xx 个 b2b^2 ，那么 a=xb2−ba = xb^2 - b (移项) 。 又因为 a≤na \le n ，所以 xb2−b≤nxb^2 - b \le n ，xx 一定小于等于 nn ，xx 最大为 (n+b)÷b2(n + b) \div b^2 ，也就是从 1−n1 - n 中有 (n+b)÷b2(n + b) \div b^2 个 xx 的可能性。 所以我们要枚举 bb ，每枚举一个 bb ，就让 ans += (n + b) / (b * b) ，由于 b * b 有可能溢出，所以改为 (n + b) / b / b ，记得开 long long。

此题证毕。

Code:Code:

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

signed main ()
{
    freopen ("math1.in", "r", stdin);
    freopen ("math1.out", "w", stdout);
    cin >> n >> m;
    for (int b = 1; b <= m; b ++)
        ans += (n + b) / b / b;
    cout << ans - 1;
    return 0;
}

感受与学习：本题我知道了在遇到一时摸不着头脑的纯数学题时应该先从各种数字的性质入手，如 gcd⁡\gcd ，质数，奇偶数等。再通过不同的转换、合并来求解(如本题当 aa 是 bb 的倍数时， gcd⁡(a,b)=b\gcd (a, b) = b 等)

错误原因：本题由于对数学题的练习不够多，导致做题时根本找不到头绪，不知道 a+ba + b 是 gcd⁡(a,b)⋅b\gcd (a, b) \cdot b 的倍数是有什么性质，也没有仔细深入地想，粗略敷衍地骗了个分就没有管了，以后当考试出数学题时，我会将它细致认真的推演出来，明白它的性质。

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

T6.小z的徒步旅行

题目传送门

本题乍一看，所有路径，像是深搜或最短路，可是再仔细读完题后，原来是一道 DP 。

思路：

  1. 我们先不管至少要有一条短路径的限制，也不管有 mm 个小屋，我们先想如果只有两个房子，并且不分路径，从出发的房子 AA 到湖边有 33 条路，从另一栋房子 BB 到湖边也有 33 条路。那么试问当我们从 AA 出发，走到湖边又走回任意一座小屋，有几种路径选择呢？ 很明显，从 AA 走到湖边有 33 条路，回来时既可以回到 AA ，也可以走到 BB ，有 3+3=63 + 3 = 6 条路。一共有 3×6=183 \times 6 = 18 条路径。
  2. 那么现在，我们开始考虑有路径的长短之分。容易得知，我们的 s[i]+l[i]s[i] + l[i] 就是从第 ii 座房子到湖边的路径数，而 s[1]+s[2]+...s[m]+l[1]+l[2]+...+l[m]s[1] + s[2] + ... s[m] + l[1] + l[2] + ... + l[m] 就是再从湖边回到所有屋子的所有路径数。我们设 rd[i]=s[i]+l[i]rd[i] = s[i] + l[i] ，也就是从第 ii 个屋子到湖边的路径数。那么我们枚举一个 jj 从 11 到 mm ，代表出发的屋子，一个 kk 也是从 11 到 mm ，代表要去的屋子，那么每次用一个 sumsum 加上 r[j]×r[k]r[j] \times r[k] ，也就是从一天里所有到湖边再回来的路径数。 而我们如果想要得到所有至少有一条短路的路径，就必须减去所有只走长路的路径数 →l[j]×l[k]\rightarrow l[j] \times l[k] ，从开始到回来只走长路径的方案数，最终得到一天里能走的所有路径数： r[j]×r[k]−l[j]×l[k]r[j] \times r[k] - l[j] \times l[k]。
  3. 但是题目要求我们走 nn 天，那么可以考虑用 DP 维护每天的路径数 r[j]×r[k]−l[j]×l[k]r[j] \times r[k] - l[j] \times l[k] 。那么状态表示 f[i][j]f[i][j] 就可以表示第 ii 天走到第 jj 个小屋方案，属性为数量。状态计算就是每次将 f[i][j]f[i][j] 设为一天里能走的路径的数量，但是这里的路径数不仅仅是 r[j]×r[k]−l[j]×l[k]r[j] \times r[k] - l[j] \times l[k] 了，由于在第 ii 天之前可能有许多地方能走到第 jj 个房子，每个房子都有可能走到 jj ，所以我们要再乘上一个 f[i−1][k]f[i - 1][k] ，也就是前一天能走到的路径数。同时， f[0][1]=1f[0][1] = 1 ，代表开始前(第 00 天) ，到第一个屋子，只有一条路。
  4. 最后的答案，就是 ∑fn,mfi,j\sum^{f_{i,j}}_{f_{n,m}} ，代表在最后一天(第 nn 天) ，走到任何房子的路径数。

Code:Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9 + 7, N = 1e2 + 10;
int n, m, s[N], rd[N], f[N * 10][N * 10], l[N];

signed main ()
{
    freopen ("walk.in", "r", stdin);
    freopen ("walk.out", "w", stdout);
    cin >> m >> n;
    for (int i = 1; i <= m; i ++) cin >> s[i];
    for (int i = 1; i <= m; i ++)
    {
        cin >> l[i];
        rd[i] = l[i] + s[i];
    }
    f[0][1] = 1;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            int sum = 0;
            for (int k = 1; k <= m; k ++)
            {
                sum += (rd[j] * rd[k] - l[j] * l[k]) * f[i - 1][k];
                sum %= MOD;
            }
            f[i][j] = sum;
        }
    }
    int sum = 0;
    for (int i = 1; i <= m; i ++)
        sum = (sum + f[n][i]) % MOD;
    cout << sum;
    return 0;
}

感受与学习：本题我明白了对于一道 DP题 ，应该先想好要求什么，怎么表示，然后将状态表示和计算想清楚，就能迎刃而解。

错误原因：对于本题，自己认为题目太过复杂，暴力与优化都不想也想不到思路。下次对于 DP ，我会尽力(因为有些 真的难 知识面过于深奥) 。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 38ms
  4. Powered by Hydro v5.0.0-beta.13 Community