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

T1 - 小田的消消乐游戏

题目描述

小田得到了一个由 $n$ 个整数组成的数组 $a$ ，现在他可以对对数组进行如下操作：

选择一对 $(i, j)$ ，必须满足 $1 \le i \lt j \le n$ ，并且 $a_{i} == a_{j}$ ，然后将 $[a_{i}, a_{i+1}, ..., a_{j-1}, a_{j}]$ 这些数字全部从数组中删除。易知，删除后数组将变成 $[a_{1}, a_{2}, ..., a_{i-1}, a_{j+1}, ..., a_{n-1}, a_{n}]$ 。

现在小田通过若干次上述操作，将数组中的元素全部删除，请问他最少需要多少次操作呢？

输入描述

输入包含两行。第一行一个正整数 $n$ ，表示数组的长度。第二行输入 $n$ 个整数 $a_{i}$ ，数字之间用空格隔开。

输出描述

输出包含一行一个整数，表示最少的操作次数。如果无论如何都无法使数组变为空，那么输出 -1 。

输入输出样例

输入 #1

5
0 1 0 1 1

输出 #1

输入 #2

5
1 1 1 1 0

输出 #2

-1

说明/提示

【样例 1 解释】 第一次操作选择 $i=1, j=3$ ，删除后数组变为 $[1, 1]$ 。第二次操作选择 $i=1, j=2$ ，删除后数组变为空。共两次。 【数据范围】 对于 $5 \%$ 的数据，有： $n = 1$ 。对于 $15 \%$ 的数据，有： $n = 2$ 。对于所有测试数据，有： $1 \le n \le 5 \times 10^{5}, 0 \le a_{i} \le 1$ 。

题目分析

因为数字只由 $0$ 和 $1$ 组成，所以处理还是很简单的，只有几种情况：

头尾数字相同，只需要删除一次。
头尾数字不同，但是在 $2 \sim n-1$ 这个范围中，存在一组相邻的数字，使得 $a[1] == a[i]$ 且 $a[i+1] == a[n]$ ，那么 $2$ 次就可以删掉
否则不能删除，比如 $1 1 1 1 0$ 。
特殊情况，只有一个数字，无法删除。

示例代码：

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

const int N = 5e5+5;  

int n, a[N];  

int main() {   
	    cin >> n;  
	    for (int i=1; i<=n; i++) {  
		        cin >> a[i];  
	    }  
	    if (n == 1) cout << -1;  
	    else if (a[1] == a[n]) cout << 1;  
	    else {  
		        for (int i=2; i<n-1; i++) {  
			            if (a[1] == a[i] and a[i+1] == a[n]) {  
				                cout << 2;  
				                return 0;  
			            }  
		        }  
		        cout << -1;  
	    }  
	    return 0;  
}

T2 - 小田的气球爆炸啦

题目描述

小田有 $n$ 种不同颜色的气球，每种气球有 $a_i$ 个，两个不同颜色的气球接触在一起后会爆炸！小田不小心把所有的气球混在了一起，于是气球们自由的运动着（即任何两个气球都可能会相碰），开始接触并且爆炸。气球会一直运动、碰撞，直到没有气球能发生爆炸，即气球没了或者只剩下一种颜色的气球。听着气球劈里啪啦的爆炸声，小田哇哇大哭。为了安慰他，请你为他计算出剩下的气球的颜色有多少种可能。

输入描述

输入包含两行。第一行一个正整数 $n$ ，表示气球的颜色数。第二行输入 $n$ 个整数 $a_{i}$ ，数字之间用空格隔开，表示每种气球的数量。

输出描述

输出包含一行一个整数，表示剩下的气球颜色有多少种可能，如果不可能有气球会剩下，则输出 $0$ 。

输入输出样例

输入 #1

4
2 2 3 4

输出 #1

输入 #2

2
1 1

输出 #2

说明/提示

