2024牛客寒假算法基础集训营4（视频讲解题目）

视频链接

2024牛客寒假算法基础集训营4（视频讲解题目）

A

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
	int a, b ,k;
	cin >> a >> b >> k;
	if(a >= k * b){
		cout << "good" << endl;
	}else{
		cout << "bad" << endl;
	}
	
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	//cin >> t;
	while(t--)
	solve();
}
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

B

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;

void solve()
{
	int n; cin >> n;
	vector<int>a(n);
	int x = 0;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
		x += (a[i] - 1);
	}
	if(x % 2){
		cout << "gui" << endl;
	}else{
		cout << "sweet" << endl;
	}

}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}
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

C

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> pii;
void solve()
{
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	x -- ,y --;
	vector<string> g(n + 10);
	for(int i = 0; i < n; i ++){
		cin >> g[i];
	}
	int p, q; cin >> p >> q;

	vector<pii>ops(q);
	
	for(int i = 0; i < q; i ++){
		cin >> ops[i].first >> ops[i].second;
	}
	while(p--){
		for(int j = 0; j < q; j ++){
			int op = ops[j].first, z = ops[j].second - 1;
			if(op == 1){
				char s = g[z][m - 1];
				for(int i = m - 1; i >= 1; i --){
					g[z][i] = g[z][i - 1];
				}
				g[z][0] = s;
			}else{
				char s = g[n - 1][z];
				for(int i = n - 1; i >= 1; i --){
					g[i][z] = g[i - 1][z];
				}
				g[0][z] = s;
			}
		}
	}

	cout << g[x][y] << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}
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

D

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;

void solve()
{
	int n; cin >> n;
	vector<int>a(n);
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	if(n == 1){
		cout << 1 << endl;
		return;
	}
	int s = 0;
	for(int i = 0; i < n; i ++){
		s += a[i];
	}
	int ans = 0;
    
	for(int i = 1; i <= s / i; i ++){
		if(s % i){
			continue;
		}
        int a = i, b = s / i;
        if(s / a >= n){
            ans ++;
        }
        if(a != b and s / b >= n){
            ans ++;
        }
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	//cin >> t;
	while(t--)
	solve();
}
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

E

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
#define int long long
using namespace std;

void solve()
{
	int n, k; cin >> n >> k;
	vector<int>a(n + 1), s(n + 1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		s[i] = s[i - 1] + a[i];
	}
	int ans = 0;
	map<int,int>st;
	st[0] = 1;

	for(int i = 1; i <= n; i ++){
		int p = s[i] % k;
		if(st[p]){
			ans += st[p];
			st.clear();
		}
		st[p] ++;
	}

	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	//cin >> t;
	while(t--)
	solve();
}
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

F

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f3f3f3f3f
#define int long long 
using namespace std;
const int N = 1e3 + 10;
int a[N];
int f[N][10], g[N][10], dp[N];
int has[N][N][2];
int cal(int x, int y){
	if(y - x + 1 < 6){
		return 0;
	}

	if(has[x][y - 1][0] != INF and has[x][y - 1][1] != INF){
		int res = max(has[x][y - 1][1], has[x][y - 1][0] - a[y]);
		return res;
	}

	for(int i = x; i <= y + 1; i ++){
		for(int j = 0; j <= 6; j ++){
			f[i][j] = -INF;
			g[i][j] = INF;
		}
	}
	for(int i = x; i <= y; i ++){

		if(i != x)
		{
			f[i][1] = max(f[i - 1][1], a[i]);
			g[i][1] = min(g[i - 1][1], a[i]);
		}
		else
		{
			f[i][1] = a[i];
			g[i][1] = a[i];
		}


		if(i - x + 1 >= 2)
		{
			g[i][2] = min(g[i - 1][2], g[i - 1][1] - a[i]);
			f[i][2] = max(f[i - 1][2], f[i - 1][1] - a[i]);
		}
		else
			continue;

		if(i - x + 1 >= 3){
			if(g[i - 1][2] != INF){
				f[i][3] = max(f[i - 1][3], max(g[i - 1][2] * a[i], f[i - 1][2] * a[i]));
			}else{
				f[i][3] = max(f[i - 1][3], f[i - 1][2] * a[i]);
			}
			if(f[i - 1][2] != -INF)
				g[i][3] = min(g[i - 1][3], min(g[i - 1][2] * a[i], f[i - 1][2] * a[i]));
			else
				g[i][3] = min(g[i - 1][3], g[i - 1][2] * a[i]);
		}else
			continue;
		
		if(i - x + 1 >= 4)
		{
			f[i][4] = max(f[i - 1][4], f[i - 1][3] - a[i]);
			g[i][4] = min(g[i - 1][4], g[i - 1][3] - a[i]);
		}
		else
			continue;

		
		if(i - x + 1 >= 5){
			if(g[i - 1][4] != INF)
				f[i][5] = max(f[i - 1][5], max(g[i - 1][4] * a[i], f[i - 1][4] * a[i]));
			else
				f[i][5] = max(f[i - 1][5], f[i - 1][4] * a[i]);

			if(f[i - 1][4] != -INF)
				g[i][5] = min(g[i - 1][5], min(g[i - 1][4] * a[i], f[i - 1][4] * a[i]));
			else
				g[i][5] = min(g[i - 1][5], g[i - 1][4] * a[i]);
		}else
			continue;

		if(i - x + 1 >= 6)
			f[i][6] = max(f[i - 1][6], f[i - 1][5] - a[i]);

	}
	int res = 0;
	int xx = 0;
	for(int i = x; i <= y; i ++){
		res = max(res, f[i][6]);
		xx = max(xx, f[i][5]);
	}
	has[x][y][1] = res;//选6个数字的最大值
	has[x][y][0] = xx;//选5个数字的最大值
	return res;
}
void solve()
{
	int n; scanf("%lld", & n);
	for(int i = 1; i <= n; i ++){
		scanf("%lld", a + i);
	}

	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++){
				has[i][j][0] = has[i][j][1] = INF;
		}
	}
	
	for(int i = 1; i <= n; i ++){
		dp[i] = dp[i - 1];
		for(int j = 1; j <= i; j ++){
			dp[i] = max(dp[i], dp[j - 1] + cal(j, i));
		}
	}
	printf("%lld", dp[n]);
}

