CF 459D Pashmak and Parmida’s problem

題目鏈接

最近感覺對數據結構題的反應度提升了，這一題是上午看的但是當時旁邊沒電腦，傍晚這會兒可能思路就出現了點偏差，想到了樹狀數組+前綴，應該是能獨立寫出來的一道題

正著反著各跑一遍前綴和，記錄下每個數是第幾次出現，把反著跑的結果存到樹狀數組里，之后遍歷原數組，答案每次加上當前數后方的出現次數比當前數小的個數

#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 = 1e6 + 10;
const int mod = 998244353;
const int maxn = 1e6 + 10;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;int tr[N];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 pos)
{int res = 0;for (int i = pos; i > 0; i -= lowbit(i)) res += tr[i];return res;
}void solve()
{int n, ans = 0;cin >> n;vector<int> a(n);for (int i = 0; i < n; i ++ ) cin >> a[i];map<int, int> mp;vector<int> pre(n), back(n);for (int i = 0; i < n; i ++ ){mp[a[i]] ++ ;pre[i] = mp[a[i]];}mp.clear();for (int i = n - 1; i >= 0; i -- ){mp[a[i]] ++ ;back[i] = mp[a[i]];}for (int i = 0; i < n; i ++ ) add(back[i], 1);for (int i = 0; i < n; i ++ ){add(back[i], -1);ans += query(pre[i] - 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 1388C Uncle Bogdan and Country Happiness

題目鏈接

也是上午看的一道題，思路非常正確，但還是經不住暈遞歸，調了很久，賽時看不到錯誤數據估計要調更久，唉

先dfs算一下每個點有多少人經過，然后再dfs給每個點分配開心的人數，如果有一個點不能分配就no，否則yes

#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 = 1e6 + 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> p(n + 1), h(n + 1);for (int i = 1; i <= n; i ++ ) cin >> p[i];for (int i = 1; i <= n; i ++ ) cin >> h[i];vector<vector<int>> g(n + 1);for (int i = 0; i < n - 1; i ++ ) {int x, y;cin >> x >> y;g[x].push_back(y);g[y].push_back(x);}vector<int> pass(n + 1); // 每個點經過多少人function<void(int, int)> dfs1 = [&](int u, int fa){for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa) continue;dfs1(j, u);pass[u] += pass[j];}pass[u] += p[u];};dfs1(1, -1);function<bool(int, int, int)> dfs2 = [&](int u, int fa, int ha){for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa) continue;if ((h[j] < 0 && h[j] >= -pass[j]) || (h[j] >= 0 && h[j] <= pass[j])){if ((h[j] + pass[j]) % 2 != 0) return false;if ((h[j] + pass[j]) / 2 > min(ha, pass[j]) || (h[j] + pass[j]) / 2 < 0) return false;if (!dfs2(j, u, (h[j] + pass[j]) / 2)) return false;ha -= (h[j] + pass[j]) / 2;}else return false;}return true;};if (h[1] < -m || h[1] > m || (h[1] + m) % 2 != 0) cout << "NO\n";else if (dfs2(1, -1, (h[1] + m) / 2)) cout << "YES\n";else cout << "NO\n";
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

CF 1525D Armchairs

題目鏈接

dp

看到數據范圍就想到dp，甚至連狀態表示都構造出來了還搞不出來轉移方程，真是沒腦子啊

dp[i][j] 表示前 i 個需要變動的位置挪到前 j 個空位需要的最小代價

轉移方程： dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + abs(a[i] - b[j]))

#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 = 1e6 + 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, b;a.push_back(0), b.push_back(0);for (int i = 1; i <= n; i ++ ){int x;cin >> x;if (x) a.push_back(i);else b.push_back(i);}vector<vector<int>> dp(n + 1, vector<int>(n + 1, INF));for (int i = 0; i < b.size(); i ++ ) dp[0][i] = 0;for (int i = 1; i < a.size(); i ++ ){for (int j = 1; j < b.size(); j ++ ){dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1] + abs(a[i] - b[j]));}}cout << dp[a.size() - 1][b.size() - 1] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}

CF 220B Little Elephant and 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;
typedef pair<PII, int> PPI;const int N = 1e6 + 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 size = sqrt(n);int bnum = ceil((double)n / size); // 把序列分成了多少塊vector<int> belong(1e6 + 10);for (int i = 1; i <= bnum; i ++ )for (int j = (i - 1) * size + 1; j <= i * size; j ++ ){belong[j] = i; // 標記每個元素屬于哪個塊}vector<int> a(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i];vector<PPI> q(m);for (int i = 0; i < m; i ++ ){cin >> q[i].first.first >> q[i].first.second;q[i].second = i;}function<bool(PPI a, PPI b)> cmp = [&](PPI a, PPI b){if (belong[a.first.first] != belong[b.first.first]) return belong[a.first.first] < belong[b.first.first];else{if (belong[a.first.first] % 2 == 1) return belong[a.first.second] < belong[b.first.second];else return belong[a.first.second] > belong[b.first.second];}};sort(q.begin(), q.end(), cmp);int l = 1, r = 0, cnt = 0;unordered_map<int, int> mp;vector<int> ans(m);// 添加數function<void(int)> add = [&](int pos){mp[a[pos]] ++ ;if (mp[a[pos]] == a[pos]) cnt ++ ;if (mp[a[pos]] == a[pos] + 1) cnt -- ;};// 刪除數function<void(int)> del = [&](int pos){if (mp[a[pos]] == a[pos]) cnt -- ;if (mp[a[pos]] == a[pos] + 1) cnt ++ ;mp[a[pos]] -- ;};for (int i = 0; i < m; i ++ ){int ql = q[i].first.first, qr = q[i].first.second;while (l < ql) del(l++); // 如左指針在查詢區間左方，左指針向右移直到與查詢區間左端點重合while (l > ql) add(--l); // 如左指針在查詢區間左端點右方，左指針左移while (r < qr) add(++r); // 右指針在查詢區間右端點左方，右指針右移while (r > qr) del(r--); // 否則左移ans[q[i].second] = cnt;}for (int i = 0; i < m; i ++ ) cout << ans[i] << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}