2025.8.3.模擬賽總結

原題戳我

T1

靈感這種東西，真的是聽玄幻的（霧）

題目不難，就簡單寫寫我做題時候的腦路歷程吧

最開始是讀題讀錯了，以為是每次是插入到當前排名為第ei的小朋友后面，然后就自然而然想到直接是拿最大值減去最小值就有答案了......當然沒有這么美好

結果打開一大樣例一對了一下，誒，不對！

重新讀了一遍題目之后，又想到說，我每次插入的時候都當前把最小值擴展到它左右兩個小朋友的值之中的較小值去，再把本次更新的值加到 ans 中，等到整個環都是一個數為止就行了

這次的思路邏輯是對的，但敲出來之后每次輸入一個新小朋友的時候代碼都會把這個流程又走一遍，結果就是只拿了40分，剩下點全都TLE了（）

（說起來好像題目讀取得有點問題有個特殊性質沒讀出來，不過問題不大）

鑒于我 拿到分就行了別糾結滿分 的不當思想，拿完四十分之后就跑去做后面的題了（）

~~結果發現自己剩下三道題根本做不出來只能騙分......~~

于是又回來研究第一題了(笑)

再好好看題，既然每次插入小朋友都會更新答案的值，那我們能不能根據之前已經計算好的值來動態維護答案呢？

當然可以

模擬一下，開始時只有1號節點，環中只有一個自環

對于每個新加入的節點，將其插入到指定節點的后面

刪除舊邊：移除插入位置原有的邊（即插入節點與其后繼節點之間的邊）

添加新邊：添加插入節點與前后節點之間的兩條新邊

根據刪除和添加的邊的差值......好像不對啊怎么還帶負數玩的？

欸，然后我就突然想到昨天我做的一道題用到的一個概念：絕對值

重新來一遍

初始化環：開始時只有1號節點，環中只有一個自環，相鄰節點差值的絕對值之和為0

插入新節點：對于每個新加入的節點，將其插入到指定節點的后面

更新差值總和：根據刪除和添加的邊的差值，更新環上相鄰節點差值的絕對值總和

接著就又卡住了......

好像求出來的值跟答案......相差甚遠啊......嗎？

欸，大樣例里頭 678 903 407 824 300 (為了方便直接按照順序把鏈排好了)的標準輸出是 1020 ，我們用以上流程來一輪算出來的是 2040 ，兩倍欸！

會不會答案就是我們剛剛所求的值/2？

驗證一下......好像確實是這么回事啊！

最終在考場上，我在并未完全參透原理的情況下把代碼給敲了出來

然后吃中午飯的時候研究了一下，其實就是利用了環的性質：
變量 $S$ 維護的是當前圈中所有有向邊的計數器值差的絕對值之和
具體來說：
對于圈中的每個小朋友 i，計算 $|a[i] - a[nxt[i]]|$（即當前小朋友計數器值與下一個小朋友計數器值的絕對差）
S 是所有這樣的絕對值之和：$S = \sum_{i=1}^{k} |a_i - a_nxt[i]|$
其中 k 是當前圈中的小朋友數量（從 2 開始逐步增加）
而在環形結構中，每條邊都被計算兩次（物理上相鄰的一對節點在環中形成兩條有向邊）
例如兩個節點時：$S = |a_1-a_2| + |a_2-a_1| = 2 \times |a_1-a_2|$
輸出 $S/2 = |a_1-a_2|$ 即為答案
每次按按鈕操作會使一個連通塊的值整體 +1
最優策略：總是操作當前圈中的"低谷"（計數器值小于等于相鄰節點的連通塊）
每次這樣的操作會使總差值 $S$ 減少 2：減少與左側鄰居的差值 1 和減少與右側鄰居的差值 1
模擬一下，當加入新小朋友 i 時：
S-=llabs(a[y]-a[z]);  // 刪除原有邊 y→z 的貢獻
S+=llabs(a[y]-a[i]);  // 增加新邊 y→i 的貢獻
S+=llabs(a[i]-a[z]);  // 增加新邊 i→z 的貢獻
這等價于：
移除原有邊 $y \rightarrow z$ 的差值 $|a_y-a_z|$
新增兩條邊：
$y \rightarrow i$ 的差值 $|a_y-a_i|$
$i \rightarrow z$ 的差值 $|a_i-a_z|$
此時當前圈的總差值和 $S$ 恰好包含所有相鄰節點對的差值（每個物理相鄰對通過兩條有向邊表示）
所以 $S/2$ 就是當前狀態下使所有相鄰節點值相同的最少操作次數

注意，還有一個坑點！

這題數據又大又多，別用 cin 和 cout ！

代碼流程總結

