[数据结构与算法]蓝桥31天|今天3道题Day27|C++

1.七段数码管

#include <iostream>
using namespace std;
int g[7][7]={
    {1,1,0,0,0,1,0},
    {1,1,1,0,0,0,1},
    {0,1,1,1,0,0,1},
    {0,0,1,1,1,0,0},
    {0,0,0,1,1,1,1},
    {1,0,0,0,1,1,1},
    {0,1,1,0,1,1,1}
};
bool vis[7];//是否点亮
int dfs(int x){
  int cnt=1;
  for(int i=0;i<7;i++){
    if(!vis[i]&&g[x][i]){
      vis[i]=true;
      cnt+=dfs(i);
      vis[i]=false;
    }
  }
  return cnt;
}
int main()
{
  printf("%d",dfs(0)/2);
  return 0;
}

2.区间移位

添加链接描述

开始以为跟扫地机器人差不多，
然后写到check就不会了，看了大佬的解法
思路是用贪心实现区间覆盖

#include <bits/stdc++.h>
using namespace std;
const int maxn = 20000;
int n;
struct node
{
	int a;
	int b;
};
vector<node> reg;
  //从左边开始选，按r排，保证覆盖范围最大
bool cmp(node x,node y)
{
	return x.b<y.b;
}
bool check(int x)
{
	int k = 0;
	vector<node> tmp(reg);
	//可能存在暂时没用到的点所以要一直循环
	while(true)
	{
	//判断能不能找到偏移x就可覆盖的区间，找不到直接返回false
		bool found = false;
		 //对于区间[a,b],可变换范围为[a-x,b+x]
		for(int i=0;i<tmp.size();i++)
		{
			node now = tmp[i];
			int ta = now.a;
			int tb = now.b;
			if(ta-x<=k && tb+x>=k)
			{
				found = true;
				int len = tb-ta;
				if(ta+x>=k) k += len;
				else k = tb+x;
				tmp.erase(tmp.begin()+i);//用过删除
				break;
			}
		}
		if(!found || k>=maxn) break;
	}
	return k>=maxn;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		a *= 2;
		b *= 2;
		reg.push_back({a,b});
	}
	sort(reg.begin(),reg.end(),cmp);
	int l = 0,r = maxn;
	double ans = 0;
	  //对最大移动位移进行二分
	while(l<=r)
	{
		int mid = (l+r)/2;
		if(check(mid))
		{
			r = mid-1;
			ans = mid;
		}
		else
		{
			l = mid+1;
		}
	}
	ans/=2.0;
	cout<<ans<<endl;
	return 0;
}

3.数正方形

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,ans;
int main(){
  cin>>n;
  for (ll i=1;i<n;i++){
    ans=ans+i*(n-i)*(n-i)%mod;
    ans=ans%mod;
  }
  cout<<ans;
  return 0;
}