视频链接

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

A

#include<bits/stdc++.h>
#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();
}

B

#include<bits/stdc++.h>
#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();
}

C

#include<bits/stdc++.h>
#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();
}

D

#include<bits/stdc++.h>
#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();
}

E

#include<bits/stdc++.h>
#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();
}

F

#include<bits/stdc++.h>
#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]);}elsecontinue;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]));elseg[i][3] = min(g[i - 1][3], g[i - 1][2] * a[i]);}elsecontinue;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]);}elsecontinue;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]));elsef[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]));elseg[i][5] = min(g[i - 1][5], g[i - 1][4] * a[i]);}elsecontinue;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();
}

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

#include<bits/stdc++.h>
#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();
}