signed main()
{
	int t = 1;
	while(t--)
	solve();
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

G、H（下面是hard版本的代码两个都可以过）

#include
#define endl '\n'
#define deb(x) cout << #x << " = " << x << '\n';
#define INF 0x3f3f3f3f
using namespace std;
const int N = 3e3 + 10;
char g[N][N];
int ul[N][N], ur[N][N], ls[N][N], rs[N][N];

class BIT{
private:
    vector<long long>tre;
    int n;
public:
    BIT(int size): n(size), tre(size + 1, 0) {};

public:
    int lowbit(int x){
        return x & -x;
    }

    void add(int pos, long long x){
        for(int i = pos; i <= n; i += lowbit(i))
            tre[i] = tre[i] + x;
    }

    long long sum(int pos){
        long long res = 0;
        for(int i = pos; i; i -= lowbit(i))
            res = res + tre[i];
        return res;
    }

};
void solve()
{
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		string s; cin >> s;
		for(int j = 1; j <= m; j ++){
			g[i][j] = s[j - 1];
		}
	}

	for(int i = n; i >= 1; i --){
		for(int j = 1; j <= m; j ++){
			if(g[i][j] == '*'){
				ul[i][j] = ul[i + 1][j - 1] + 1;
				ur[i][j] = ur[i + 1][j + 1] + 1;
				ls[i][j] = ls[i][j - 1] + 1;
			}else{
				ul[i][j] = ur[i][j] = ls[i][j] = 0;
			}
		}
		for(int j = m; j >= 1; j --){
			if(g[i][j] == '*'){
				rs[i][j] = rs[i][j + 1] + 1;
			}else{
				rs[i][j] = 0;
			}
		}
	}
	long long ans = 0;
	for(int j = 1; j <= m; j ++){
		BIT t(n);//记录合法点的个数
		vector<vector<int>>del(n + 1);//记录在v这个点需要删除的点。
		for(int i = n; i >= 1; i --){
			
			if(g[i][j] == '*'){
				int v = i - min(ls[i][j], rs[i][j]) + 1;
				if(v >= 1){
					del[v].push_back(i);
				}
				int low = i + min(ul[i][j], ur[i][j]) - 1;
				ans += t.sum(low);
				t.add(i, 1);
			}
			
			for(auto x: del[i]){
				t.add(x, -1);
			}
		}
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while(t--)
	solve();
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97