可以自学做网站吗,免费crm管理系统软件,企业文化标语经典,pc建站网站这几天又忘记每天复习了#xff0c;以后在实验室复习完再回去好了
最近做1800的题目好多dp啊太ex了 文章目录 牛客 练习赛122D 圆CF 1396B Stoned GameCF 1355C Count TrianglesCF 1437C Chef MonocarpCF 271D Good SubstringsCF 1475D Cleaning the PhoneCF 1362D2 Prefix-…这几天又忘记每天复习了以后在实验室复习完再回去好了
最近做1800的题目好多dp啊太ex了 文章目录 牛客 练习赛122D 圆CF 1396B Stoned GameCF 1355C Count TrianglesCF 1437C Chef MonocarpCF 271D Good SubstringsCF 1475D Cleaning the PhoneCF 1362D2 Prefix-Suffix Palindrome (Hard version)CF 722C Destroying Array 牛客 练习赛122D 圆
题目链接
虽然没能自己做出来但是还是挺高兴的首先是因为用到了之前在atc碰到过然后记录下来的一个trick就是把圆拉成一条线弦看作曲线来判断有没有交点然后也自己想到了转换成求区间最大的思路
剩下没想到的点就是要记录下来以每个点结束的弦的起始位置之后更新的时候会用到
#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 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin n m;int sum 0;vectorvectorint w(n 1, vectorint(n 1));vectorsetint eg(n 1);for (int i 0; i m; i ){int a, b, c;cin a b c;sum c;w[min(a, b)][max(a, b)] max(w[min(a, b)][max(a, b)], c);eg[max(a, b)].insert(min(a, b));}vectorvectorint dp(n 1, vectorint(n 1));for (int len 2; len n; len ){for (int l 1; l len - 1 n; l ){int r l len - 1;dp[l][r] max(dp[l][r], dp[l 1][r - 1]);dp[l][r] max({dp[l][r], dp[l 1][r], dp[l][r - 1], dp[l 1][r - 1] w[l][r]});for (auto ver : eg[r]){if (ver l) continue;dp[l][r] max({dp[l][r], dp[l][ver - 1] dp[ver][r]});}}}cout sum - dp[1][n] \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}CF 1396B Stoned Game
题目链接
感觉没有1800 虚高了
优先队列模拟一下每次取能取的最多的就可以
#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 998244353;
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);priority_queuePII q;for (int i 0; i n; i ){cin a[i];q.push({a[i], i});}int idx1 -1, idx2 -1;bool flag true; // true表示T的回合 反之while (q.size()){auto t q.top();q.pop();if (flag){if (t.second idx2){if (q.size() 0){cout HL\n;return;}auto tt q.top();q.pop();q.push(t);idx1 tt.second;tt.first -- ;if (tt.first ! 0) q.push(tt);}else{t.first -- ;idx1 t.second;if (t.first ! 0) q.push(t);}flag false;}else{if (t.second idx1){if (q.size() 0){cout T\n;return;}auto tt q.top();q.pop();q.push(t);idx2 tt.second;tt.first -- ;if (tt.first ! 0) q.push(tt);}else{t.first -- ;idx2 t.second;if (t.first ! 0) q.push(t);}flag true;}}if (flag) cout HL\n;else cout T\n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}CF 1355C Count Triangles
题目链接
组合数学
枚举xy的值因为x最小是ay最小是b所以xy最小是ab同时z最小是c所以xy最小要是c1因此xy的最小值为max(ab, c1)最大值是cb
现在xyi有多少符合条件的z呢z的最大值是d和 i - d 里小的那个最小值是c所以z有min(i - 1, d) - c 1种情况
再看对于每个y有多少个符合条件的x呢
y的取值范围是bc之间所以x的取值范围是[i-c, i-b]同时x还有[a,b]的限制于是x的取值情况min(i - b, b) - max(i - c, a) 1
乘法原理
#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 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int a, b, c, d;cin a b c d;int ans 0;for (int i max(a b, c 1); i c b; i ) // 枚举xy{ans (min(i - 1, d) - c 1) * (min(i - b, b) - max(i - c, a) 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();}
}CF 1437C Chef Monocarp
题目链接
dp
dp[i][j] 表示第 i 盘菜在第 j 时间拿出来的最小值
转移方程dp[i][j] min(dp[i][j - 1], dp[i - 1][j - 1] abs(t[i] - j))
dp真的好难想到啊…
#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 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n;cin n;vectorint t(n 1);for (int i 1; i n; i ) cin t[i];sort(t.begin(), t.end());vectorvectorint dp(n 1, vectorint(2 * n 1, INF));for (int i 0; i 2 * n; i ) dp[0][i] 0;for (int i 1; i n; i ){for (int j 1; j n * 2; j ){dp[i][j] min(dp[i][j - 1], dp[i - 1][j - 1] abs(t[i] - j));}}int ans INF;for (int i 1; i n * 2; i ) ans min(ans, dp[n][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();}
}CF 271D Good Substrings
题目链接
第一次写出来1800的字符串
一开始想单纯枚举左右端点利用前缀和再放到set里判断但是substr的复杂度肯定就爆了
然后想到trie树枚举每个位置为开头把从该位置一直到末尾的字符串存进trie树就可以啦然后在每个符合条件的地方都打上标记最后dfs一下整个树记录ans
#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 2e6 10;
const int mod 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int k;
mapchar, bool mp;
int nxt[N][26], cnt;
bool st[N]; // 该结点结尾的字符串是否存在
int num[N];
int ans 0;
void insert(string s, int l) // 插入字符串l是字符串长度
{ int p 0;for (int i 0; i l; i){int c s[i] - a;if (!nxt[p][c]) nxt[p][c] cnt; // 如果没有就添加结点if (!mp[s[i]]) num[nxt[p][c]] num[p] 1;else num[nxt[p][c]] num[p];p nxt[p][c];if (num[p] k) st[p] true;}
}void dfs(int u)
{if (st[u]) ans ;for (int i 0; i 26; i ){if (!nxt[u][i]) continue;dfs(nxt[u][i]);}
}void solve()
{string s;cin s;for (int i 0; i 26; i ){char c;cin c;if (c 1) mp[(char)(i a)] true;else mp[(char)(i a)] false;}cin k;for (int i 0; i s.size(); i ){string ns s.substr(i, s.size() - i);insert(ns, s.size() - i);}dfs(0);cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}CF 1475D Cleaning the Phone
题目链接
因为看到b只可能为1/2所以肯定是有啥特殊的地方
于是想到把b为1和2的分开算每次枚举在b为1的集合中取了几个肯定是从大到小取二分查找b为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 2e6 10;
const int mod 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin n m;vectorint a(n 1), b(n 1);for (int i 1; i n; i ) cin a[i];for (int i 1; i n; i ) cin b[i];vectorint c1, c2;c1.push_back(0), c2.push_back(0);for (int i 1; i n; i ){if (b[i] 1) c1.push_back(a[i]);else c2.push_back(a[i]);}sort(c1.begin() 1, c1.end(), greaterint());sort(c2.begin() 1, c2.end(), greaterint());vectorint pre1(c1.size()), pre2(c2.size());for (int i 1; i c1.size(); i ) pre1[i] pre1[i - 1] c1[i];for (int i 1; i c2.size(); i ) pre2[i] pre2[i - 1] c2[i];int ans INF;for (int i 0; i c1.size(); i ){int save m - pre1[i];int pos lower_bound(pre2.begin(), pre2.end(), save) - pre2.begin();if (pos c2.size()) continue;ans min(ans, pos * 2 i);}if (ans INF) ans -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();}
}CF 1362D2 Prefix-Suffix Palindrome (Hard version)
题目链接
今天学到的新算法Manacher马拉车算法
这一题只需要先判断原字符串的前缀和后缀有多少对称的如果完全对称直接输出原字符串如果还有剩下的不对称就求剩下的部分中最长前缀/后缀回文子串哪个长要哪个套个板子就可以
#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 2e6 10;
const int mod 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int flag;string Manacher(string s)
{int sl s.size(); // 原字符串长度if (sl 0 || sl 1) return s;// 构建新串string ns $#;for (int i 0; i sl; i ){ns s[i];ns #;}int len ns.size();int c 0; // 最靠右的回文子串的中心点下标int m 0; // 最靠右的回文子串的右端点下标int pos 0; // 最长回文子串的中心点int maxlen 0; // 最长回文子串的半径不包括中心点新字符串中vectorint p(len); // p[i]表示以i为中心点的回文子串的半径包括ifor (int i 1; i len; i ){if (i m) p[i] min(p[c - (i - c)], m - i 1); // c-(i-c)是i关于c的对称点 当前情况表示i在目前最靠右侧的回文子串中else p[i] 1 (ns[i] ! #); // 当前不是#的话 其两侧就是# 所以半径可以加1if (i - p[i] 0 i p[i] ns.size())while (ns[i - p[i]] ns[i p[i]]) p[i] ; // 对半成品的i位置进行中心扩散if (i p[i] - 1 m) // 产生了比以c为中心时更靠右的回文子串{c i;m i p[i] - 1;}if (p[i] i maxlen p[i]){maxlen p[i] - 1;pos i;// flag 1;}if (p[i] i len maxlen p[i]){maxlen p[i] - 1;pos i;// flag 2;}}string ans ;char tmp;for (int i 0; i 2 * maxlen * 1; i ) // 遍历最长字串的每个位置 得出原字符串中的最长字串{tmp ns[pos - (maxlen - 1) i];if (tmp ! #) ans tmp;}return ans;
}void solve()
{string s;cin s;int idx1 0, idx2 s.size() - 1;while (idx1 idx2){if (s[idx1] ! s[idx2]) break;idx1 , idx2 -- ;}if (s[idx1] ! s[idx2]){string ss s.substr(idx1, idx2 - idx1 1);string ans Manacher(ss);string tmp1 s.substr(0, idx1), tmp2 s.substr(idx2 1, s.size() - idx2 - 1);ans tmp1 ans tmp2;cout ans \n;}else cout s \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t -- ){solve();}
}CF 722C Destroying Array
题目链接
没脑子了用线段树写的写完一搜题解原来是并查集
#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 100010;
const int mod 998244353;
const int maxn 1e6 10;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int a[N];struct Node
{int l, r;int maxx, maxl, maxr, sum;
} tr[N * 4];void pushup(Node u, Node l, Node r)
{u.l l.l, u.r r.r;u.maxl l.maxl;if (l.maxl l.sum r.maxl 0) u.maxl r.maxl;u.maxl max(-INF, u.maxl);u.maxr r.maxr;if (r.sum r.maxr l.maxr 0) u.maxr l.maxr;u.maxr max(-INF, u.maxr);u.maxx max({l.maxx, r.maxx, l.maxr r.maxl, -INF});u.sum l.sum r.sum;
}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].maxx tr[u].maxl tr[u].maxr tr[u].sum a[l];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 pos, int x)
{if (tr[u].l pos tr[u].r pos){tr[u].maxx tr[u].maxl tr[u].maxr x;return;}int mid tr[u].l tr[u].r 1;if (pos mid) modify(u 1, pos, x);else modify(u 1 | 1, pos, x);pushup(u);
}void solve()
{int n;cin n;for (int i 1; i n; i ) cin a[i];build(1, 1, n);for (int i 0; i n; i ){int pos;cin pos;modify(1, pos, -INF);cout max((i64)0, tr[1].maxx) \n;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t -- ){solve();}
}
