P1

題敘

題目大概是說
有一個網格圖，每個圖有一個點，如果從一格走到相鄰的另一格 這兩格的總和是奇數的話稱此步為好步反之稱之壞步
給定k求最左上走到最左下不超過k次壞步的最短步數。

思路

我沒想太多就寫了個帶狀態的bfs,但因為k很小,應該要再開一層維度記錄。 dist[i][j][k] //k為壞步數量
我的判斷只有 超過壞步數量or小於下一格時 就不走 dist紀錄也都只有二維
除非他測資很爛不然我應該只能拿子題

P2

超裸的二分混貪心題
因為我根本沒看完題敘所以我講不出來
總之跟這題CSES 一模一樣
直接秒殺

思路

當時是沒想甚麼, 可以先發現到, 對於一個最大值我們判斷他能不能夠切成<=k個子陣列。
會發現 如果x可以, 那x+1,x+2….x+1e9+9也可以。
如果x不行,那x-1,x-2….0,也都不行。
具有單調性所以能夠二分搜答案，接著就是判斷
判斷只要

O(n)O(n)

就能判斷完
所以整體複雜度是

O(nlogK)O(nlogK)

K為最大可行答案

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9+9;
int n,k;
bool chk(ll m,vector<ll> &v){
    ll cur=0,cnt=1;
    for(ll i:v){
        if(i>m) return 0;
        if(cur+i<=m){
            cur+=i;
        }
        else{
            cur=i;
            cnt++;
        }
    }
    return cnt<=k;
}
int main(){
    cin>>n>>k;
    vector<ll> v(n);
    for(ll &i:v) cin>>i;
    ll l=0,r=1e15,ans=0;
    while(l<=r){
        ll mid = (l+r)/2;
        if(chk(mid,v)){
            ans = mid;
            r = mid-1;
        }
        else l = mid+1;
    }
    cout << ans << '\n';
}

P3

看到題目嚇哭了,因為我有學過但我剛好忘記怎麼O(n)建笛卡爾樹

題敘

(一大串笛卡爾樹的定義)
給定一個數列 求此數列的笛卡爾樹中數值*深度的總和

思路

一開始還想用單調堆疊建樹,但後來放棄了,因為不會,而且他不會考一個真正的笛卡爾樹。
考點肯定在其他地方, 往數值範圍一看會發現

n≤104 n\le 10^4


那我直接遞迴配上線性搜尋法找最小值不就可以了嗎?
不知道怎樣總之它的複雜度會是

O(nlog2n)O(n log^2 n)

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1e9+9;
int a[1005];
ll ans=0;

void rec(int l,int r,int d){
    if(r<l) return;
    int idx=-1,mn=1e9;
    for(int i=l;i<=r;i++){
        if(a[i]<mn){
            idx = i;
            mn = a[i];
        }
    }
    ans+=mn*d;
    rec(l,idx-1,d+1);
    rec(idx+1,r,d+1);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    rec(0,n-1,1);
    cout << ans << '\n';
}

結尾

成績好慢 期待但我覺得我P1應該已經炸了
2,3我應該有信心拿滿分 識讀也應該有5級

更新

p1只拿40分 確實寫爛了
p2,p3都滿分, 識讀只有4級qwq