蓝桥3511

这是一个搜索问题，但是用dfs的话要怎么处理传参问题呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

int T,N;
int a[11][3];
int vis[11];
bool flag = false;
int ans = 0; // 记录当前降落飞机的个数

void dfs(int m,int last) { // m是当前已经降落的飞机的数量，last是最后的时间
	if (m == N) {
		flag = true; return;
	}
	for (int i = 1; i <= N; i++) {
		if (vis[i]) continue;
		if (a[i][0] + a[i][1] >= last) {
			vis[i] = 1;
			dfs(m + 1, max(a[i][0],last) + a[i][2]);    // 这是一个细节
			vis[i] = 0;
		}
	}
}

int main() {
	cin >> T;
	while (T--)
	{
		cin >> N;
		memset(a, 0, sizeof a),memset(vis,0,sizeof vis),flag =false;
		for (int i = 1; i <= N; i++) {
			cin >> a[i][0] >> a[i][1] >> a[i][2];
		}
		dfs(0, 0);
		if (flag) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	return 0;
}

方程 (算法)

image-20240222074914374

用递归的方法做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e9 + 7;
int n, k[5];

int cal(int n)
{
    if (n < 3)
        return k[n];
    else
    {
        if (n % 2)
            return (cal(n / 2) * cal(n / 2 + 1)- k[1])%M ;
        else 
        {
            int tmp = cal(n / 2);
            return (tmp * tmp-2)%M;
        }
    }
}
void solve()
{
    cin >> n >> k[1];
    k[2] = (k[1] * k[1] - 2)%M;
    cout << cal(n) << endl;
}
signed main()
{    
    int t; cin >> t;
    while (t--)
        solve();
    return 0;
}

用类似于矩阵乘法来做 f(n) = kf(n-1)-f(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include<cstring>
using namespace std;
const int p=1e9+7;
typedef long long ll;
void mul(ll c[][2],ll a[][2],ll b[][2]){
  ll temp[2][2]={0};
  for(ll i=0;i<=1;i++)
    for(ll j=0;j<=1;j++)
      for(ll k=0;k<=1;k++)
        temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%p;
  memcpy(c,temp,sizeof temp);
}
void qpow(ll a[2][2],ll b){
  ll res[2][2]={0};
  res[1][1]=res[0][0]=1;
  while(b){
    if(b&1) mul(res,res,a);
    mul(a,a,a);
    b>>=1;
  }
  memcpy(a,res,sizeof res);
}
ll n,t,k;
int main()
{
  // 请在此输入您的代码
  cin>>t;
  while(t--){
    cin>>n>>k;
    ll f1=k;
    ll f2=((k*k-2)%p+p)%p;
    if(n==1){
      cout<<f1<<endl;continue;
    }
    if(n==2){
      cout<<f2<<endl;continue;
    }
    ll a[2][2]={{k,-1},{1,0}};
    qpow(a,n-2);
    ll res=(a[0][0]*f2+a[0][1]*f1)%p;
    cout<<(res+p)%p<<endl;
  }
  return 0;
}

蓝桥3512

image-20240222104913890

要用动态规划做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int f[N];
int l[N], r[N];
int n;
int ans = 0;

int main() {
	string s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		l[i] = s[0], r[i] = s[s.size() - 1];
	}
	for (int i = 0; i < n; i++) {
		f[i] = 1;
		for (int j = 0; j < n; j++) {
			if (r[j] == l[i]) f[i] = max(f[i], f[j] + 1);
		}
		ans = max(ans, f[i]);
	}
	cout << n - ans;
	return 0;
}

但是还是会超时

优化以后的dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
using namespace std;
int dp[10];
int main()
{
    int n;
    cin>>n;
    string s;
    int m=0;
    for(int i=0;i<n;++i)
    {
        cin>>s;
        int x=s[0]-'0',y=s[s.size()-1]-'0';
        dp[y]=max(dp[x]+1,dp[y]);
        m=max(m,dp[y]);
    }
    cout<<n-m<<endl;
    return 0;
}

蓝桥3513

image-20240224151157905

这题要怎么处理子岛屿的问题呢，思考了一下，就是解决子岛屿的问题，感觉就是一个求联通分量的问题

  • 还有一个难点就是如何改进输入呢？
  • 我从(0，0)开始搜索的话，虽然可以解决不访问里面小岛屿的问题，但是会出现一些伪岛屿的问题

可以通过八连通来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N = 55;
int t,n, m;
int p[N][N]; // 存储是海洋还是岛屿
int vis[N][N]; // 岛屿是否访问过
int dx[] = { 0,0,-1,1,-1 ,-1,1,1};
int dy[] = { 1,-1,0,0,-1 ,1,-1,1};
// 我们从下标为 0 开始搜索

int ans = 0;

bool check(int x, int y) {
	if (x<0 || x>m+1 || y<0 || y>n+1) return 0;
	return 1;
}

void dfs(int x,int y) {
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		int xx = x + dx[i], yy = y + dy[i];
		if (p[xx][yy] == 1 && vis[xx][yy] == 0 && check(xx,yy)) {
			dfs(xx, yy);
		}
	}
}

