教育培训学校网站建设策划,泰安做网站建设的公司,网站快照,平面设计每天的题目总结在一起#xff0c;睡觉之前一定要再看一遍复习一下思路尽快恢复状态#xff0c;计划是先把前几场没补的牛客补一下#xff0c;然后开始刷洛谷 文章目录 牛客 寒假集训4F 来点每日一题牛客 寒假集训4H 数三角形#xff08;hard#xff09;牛客 寒假集训4K 方…每天的题目总结在一起睡觉之前一定要再看一遍复习一下思路尽快恢复状态计划是先把前几场没补的牛客补一下然后开始刷洛谷 文章目录 牛客 寒假集训4F 来点每日一题牛客 寒假集训4H 数三角形hard牛客 寒假集训4K 方块掉落牛客 寒假集训5B tomorin的字符串迷茫值牛客 寒假集训5E soyorin的数组操作easy牛客 寒假集训5F soyorin的数组操作hard牛客 寒假集训5J rikki的数组陡峭值 牛客 寒假集训4F 来点每日一题
题目链接
这题首先要想到 dp
可以选很多六个数的情况比较复杂我们首先考虑只能选六个数的情况
二维dp使用 dp[i][j] 表示在前 i 个数里选已经选了 j 个数的最大值转移的时候要不然就是前 i - 1 个数的最优情况要不然就是前 i - 1 里选 j - 1 个数把第 i 个数当做最后一个被选择的数的最优情况
解决了只能选六个数的问题再回头看原题因为能选很多个六个所以由这里想到区间处理maxx[i][j][k] 表示 [i, j] 中选了 k 个的最大值minn[i][j][k] 表示 [i, j] 中选了 k 个的最小值为什么要记录下最小值因为有乘法负负也能得正之后 dp[i] 表示前 i 个数中的最佳答案
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 10;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint a(n 1);for (int i 1; i n; i ) cin a[i];vectorvectorvectorint maxx(n 1, vectorvectorint(n 1, vectorint(7, -INF))), minn(n 1, vectorvectorint(n 1, vectorint(7, INF)));vectorint dp(n 1);for (int i 1; i n; i ){for (int j i; j n; j ){maxx[i][j][1] max(maxx[i][j - 1][1], a[j]);if (j - i 1 1) maxx[i][j][2] max(maxx[i][j - 1][2], maxx[i][j - 1][1] - a[j]);if (j - i 1 2) maxx[i][j][3] max({maxx[i][j - 1][3], maxx[i][j - 1][2] * a[j], minn[i][j - 1][2] * a[j]});if (j - i 1 3) maxx[i][j][4] max(maxx[i][j - 1][4], maxx[i][j - 1][3] - a[j]);if (j - i 1 4) maxx[i][j][5] max({maxx[i][j - 1][5], maxx[i][j - 1][4] * a[j], minn[i][j - 1][4] * a[j]});if (j - i 1 5) maxx[i][j][6] max(maxx[i][j - 1][6], maxx[i][j - 1][5] - a[j]);minn[i][j][1] min(minn[i][j - 1][1], a[j]);if (j - i 1 1) minn[i][j][2] min(minn[i][j - 1][2], minn[i][j - 1][1] - a[j]);if (j - i 1 2) minn[i][j][3] min({minn[i][j - 1][3], minn[i][j - 1][2] * a[j], maxx[i][j - 1][2] * a[j]});if (j - i 1 3) minn[i][j][4] min(minn[i][j - 1][4], minn[i][j - 1][3] - a[j]);if (j - i 1 4) minn[i][j][5] min({minn[i][j - 1][5], minn[i][j - 1][4] * a[j], maxx[i][j - 1][4] * a[j]});if (j - i 1 5) minn[i][j][6] min(minn[i][j - 1][6], minn[i][j - 1][5] - a[j]);}}for (int i 1; i n; i ){for (int j 0; j i; j ){if (i - j 6) dp[i] max(dp[i], dp[j]);else dp[i] max(dp[i], dp[j] maxx[j 1][i][6]);}}cout dp[n] \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}牛客 寒假集训4H 数三角形hard
题目链接
这一题没做出来不太应该debug的时候发现问题了但是没有想到解决办法现在看来就是树状数组不太熟悉区间求和思路被前缀和锁死了
大体思路就是枚举每个点为三角形顶点和底边中点顶点时候更新答案底边中点的时候在树状数组中加上该点的贡献还要另外开一个数组v来记录这个点为底边中点的时候最高对哪一行产生影响那一行计算完之后要消去这个影响
#include bits/stdc.husing namespace std;// #define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 3010;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
// const int INF 0x3f3f3f3f3f3f3f3f;int n, m;
vectorint tr;int lowbit(int x)
{return x -x;
}void add(int pos, int x)
{for (int i pos; i n; i lowbit(i)){tr[i] x;}
}int query(int x)
{int res 0;for (; x 0; x - lowbit(x)){res tr[x];}return res;
}void solve()
{cin n m;vectorstring g(n 2);for (int i 1; i n; i ){string s;cin s;s s ;g[i] s;}vectorvectorint l(n 2, vectorint(m 2));vectorvectorint r(n 1, vectorint(m 2));for (int i 1; i n; i ){for (int j 1; j m; j ){if (g[i][j] *) l[i][j] l[i][j - 1] 1;else l[i][j] 0;}for (int j m; j 0; j -- ){if (g[i][j] *) r[i][j] r[i][j 1] 1;else r[i][j] 0;}}vectorvectorint lx(n 2, vectorint(m 2)), rx(n 2, vectorint(m 2));for (int i n; i 0; i -- ){for (int j 1; j m; j ){if (g[i][j] *){lx[i][j] lx[i 1][j - 1] 1;rx[i][j] rx[i 1][j 1] 1;}else lx[i][j] 0, rx[i][j] 0;}}i64 ans 0;for (int j 1; j m; j ){tr vectorint(n 2);vectorvectorint v(n 2);for (int i n; i 0; i -- ){if (g[i][j] .){for (auto t : v[i]) add(t, -1);continue;}// 顶点int num min(lx[i][j], rx[i][j]);if (num 2) ans query(i num - 1) - query(i);// 底边中点num min(l[i][j], r[i][j]);if (num 1){add(i, 1);int lim i - num 1;lim max(lim, 0);v[lim].push_back(i);}for (auto t : v[i]) add(t, -1);}}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}牛客 寒假集训4K 方块掉落
题目链接
果然一复杂就不会写线段树了只能看出来是线段树但是pushup根本不知道怎么写
struct Node
{int l, r; // 区间端点int sum; // 方块总数int sum_red; // 红色方块总数int lb; // 第一个蓝色方块左边有多少红色方块int rb; // 最后一个蓝色方块右边有多少方块bool eb; // 是否有蓝色方块
} tr[N * 4];应该怎么想到这个结点信息的定义呢
首先端点和方块总数不用说了想一想方块数的翻倍变化都来自于红色所以要对红色特殊注意合并的时候右边结点不收红方块的影响因为已经计算过了收到影响的就是左边结点中在最后一个蓝色方块右边的所有方块所以我们要记录最后一个蓝色方块右边有多少方块而影响它们的是右边结点中第一个蓝色方块左边所有的红色方块所以我们要记录第一个蓝色方块左边有多少红色方块更新这个信息的时候需要用到红色方块总数和是否存在蓝色方块所以记录这两个信息
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 200010;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;string s;
int p[N];struct Node
{int l, r; // 区间端点int sum; // 方块总数int sum_red; // 红色方块总数int lb; // 第一个蓝色方块左边有多少红色方块int rb; // 最后一个蓝色方块右边有多少方块bool eb; // 是否有蓝色方块
} tr[N * 4];void pushup(Node u, Node l, Node r)
{u.sum (1ll * l.rb * p[r.lb] l.sum - l.rb r.sum) % mod;u.sum_red (l.sum_red r.sum_red) % mod;if (l.eb) u.lb l.lb;else if (r.eb) u.lb (l.sum_red r.lb) % mod;else u.lb (l.sum_red r.sum_red) % mod;if (r.eb) u.rb r.rb;else if (l.eb) u.rb (1ll * l.rb * p[r.lb] % mod r.sum) % mod;else u.rb u.sum;u.eb l.eb | r.eb;
}void pushup(int u)
{pushup(tr[u], tr[u 1], tr[u 1 | 1]);
}void build(int u, int l, int r)
{tr[u] {l, r};if (l r){tr[u].sum tr[u].rb 1;if (s[l] R) tr[u].sum_red tr[u].lb 1;if (s[l] B) tr[u].eb true;return;}int mid l r 1;build(u 1, l, mid), build(u 1 | 1, mid 1, r);pushup(u);
}void modify(int u, int x, char c)
{if (tr[u].l x tr[u].r x){tr[u].lb tr[u].eb tr[u].sum_red 0;if (c B) tr[u].eb true;if (c R) tr[u].lb tr[u].sum_red 1;return;}int mid tr[u].l tr[u].r 1;if (x mid) modify(u 1, x, c);else modify(u 1 | 1, x, c);pushup(u);
}Node query(int u, int l, int r)
{if (tr[u].l l tr[u].r r) return tr[u];int mid tr[u].l tr[u].r 1;if (r mid) return query(u 1, l, r);else if (l mid) return query(u 1 | 1, l, r);else{Node res;auto left query(u 1, l, mid);auto right query(u 1 | 1, mid 1, r);pushup(res, left, right);return res;}
}void solve()
{int n, q;cin n q;p[0] 1;for (int i 1; i n; i ) p[i] p[i - 1] * 2 % mod;cin s;s s;build(1, 1, n);while (q -- ){int op;cin op;if (op 1){int p;char c;cin p c;modify(1, p, c);}else{int l, r;cin l r;auto res query(1, l, r);cout res.sum % mod \n;}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}牛客 寒假集训5B tomorin的字符串迷茫值
题目链接
要比想象中简单很多对于目标字符串mygo因为不能删连续的两个字符所以只有这些删除方式mygo, m_ygo, my_go, myg_o, m_y_go, m_yg_o, my_g_o, m_y_g_o只需要在原来的字符串中枚举是否出现过这些子串即可暴力枚举就可只要出现过当前情况的方案数就是左右两边的字符串方案数相乘所以我们先预处理出长度为i的字符串有多少种删除方案dp即可dp[i] dp[i - 1] dp[i - 2]
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 10;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{string s;cin s;int n s.size();s s enfikojlrnvol;vectorint cnt(n 1);cnt[0] 1, cnt[1] 2;for (int i 2; i n; i ) cnt[i] (cnt[i - 1] cnt[i - 2]) % mod;vectorstring v {mygo, m_ygo, my_go, myg_o, m_y_go, m_yg_o, my_g_o, m_y_g_o};auto check [](string s1, string s2){for (int i 0; i s1.size(); i ){if (s1[i] s2[i]) continue;else if (s1[i] _) continue;else return false;}return true;};int sum 0;for (int i 1; i n; i ){for (auto t : v){auto j s.substr(i, t.size());if (check(t, j)){sum (sum cnt[i - 1] * cnt[n - (i t.size() - 1)]) % mod;}}}cout sum \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}牛客 寒假集训5E soyorin的数组操作easy
题目链接
偶数是一定满足情况的只需要判定奇数
我们可以计算出每一个偶数位最多能进行多少次操作进行最多次操作判断即可
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 10;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint a(n 1);for (int i 1; i n; i ) cin a[i];if (n % 2 0){cout YES\n;return;}int op 0;for (int i n - 1; i 1; i - 2){if (a[i] op * i a[i 1]){cout NO\n;return;}a[i] op * i;a[i - 1] op * (i - 1);int diff a[i 1] - a[i];int cnt diff / i;op cnt;a[i] cnt * i;a[i - 1] cnt * (i - 1);if (a[i] a[i - 1]){cout NO\n;return;}}cout YES\n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}牛客 寒假集训5F soyorin的数组操作hard
题目链接
利用E题代码判断能否实现如果能实现的话答案就是相邻两数最大差值
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 10;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint a(n 1);for (int i 1; i n; i ) cin a[i];int ans 0;if (n % 2 0){for (int i n - 1; i 1; i -- ){if (a[i] a[i 1]) ans max(ans, a[i] - a[i 1]);}}else{for (int i n - 1; i 1; i -- ){if (a[i] a[i 1]) ans max(ans, a[i] - a[i 1]);}int op 0;for (int i n - 1; i 1; i - 2){if (a[i] op * i a[i 1]){cout -1\n;return;}a[i] op * i;a[i - 1] op * (i - 1);int diff a[i 1] - a[i];int cnt diff / i;op cnt;a[i] cnt * i;a[i - 1] cnt * (i - 1);if (a[i] a[i - 1]){cout -1\n;return;}}}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}牛客 寒假集训5J rikki的数组陡峭值
题目链接
贪心每次取最优记录一下可以取的左右端点
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;const int N 10;
const int mod 1e9 7;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint l(n), r(n);for (int i 0; i n; i ) cin l[i] r[i];int ltl l[0], ltr r[0];int ans 0;for (int i 1; i n; i ){if (ltl r[i] ltr l[i]){ltl max(ltl, l[i]);ltr min(ltr, r[i]);}else if (ltr l[i] ltl r[i]){ltl max(ltl, l[i]);ltr min(ltr, r[i]);}else{if (r[i] ltl){ans abs(r[i] - ltl);ltl r[i];ltr r[i];}else if (l[i] ltr){ans abs(l[i] - ltr);ltl l[i];ltr l[i];}}}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}
