2024.3.3 訓練記錄（7）

這幾天又忘記每天復習了，以后在實驗室復習完再回去好了

最近做1800的題目好多dp啊太ex了

文章目錄

牛客練習賽122D 圓
CF 1396B Stoned Game
CF 1355C Count Triangles
CF 1437C Chef Monocarp
CF 271D Good Substrings
CF 1475D Cleaning the Phone
CF 1362D2 Prefix-Suffix Palindrome (Hard version)
CF 722C Destroying Array

牛客練習賽122D 圓

題目鏈接

雖然沒能自己做出來但是還是挺高興的，首先是因為用到了之前在atc碰到過然后記錄下來的一個trick，就是把圓拉成一條線，弦看作曲線來判斷有沒有交點，然后也自己想到了轉換成求區間最大的思路

剩下沒想到的點就是：要記錄下來以每個點結束的弦的起始位置，之后更新的時候會用到

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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;vector<vector<int>> w(n + 1, vector<int>(n + 1));vector<set<int>> 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));}vector<vector<int>> dp(n + 1, vector<int>(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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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;vector<int> a(n);priority_queue<PII> 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

題目鏈接

組合數學

枚舉x+y的值，因為x最小是a，y最小是b，所以x+y最小是a+b，同時z最小是c，所以x+y最小要是c+1，因此x+y的最小值為max(a+b, c+1)，最大值是c+b

現在x+y=i，有多少符合條件的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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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 ++ ) // 枚舉x+y{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[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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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;vector<int> t(n + 1);for (int i = 1; i <= n; i ++ ) cin >> t[i];sort(t.begin(), t.end());vector<vector<int>> dp(n + 1, vector<int>(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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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;
map<char, 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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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;vector<int> 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];vector<int> 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(), greater<int>());sort(c2.begin() + 1, c2.end(), greater<int>());vector<int> 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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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; // 最長回文子串的半徑（不包括中心點）（新字符串中）vector<int> p(len); // p[i]表示以i為中心點的回文子串的半徑（包括i）for (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++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, 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();}
}