Google Kickstart D 2018題解

來自專欄 wx演算法筆記5 人贊了文章

A題

題目大意是給n塊糖，每塊糖甜度為Si(Si可能小於0)；如果Si不能被2整除，那麼稱這塊糖甜度為odd ，主人公Supervin最多可以接受O塊odd糖，最多接受的甜度為D，並且他只會吃一個連續區間的糖果。求可以吃到的最大甜度。

數據範圍

N≤ 5 × 10^5

10^-15<D<10^15

...

Small dataset

小數據中所有糖果甜度都是正的，尺取法很容易處理，只需要2個坐標，分別表示當前取到區間的頭和尾，當甜度>d或者區間內odd糖數目>o時，向前挪動區間尾坐標，使區間滿足條件；當區間滿足條件時，則向前挪動區間頭，更新最大數值得到最優解。當所有糖果都大於D，則輸出IMPOSSIBLE

Large dataset

大數據中糖果數量可能為負的，這樣上面的方法就出現問題了，因為D過小時，你可以吃負數糖果越來越小；或者當前甜度>d,可以繼續吃負數的糖果使甜度變小，而不是向前挪動區間尾。當時做題時沒考慮這麼多，以為數據量沒啥差別跪orz

正確解法時，還是枚舉區間，不過先預處理前綴和sum，可以使用平衡二叉查找樹或者c++多重集來存儲，使查找時間為log(n)。用l表示集合中最後一位，預處理之後循環訪問第i個糖果，其中統計odd糖果數目，odd過多，則將末尾l的前綴和刪除，直到odd滿足條件。最後二分查找前綴集合中sum[j]>=sum[i]-D（j<i）, ans=max(ans,sum[i]-sum[j])。複雜度為n*log(n)。

B題

N個塔，塔底坐標為（pi，0），高hi；有k個氣球，坐標（xi，yi）。可以從任意塔上任意位置向斜下方45度（左右都可以）沿直線滑行，統記可以拿到的氣球個數。

Small dataset

2 ≤ N ≤ 1000.

可以直接暴力判斷從i塔可不可以拿到第j個氣球,時間複雜度O（N*K），最大計算量10^6，

Large dataset

2 ≤ N ≤ 10^5.

2 ≤ K ≤ 10^5

當N，K過大時，暴力會超時。因為高的位置可以覆蓋低的位置所能到達的區域，所以用一個結構體數組{x,y,i}統一存儲塔和氣球（塔的i標記為-1，氣球標記為1,2,3,4...）,然後按先x後y排序。我們記錄當前能到達的最高位置，先統一從前往後處理，遇到氣球判斷從最高位置是否可以夠到，遇到塔，更新當前p的最高高度；在從後往前處理一遍，注意可能有重複的需要去重。複雜度為O（n+k）。

orz因為for循環多了一位，兩個數據都沒過，結束後發現+1，去掉都過，血虧zzzzz

C題

題目大意是R*C的字母矩陣，其中存在W個不同的有效單詞，從位置（i，j）可以向四個方向（上下左右）匹配這W個單詞，不可以斜著匹配。定義一個子矩陣的得分為fun value= (total length of words matched) / ((width of subgrid) + (height of subgrid))

求最大得分a/b，以及個數c，（a/b為分數最簡形式）

數據範圍

• 1 ≤ T ≤ 100.
• 1 ≤ R ≤ 100.
• 1 ≤ C ≤ 100.

Small dataset

• The length of each valid word is exactly 1.
• 1 ≤ W ≤ 26.

由於只有單詞只有一位，一個單詞得分為4。先統計前綴和S（i，j），然後枚舉Score[i1， j1，i2，j2] = S（i2，j2）-S（i1-1，j2）-S（i2，j1-1）+ S（i1-1，j1-1），統計最大值個數即可。

Wuuuuuuu，沉迷於+1bug，血虧

Large dataset

1 ≤ W ≤ 1000

重點來了！！先將word正向與反向都統計到一個next[10010][26]的數組中。

int id = 1;for (int i = 0; i < len; i++) { int t = s[i] - A; if (!next[id][t]) { next[id][t] = ++n_nodes; } id = next[id][t];}weight[id] += len;

然後可以去統計sum_d（i，j，k）即從（i，j）向下到k位的前綴和，同理sum_d（i，j，k）向右到k位的前綴和。

sumd（i，j，k）=weight[id]+sumd（i，j，k-1）

之後summd（x，i，j）統計第x列從（x，i）到（x，j）的前綴和

summd（x，i，j）=summd（x-1，i，j）+sco

其中sco為sumd（i，x，j）+..sumd（j，x，j）.的和，

同理summr（x，i，j）

最後score（i，j，x，y）= summd（y，i，x）- summd（j，i，x）

+summr（x，j，y）- summr（i，j，y）

求出最大的score以及個數

最後感覺自己還是太菜了orz，3個small data應該可以拿下來，B題big data也是必須做出來的，可是最後只有一題，血虧，耽誤在了B題+1bug上，卒。