算法每日一题8

2023-04-11

竞赛 / 算法 / 每日一题

Word count: 2.2k | Reading time≈ 10 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、寒假作业

lanqiao-1388：寒假作业 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：dfs

$\textcolor{red}{分析：}$

使用深度优先搜索将所有情况遍历一遍，判断最终符合要求的方案数；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 寒假作业
int a[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};// 下标从0开始 
int b[20];
bool visit[20];
int ans = 0;

void dfs(int s, int len){
	if(s==13){
		ans++;
		return;
	}
	if(s==3&&b[0]+b[1]!=b[2])return;
	if(s==6&&b[3]-b[4]!=b[5])return;
	if(s==9&&b[6]*b[7]!=b[8])return;
	if(s==12&&b[9]!=b[11]*b[10])return;// 将除法转换为乘法 
	for(int i=0;i<len;++i){
		if(!visit[i]){// 未使用过 
			visit[i] = true;
			b[s] = a[i];
			dfs(s+1, len);
			visit[i] = false;// 恢复现场 
		}
	}
} 

int main() {
	dfs(0, 13);
	cout<<ans;
	return 0;
}

2、跳蚱蜢

lanqiao-642：跳蚱蜢 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：dfs、思维

$\textcolor{red}{分析：}$

采用queue队列实现bfs遍历，由初始态012345678到目标087654321；
因为蚱蜢很多，跳蚱蜢很复杂，因此建议跳空盘，更好理解；
注意根据题意知，应该有4中跳法：顺时针跳1步、顺时针跳2步、逆时针跳1步、逆时针跳2步；
可以采用set和map进行去重以及判断是否达到了最后的目标。

$\textcolor{red}{注意：}$

将反方向的-2到达的位置，转换为正方向下的位置坐标7。int k=(j+9)%9;

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 跳蚱蜢——广度优先搜索 ——求最短路径问题 
string str;
unordered_map<string, bool>visited;// 标记是否已经跳过当前状态 
struct node{
	string s;// 当前状态 
	int t;// 到达当前状态的跳跃次数
	node(string ss, int tt){
		s = ss;
		t = tt;
	} 
};
queue<node>q;

void bfs(){// 广度优先搜索 
	while(!q.empty()){
		node now = q.front();
		q.pop();
		string s = now.s;
		int step = now.t;
		if(s=="087654321"){
			cout<<s<<endl;
			cout<<"result:"<<step;// 最终结果
		}
		int i;
		for(i=0;i<s.length();++i){
			if(s[i]=='0'){
				break;
			}
		}
		for(int j=i-2;j<=i+2;++j){// 四种移动方式 
			int k = (j+9)%9;// 方便向逆时针跳动时得到的下标为顺时针下的位置
			if(i==k)continue;// 相当于没有移动 
			string news = s;
			swap(news[i], news[k]);// 当前空盘与目标数进行交换
			if(!visited[news]) {// 如果还没有访问过 
				visited[news] = true;
				q.push(node(news, step+1)); 
			}
		}
	}
	
}

int main() {
	str = "012345678";
	q.push(node(str, 0));
	visited[str] = true;// 当前状态已经遍历过
	bfs();
	return 0;
}

3、七段码

lanqiao-595：七段码 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月6日

tags：回溯法、思维

$\textcolor{red}{分析：}$

邻接矩阵+回溯法；
还可以通过并查集+dfs来解决；

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 七段码 ——dfs+并查集 
int ans;// 结果 
bool un[8][8];
bool visit[8];// 标记是否点亮 
int parent[8];

void init(){// 并查集初始化 
	for(int i=1;i<=7;++i){
		parent[i] = i;
	}
}

