chenshixian 的博客
陈室先的总结7.9day2
chenshixian LV13 太乙真仙 LV 2 @ 2024-7-9 20:11:12

🚀️题目传送门

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 解释】 第一次操作选择 $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$ 。

错的地方😕

1.思路不够完善，要多打草稿

2.过于急躁，要仔细思考

考试不急躁打卡👀️

第一阶段：

第二阶段：

第三阶段：

第四阶段：

❤️思路

这道题很简单~~虽然我没写出来~~，我们看到 $1 \le n \le 5 \times 10^{5},0 \le a_{i} \le 1$ 。注意 !

0 \le a_i \le 1

所以很简单我们现在可以推出，输出只可能是-1/1/2,-1是只有一个元素，永远不能消除，1是数组第一个与最后一个一样直接全消，这里特判不要错了~~我就错了~~ 2的情况是在 a 数组中找两个不同的分割点，使其一个与左配对，一个与边配对：

一个 $𝑖 (1<𝑖<𝑛−1)$ ，如果 $𝑎[1]=𝑎[𝑖], a[i+1]=a[n]$ 那么 $i$ 就是一个可分割点，输出 2 。

代码（暴力！！！）🎉️

#include<bits/stdc++.h>
using namespace std;
int a[500010],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;
}

T2 - 小田的气球爆炸啦😄 😄

题目描述

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

输入描述

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

输出描述

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

样例省略

说明/提示

【样例 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}$

错的地方😕

1.分类讨论没深入,要更具题意来，不能瞎想

2。在再做时，有些思路没理清，导致错误，思路还是要认真整理在草稿纸上

❤️ 思路

这道题要分类讨论（一共四种）：第一种是一个特判，在数组长度为2数组时，如果第一种与第二种一样多那么直接全没cout<<0;第二种是出现巨无霸，只有巨无霸能活下来（巨无霸的定义是一种气球的数量比其他的加起来还多）cout<<1;第三种是气球总和为奇数，所有种类都可以存留下来，cout<<n;第四种时气球总数是偶数，只有数量适宜的留不下来cout<<o(不是零的数量)

代码（暴力）🎉️

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
	freopen("balloon.in","r",stdin);
	freopen("balloon.out","w",stdout);
	int o=0,ma=-190000,n;
	long long l=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]!=1)o++;
		l+=a[i];
		ma=max(ma,a[i]);
	}
	if(n==2&&a[1]==a[2])cout<<0;
	else if(ma>=l-ma)cout<<1;
	else if(l%2==1)cout<<n;
	else if(l%2==0)cout<<o;
}

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 \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。

错的地方😕

1.模拟有误，以后过程要写下来

❤️ 思路

1.dfs直接暴力 2.贪心模拟（样例太水，错的代码都能对，要正确就要每次都要考虑后面的操作。）

代码🎉️

第一种朴素贪心（错的，AC是因为数据水）

#include<bits/stdc++.h>
using namespace std;
int n,a[100],l=1;
string s;
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	cin>>n>>a[0]>>a[1]>>a[2];
	for(int i=1;i<=n;i++){
		string h;
		cin>>h;
		int x=h[0]-'A',y=h[1]-'A';
		if(a[x]>a[y])a[x]--,a[y]++,s+=h[1];
		else a[y]--,a[x]++,s+=h[0];
		if(a[x]==-1||a[y]==-1)l=0;
		
	}
	if(l==0)cout<<"No";
	else{
		cout<<"Yes\n";
		for(int i=0;i<s.size();i++)cout<<s[i]<<"\n";
	}

}

第二种绝“对”模拟（所有数据都能过）

#include <bits/stdc++.h>
using namespace std;
string t;
string s;
vector<string> vctr;
int n,a,b,c;
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;
		vctr.push_back(s);
	}
	for(int i=0;i<vctr.size();i++){
		if(vctr[i]=="AB"){
			if(a==1&&b==1){
				if(i==vctr.size()-1){
					t=t+"A";
				}else{
					if(vctr[i+1]=="BC"){
						a--,b++;
						t=t+"B";
					}else{
						a++,b--;
						t=t+"A";
					} 
				}
			}else{
				if(!a&&!b){
					cout << "No";
					return 0;
				}
				if(a>b){
					a--,b++;
					t=t+"B";
				}else{
					a++,b--;
					t=t+"A";
				}
			}
		}if(vctr[i]=="BC"){
			if(b==1&&c==1){
				if(i==vctr.size()-1){
					t=t+"B";
				}else{
					if(vctr[i+1]=="AC"){
						b--,c++;
						t=t+"C";
					}else{
						b++,c--;
						t=t+"B";
					}
				}
			}else{
				if(!c&&!b){
					cout << "No";
					return 0;
				}
				if(b>c){
					b--,c++;
					t=t+"C";
				}else{
					b++,c--;
					t=t+"B";
				}
			}
		}if(vctr[i]=="AC"){
			if(a==1&&c==1){
				if(i==vctr.size()-1){
					t=t+"A";
				}else{
					if(vctr[i+1]=="AB"){
						a++,c--;
						t=t+"A";
					}else{
						a--,c++;
						t=t+"C";
					}
				}
			}else{
				if(!a&&!c){
					cout << "No";
					return 0;
				}
				if(a>c){
					a--,c++;
					t=t+"C";
				}else{
					a++,c--;
					t=t+"A";
				}
			}
		}
	}
	cout << "Yes\n"; 
	for(int i=0;i<t.size();i++){
		cout << t[i] << endl;
	}
}