用循環鏈表動態維護小朋友的圈，每次加入新小朋友時：

讀入插入位置 pos

定位 y = pos 和 z = nxt[y]

更新 S：移除 y-z 邊的貢獻，添加 y-i 和 i-z 邊的貢獻

更新鏈表：在 y 和 z 之間插入 i

輸出 S/2 作為當前狀態的最少按鈕次數

代碼實現

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000005;
ll a[MAXN];
int nxt[MAXN];
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    nxt[1]=1;
    ll S=0;
    for(int i=2;i<=n;i++)
    {
        int pos;
        scanf("%d",&pos);
        int y=pos;
        int z=nxt[y];
        S-=llabs(a[y]-a[z]);
        S+=llabs(a[y]-a[i]);
        S+=llabs(a[i]-a[z]);
        nxt[y]=i;
        nxt[i]=z;
        printf("%lld\n",S/2);
    }
	//fclose(stdin);
	//fclose(stdout);
    return 0;
}

T2

看到題目的第一眼首先想到的是背包，但是再看幾眼就能發現他這種又買又發的模型其實跟背包沒什么關系

接下來的第二個想法是動態規劃，但他那個容量其實不太好決策，直覺告訴我這應該不是正解

~~(雖然dp好像確實能做出來)~~

第三個想法就是貪心了，答案也確實是貪心

但......沒敲出來......

主要是想的時候的決策有問題，對于他的容量 V 沒處理好決策......死活沒想到單調隊列我這豬腦QAQ

~~（其實這題要是沒有容量限制頂天就是個橙題）~~

想了半天沒個結果之后就沒再消耗腦細胞了，盯緊那十分的特殊情況一，分類討論n=1和n=2的情況，騙了 10 分后又給剩下情況敲了個隨機數就跳下一題了

提一嘴，想用隨機數這東西來騙分真的是太困難了......就當是心理安慰吧

代碼流程總結

其實對于這道題的貪心，用單調隊列來維護是比較好的辦法

我們按照時間從前往后一天一天來考慮

對于第 $ i $ 天的需求，應該是在之前找一天 $ j < i $，滿足從第 $ j $ 天到第 $ i $ 天，冰棍還有剩余容量，并且 $ P_j + (i - j) \times m $ 最小

在掃描過程中，使用單調隊列，維護 $ P_j - j \times m $ 的最小值——如果 $ P_{j+1} - (j + 1) \times m \leq P_j - j \times m $，則在 $ j + 1 $ 天之后不可能從第 $ j $ 天購買冰棍——這組數據具有單調性

隊列維護：
- 移除不滿足冰箱容量的決策點
- 隊首元素即為當前最優購買決策
標記更新：
- 購買完成后，隊列中所有決策的剩余容量減少
- 通過全局標記記錄容量減少量

代碼實現

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2000010;
ll D[MAXN],P[MAXN],R[MAXN],Q[MAXN];
int main()
{
    //freopen("ice.in","r",stdin);
    //freopen("ice.out","w",stdout);
    ll n,m,V;
    scanf("%lld%lld%lld",&n,&m,&V);
    for(int i=1;i<=n;i++)
        scanf("%lld",&D[i]);
    for(int i=1;i<=n;i++)
        scanf("%lld",&P[i]);
    int l=1,r=0;
    ll tag=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        while(l<=r&&P[Q[r]]-m*Q[r]>=P[i]-m*i)
            r--;
        while(D[i]&&l<=r)
        {
            ll w=min(D[i],R[Q[l]]-tag);
            ans+=w*(P[Q[l]]+m*(i-Q[l]));
            tag+=w;
            D[i]-=w;
            if(R[Q[l]]-tag==0)
                l++;
        }
        if(D[i])
            ans+=D[i]*P[i];
        Q[++r]=i;
        R[i]=V+tag;
    }
    printf("%lld\n",ans);
    //fclose(stdin);
	//fclose(stdout);
    return 0;
}

T3

做的時候在想，是不是我可以走個dp來維護這么一組“最短路”

然后發現自己整出來一個四維的超絕狀態轉換方程

~~而且測試點全WA~~

然后就跳過這題去坐T4了......完全做不出來......回去做T1了（）

做完T1、騙完T2的分之后，我決定也騙點這題的分

觀察特殊性質，欸，有一組是所有$y[i]$都為1啊，那分不就好騙了嗎？

于是開開心心第拿了 10 分，耶

而題目正解其實是有點思維深度的......