int find(int x){
	if(x!=parent[x]){
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

void unionSet(int x, int y){
	int xx = find(x);
	int yy = find(y);
	if(xx!=yy)parent[xx] = yy;
}

bool check(){
	int flag = 0;
	init();// 并查集初始化
	for(int i=1;i<=7;++i){
		for(int j=1;j<=7;++j){
			if(un[i][j]&&visit[i]&&visit[j])unionSet(i, j);
		} 
	}
	for(int i=1;i<=7;++i){
		if(visit[i]&&parent[i]==i)flag++;
	}
	if(flag==1)return true;// 只有flag为1时才能够证明整个七段码中只有一个连通图 
	return false; 
}

void dfs(int x){
	if(x==8){
		if(check())ans++;
		return;
	}
	visit[x] = true;// 点亮
	dfs(x+1);
	
	visit[x] = false;// 不点亮
	dfs(x+1);
}

int main() {
	un[1][2] = un[1][6] = 1; 
	un[2][1] = un[2][3] = un[2][7] = 1;
	un[3][4] = un[3][7] = un[3][2] = 1;
	un[4][3] = un[4][5] = 1;
	un[5][4] = un[5][6] = un[5][7] = 1;
	un[6][5] = un[6][1] = un[6][7] = 1;
	un[7][2] = un[7][3] = un[7][5] = un[7][6] = 1;
	dfs(1);
	cout<<ans;
	return 0;
}

4、分割立方体

lanqiao-1620：分割立方体 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：组合数学、数学思维

$\textcolor{red}{分析：}$

1）正方体和周围3个正方体相邻，总个数3 × 8；

2）正方体和周围4个正方体相邻，总个数4×(n-2)×12；

3）正方体和周围5个正方体相邻，总个数5×6×(n×n -4×n+4)；

4）正方体和周围6个正方体相邻，总个数6 ×(n×n×n - n×n×6+n×12-8)；

最后把这4个情况求和再除以2（因为求的是对数而不是个数）。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 分割立方体——逆向思维，用总共的两两关系减去共有4个公共点的关系数 
using ll = long long;
int n;

int main() {
	cin>>n;
	if(n==1){
		cout<<0;
		return 0;
	}
	ll sum = n*n*n*(n*n*n-1)/2;
	int edge3 = 8;// 与三个小正方体直接邻接的正方体数量（以面邻接而不是边） 
	int ans3 = 3*edge3;
	int edge4 = (n-2)*12;
	int ans4 = 4*edge4;
	int edge5 = 6*(n*n-4*n+4);
	int ans5 = 5*edge5;
	int edge6 = (n*n*n-n*n*6+n*12-8);
	int ans6 = 6*edge6;
	ll ans = ans3+ans4+ans5+ans6;
	cout<<(sum-ans/2);// 除2是因为求的是对数而不是个数 
	return 0;
}

5、挑选子串

lanqiao-1621：挑选子串 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：组合数（无序）、数学思维

$\textcolor{red}{分析：}$

一个个地输入ai，直到输入的数字里，大于m的数够k个，就可以开始统计了。

（1）若正好到k个数，情况总数是：第一个大于m的位置i，乘以i以后的个数，相当于求出了这一段区间的总个数。

（2）大于k个后，怎么求出以后的序列个数而且保证不重复呢？从前往后推理，用倒数第二个位置-倒数第一个位置的差，乘上后面的个数。
（1）与（2）分析没有看懂？？？

解决代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 200050;
int a[N];
long long d[N];
int main(){
        int n,m,k;  scanf("%d %d %d",&n,&m,&k);
        int t=0;
        long long sum=0;
        for(int i=1; i<=n; i++)  {
            scanf("%d",&a[i]);
            if(a[i]>=m){
                d[++t]=i;      //d[]：比m大的数字所在位置
                if(t>=k) {     //首先统计出k个比m大的
                    if(t==k)   sum += d[1]*(n-i+1);// ???
                    else       sum += (d[t-k+1]-d[t-k])*(n-i+1);// ???
                }
            }
        }
        printf("%lld\n",sum);
    return 0;
}

6、糊涂人装信

lanqiao-1622：糊涂人装信 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：组合数（无序）、数学思维

$\textcolor{red}{分析：}$

如果只有1封信完全放错，那么其它n-1封信都没有放错，那么这封放错的信又应该放到什么位置上呢，所以为0种可能；
只有至少2封信完全放错才能够成立， $C_2^2 = 1$ (组合数) 。

解决代码：

#include<bits/stdc++.h>
using namespace std;
// 糊涂人装信
typedef long long ll;
int n;
ll dp[30];

int main() {
	dp[1] = dp[0] = 0;// 如果只有1封信完全放错，那么其它n-1封信都没有放错，那么这封放错的信又应该放到什么位置上呢，所以为0种可能 
	dp[2] = 1;// 只有至少2封信完全放错才能够成立，C_2^2 = 1(组合数) 
	for(int i=3;i<=22;++i){
		dp[i] = (i-1)*(dp[i-1]+dp[i-2]);
	} 
	while(cin>>n)cout<<dp[n]<<endl;
	return 0;
}

7、战斗吧N皇后

lanqiao-1623：战斗吧N皇后 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月7日

tags：组合数（无序）、数学思维

$\textcolor{red}{分析：}$

两个皇后如果能攻击，位于同一行、同一列、同一对角线。
设矩阵为n * m，前2者的可能性是(m+n-2) * n * m。
其他情况请自己思考。

以下代码中的各种请况没有看懂？？？

解决代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n, m;
    while(cin >> n >> m) {
        if(n > m)    swap(n, m);
        if(n == 1){
            cout << m * (m - 1)<<endl;
            continue;
        }
        ll ans = m * n * (m + n - 2);
        ans += 2 * (n - 2) * (n - 1) * (2 * n - 3) / 3;
        ans += 2 * (n - 1) * (n - 2);
        ans += 2 * (m - n + 1) * n * (n - 1);
        cout << ans << endl;
    }
    return 0;
}

Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.