【样例 1 解释】 四种气球都可能是剩下的那一种，所以答案是 $4$ 。 【样例 2 解释】 两种气球发生碰撞就没有了，所以答案是 $0$ 。 【数据范围】 对于 $5 \%$ 的数据，有： $n = 1$ 。对于另外 $10 \%$ 的数据，有： $n = 2$ 。对于另外 $15 \%$ 的数据，有： $n = 3$ 。对于所有测试数据，有： $1 \le n \le 10^{5}, 1 \le a_{i} \le 10^{5}$ 。

题目分析

一样是分类讨论的题目，情况具体看注释，一样的。示例代码：

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

const int N = 1e5+5;  

int n, a[N], maxx, cnt;  
long long sum;  

int main() {  
	cin >> n;  
	for (int i=1; i<=n; i++) {  
		cin >> a[i];  
		maxx = max(maxx, a[i]);  
		sum += a[i];  
		if (a[i] > 1) cnt++;  
	}  
	if (n == 2 and a[1] == a[2]) cout << 0;  // 特殊情况，两种气球一样多，只能是0  
	else if (maxx >= sum-maxx) cout << 1;  // 否则，最大值比其他数的总和还大时，必然只能留下最大值的气球  
	else if (sum & 1) cout << n;  // 奇数的情况，每种气球都可以留下来  
	else cout << cnt;  // 偶数的情况，只要气球的数量大于1，就可以留下来  
	return 0;  
}

T3 - 小k的加减游戏

题目描述

小k有三个整数A，B，C，游戏共有N论，操作如下：每一轮需要选择A，B，C中任意两个数，将其中一个+1，另外一个-1，每次操作后，不允许出现负数。请问游戏是否可以进行N轮？如果可以输出yes，并且打印每轮操作中选择+1的那个数。

输入描述

第一行4个数，N，A，B，C。接下来N行，每行一个字符串，为AB，AC，BC其中一个。

输出描述

如果可以操作N轮，输出Yes，并且把每轮+1的数打印，一个一行。否则输出No。

输入输出样例

输入 #1

2 1 3 0
AB
AC

输出 #1

Yes
A
C

输入 #2

3 1 0 0
AB
BC
AB

输出 #2

No

输入 #3

8 6 9 1
AC
BC
AB
BC
AC
BC
AB
AB

输出 #3

Yes
C
B
B
C
C
B
A
A

说明/提示

【数据范围】

$1 \leq N \leq 10^5$
$0 \leq A,B,C \leq 10^9$
$N, A, B, C$ 均为整数 【样例1解释】 可以成功地做出两次操作，如下所示：
在第一次操作中，将 1 与 𝐴 相加，并从 𝐵 中减去 1 。 𝐴 变为 2 ， 𝐵 变为 2 。
在第二次操作中，将 1 与 𝐶 相加，并从 𝐴 中减去 1 。 𝐶 变为 1 ， 𝐴 变为 1。

解析

dfs暴力搜索所有情况，若存在答案一定可以找到，输出即可，若没有答案，递归会于某一层终止。如果找到了，直接输出答案并系统性退出，没有回溯过程。每层递归只会进入一条分支，执行一次赋值与判断操作，时间复杂度O(n)。

#include<bits/stdc++.h>  
using namespace std;  
  
const int N = 1e5+10;  
int n, a, b, c, f=0;  
string s[N];  
char ans[N];  
  
void dfs(int x, int a, int b, int c)  
{  
    if (x > n)                                        // x>n说明此时已经进行了n个操作  
    {  
        puts("Yes");  
        for (int i = 1; i <= n; i++)cout << ans[i] << endl;   // 输出每次操作对应执行+1的字母  
        exit(0); 
    }  
    if (s[x] == "AB")  
    {  
        if (a) ans[x] = 'B', dfs(x + 1, a - 1, b + 1, c);  
        if (b) ans[x] = 'A', dfs(x + 1, a + 1, b - 1, c);  
    }  
    else if (s[x] == "AC")  
    {  
        if (a) ans[x] = 'C', dfs(x + 1, a - 1, b, c + 1);  
        if (c) ans[x] = 'A', dfs(x + 1, a + 1, b, c - 1);  
    }  
    else  
    {  
        if (b) ans[x] = 'C', dfs(x + 1, a, b - 1, c + 1);  
        if (c) ans[x] = 'B', dfs(x + 1, a, b + 1, c - 1);  
    }  
}  
  
