天天看點
傳回

CodeForcesD題記錄

D. Glass Half Spilled

題目連結：https://codeforces.com/contest/1459/problem/D

本題的意思就是給你 n n n個杯子的容量 a [ i ] a[i] a[i]和存有的水的量 b [ i ] b[i] b[i]，每個被子裡的水都可以轉到其他杯子去，但是每次都要損失 b [ i ] 2 \frac{b[i]}{2} 2b[i]​，問我們從 n n n個杯子中取得 k k k個杯子，這些杯子中最多有多少水。

假設 n n n個杯子的容量有 S a S_a Sa​,水有 S b S_b Sb​， k k k個杯子有容量 S a k S_{ak} Sak​，水 S b k S_{bk} Sbk​

容易知道：我們固定 k k k個杯子後，剩下的杯子裡的水都要轉進來，則得到的最大的水為 m i n ( S a k , S b k + S a − S b k 2 ) min(S_{ak},S_{bk}+\frac{S_a-S_{bk}}{2}) min(Sak​,Sbk​+2Sa​−Sbk​​)

其中如果知道是哪 k k k個杯子，那麼 S a k S_{ak} Sak​和 S a k S_{ak} Sak​都會得到，是以，問題轉為了要知道是哪幾個杯子。

對于給定的 n n n個杯子，要取得其中 k k k個杯子，确認過和背包問題很像。

是以我們首先想到 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i個杯子中取 j j j個杯子得到的最大值。

但是再想想，我們得到的最大值雖然表示了在這個狀态下可能的最大值，但是我們知道是取哪幾個嗎？是真正的最大值嗎？

就舉個二維費用背包的例子，二維背包要枚舉體積和重量，不妨令 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示前 i i i個物品體積為 j j j，重量為 k k k的狀态，隻有這樣才确定了我們在這得到的狀态，假如二維背包的 d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i個物品，體積為 j j j的狀态，我們能得到最優的 d p [ i + 1 ] [ j + v ] dp[i+1][j+v] dp[i+1][j+v]嗎？

答案是不能。因為可能我們得到體積 v v v的最好狀态卻浪費了大量的重量，如果我們根據這轉移，明顯不是最優解。即後續的最大值也會發生變化。

是以在這題裡，我們設三維 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]，表示前 i i i個物品，取 j j j個物品，容量是 k k k的狀态，這使得我們目前的狀态唯一了，即固定了取了哪幾個杯子。而很明顯，取的物品個數相當于二維背包得體積，容量相當于二維背包的重量。

又因為空間複雜度太大，可以用滾動數組優化，就像二維背包，後面2個參數倒序就行。

下面是代碼

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
typedef long long ll;
const int MAXN = 105;
int dp[105][10005];
int a[MAXN],b[MAXN];
int main() {
    int n;
    cin >> n;int sa = 0,sb=0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i] >> b[i];
        sa += a[i];
        sb += b[i];
    }
    memset(dp, -1, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = i;j >0;j--) {
            for (int k = sa;k >= a[i];k--) {
                if (dp[j - 1][k - a[i]]!=-1) {
                    dp[j][k] = max(dp[j][k], dp[j - 1][k - a[i]] +b[i]);
                }
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        double tp=0;
        for (int j = 0;j <= sa;j++) {
            if (dp[i][j] != -1)tp = max(tp, min(1.0 * j, (sb + 1.0*dp[i][j]) * 0.5));
        }
        cout << fixed << setprecision(10) << tp << " ";
    }
}

D. Ceil Divisions

題目連結：https://codeforces.com/contest/1469/problem/D

這題意思就是給你一個 1 1 1 ~ n n n的數組，每次選擇2個位置 x , y x,y x,y， 1 ⩽ x , y ⩽ n    ( x ≠ y ) 1\leqslant x,y\leqslant n~~(x\ne y) 1⩽x,y⩽n  (x​=y)，使得數組中的 x x x位置的 a x a_x ax​元素變為 ⌈ a x a y ⌉ \lceil\frac{a_x}{a_y} \rceil ⌈ay​ax​​⌉，最多操作 n + 5 n+5 n+5次使得數組中隻有1個2，其餘都是1

剛開始的思路肯定很簡單，就是二倍的往下，比如給你一個數組