此代码作者为伍衍，此代码遵循CC-SA-BY 4.0协议

第三种 dfs（老师所著）

#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解释】

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.有几个h[a]达成了a,以后要注意这些细节

思路❤️

1.很简单，在输入时标记，排除不可能的，输出剩下的个数

2 邻接表,太简单了，就不写了~~我不想写~~

代码(邻接表不写我就是不想写)🎉️

#include<bits/stdc++.h>
using namespace std;
int n,m,st[100010],h[100010];
long long c;
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];
		st[i]=1;
	}
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		if(h[a]==h[b])st[a]=st[b]=0;
		else if(h[a]<h[b])st[a]=0;
		else st[b]=0;
	}
	for(int i=1;i<=n;i++){
		if(st[i])c++;
	}
	cout<<c;
}

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

const int N = 2e5 + 20;
int h[N], e[N], ne[N], idx, a[N];
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int main()
{
	freopen("penglai.in", "r", stdin);
	freopen("penglai.out", "w", stdout);
	int n, m;
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		add(x, y);
		add(y, x);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		bool flag = true;
		for(int j = h[i]; j != -1; j = ne[j])
		{
			int id = e[j];
			if(a[id] >= a[i]) {
				flag = false;
				break;
			} 
		}
		if(flag ) ans ++;
	}
 	cout << ans;
	return 0;
}

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

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

样例省略

Limitation

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

😕 错的点

1.我本来就写了纯暴力,不过因为下划线函数不能直接调用导致没拿分,以后要细心点

❤️ 思路

bgcd(a,b)一定是b的倍数那么a+b一定是b的倍数 a也是b的倍数 gcd(a,b)=b; a+b=b^2的倍数 a+bb=x(b^2) a<=n xb^2-b<=n max(x)<=(n+b)/(b^2)

代码🎉️

#include<bits/stdc++.h>
using namespace std;
long long c;
int main(){
	freopen("math1.in","r",stdin);
	freopen("math1.out","w",stdout);
	long long n,m;
	cin>>n>>m;
	for(int b=1;b<=m;b++)c+=(n+b)/b/b;
	cout<<c-1;
}

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

错的点😕

1.题目更本没看懂，以后看这种dp是要好好读图题

❤️ 思路

一道很简单的dp，状态转移方程是：

$$sum += (r[j] * r[k] - l[j] * l[k]) * dp[i - 1][k];$$

sum 取模1e9+7

腿的过程很简单~~明明很难~~我就不讲了~~懒得讲~~

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s[111],l[111],r[111],f[1111][111];
int e=1e9+7;
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];
	}
	f[0][1]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int s=0;
			for(int k=1;k<=m;k++){
				s+=f[i-1][k]*(r[k]*r[j]-l[k]*l[j]);
				s%=e;
			}
			f[i][j]=s;
		}
	}
	int s=0;
	for(int i=1;i<=m;i++){
		s=(s%e+f[n][i])%e;
	}
	cout<<s;
}

陈室先的总结7.9day2

🚀️题目传送门

T1 - 小田的消消乐游戏 😄 😄

题目描述

输入描述

输出描述

样例省略

说明/提示

错的地方😕

1.思路不够完善，要多打草稿

2.过于急躁 ，要仔细思考

考试不急躁打卡👀️

第一阶段：

第二阶段：

第三阶段：

第四阶段：

❤️思路

代码 （暴力！！！）🎉️

T2 - 小田的气球爆炸啦😄 😄

题目描述

输入描述

输出描述

样例省略

说明/提示

错的地方😕

1.分类讨论没深入,要更具题意来，不能瞎想

2。在再做时，有些思路没理清，导致错误，思路还是要认真整理在草稿纸上

❤️ 思路

代码（暴力）🎉️

T3 - 小k的加减游戏😄 😄

题目描述

输入描述

输出描述

样例省略

说明/提示

错的地方😕

1.模拟有误，以后过程要写下来

❤️ 思路

代码🎉️

第一种朴素贪心（错的，AC是因为数据水）

第二种绝“对”模拟（所有数据都能过）

此代码作者为伍衍，此代码遵循CC-SA-BY 4.0协议

第三种 dfs（老师所著）

T4 - 蓬莱山仙峰台😄 😄

题目描述

输入描述

输出描述

样例省略

说明/提示

错的原因😕

1.有几个h[a]达成了a,以后要注意这些细节

思路❤️

代码(邻接表不写我就是不想写)🎉️

T5 😄 😄

Background

Description

Format

Input

Output

样例省略

Limitation

😕 错的点

1.我本来就写了纯暴力,不过因为下划线函数不能直接调用导致没拿分,以后要细心点

❤️ 思路

代码🎉️

T6 小z步行之旅😄 😄 😄

样例输入1

样例输出1

错的点😕

1.题目更本没看懂，以后看这种dp是要好好读图题

❤️ 思路

代码

状态

开发

支持

关于

登录

2.过于急躁，要仔细思考

代码（暴力！！！）🎉️

1.有几个`h[a]`达成了`a`,以后要注意这些细节