2025-11-21 hetao1733837的刷題記錄
LG14415/LOJ3004 [JOISC 2015] Inheritance
呃……居然tag是二分！我們考慮單調性在哪……發現對於一條邊，若其不為第$K$次操作的邊權（比較小），則不為所有小於$K$操作的刪邊。考慮怎麼$check$，模擬$Kruskal$的過程，通過$K$個並查集進行維護即可。這個思想是真的🐂🍺！
HE一下。
正解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1005, M = 300005, K = 10005;
struct node{
int a, b, c, id;
}e[M];
int fa[K][N], sz[K][N], ans[M];
bool cmp(node x, node y){
return x.c > y.c;
}
int getfa(int k, int x){
return x == fa[k][x] ? x : fa[k][x] = getfa(k, fa[k][x]);
}
void merge(int k, int x, int y){
x = getfa(k, x);
y = getfa(k, y);
if (x == y)
return ;
if (sz[k][x] > sz[k][y])
swap(x, y);
fa[k][x] = y;
sz[k][y] += sz[k][x];
}
int n, m, k;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++){
cin >> e[i].a >> e[i].b >> e[i].c;
e[i].id = i;
}
sort(e + 1, e + m + 1, cmp);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= k; j++){
fa[j][i] = i;
sz[j][i] = 1;
}
}
for (int i = 1; i <= m; i++){
int u = e[i].a, v = e[i].b, w = e[i].c, id = e[i].id;
int l = 1, r = k;
int pos = 0;
while (l <= r){
int mid = (l + r) >> 1;
if (getfa(mid, u) != getfa(mid, v)){
pos = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
ans[id] = pos;
if (pos)
merge(pos, u, v);
}
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
}LG14412/JOI3001 [JOISC 2015] AAQQZ
原題鏈接1：
原題鏈接2：
分析
根本不會，mhh推了兩篇題解，粘在這。
正解
#include <bits/stdc++.h>
using namespace std;
const int N = 3005;
int n, c, a[N], cntl[N], cntr[N], dp[N][N], ans;
int calc(int l, int r, int lim){
for (int i = 0; i <= c; i++)
cntl[i] = cntr[i] = 0;
if (l < 1 || l > n)
return 0;
cntl[a[l]]++;
int L = l, suml = 1, sumr = 0, maxn = 0, cnt = 0;
while (L > 1 && a[L - 1] >= a[L]){
cntl[a[--L]]++;
suml++;
}
int R = a[L];
L = 0;
for (int i = r; i <= n; i++){
cntr[a[i]]++;
if (a[i] < lim)
return maxn;
if (a[i] == lim)
cnt++;
else if (cntr[a[i]] > cntl[a[i]]){
while (R > a[i] && R >= 0){
suml -= cntl[R];
R--;
}
}
else{
while (L <= c && cntl[L] <= cntr[L]){
sumr += cntl[L];
L++;
}
}
int add = (L <= c) ? cntr[L] : 0;
int len = min(sumr + add, suml);
if (len + cnt == i - r + 1 && l >= len && l - len >= 0 && i + 1 <= n + 1)
len += dp[l - len][i + 1];
maxn = max(maxn, 2 * len + cnt);
}
return maxn;
}
void solve(){
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++)
dp[i][j] = 0;
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++){
dp[i][j] = 0;
if (a[i] == a[j])
dp[i][j] = dp[i - 1][j + 1] + 1;
}
}
for (int i = 1; i <= n; i++)
ans = max(ans, 2 * dp[i][i] - 1 + calc(i - dp[i][i], i + dp[i][i], 0));
for (int i = 1; i < n; i++)
ans = max(ans, 2 * dp[i][i + 1] + calc(i - dp[i][i + 1], i + dp[i][i + 1] + 1, 0));
for (int i = 1; i <= n; i++){
int minn = 0;
for (int j = i + 1; j <= n; j++){
if (a[j] < a[i]) {
minn = a[j];
break;
}
}
ans = max(ans, calc(i, i + 1, minn));
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> c;
for (int i = 1; i <= n; i++){
cin >> a[i];
}
solve();
for (int i = 1; i <= n; i++)
a[i] = c - a[i] + 1;
reverse(a + 1, a + n + 1);
solve();
sort(a + 1, a + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++){
if (a[i] != a[i - 1]){
ans = max(ans, sum);
sum = 0;
}
sum++;
}
ans = max(ans, sum);
cout << ans;
return 0;
}LG14413/LOJ [JOISC 2015] Card Game Is Great Fun
分析
14點38分
$DP$是一眼的吧……但是我好像並不會設計狀態和轉移，稍考一會。
14點39分
想到fqh講的一個trick，當時是矩陣長寬連邊，此題我們難道可以花色點數連邊？
那麼，我們會建成一張圖？這不是廢話嗎？咦，$V_i\ge 1$似乎可以貪心的$DP$一下？我在寫什麼？
那，建出圖，我們找最長鏈即可？這不是藍題嗎？
但是，問題在於建圖，這樣是$O(n^2)$難道要運用另一個限制條件——只取第一或第三個？何意味？
14點50分
何意味啊？居然是高維$DP$！
既然限制了只能取第一或第三，那麼，我們就把他計入狀態！
即設$f_{i,j}$表示當前序列的第一個元素位置為$i$，第三個元素位置為$j$。但是，選第三個直接轉移到$f_{i,j+1}$，但是選第一個沒法轉移，不知道$i$和$j$之後選哪個。
那麼，多加一維$k$表示前三個元素怎麼樣？也不太行，因為不知道棧頂牌的具體信息。
那麼，再加一維吧🤮，設$dp_{i,j,k,l}$表示上一次選擇了原序列的第$l$張牌。選第一張即可轉移到$f_{j,k,k+1,i}$，選第三張即可轉移到$f_{i, j, k+1, k}$。顯然，狀態是 $O(n^4)$無法滿足，/(ㄒoㄒ)/~~藍題別搞！
發現$k=max(j,l)$，那不就省略一維了嗎？
直接跑滿！
然後呢，我想説，一些DP題實際上是記憶化搜索的手筆，所以，不會DP時，可以嘗試寫暴力，然後記憶化一下，説不定有客觀的分數！
總結
限制扔進狀態，觀察數據範圍大略估計狀態維數，然後拿下！
正解
何意味，少開個long long卡我快20分鐘，居然報TLE!
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505;
int f[N][N][N];
int c[N], a[N], v[N];
int n;
bool check(int x, int y){
if (!x || !y) //最開始和最結尾隨便選
return true;
if (c[x] == c[y] || a[x] == a[y])
return true;
return false;
}
int dfs(int i, int j, int k, int l){
if (f[i][j][l] != -1){
return f[i][j][l];
}
int ans = 0;
if (i <= n && check(l ,i)){
ans = max(ans, v[i] + dfs(j, k, k + 1, i));
}
if (k <= n && check(l ,k)){
ans = max(ans, v[k] + dfs(i, j, k + 1, k));
}
f[i][j][l] = ans;
return f[i][j][l];
}
int read(){
char c = getchar();
int x = 0, f = 1;
while (c < '0' || c > '9'){
if (c == '-')
f = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
x = x * 10 + (c - '0');
c = getchar();
}
return x * f;
}
signed main(){
n = read();
for (int i = 1; i <= n; i++){
c[i] = read();
a[i] = read();
v[i] = read();
}
memset(f, -1, sizeof(f));
printf("%lld", dfs(1, 2, 3, 0));
}LG3615/LOJ2734 [JOISC 2016] Toilets
分析
記女生為+1，男生為-1，那麼，發現每個男生需要"消耗"一個女生以保證兩個廁所都不為空（$2N$個人$N$個廁所，空依次就得崩）。那麼，轉化為後綴和，當後綴和小於$-1$時，就需要調整，然後喫喫吃，就做完了？何意味。
正解
#include <bits/stdc++.h>
using namespace std;
const int M = 100005;
int m;
long long n, ans = -1, k[M];
string s[M];
int main(){
cin >> n;
cin >> m;
for (int i = 1; i <= m; i++){
cin >> s[i] >> k[i];
reverse(s[i].begin(), s[i].end());
}
long long tmp = 0;
for (int i = m; i >= 1; i--){
long long sum = 0, v = 1e9;
for (int j = 0; j < s[i].length(); j++){
if (s[i][j] == 'F')
sum += 1;
else
sum += -1;
v = min(sum, v);
}
if (sum >= 0){
ans = min(ans, tmp + v);
tmp += sum * k[i];
}
else{
tmp += sum * (k[i] - 1);
ans = min(ans, tmp + v);
tmp += sum;
}
}
ans = -ans - 1LL;
if (tmp < 0)
cout << -1;
else
cout << ans;
}本文章為轉載內容，我們尊重原作者對文章享有的著作權。如有內容錯誤或侵權問題，歡迎原作者聯繫我們進行內容更正或刪除文章。