1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 1,2,3,4,5,6,7,8,9,10,11,12,13 1,2,3,4,5,6,7,8,9,10,11,12,13，先設 a = ⌈ 13 2 ⌉ = 7 a=\lceil\frac{13}{2}\rceil=7 a=⌈213​⌉=7，然後讓 [ 8 , 12 ] [8,12] [8,12]的數都與13除，使得 [ 8 , 12 ] [8,12] [8,12]的數都為1，然後令 ⌈ 13 7 ⌉ = 2 \lceil\frac{13}{7}\rceil=2 ⌈713​⌉=2，再 ⌈ 2 7 ⌉ = 1 \lceil\frac{2}{7}\rceil = 1 ⌈72​⌉=1，使得13的位置變為1，這很明顯就是節省了很多步驟，但是仔細想，我每次除2，在商的那個位置，我要操作2次，才能變為1，其餘的都操作1次，最後的結果就是 n + log ⁡ 2 n n+\log_{2}n n+log2​n，很明顯不符合題意。

我們繼續往下想，我們每次除2，得到 n + log ⁡ 2 n n+\log_{2}n n+log2​n，那我們每次多除一點，假如除 t t t,那麼我們得到的便是 O ( n + log ⁡ t n ) O(n+\log_{t}n) O(n+logt​n),但事實不是這樣， t t t如果很大，在一個位置為 k k k的數 a k a_k ak​， ⌈ a k t ⌉ = 1 \lceil\frac{a_k}{t}\rceil=1 ⌈tak​​⌉=1時，就轉為了 O ( k ) O(k) O(k)的次數，是以 t t t作為常數，我們找不到（即我們不能每次除固定的數），是以我們就繼續想，要比2多，但是不是常數，要随着我們現在處理的 a k a_k ak​大小有關，不斷嘗試，最後會得到 log ⁡ 2 a k , a k \log_{2}a_k,\sqrt{a_k} log2​ak​,ak​

​等數,然後驗算，發現 a k \sqrt{a_k} ak​

​适合。

下面是代碼：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
typedef long long ll;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a = n;
        int cnt = 0;
        int pre = n;
        while (a!=2) {
            int b = ceil(sqrt(a*1.0));
            cnt += 2;
            cnt += pre - b - 1;
            pre = b;
            a = b;
        }
        cout << cnt << endl;
        a = n;
        pre = n;
        while (a != 2) {
            int b = ceil(sqrt(a * 1.0));
            for (int i = b + 1;i <= a - 1;i++) {
                cout << i << " " << a << endl;
            }
            cout << a << " " << b << endl;
            cout << a << " " << b << endl;
            a = b;
        }
    }
}

A. Regular Bracket Sequence

題目連結：https://codeforces.com/contest/1469/problem/A

首先，要明白題目的意思，題目介紹對于給定的字元串，隻會出現一個" ( ( (" 和一個" ) ) )"，其餘都是" ? ? ?",是以很容易想到，字元串長度為奇數，肯定不行，如果是偶數，那麼" ( ( (" 在最右或者 " ) ) )"在最左也不行。

這題就很快出來了。但是我們往深想，如果沒規定兩個括号的個數呢？

我們想，對于沒有" ? ? ?" 的字元串，我們找出合格的，就是申明變量 c n t = 0 cnt=0 cnt=0然後遇到左括号 c n t + + cnt++ cnt++，右括号 c n t − − cnt-- cnt−−，一旦 c n t < 0 cnt<0 cnt<0就不合格，到最後，如果 c n t > 0 cnt>0 cnt>0也不合格

那麼我們對于有" ? ? ?" 的能不能像它一樣處理呢？

我們對于" ? ? ?" 轉換，如果轉化為左括号，目的是為了消除右邊的右括号，轉化為右括号，目的是為了消除左邊的左括号。

