倒计时68天

题单详情 – 蓝桥云课 (lanqiao.cn)

2.2.串门 – 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int inf = 0x3f3f3f3f;
typedef pair pii;
vectorve[N];
int dis[N];//记录以i为起点走的步数

void dfs(int u, int fa) {
	for (auto[v, w] : ve[u]) {
		if (v == fa)
			continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

void solve() {
	int n, cn = 0;
	cin >> n;
	for (int i = 1; i > v >> u >> w;
		cn += 2 * w;
		ve[v].push_back({u, w});
		ve[u].push_back({v, w});
	}
	dfs(1, 0);
	//遍历，从1到其他边的距离
	int mx = -inf, flag = 1;
	for (int i = 2; i  mx) {
			mx = dis[i];
			flag = i;//求最长的那个边端点对应的编号
		}
	}
	memset(dis, 0, sizeof dis);
	dfs(flag, 0);
	mx = -inf;
	for (int i = 1; i <= n; i++) {
		mx = max(mx, dis[i]);
	}
	cout << cn - mx;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

想到了之前做的一题，好像，，，，，都是树的遍历

E-小红树上染色_牛客周赛 Round 30 (nowcoder.com)

#include
using namespace std;
#define int long long
const int N=2e5+5;
const int inf=0x3f3f3f3f;
vectorve[N];
int mod=1e9+7;
int dp[N][2];
//dp[i][0]:i号节点不染红时,i号结点的子树方案数;
//dp[i][1]:i号结点染红时,i号结点的子树方案数。
void dfs(int x,int fa)
{
    dp[x][0]=1,dp[x][1]=1;
    for(auto i:ve[x])
    {
        if(i==fa)continue;
        dfs(i,x);
//不染红,孩子一定染红,这时候父亲不染红时的方案数即为：目前父亲的方案数乘这个孩子的方案数
        dp[x][0]=dp[x][0]*dp[i][1]%mod;
//染红,孩子可染可不染,就是此时父亲的方案数乘(如果染的方案数加上如果不染的方案数)
        dp[x][1]=dp[x][1]*(dp[i][0]+dp[i][1])%mod;
    }
}
void solve()
{
	int n;
    cin>>n;
    for(int i=1;i>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    dfs(1,0);
    cout<<(dp[1][0]+dp[1][1])%mod;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	solve();
	return 0;
}

3.3.迷宫逃脱【算法赛】 – 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;
#define int long long
const int N = 3e4 + 5;
const int inf = 0x3f3f3f3f;
int w[1100][1100];
int aa[1100][1100][4];
int n, m;

int dfs(int i, int j, int q) {
	if (i == n + 1 || j == m + 1 || q == -1)
		return INT64_MIN;//走到墙外面或钥匙用超了
	if (i == n && j == m)
		return w[i][j];
	if (aa[i][j][q])
		return aa[i][j][q];
	int ma = 0;
	if (__gcd(w[i][j], w[i][j + 1]) == 1)
		ma = 1;
	int a = dfs(i, j + 1, q - ma);
	int mb = 0;
	if (__gcd(w[i][j], w[i + 1][j]) == 1)
		mb = 1;
	int b = dfs(i + 1, j, q - mb);
	int cn = w[i][j] + max(a, b);
	aa[i][j][q] = cn;
	return cn;
}

void solve() {
	int q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j > w[i][j];
		}
	}
	int ans = dfs(1, 1, q);
	ans = ans <= 0 ? -1 : ans;
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

4.5.数组分割 – 蓝桥云课 (lanqiao.cn)

#include
using namespace std;
#define int long long
const int N=3e4+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int counting(int a,int b)
{
  int result=1;
  while(b)
  {
    if(b&1)
    {
      result=(result*a)%mod;
      b/=2;
      a=(a*a)%mod;
    }
    else
    {
      b/=2;
      a=(a*a)%mod;
    }
  }
  return result;
}
void solve()
{
	int t;
  cin>>t;
  while(t--)
  {
    int n,a,odd=0,even=0;
    cin>>n;
    for(int i=0;i>a;
      if(a&1)odd++;//奇数
      else even++;//偶数
    }
    if(odd&1)cout<<0<<endl;
    else
    {
      int sum1=counting(2,odd-1);
      if(odd==0)sum1=1;
      int sum2=counting(2,even);
      cout<<(sum1*sum2)%mod<<endl;
    }
  }
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	solve();
	return 0;
}