void dfsfirst(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int xx = x + dx[i], yy =y+ dy[i];
		if (check(xx, yy) == 0) continue;
		if (p[xx][yy] == 0 && vis[xx][yy]!=-1) vis[xx][yy]=-1,dfsfirst(xx, yy);
		else if (p[xx][yy] == 1 && vis[xx][yy]==0) {
			ans++;
			dfs(xx, yy);
		}
	}
}


int main() {
	cin >> t;
	while (t--)
	{
		memset(p, 0, sizeof p), memset(vis, 0, sizeof vis),ans=0;
		cin >> m >> n;
		string s;
		for (int i = 1; i <= m; i++) {
			cin >> s;
			for (int j = 1; j <= n; j++) {
				p[i][j] = s[j-1]-'0';
			}
		}
		dfsfirst(0, 0);
		cout << ans << endl;
	}
}

用bfs改写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

const int N = 55;
int t,n, m;
int p[N][N]; // 存储是海洋还是岛屿
int vis[N][N]; // 岛屿是否访问过
int dx[] = { 0,0,-1,1,-1 ,-1,1,1};
int dy[] = { 1,-1,0,0,-1 ,1,-1,1};
// 我们从下标为 0 开始搜索

int ans = 0;

bool check(int x, int y) {
	if (x<0 || x>m+1 || y<0 || y>n+1) return 0;
	return 1;
}

void bfs(int x,int y) {
	queue<pair<int, int>> q;
	q.push({ x,y });
	vis[x][y] = 1;
	while (q.size())
	{
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (check(xx, yy) == 0) continue;
			if (p[xx][yy] == 1 && vis[xx][yy] == 0) {
				vis[xx][yy] = 1;
				q.push({ xx,yy });
			}
		}
	}
}

void bfsfirst() {
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	while (q.size())
	{
		int x = q.front().first, y = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			int xx = x + dx[i], yy = y + dy[i];
			if (check(xx, yy) == 0) continue;
			if (p[xx][yy] == 0 && vis[xx][yy] != -1)  vis[xx][yy] = -1, q.push({ xx,yy });
			else if (p[xx][yy] == 1 && vis[xx][yy] == 0) ans++,bfs(xx, yy);
		}
	}
}


int main() {
	cin >> t;
	while (t--)
	{
		memset(p, 0, sizeof p), memset(vis, 0, sizeof vis),ans=0;
		cin >> m >> n;
		string s;
		for (int i = 1; i <= m; i++) {
			cin >> s;
			for (int j = 1; j <= n; j++) {
				p[i][j] = s[j-1]-'0';
			}
		}
		bfsfirst();
		cout << ans << endl;
	}
}

蓝桥3515

image-20240226151848529

如何分析这种问题

暴力算法肯定会超时，虽然可以找到

[RC-04] 01 背包

有一个容积为 $+\infty $ 的背包，你要往里面放物品。

你有 $n$ 个物品，第 $i$ 个体积为 $a_i$。

你有一个幸运数字 $p$，若放入的物品体积和为 $k$，你会得到 $p^k$ 的收益。特别地，$0^0=1$。

求所有 $2^n$ 种放入物品的方案的收益和。答案很大，因此请输出它对 $998244353$ 取模的值。

输入格式

第一行两个整数 $n,p$。

接下来一行 $n$ 个正整数 $a_1\sim a_n$，描述这 $n$ 个物品的体积。

输出格式

输出一个整数，为所有 $2^n$ 种方案的收益和对 $998244353$ 取模的值。

样例 #1

样例输入 #1

1
2
2 2
1 4

样例输出 #1

1
51

提示

【样例解释】

答案为 $2^0+2^1+2^4+2^5=51$。

【数据范围】

对于所有数据，$1\le n\le 10^6$，$0\le p,a_i<998244353$。

详细数据范围如下表：

测试点编号 $n$ $p$ $\sum_{i=1}^na_i$ 每测试点分数
$1$ $=0$ $2$
$2\sim 5$ $\le 22$ $6$
$6\sim 9$ $\le 1000$ $\le 1000$ $6$
$10\sim 14$ $\le 100000$ $\le 100000$ $5$
$15$ $25$

首先我采用了搜索的方法去写，但是这样肯定会超时的

这是我的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
int storage[1000005];
int n, p;

const int mod = 998244353;
long long ans = 0;

void dfs(int i,long long sum) {
	if (i > n) {
		ans = (ans + (long long)pow(p,sum)) % mod;
		return;
	}
	sum = (sum+storage[i])%mod;
	dfs(i + 1, sum);
	sum = (mod + sum - storage[i]) % mod;
	dfs(i + 1, sum);  //别忘记了
}

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i++) {
		cin >> storage[i];
	}
	dfs(1, 0);
	cout << ans;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, p;

const int mod = 998244353;
long long ans = 1;

ll mul(ll x,ll u) {
	x %= mod;
	ll temp = 1;
	while (x)
	{
		if (x & 1) {
			temp = (temp * u) % mod;
		}
		u = (u * u) % mod;  // 这个不在判断内
		x >>= 1;
	}
	return (temp+1) % mod;
}

int main() {
	cin >> n >> p;
	int y;
	for (int i = 1; i <= n; i++) {
		cin >> y;
		ans = ans * (mul(y, p))%mod;
	}
	cout << ans;
	return 0;
}