A - Memory and Crow

這題我沒看題意，看了樣例猜了一下就AC了，題目好像還挺復雜的。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<n;i++) printf("%d ",a[i]+a[i+1]);printf("%d\n",a[n]);return 0;
}

View Code

?

?B - Memory and Trident

題目大意：一個人可以往上下左右走，給你一串操作，問你最少改變幾個能回到原地。

?

思路：將上下分成一堆，左右分成一堆，改變的時候優(yōu)先同一堆里面的互換。這樣能

保證次數(shù)最少。代碼寫的有點搓。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
char s[N];
int vis[4];
int main()
{scanf("%s",s);int len=strlen(s);if(len%2){puts("-1");return 0;}for(int i=0;i<len;i++){if(s[i]=='U') vis[0]++;else if(s[i]=='D') vis[1]++;else if(s[i]=='L') vis[2]++;else vis[3]++;}if((vis[0]+vis[1])%2==0){int a=(vis[0]+vis[1])/2-min(vis[0],vis[1]);int b=(vis[2]+vis[3])/2-min(vis[2],vis[3]);cout<<a+b<<endl;}else{int a=(vis[0]+vis[1]-1)/2-min(vis[0],vis[1]);//cout<<a<<endl;int b=(vis[2]+vis[3]-1)/2-min(vis[2],vis[3]);cout<<a+b+1<<endl;}return 0;
}

View Code

?

C - Memory and De-Evolution

題目大意：給你兩個邊長分別為x和y的等邊三角形，問你最少通過多少次改變可以把x變成y(x>y)

每次改變可以改變一條邊，且改變后三邊依舊能構(gòu)成三角形。

?

思路：想了一會就想出來了，反過來模擬，從y模擬到x，每次y都取出最小的邊把它變成能變成

的最大值，等到最小的邊都大于x了就結(jié)束。

#include<bits/stdc++.h>
using namespace std;
int x,y;
int a[3];
int main()
{cin>>x>>y;a[0]=a[1]=a[2]=y;int i=0;int ans=0;for(;;i++){ans++;a[i%3]=a[(i+1)%3]+a[(i+2)%3]-1;//printf("%d %d %d\n",a[0],a[1],a[2]);if(min(a[(i+1)%3],a[(i+2)%3])>=x) break;}cout<<ans<<endl;return 0;
}

View Code

?

D - Memory and Scores

題目大意：兩個人有初試分數(shù)a和b，有 t ?輪游戲，每輪游戲每人隨機得到[-k,k]中的一個數(shù)加

到自己的分數(shù)中，問你k輪以后，有多少個結(jié)果是 第一個人得分數(shù)大于第二個人的。結(jié)果對1e9+7取模。

?

思路：用dp[i][j] 表示進行到 i 輪，分數(shù)為得到的分數(shù)為j 的方案數(shù)。

狀態(tài)轉(zhuǎn)移方程，dp[i][j]=dp[i-1] [j-k]+dp[i-1][j-k+1]+...+dp[i-1][j+k]。

直接這樣寫可能會超時，我們考慮用前綴和優(yōu)化，即每一輪更新

的時候保存當前輪dp的前綴和，用于更新下一輪。最后就是計算

方案總數(shù)的問題了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2*1e5+1;
ll dp[101][N],a[N],b[N];
ll x,y,k,t;
const ll mod=1e9+7;
int main()
{cin>>x>>y>>k>>t;ll up=k*t*2;dp[0][k*t]=1;for(ll i=0;i<=up;i++){if(i==0) a[i]=dp[0][i];else a[i]=a[i-1]+dp[0][i];}ll *p=a,*q=b,*g;for(ll i=1;i<=t;i++){for(ll j=0;j<=up;j++){ll l=j-k,r=j+k;l=max((ll)0,l);r=min(up,r);ll t=dp[i][j];if(l==0) dp[i][j]=(dp[i][j]+p[r])%mod;else dp[i][j]=(dp[i][j]+p[r]-p[l-1]+mod)%mod;if(j==0) q[j]=dp[i][j]%mod;else q[j]=(dp[i][j]+q[j-1])%mod;}g=q;q=p;p=g;}ll ans=0;ll dis=y-x+1;for(ll i=0;i<=up;i++){ll now=i-dis;if(now>up) now=up;if(now>=0) ans=(ans+((dp[t][i])*p[now])%mod)%mod;}cout<<ans%mod<<endl;return 0;
}

View Code

?

E - Memory and Casinos

題目大意：有n個賭場，每個賭場你贏的概率為p，如果贏了你往右邊的賭場走，輸了往左邊的賭場走，

給你一個范圍 l 到 r 問你從 l 開始，最后在 r 贏且不在 l 輸?shù)母怕适嵌嗌?#xff0c;寫的時候真的不知道怎么寫。。

還是太菜了。

?

思路：我們可以用線段樹進行區(qū)間合并，我們記L( l , r )為從 l 開始最后在r贏不在且在 l 永遠不輸?shù)母怕?#xff0c;