首先注意到一個特殊性質：$y[i]=1$
容易想到，該特殊性質的最優策略就是從小往大依次檢查所有倉庫，答案為坐標的極差
而對于其它的數據，當出現 $y[i]=2$ 的時候，答案肯定不比 $y[i]=1$ 的情況小，這樣我們得到了一個答案的下界
此外，我們還能發現一個答案的上界，就是坐標極差的兩倍
why? 因為我們從最左側的倉庫出發走到最右側，再回到最左側，一定能夠檢查完所有的倉庫
那么，有什么其它方案會位于這個上界和下界之間呢？
我們整體的趨勢還是從左走到右，但是在走的過程中，會有一些小的折返，形如:

也就是說，可以把整個路徑分為一段一段的，每一段要么直接走過去，要么做一次折返
然后我們用DP來求解，表示考慮完了前個關卡的答案，轉移就是枚舉接下來一段是直接走過去，還是做一次折返
可以用前綴最大值把DP優化到線性

代碼實現

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
struct Node 
{
    long long x;
    int y;
    int k;
} info[MAXN];
int main()
{
    freopen("warehouse.in", "r", stdin);
    freopen("warehouse.out", "w", stdout);
    int n;
    cin>>n;
    long long min_x_all = LLONG_MAX, max_x_all = LLONG_MIN;
    for (int i=1; i<=n; i++) 
    {
        cin>>info[i].x;
        if (info[i].x < min_x_all) 
            min_x_all = info[i].x;
        if (info[i].x > max_x_all) 
            max_x_all = info[i].x;
        cin>>info[i].y;
        if (info[i].y==2)
            cin>>info[i].k;
        else 
            info[i].k = -1;
    }
    vector<long long> type1_x;
    map<long long, long long> minLeftMap;
    for (int i=1; i<=n; i++) 
    {
        if (info[i].y==1) 
            type1_x.push_back(info[i].x);
        else 
        {
          if (info[i].y==2) 
          {
            int k = info[i].k;
            long long key_x = info[k].x;
            long long cur_x = info[i].x;
            if (cur_x < key_x) 
            {
                if (minLeftMap.find(key_x)==minLeftMap.end()) 
                    minLeftMap[key_x] = cur_x;
                else
                    if (cur_x < minLeftMap[key_x]) 
                        minLeftMap[key_x] = cur_x;
            }
         }
      }
    sort(type1_x.begin(), type1_x.end());
    long long main_dist = 0;
    if (type1_x.size()>0) 
        for (int i=1; i<type1_x.size(); i++) 
            main_dist += type1_x[i] - type1_x[i-1];
    long long branch_dist = 0;
    for (auto &kv : minLeftMap) 
        branch_dist += 2 * (kv.first - kv.second);
    long long extra_dist = 0;
    if (!type1_x.empty()) 
        extra_dist = max_x_all - type1_x.back();
    long long ans = main_dist + branch_dist + extra_dist;
    cout<<ans<<endl;
    return 0;
}

T4

自己都沒解出來，還是不亂寫東西糊弄人了（）

附上標準題解：

騎車

首先思考最大收益。當從景點 $ \alpha $ 走到景點 $ \beta $ 時，如果 $ p_\alpha > p_\beta $，則一定會帶著一瓶飲料過去，獲得 $ p_\alpha - p_\beta $ 的收益；如果 $ p_\alpha < p_\beta $，則不可能帶飲料過去。因此，>對于路徑經>過的點 $ z_1, z_2, \ldots, z_l $，最大收益為：

$\sum_{i=1}^{l-1} \max(p_{z_{i+1}} - p_{z_i}, 0)$

方案數分析

當 $ p_\alpha \neq p_\beta $ 時，最優方案唯一。

當 $ p_\alpha = p_\beta $ 時，可選擇帶或不帶飲料（兩種方案）。
因此，方案總數可表示為：

$\sum_{i=1}^{l-1} |p_{z_{i+1}} - p_{z_i}|$

此解法可獲得 20 分。

優化思路

預處理
路徑固定不變，僅價格會修改。預處理樹上每條邊的出現次數。

部分分（$ Q = 0 $)
用前綴和維護每條路徑的答案。

滿分優化

對每個點維護平衡樹，按子節點價格排序。

存儲從該點到子節點的邊的出現次數之和。

修改某點價格時，只需重新計算該點與父節點、子節點的關聯答案。

簡潔的結尾

posted @ 2025-08-03 19:28 Kaos·Abraham 閱讀(13) 評論(0) 收藏舉報

刷新頁面返回頂部

apprentice-K

2025.8.3.模擬賽總結

原題戳我

T1

刪除舊邊：移除插入位置原有的邊（即插入節點與其后繼節點之間的邊）

添加新邊：添加插入節點與前后節點之間的兩條新邊

代碼流程總結

代碼實現

T2

代碼流程總結

代碼實現

T3

代碼實現

T4

騎車

方案數分析

優化思路

簡潔的結尾

公告