我們繼續想，對于字元串 ( ? ? ? ? ? ? (?????? (??????我們為了消除左括号，肯定要令？中的一個變為右括号，那我們變哪個才最好呢？

答案是最後一個，為何，因為最後一個的右括号，它可以消除它前面的多餘的任意一個左括号，貪心的思維。

( ? ? ? ? ? ? \color{blue}(???\color{red}{?}\color{black}?? (??????,比如就把紅色問号這個變為右括号，那麼它隻能消除藍色的位置的左括号，但是黑色位置的消除不了。

是以我們知道如果字元串不平衡， c n t > 0 cnt>0 cnt>0時，最優解肯定是從右到左将問号變為右括号。

那麼同理，左括号一樣的情況。但是，我們如果同時處理2種括号，會複雜。因為不知道哪個臨界點 是左右括号的臨界點。是以，我們可以直接将所有問号先當作"（"處理。周遊字元串，得到 c n t cnt cnt。

f l a g = { f a l s e , 如果 c n t  為奇數或者 c n t < 0 t r u e   o r   f a l s e , c n t ⩾ 0 flag = \begin{cases} false, & \text{如果}cnt\text{ 為奇數或者}cnt<0 \\ true~or~false, & cnt\geqslant 0 \end{cases} flag={false,true or false,​如果cnt 為奇數或者cnt<0cnt⩾0​

下面對于 c n t ⩾ 0 cnt\geqslant 0 cnt⩾0的情況，隻要将問号從右到左變為左括号， c n t − = 2 cnt-=2 cnt−=2，一旦 c n t = = 0 cnt==0 cnt==0就退出。

但是" ) ) ? ? ))?? ))??"這種情況不行，是以我們從左到右再跑一遍無問号的字元串，如果符合就可以，不符合就不行。

下面是代碼：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
typedef long long ll;
char ch[1005];
int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> ch;
        int cnt = 0;
        int len = strlen(ch);
        for (int i = 0;i < len;i++) {
            if (ch[i] == '(' || ch[i] == '?')cnt++;
            else cnt--;
        }
        if (cnt < 0||cnt%2) { cout << "NO" << endl;continue; }
        for (int i = len - 1;i >= 0;i--) {
            if (cnt == 0)break;
            if (ch[i] == '?') {
                ch[i] = ')';
                cnt -= 2;
                if (cnt == 0)break;
            }
        }
        bool f = true;
        for (int i = 0;i < len;i++) {
            if (ch[i] == '(' || ch[i] == '?')cnt++;
            else cnt--;
            if (cnt < 0) {
                f = false; break;
            }   
        }
        if (f)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
        
}

C. Busy Robot

題目連結：https://codeforces.com/contest/1463/problem/C

題目意思是給你 n n n組數字，每組包含一個時間點和位置，第 i i i個點的時間點設為 t [ i ] t[i] t[i],位置設為 p [ i ] p[i] p[i]，當一個機器人在 t [ i ] t[i] t[i]到 t [ i + 1 ] t[i+1] t[i+1]經過 p [ i ] p[i] p[i]時，答案數+1，一旦接受一個指令，機器人肯定要将路走完，走的時候釋出的指令都不會聽從，停下來時釋出的指令才會接受。

很明顯，是個模拟題。但是這個模拟還是比較惡心的。

因為我們對于在 t [ i ] t[i] t[i]時的狀态，我們要先知道運動的方向，要知道是處于停止狀态還是走路狀态，然後是運動的起始點和終點。

是以我們用 f f f記錄方向，-1為反方向，1為正方向，0表示不動， p t pt pt記錄前一次停止的時間，初始化 t [ 1 ] t[1] t[1]， p o s pos pos記錄前一次停止的位置， p r e x prex prex記錄在 t [ i − 1 ] t[i-1] t[i−1]到達的位置， t x tx tx表示在 t [ i ] t[i] t[i]時到達的位置， n t nt nt就是現在的時間 t [ i ] t[i] t[i],設定第 n + 1 n+1 n+1是因為第一個樣例的啟發。

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
#define Min(x,y,z) min(x,min(z,y))
#define Max(x,y,z) max(x,max(z,y))
typedef long long ll;
const int MAXN = 1e5 + 5;
ll t[MAXN], p[MAXN];
ll change(ll prex,ll nowx) {
    if (prex < nowx)return 1;
    if (prex == nowx)return 0;
    if (prex > nowx)return -1;
}
int main() {
    ll T;
    cin >> T;
    while (T--) {
        ll n;
        cin >> n;
        for (int i = 1;i <= n;i++) { cin >> t[i] >> p[i]; }
        ll cnt = 0;
        ll f;
        ll pt = t[1];
        ll pos = 0;
        ll prex = 0;
        ll tar = p[1],to=p[1];
        ll nt, tx;
        t[n + 1] = 1e17;p[n + 1] = 0;
        f = change(prex, tar);
        for (int i = 2;i <= n+1;i++) {
            nt = t[i];
            tx = (nt - pt) * f + pos;
            if (tx * f >= to * f) {
                tx = to;
                pos = to;
                to = p[i];
                f = change(pos, to);
                pt = nt;
               
            }
            if (min(prex, tx) <= tar && max(prex, tx) >= tar)cnt++;
            prex = tx;tar = p[i];
        }
        cout << cnt << endl;
    }
}

D. Pairs

題目連結：https://codeforces.com/contest/1463/problem/D

題目大意：你有 [ 1 , 2 n ] [1,2n] [1,2n]的數，以及一個數組 b b b，對于 [ 1 , 2 n ] [1,2n] [1,2n]你可以找劃分為 n n n對，每隊我們可以取最小值，也可以最大值，令取最小值的對數為 x x x，然後令所有對取得的結果組成 b b b數組，問 x x x能取幾種情況。

對于 b b b數組，我們發現取最小值最優的是從左往右取，最大值是從右往左取，因為 b b b數組是有序的。

我們設 a a a數組是 [ 1 , 2 n ] [1,2n] [1,2n]中去除 b b b數組裡 數的一個數組。

分析一波：假設我們不是上面這取法，舉例令 b [ i ] b[i] b[i]是取 m a x max max得到的， b [ i + 1 ] b[i+1] b[i+1]是取 m i n min min得到的。

是以有即 b [ i ] = m a x ( b [ i ] , a [ k ] ) , b [ i + 1 ] = m i n ( b [ i + 1 ] , a [ t ] ) b[i]=max(b[i],a[k]),b[i+1]=min(b[i+1],a[t]) b[i]=max(b[i],a[k]),b[i+1]=min(b[i+1],a[t]),又因為 b [ i ] < b [ i + 1 ] b[i]<b[i+1] b[i]<b[i+1]，是以 a [ k ] < a [ t ] a[k]<a[t] a[k]<a[t],是以如果 b [ i ] = m i n ( b [ i ] , a [ t ] ) , b [ i + 1 ] = m a x ( b [ i + 1 ] , a [ k ] ) b[i]=min(b[i],a[t]),b[i+1]=max(b[i+1],a[k]) b[i]=min(b[i],a[t]),b[i+1]=max(b[i+1],a[k])也一定成功。

但是反過來卻不一定。

是以，我們知道從左到右是取最小值，從右到左取最小值。

那麼，我們可以對于一個 b [ i ] b[i] b[i]，假如取最小值，可以取幾次呢，設在 a a a數組中比 b [ i ] b[i] b[i]大的有 s s s個。這說明什麼，對于 b [ i + 1 − s ] b[i+1-s] b[i+1−s]開始到 b [ i ] b[i] b[i]取最小值，都是可以的。然後其他也一樣。

下面是代碼

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
#define Min(x,y,z) min(x,min(z,y))
#define Max(x,y,z) max(x,max(z,y))
typedef long long ll;
const int MAXN = 4e5 + 5;
int a[MAXN], b[MAXN];
int pre[MAXN], last[MAXN];
int tong[MAXN];
int main() {
    std::ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        
        int n;
        cin >> n;
        for (int i = 1;i <= n;i++) {
            pre[i] = last[i] = 0;
            cin >> a[i];
            tong[a[i]] = 1;
        }
        int cnt = 0;
        int tnt = 1;
        for (int i = 1;i <= 2*n;i++) {
            if (!tong[i])b[++cnt] = i;
        }
        
        cnt = 1, tnt = 1;
        for (int i = 1;i <= n;i++) {
            pre[i] = pre[i - 1];
            while (b[tnt] < a[i]&&tnt<=n) {
                pre[i]++;
                tnt++;
            }
        }
        tnt = n;
        for (int i = n;i >= 1;i--) {
            last[i] = last[i + 1];
            while (b[tnt] > a[i]&&tnt>=1) {
                last[i]++;
                tnt--;
            }
        }
        int r = 2e6;
        int l = 0;
        for (int i = 1;i <= n;i++) {
            tong[a[i]] = 0;
            r = min(r, i + last[i] - 1);
            int j = n - i + 1;
            l = max(l, j - pre[j]);
        }
        for (int i = 0;i <= n+1;i++)pre[i] = last[i] = 0;
        cout << max(r - l + 1, 0) << endl;
    }
}

D. 13th Labour of Heracles

題目連結：https://codeforces.com/contest/1466/problem/D

題目大意：給你一棵樹，每個節點都有權值，要你給這棵樹的邊染色，從一種顔色到 n − 1 n-1 n−1種顔色。要求得到所有不同顔色的分支的權值和的最大值，要保證每種顔色的子圖要連通。

首先，當顔色為1時，很明顯，答案就是所有點的權值和，顔色為2的時候，我們要分情況了，對于度(入度+出度)大于等于2的點，我們可以選一個點為中心，然後這個點有多條邊，一條邊引出去的樹為color1，其他為color2，這樣可以使得這個點被加了2次。

這也明顯得到，為了讓權值大的點被多加幾次，這個點的度數肯定要滿足一定條件。

度數為1最多加1次，度數為2最多加2次，度數為3最多加3次。。。。。。

下面是代碼：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
#include<queue>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
#define Min(x,y,z) min(x,min(z,y))
#define Max(x,y,z) max(x,max(z,y))
typedef long long ll;
const int MAXN = 1e5 + 5;
ll a[MAXN], b[MAXN];
struct Node {
    int du=0, val=0;
    bool operator<(const Node& a)const {
        return val > a.val;
    }
}node[MAXN];
queue<Node>q;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ll s = 0;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
            s += a[i];
            node[i].val = a[i];
            node[i].du = 0;
        }
        for (int i = 1;i < n;i++) {
            int u, v;
            cin >> u >> v;
            node[u].du++;
            node[v].du++;
        }
        sort(node + 1, node + 1 + n);
        cout << s << " ";
        int tnt = 2;
        for (int i = 1;i <= n;i++) {
            if (node[i].du >= 2) {
                for (int j = 2;j <= node[i].du && tnt <= n-1;j++) {
                    tnt++;
                    s += node[i].val;
                    cout << s << " ";
                }
                if (tnt == n)break;
            }
        }
        cout << endl;
    }
}

D. Grime Zoo

題目大意：給你一個隻含有0，1，?的字元串以及x和y。？可以變為0或者1，然後出現01子串，憤怒值+x，出現10子串，憤怒值+y。

假如我們 x > y x>y x>y，很明顯，我們希望01出現的少，那麼對于"?"集合的處理，肯定要使得問号變成的1在問号變成的0前面，即 000 、 100 、 110 、 111 000、100、110、111 000、100、110、111這種，而不會是 010 、 011 、 001 010、011、001 010、011、001這種。

同理， y < x y<x y<x就相反。

那麼我們現在其實就是處理一個問号的字首0，1和字尾0，1。對于一整個字元串的貢獻，我們可以将問号拿出來單獨算，然後，那些非問号的提前算，後面，我們隻需要對于問号進行單獨修改，比如0變成1，我們隻要将原來這個0對于整個字元串的貢獻減掉，加上1對于整個字元串的貢獻就行。然後再加上問号集合的貢獻就像。

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<stdio.h>
#include<map>
#include<queue>
using namespace std;
#define check(x) cout<<"x:"<<x<<" "
#define Min(x,y,z) min(x,min(z,y))
#define Max(x,y,z) max(x,max(z,y))
typedef long long ll;
const int MAXN = 1e5 + 5;
string str;
ll x, y;
ll pre[MAXN][2];
ll last[MAXN][2];
vector<int>v;
int main() {
    cin >> str;
    cin >> x >> y;
    int len = str.length();
    ll s = 0;
    for (int i = 0;i < len;i++) {
        if (str[i] == '?') { v.push_back(i + 1); }
        pre[i + 1][1] = pre[i][1];
        pre[i + 1][0] = pre[i][0];
        if (str[i] == '1') { 
            s += pre[i + 1][0] * x;
            pre[i + 1][1]++;
        }
        if (str[i] == '0'){
            s += pre[i + 1][1] * y;
            pre[i + 1][0]++;
        }
    }
    for (int i = len - 1;i >= 0;i--) {
        last[i + 1][0] = last[i + 2][0];
        last[i + 1][1] = last[i + 2][1];
        if (str[i + 1] == '1')last[i + 1][1]++;
        if (str[i + 1] == '0')last[i + 1][0]++;
    }
    /*for (int i = 1;i <= len;i++) {
        cout << pre[i][0] << " " << pre[i][1] << endl;
        cout << last[i][0] << " " << last[i][1] << endl;
    }*/
    ll minn = 1e18;
    if (x > y) {
        for (auto i : v) {
            s += pre[i][1] * y+last[i][1]*x;
        }
        int num = v.size();
        int tnt = 0;
        minn = min(s, minn);
        for (auto i : v) {
            tnt++;
            s -= pre[i][1] * y + last[i][1] * x;
            s += pre[i][0] * x + last[i][0] * y;
            s += tnt * (num - tnt) * y;
            minn = min(s, minn);
            s -= tnt * (num - tnt) * y;
        }
        cout << minn << endl;
    }
    else {
        for (auto i : v) {
            s += pre[i][0] * x + last[i][0] * y;
        }
        int num = v.size();
        int tnt = 0;
        minn = min(s, minn);
        for (auto i : v) {
            tnt++;
            s -= pre[i][0] * x + last[i][0] * y;
            s += pre[i][1] * y + last[i][1] * x;
            s += tnt * (num - tnt) * x;
            minn = min(s, minn);
            s -= tnt * (num - tnt) * x;
        }
        cout << minn << endl;
    }
}
算法入門 算法
上一篇: 從SUN+MySQL看開放源碼的商業模式
下一篇: 消費金融業務場景裡，結算系統該如何設計？

繼續閱讀