R( l , r )為從 r 開始，最后在 r 贏，且永遠不在 l 輸?shù)母怕省Ｎ覀儗€段樹的每個節(jié)點保存當前區(qū)間的這

兩個值，每個節(jié)點保存該區(qū)間的 L 和 R 值。那么兩個區(qū)間該如何合并呢？

我們可以先考慮只有兩個點的情況 a 點和 b 點，求從 a 開始，最終在 b 點贏，且在 a 點永遠不輸?shù)母怕?#xff0c;

且 在 a 點贏的概率為p1，b 點為 p2，那么我們可以知道我們要求的概率就是一下式子的和

p1*p2 ? ? ? ? a(win) ? b(win)

p1 * ( ( 1 - p2 ) * p1 ) * p2 ? ? ? ?a(win) b(lose) a(win) b(win)

p1 * ( ( 1 - p2 ) * p1)^2 * p2 ? ? a(w) ( b(l) ?a(w) ?b(l) ?a(w) ) b(w)

.............

p1 * ( ( 1 - p2 ) * p1)^n * p2

求和就是等比數(shù)列求和。

那么對于兩個區(qū)間也是同理，對于兩個區(qū)間a，b，他們的L,R分別為 ?L1 , L2 , R1 ?R2，合并之后的 L 為 L3 ?R 為 R3

那么 L3 為以下式子的和

L1 * L2

L1 * ( ( 1 - L2 ) * R1 ) * L2

L1 * ( ( 1 - L2 ) * R1 )^2 ?* L2

............

L1 * ( ( 1 - L2 ) * R1 ) ^n * L2

?

R3 為以下式子的和

R2

( 1 - R2 ) * R1 * L2

( 1 - R2 ) * R1 *( ( 1 - L2 ) * R1 ) * L2

( 1 - R2 ) * R1 *( ( 1 - L2 ) * R1 )^2 * L2

.............

( 1 - R2 ) * R1 *( ( 1 - L2 ) * R1 )^n * L2

這樣就能完成線段樹的區(qū)間合并了。

#include<bits/stdc++.h>
#define pdd pair<double,double>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
const int N=1e5+5;
pdd st[N<<2];
int n,q;
pdd Merge(pdd x,pdd y)
{pdd ans;ans.fi=(x.fi*y.fi)/(1.0-x.se*(1.0-y.fi));ans.se=y.se+((1.0-y.se)*x.se*y.fi)/(1.0-(1.0-y.fi)*x.se);return ans;
}
void build(int l,int r,int rt)
{if(l==r){double a,b;scanf("%lf%lf",&a,&b);st[rt].fi=a/b; st[rt].se=a/b;return;}int m=(l+r)>>1;build(lson);build(rson);st[rt]=Merge(st[ls],st[rs]);
}
void updata(int l,int r,int rt,int x,double a,double b)
{if(l==r && r==x){st[rt].fi=a/b;st[rt].se=a/b;return;}int m=(l+r)>>1;if(x<=m) updata(lson,x,a,b);else updata(rson,x,a,b);st[rt]=Merge(st[ls],st[rs]);
}
pdd query(int L,int R,int l,int r,int rt)
{if(l>=L && r<=R) return st[rt];int m=(l+r)>>1;if(R<=m) return query(L,R,lson);else if(L>m) return query(L,R,rson);else return Merge(query(L,R,lson),query(L,R,rson));
}
int main()
{cin>>n>>q;build(1,n,1);while(q--){int op;scanf("%d",&op);if(op==1){int  x;double a,b;scanf("%d%lf%lf",&x,&a,&b);updata(1,n,1,x,a,b);}else{int l,r;scanf("%d%d",&l,&r);pdd ans=query(l,r,1,n,1);printf("%.12f\n",ans.fi);}}return 0;
}

View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/CJLHY/p/7240669.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #370 (Div. 2)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。