NOIP2018提高组模拟题（六）
購物(shop)
Description
小林來到商店中進行購物。商店里一共有 n 件物品，第 i 件物品的價格為 a[i] 元。小林總共需要購買 m 件物品，他希望他所花費的錢最少，請你計算出最小 花費。
由于輸入的數據數量過大，我們采用一種加密的方式進行輸入。給出兩個密 鑰 x 和 y。則 a[1] = x, a[i] = (y*a[i-1] + x) % 10^9。
Input
一行兩個整數 n 和 m。
第二行共兩個整數 x 和 y，表示密鑰。
Output
輸出只有一個整數，表示最小花費。
數據規模
對于 50%的數據， n <= 1000；
對于 100%的數據， 1 <= n <= 10^7, 1 <= m <= 100, 1 <= x,y < 10^9。
對于 100%的數據，保證 m <= n。
看到題的一瞬間,這不傻逼題.
\(sort\)！轉眼一想貌似過不去。
不過有人用sort過了
這里用的是大根堆維護價值,
PS：注意要先在堆里墊上\(m\)個元素.
如果某一個物品的價值比當前堆頂的價值要小,就替換它.
最后取出堆中\(m\)個元素就好了。
代碼
#include<cstdio> #include<queue> #include<iostream> #define mod 1000000000 #define R registerusing namespace std;inline void in(int &x) {int f=1;x=0;char s=getchar();while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}while(isdigit(s)){x=x*10+s-'0';s=getchar();}x*=f; }int n,m,cnt=1; long long x,y,tmp,ans; priority_queue<int>q;int main() {freopen("shop.in","r",stdin);freopen("shop.out","w",stdout);in(n),in(m);scanf("%lld%lld",&x,&y);tmp=x;q.push(x);for(R int i=2;i<=n;i++){tmp=(tmp*y+x)%mod;tmp=(tmp+mod)%mod;if(cnt<m){cnt++;q.push(tmp);continue;}if(q.top()>tmp)q.pop(),q.push(tmp);}for(R int i=1;i<=m;i++)ans+=q.top(),q.pop();printf("%lld\n",ans);fclose(stdin);fclose(stdout);return 0; }期望(exp)
Description
我們知道，若一個隨機變量 \(X\)，在 \(p_i\) 的概率下，它的值等于 \(x_i\)， 則它的 數學期望 \(E(X)=\sum_ip_ix_i\) ，且滿足$\sum_ip _i =1 $ 。
現在有如下一個表達式： \(0 \ a_1 \ b_1\ a_2\ b_2 ... a_n \ b_n\)
其中 \(a_i\) 為一個位運算符，是“和” “或” “異或”三者中的一種， \(b_i\) 是一 個整數。
求這一表達式的值是一件容易的事，然而剛學完數學期望的小林在思考，如 果每一對 \(a_i b_i\) 有 \(c_i\) 的概率會消失，那么這一表達式的結果的數學期望是多少。
Input
第一行只有一個正整數 \(n\)。
第二行為 \(n\) 個整數表示 \(n\)個運算符 \(a_i\)， \(0\) 表示 \(and\)， \(1\) 表示 \(or\)， \(2\) 表示 \(xor\)。
第三行為 \(n\) 個非負整數 \(b_i\)。
第四行為 \(n\) 個實數 \(c_i\)（不超過三位小數）。
Output
只有一個實數，表示表達式的數學期望，保留一位小數。
數據規模
對于 30%的數據， 1 <= n <= 10， 0 <= bi <= 20；
對于 70%的數據， 1 <= n <= 100， 0 <= bi <= 1000；
對于 100%的數據， 1 <= n <= 100000， 0 <= ai <= 2， 0 <= bi < 2^31。
對于 100%的數據， 0 <= ci <= 0.999。
看到題。woc,
期望,不會不會不會.
敲完\(30\)分的爆搜,發現貌似可以搞.
考慮\(DP\).
設\(f[i][j]\)代表處理前\(i\)個數,二進制位\(j\)上存在的概率
這里為什么要這樣設？
如果直接設是否是\(j\)，很顯然,\(2^{31}\)開不下,你滾動數組也開不下
因此拆位處理.
這題難就難在分類討論
這里把我打的草稿放上來
一.當前符號位為＆
存在兩種情況.
\[\begin{cases}當前數b[i]有二進制j這一位 此時b[i]存在消失均可,則 f[i][j]=f[i-1][j]\\ \\當前數b[i]沒有二進制j這一位 那么想要有j,b[i]必須消失,則 f[i][j]=c[i]*f[i-1][j]\end{cases}\]
二.當前符號位為 |
存在兩種情況.
那么\(b[i]\)存在消失均可
但是現在\(b[i]\)存在不需要考慮之前的,因為我是獨立的.(因為當前符號位是\(|\))
所以
\[ f[i][j]=(1-c[i])+c[i]*f[i-1][j] \]
此時消失存在均可.則
\[ f[i][j]=f[i-1][j] \]
三.當前符號位為^
依舊存在兩種情況.
要么我存在&&上一位不存在,要么我不存在&&上一位存在.
所以
\[ f[i][j]=c[i]\times(1-f[i-1][j])+(1-c[i])\times f[i-1][j] \]
此時選不選即可,直接繼承
\[ f[i][j]=f[i-1][j] \]
可以滾動數組,空間復雜度很低.
穩穩地能過.
代碼
#include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<iostream> #include<queue> #include<algorithm> #define R registerusing namespace std;inline void in(int &x) {int f=1;x=0;char s=getchar();while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}while(isdigit(s)){x=x*10+s-'0';s=getchar();}x*=f; }double ans,c[100008],f[2][40];int n,a[100008],b[100008];inline void init() {for(R int i=1;i<=n;i++)in(a[i]);for(R int i=1;i<=n;i++)in(b[i]);for(R int i=1;i<=n;i++)scanf("%lf",&c[i]); }void dfs(R int dep,R int now,R double tmp) {if(dep>n){ // printf("%d %.2lf\n",now,tmp);ans+=now*tmp;return;}if(a[dep]==0)dfs(dep+1,now&b[dep],tmp*(1-c[dep]));//不消失if(a[dep]==1)dfs(dep+1,now|b[dep],tmp*(1-c[dep]));//不消失 if(a[dep]==2)dfs(dep+1,now^b[dep],tmp*(1-c[dep]));//不消失dfs(dep+1,now,tmp*c[dep]);//消失 }int main() {freopen("exp.in","r",stdin);freopen("exp.out","w",stdout);in(n);init();if(n<=10)/*2^n*/dfs(1,0,1),printf("%.1f\n",ans);else{for(R int i=1;i<=n;i++){R int op=i&1;for(R int j=0;j<=31;j++){if(a[i]==0){if(b[i]&(1LL<<j))f[op][j]=f[op^1][j];elsef[op][j]=c[i]*f[op^1][j];}if(a[i]==1){if(b[i]&(1LL<<j)){f[op][j]=(1-c[i]);f[op][j]+=c[i]*f[op^1][j];}elsef[op][j]=f[op^1][j];}if(a[i]==2){if(b[i]&(1LL<<j)){f[op][j]=(1-c[i])*(1-f[op^1][j]);f[op][j]+=c[i]*(f[op^1][j]);}elsef[op][j]=f[op^1][j]; }}}for(R int i=0;i<=31;i++)ans+=(1LL<<i)*f[n&1][i];printf("%.1f\n",ans);}fclose(stdin);fclose(stdout);return 0; }魔法迷宮(maze)
Description
在創建了魔法森林后，亮亮興致不減，于是揮動魔杖，又創造了魔法迷宮。
魔法迷宮共有 n 個節點，由 n-1 條邊將它們相連，整個迷宮是連通的。邊的 長度只有 A 和 B 兩種。
現在有 m 只小精靈，第 i 只小精靈一開始在 ui 點，她想要到達 vi 點，每一 天，它最多移動 ki 的距離，而且她不能停留在某一條邊上。你的任務是，計算 出每一只小精靈到達自己的目的地至少需要幾天。
Input
第一行一個整數 n。
接下來 n-1 行，每行三個整數 x, y, z, 表示 x,y 之間有一條長度為 z 的邊。
隨后一行一個整數 m，表示共有 m 只小精靈。
接下來 m 行，每行三個整數 ui, vi, ki。（保證 B≤ki≤n）
Output
輸出共 m 行，每行一個整數表示答案。
數據規模
對于 20%的數據， n,m <= 5000；
對于 100%的數據， 1 <= n,m <= 50000， 1 <= A < B <= 37。
先模大佬\(GMPotlc\)：夢想得分\(100pts\)
神卡常卡過此題,
由于\(LCA\)會多\(log\),因此直接暴力向上跳,判斷情況即可.
注意卡常！
決定放一下\(\color{red}官方題解\)
考察算法： LCA， 壓位
算 LCA 是顯然的， 由于兩個點之間可能要走很多步， 所以我們預處理每一個點往上連續 走六步會出現的各種情況， 便能控制常數， 從而在 8 秒內出解。 由于邊權只有兩種， 所以一 個點往上走六步遇到的邊權只有 2^6 = 64 種情況。
暴力代碼
#include<cstdio> #include<iostream> #include<algorithm> #define R register #define N 50008using namespace std;inline void in(int &x) {int f=1;x=0;char s=getchar();while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}while(isdigit(s)){x=x*10+s-'0';s=getchar();}x*=f; }int head[N],tot,rt,dis[N],f[N],depth[N],n,m; struct cod{int u,v,w;}edge[N<<2];inline void add(int x,int y,int z) {edge[++tot].u=head[x];edge[tot].v=y;edge[tot].w=z;head[x]=tot; }void dfs(R int u,R int fa,R int dist) {f[u]=fa;dis[u]=dist;depth[u]=depth[fa]+1;for(R int i=head[u];i;i=edge[i].u){if(edge[i].v==fa)continue;dfs(edge[i].v,u,edge[i].w);} }int main() {freopen("maze.in","r",stdin);freopen("maze.out","w",stdout);in(n);for(R int i=1,x,y,z;i<n;i++)in(x),in(y),in(z),add(x,y,z),add(y,x,z);R int rt=(n+1)>>1;dfs(rt,0,0);in(m);for(R int i=1,x,y,z;i<=m;i++){R int resa,resb,ans;in(x),in(y),in(z);resb=resa=ans=0;if(depth[x]>depth[y])swap(x,y);while(depth[x]>depth[y]){if(resa+dis[x]>z)resa=dis[x],ans++;else resa+=dis[x];x=f[x];}while(x!=y){if(resa+dis[x]>z)resa=dis[x],ans++;else resa+=dis[x];if(resb+dis[y]>z)resb=dis[y],ans++;else resb+=dis[y];x=f[x];y=f[y];}if(resa+resb>z)ans+=2;else if(resa+resb!=0)ans++;printf("%d\n",ans);}fclose(stdin);fclose(stdout);return 0; }轉載于:https://www.cnblogs.com/-guz/p/9873248.html
總結
以上是生活随笔為你收集整理的NOIP2018提高组模拟题（六）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 统计字符串中某个字符的个数
- 下一篇： RISC-V评估系列