int main()  
{  
    cin >> n >> a >> b >> c;  
    for (int i = 1; i <= n; i++) cin >> s[i];     // 用二维字符串数组装所输入n个字符串  
    dfs(1, a, b, c);                              // dfs枚举所有情况，第一个参数表示第几个操作  
    puts("No");                           // 在dfs中没有输出结果，说明进行不到第n个操作  
    return 0;  
}

T4 - 蓬莱山仙峰台

题目描述

在蓬莱山有 $N$ 个观景台，称为TP. $1$ ，TP. $2$ ， $...$ ，TP. $N$ ，观景台TP. $i$ 高度为 $H_i$ 。还有 $M$ 条道路，每条道路连接两个不同的观景台。道路 $j$ 连接TP. $A_j$ 和TP. $B_j$ 。若某个观景台 TP. $i$ 满足下面的任意条件，我们则称它为仙峰站：

这个站比所有与他直接相连的站都要高
没有任何一个站能到达TP. $i$

现在给你观景台和道路数据，请你算一下蓬莱山有多少个仙峰台。

输入描述

$N$ $M$ $H_1$ $H_2$ $...$ $H_N$ $A_1$ $B_1$ $A_2$ $B_2$ $:$ $A_M$ $B_M$

输出描述

一行，输出好台的数量。

输入输出样例

输入 #1

输出 #1

输入 #2

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

输出 #2

说明/提示

【样例1解释】

TP1连接了TP3，TP1比TP3矮，所以TP1不是仙峰台
TP2连接了TP3和TP4，TP2比TP3矮，所以TP2不是仙峰台
TP3连接了TP1、TP2，TP3比1和2都高，所以TP3是仙峰台
TP4连接了TP2，TP4比TP2高，所以TP4是仙峰台仙峰台的总数量为2。

【数据范围】

$2 \leq N \leq 10^5$
$1 \leq M \leq 10^5$
$1 \leq H_i \leq 10^9$
$1 \leq A_i,B_i \leq N$
$A_i \neq B_i$
两个观测站之间可能有多条道路
输入的数据均为整数

解析：

解法1：邻接表将图存下来，遍历每个节点，看是否满足条件（连通图中的最大值或者不与其他任何点联通），是则统计。解法2：假设所有观景台都是仙峰台，若存在观景台u，v，高度h[u] > h[v]，则v不再满足条件。

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

const int N=1e5+5;
bool st[N];
int  h[N];
int main(){
    freopen("penglai.in", "r", stdin);
    freopen("penglai.out", "w", stdout);
    int n,m; cin >> n >> m;
    for(int i=1;i<=n;++i) cin >> h[i];
    for(int i=1;i<=n;++i) st[i]=1; // 初始化所有都是仙峰台
    
    for(int i=1;i<=m;++i){	//枚举所有观景台
        int u,v; 
        cin >> u >> v;
        if(h[u]>=h[v]) st[v]=0;
        if(h[v]>=h[u]) st[u]=0;
    }
    int cnt=0;
    for(int i=1;i<=n;++i) cnt+=st[i];
    cout << cnt << endl;
}

T5 `math1.in` `math1.out`

Background

这是一道数学题。

Description

题目描述：给你两个正整数 $n$ , $m$ 。计算满足下列条件的有序数对 $(a, b)$ 的个数：

$1\le a\le n$ , $1\le b\le m$ ;
$a+b$ 是 $b \cdot \gcd(a,b)$ 的倍数。

Format

Input

输入每个测试用例的第一行包含两个整数 $n$ , $m$ ( $1\le n,m\le 2 \cdot 10^6$ )。

Output

为每个测试用例输出一个整数：有序数对的个数。

Samples

1 1

2 3

1000000 1145141

Limitation

对于20%的数据， $n, m$ 不会超过 $100$ . 对于100%的数据，满足上文的输入描述。

