省選模擬測試4

2022-09-23 00:28:42 字數 2904 閱讀 4911

期望得分: \(0+40+0 = 40\)

實際得分:\(0+40+0=40\)

毒瘤出題人把每道題的演算法都寫在了標題上,但就是不會做。

\(t1\) 考試的時候題意都沒有理解透徹,想打暴力卻不知道如何下手。

\(t2\) 暴力 \(for\) 迴圈都有 \(80\) 分,自己的大常數做法跑的比暴力還慢。

\(t3\) 不說了,連題都讀不懂。

這兩天好像都考到了李超線段樹,但是我沒怎麼接觸過,考完之後去惡補了一下。

給你一個 \(n\) 維的多面體,定義它的面是一個 \(n-1\) 維多面體,已知它必定有 \(2n\) 面。

我們把這個 \(n\) 維體的所有面都染色。

現在,給你這個多面體每一維的長度,然後可以將這個 \(n\) 維體劃分成 \(\displaystyle \prod_^ a_i\) 個每個邊的邊長為 \(1\) 的小 \(n\) 維體。

定義一個小 \(n\) 維體的權值是它有多少個面被染色。

輸出每個權值的小 \(n\) 維體的個數,顯然可以知道,權值範圍在 \([0,2n)\) 中,所以只需要把 \([0,2n)\) 的所有答案都輸出即可。

答案對 \(469762049\) 取模。

資料範圍: \(n\leq 10^5, a_i\leq 469762049\)

題解的做法是找遞推式,然後用 分治 \(ntt\) 優化這個遞推過程。

不理解題意的菜雞溜了溜了。

有 \(n\) 個 \(y = kx+b\) 形式的方程,有 \(m\) 次操作,操作分為三種型別:

資料範圍:\(1\leq x\leq 1000, 1\leq v\leq 1000, k_i\leq 1000,b_i\leq 10^6,n\leq 2\times 10^5,m\leq 2\times 10^6\)

其中操作 \(1\) 的數量和操作 \(3\) 的數量和不超過 \(10^5\)

分塊套李超線段樹。

如果沒有操作 \(3\) 的話,這道題就是個李超線段樹的板子。

但有了操作 \(3\) 我們很難維護出操作後的優勢線段。

考慮用分塊套李超線段樹來解決這個問題,具體來說就是:

我們把序列劃分為 \(\sqrt\) 個塊,對於每個塊都建一棵李超線段樹。

對於操作 \(1\) ,散塊的話我們直接暴力掃一遍,對於整塊,我們在其對應的李超線段樹裡面查詢一下即可。

對於操作 \(2\), 斜率增大後的直線肯定比原來的直線更優,所以我們直接把新直線插入到對應塊的李超線段樹即可。

對於操作 \(3\), 散塊的話我們還是暴力掃一遍,把新的直線插入到對應塊的李超線段樹當中。對於整塊,相當於是把塊內的所有直線都向上平移了一段距離,優勢線段不會改變,直接打個標記即可。

不知道為什麼我的**跑的賊慢,卡了卡常才勉強過去。

#include#include#include#includeusing namespace std;

#define int long long

const int n = 2e5+10;

int n,m,maxn,block,opt,l,r,v,tot,x;

int pos[n],l[1010],r[1010],k[n],b[n],tag[1010],s[5000010],rt[1010];

struct node

tr[5000010];

#define l(o) tr[o].pl

#define r(o) tr[o].pr

inline int read()

while(ch >= '0' && ch <= '9')

return s * w;

}int calc(int id,int x)

void build(int &o,int l,int r)

void insert(int o,int l,int r,int u)

if(l(o) == r(o))

if(k[u] > k[v])

else if(k[u] < k[v])

else if(b[u] > b[v]) s[o] = u;

}else

}int query(int o,int l,int r,int x)

void modify(int x,int y,int v)

else

}int query(int x,int y,int v)

else

}signed main()

for(int i = 1; i <= n; i++)

for(int i = 1; i <= maxn; i++) build(rt[i],1,1000);

for(int i = 1; i <= n; i++) insert(rt[pos[i]],1,1000,i);

for(int i = 1; i <= m; i++)

if(opt == 2)

if(opt == 3)

}fclose(stdin); fclose(stdout);

return 0;

}

從上次打完最後的副本之後,\(qaq\) 她決心想要出一個有價值的題,然後就有了這道題。現在,她想給小朋友們發糖(大霧),她現在有 \(n\) 個薛定諤的糖果盒,她可以進行 \(m\) 次如下的三個操作

+1s選出 \(k\) 個糖果盒,每個糖果盒有 \(p\%\) 的概率開出糖果。(可以包含已經開啟的糖果盒,由於每個糖果盒是量子態的,所以可能之前有糖果的糖果盒這次扣上盒蓋的後,可能會變成一個空盒)

選出來 \(t\) 個禮品盒,第 \(i\) 個糖果盒有 \(min(p+i-1,100)\%\) 的概率開出糖果

現在 \(qaq\) 想要知道,她期望最多能拿出多少個糖果。

結果保留 \(5\) 位小數。

資料範圍:\(p\leq 100,t\leq 20,n\leq 500,m\leq 500\)

咕咕咕

省選模擬4

發現所有圓的包含關係形成了樹的結構,而如果將樹的形態確定,那麼只需要簡單dp就可以求出答案。 發現只需要在二維平面中找到被當前圓包含的圓,所...

4 3 省選模擬賽 序列遊戲 dp

可以發現 某一段被刪除後狀態難以表示 也難以連結起來。 考慮暴力 有40分的狀壓dp 暴力存狀態 然後列舉轉移即可。最後注意和f 0 這個狀...

藍橋杯 省賽試題4 奇怪的比賽

題目 某電臺舉辦了低碳生活大獎賽。題目的計分規則相當奇怪 每位選手需要回答10個問題 其編號為1到10 ,越後面越有難度。答對的,當前分數翻倍 答錯了則扣掉與題號相同的分數 選手必須回答問題,不回答按錯誤處理 。 每位選手都有一個起步的分數為10分。 某獲勝選手最終得分剛好是100分,如果不讓你看比...