解析：我们发现 $b*gcd(a,b)$ 必然为 $b$ 的倍数，那么 $b*gcd(a,b)$ 的倍数 $a+b$ 也必然为 $b$ 的倍数。所以，a必然为 $b$ 的倍数。因为 $a$ 为 $b$ 的倍数，所以 $gcd(a,b) = b$ ，原式可以化为 $a+b=xb^2$ ,其中 $x$ 为正整数。考虑枚举 $b$ ，原式可化为 $𝑎=𝑥𝑏^2−𝑏$ 。又因为 $𝑎≤𝑛$ ，则 $𝑥𝑏^2−𝑏≤𝑛$ 。则 $𝑥$ 的最大值为 $⌊𝑛+𝑏^2⌋ \div b^2$ ，共有 $⌊𝑛+𝑏^2⌋ \div b^2$ 种取值，对应的 $𝑎$ 也有 $⌊𝑛+𝑏^2⌋ \div b^2$ 种取值。注意最后有 $a=1,b=1$ 这种情况会算重，需要减去 $1$ 。

#include <bits/stdc++.h>

using namespace std;

  

typedef long long LL;

  

int main()

{

    LL n, m;

    cin >> n >> m;

    LL ans = 0;

    for (LL b = 1; b <= m; b++)

        ans += (n + b) / b / b;

    cout << ans - 1 << endl;

    return 0;

}

T6 小z步行之旅

小z在徒步旅行。在这个地区有 $m$ 个小木屋，编号从1到 $m$ 。每个小木屋都有一条或多条小路与湖边的中心集合点相连。每条小径或长或短。小木屋 $i$ 与湖边的 $s_i$ 条短路径和 $l_i$ 条长路径相连。每天，小z都会从他现在所在的小屋步行到洞庭湖，然后从那里步行到 $m$ 个小屋中的任何一个（包括他开始所在的小屋）。不过，由于他必须在一天内走完，所以两条路中至少有一条是短路。如果小z从 1 号小木屋出发，走 $n$ 天，他可以走多少条小路？请给出答案，取模 $10^9 + 7$ 。输入第一行包含整数 $m$ 和 $n$ 。第二行包含 $m$ 个整数、 $s_1, \dots, s_m$ 个整数，其中 $s_i$ 是小木屋 $i$ 和洞庭湖之间的短路径数量。第三行也就是最后一行包含 $m$ 个整数， $l_1, \dots, l_m$ ，其中 $l_i$ 是小木屋 $i$ 和洞庭湖之间的长路径的数量。我们有以下约束条件： $0 \le s_i, l_i \le 10^3$ . $1 \le m \le 10^2$ . $1 \le n \le 10^3$ .

输出小径的可能组合数，取模 $10^9 + 7$ 。

样例输入1

3 2 1 0 1 0 1 1

样例输出1

18 对于20%的数据， $1 \leq n, m \leq 10$ 对于100%的数据，与上文描述一致。 ![[Pasted image 20240708203846.png]] 代码如下：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MOD = 1e9 + 7;

int n, m, s[105], l[105], r[105], dp[1005][105];

// dp[i][j]:第 i 天时在第 j 个小屋的方案数

bool f[100005];

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];

        r[i] = l[i] + s[i];

    }

    dp[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 += (r[j] * r[k] - l[j] * l[k]) * dp[i - 1][k];

                sum %= MOD;

            }

            dp[i][j] = sum;

        }

    }

    int sum = 0;

    for(int i = 1; i <= m; i++){

        sum += dp[n][i];

        sum %= MOD;

    }

    cout << sum;

    return 0;

}

Day2 题解

T1 - 小田的消消乐游戏

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目分析

T2 - 小田的气球爆炸啦

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

题目分析

T3 - 小k的加减游戏

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

输入 #3

输出 #3

说明/提示

解析

T4 - 蓬莱山仙峰台

题目描述

输入描述

输出描述

输入输出样例

输入 #1

输出 #1

输入 #2

输出 #2

说明/提示

解析：

T5 math1.in math1.out

Background

Description

Format

Input

Output

Samples

Limitation

T6 小z步行之旅

样例输入1

样例输出1

状态

开发

支持

关于

登录

T5 `math1.in` `math1.out`