AtCoder Beginner Contest 333

A

題意

輸出n個n(n<=9)

代碼

#include<bits/stdc++.h>
using namespace std;
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)cout<<n;
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}

B

題意

給定一個正五邊形ABCDE，現在給定兩條邊問兩條邊是否相等

思路

在正五邊形里面邊長分為兩類,一類是相鄰的節點連邊（如AB,BC,CD,DE,EA）,另一類是不相鄰的節點連邊（如AC,AD,BD,BE,CE）如果兩條邊處在同一類中則邊長相等

代碼

#include<bits/stdc++.h>
using namespace std;
void solve(){string line1,line2;cin>>line1>>line2;int len1=abs(line1[1]-line1[0]);int len2=abs(line2[1]-line2[0]);if(len1==len2)cout<<"Yes\n";else if((len1+len2)%5==0)cout<<"Yes\n";else cout<<"No\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}

C

題意

一個集合A中有{1,11,111,1111,…}，需要在集合A中選出三個數（可以相同）相加后組成一個新的數x,將x放入集合B中，集合B內部按照從小到大的順序排列,問集合中第N小的元素是什么

思路

直接暴力三層循環選出三個元素相加后放入數組中，然后對整個數組排序即可

代碼

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve(){vector<int>res;for(int i=1;i<=1e18;i=10*i+1){for(int j=i;j<=1e18;j=10*j+1){for(int k=j;k<=1e18;k=10*k+1){res.push_back(i+j+k);}}}sort(res.begin(),res.end());int x;cin>>x;cout<<res[x-1]<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}

D

題意

給定一棵樹，每次可以刪除一個葉子節點及其相連邊,問至少需要刪多少次才能刪除節點1

思路

如果1是葉子節點,那么可以直接1步刪除

考慮整棵樹以1為根,如果要使得1號節點被刪除,就意味著要刪到1號節點為葉子節點的時候,那么對于1號節點的所有兒子節點為根的子樹來說,這些子樹最多只能保留一個,剩余的子樹上的節點需要全部刪除，考慮到刪除節點要最小,所以我們保留1號節點的兒子節點中最大的那一棵子樹即可。求子樹大小簡單寫一個dfs即可

(如圖：子樹1>子樹3>子樹4>子樹2,那么最優方案 一定是把子樹1保留,剩下所有子樹上的節點全部刪除)

代碼

#include<bits/stdc++.h>
using namespace std;
const int mxn=1e6+5;
int siz[mxn];
vector<int>edge[mxn];
void dfs(int u,int fa){siz[u]=1;for(auto v:edge[u]){if(v==fa)continue;dfs(v,u);siz[u]+=siz[v];}
}
void solve(){int n;cin>>n;for(int i=1;i<n;i++){int u,v;cin>>u>>v;edge[u].push_back(v);edge[v].push_back(u);}dfs(1,0);int res=n-1;for(auto v:edge[1])res=min(res,n-siz[v]);cout<<res<<"\n";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}

E

題意

Takahashi在冒險中遇到N個事件，每個事件由（op,x）組成,如果op=1說明這個地方有一瓶類型為x的藥水,如果op=2說明遇到怪物并且需要用x類型藥水才能打敗他,否則會被打敗

問在滿足不被怪物打敗的前提下,需要用背包裝藥水,問背包的容量最小為多少

思路

考慮貪心，每瓶藥在打怪之前最后出現位置才會拿。那么我們只需要從最后往前找即可

代碼

#include<bits/stdc++.h>
using namespace std;
void solve(){int n;cin>>n;vector<pair<int,int>>a(n+10);for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;vector<int>now(n+10,0);//在這之前需要取的藥vector<int>vis(n+10,0);//是否取for(int i=n;i>=1;i--){if(a[i].first==2)now[a[i].second]++;else{if(now[a[i].second]>=1)now[a[i].second]--,vis[i]=1;}}for(int i=1;i<=n;i++){if(now[i]>0){cout<<"-1\n";return;}}int maxv=0,nowv=0;//最大容量for(int i=1;i<=n;i++){if(a[i].first==1)nowv+=vis[i];else nowv--;maxv=max(maxv,nowv);}cout<<maxv<<"\n";for(int i=1;i<=n;i++){if(a[i].first==1)cout<<vis[i]<<" ";}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}

F

題意

有序號為1,2…n號人在排隊, 每一次對隊首的人進行操作,隊首的人有1/2的概率出隊，還有1/2的概率回到隊尾,問第i個人是最后一個留在隊列中的概率

思路

消元類概率 dp 經典問題

我們發現實際上無論隊伍里面的人序號是什么，我們只關心當前隊列中有多少個人,最后勝出的是排在第幾個位置上的人

先考慮我們當前知道什么?我們知道如果隊列中只有一個人,那么他必勝

再考慮我們需要求什么?在有n個人的隊伍中每個位置上的人獲勝的概率

所以我們現在已知最后的結束狀態值，我們想求初始狀態的值

因為操作可逆,所以我們可以把題意改成每一次有1/2的概率在隊首加上一個人,有1/2的概率將隊尾元素放到隊首。那么我們就可以很順其自然的推狀態

令$dp[i][j]$為當前中有i個人，其中第j個人最后勝利的概率

那么就有轉移方程$dp[i][j]=\frac{1}{2}\times dp[i?1][j?1]+\frac{1}{2}\times dp[i][j?1]$

（當前狀態可以是原先狀態在隊首加上一個人,也可以是將隊尾的人放到隊首得到的）

但我們會發現這樣轉移有一個位置不對，如果我們當前要求的是隊伍中第一個人獲勝的概率（即求dp[i][1]）,那么這個人顯然不可能是從原先第0個人轉移過來的（dp[i-1][j-1]=dp[i-1][0]=0）,而是從隊尾移到隊首的（即是從dp[i][i]）轉移過來的（在實際的意義中我們其實也不難發現隊首的這個人出隊以后就不會對后續隊列中的人產生影響）

所以最終的轉移方程應該為
$$dp[i][j]=\{\begin{array}{ll}\frac{1}{2}\times dp[i?1][j?1]+\frac{1}{2}\times dp[i][j?1]& (j\ne 1)\\ \frac{1}{2}\times dp[i][i]& (j=1)\end{array}$$
狀態轉移方程的確定僅僅是開始

我們意識到這個轉移方程不滿足無后效性的遞推條件

因為在轉移中dp[i][1]需要用到dp[i][i]的狀態，dp[i][2]要用到dp[i][1]的狀態…dp[i][i]要用到dp[i][i-1]的狀態，那么很成功的一下子整層狀態都鎖住了

但我們發現成環的部分i都相同，也就是說是在同一層的狀態，我們能否假定一個當前未知的狀態的值把環上所有狀態表示出來？

答案是肯定的

假定dp[i][1]是已知條件,則有
$$?\begin{array}{l}dp[i][1]=dp[i][1]\\ dp[i][2]=\frac{dp[i?1][1]}{2}+\frac{dp[i][1]}{2}\\ dp[i][3]=\frac{dp[i?1][2]}{2}+\frac{dp[i][2]}{2}=\frac{dp[i?1][2]}{2}+\frac{\frac{dp[i?1][1]}{2}+\frac{dp[i][1]}{2}}{2}=\frac{dp[i?1][2]}{2}+\frac{dp[i?1][1]}{4}+\frac{dp[i][1]}{4}\\ ....\\ dp[i][i]=\frac{dp[i?1][i?1]}{2}+\frac{dp[i?1][i?2]}{4}+\frac{dp[i?1][i?3]}{8}+....+\frac{dp[i?1][1]}{2^{i?1}}+\frac{dp[i][1]}{2^{i?1}}\end{array}$$

$$\begin{array}{rl}& \text{又因為?}dp[i][1]=\frac{1}{2}\times dp[i][i]\\ & \text{所以就有?}dp[i][1]=\frac{dp[i?1][i?1]}{4}+\frac{dp[i?1][i?2]}{8}+\frac{dp[i?1][i?3]}{16}+?+\frac{dp[i?1][1]}{2^i}+\frac{dp[i][1]}{2^i}\\ & \text{即?}dp[i][1]=\sum _{k=1}^{i?1}\frac{1}{2^{i?k+1}}\times dp[i?1][k]+\frac{dp[i][1]}{2^i}\\ & \text{移項后得到?}(2^i?1)\times dp[i][1]=2^i\times \sum _{k=1}^{i?1}\frac{1}{2^{i?k+1}}\times dp[i?1][k]\\ & \text{即?}dp[i][1]=\frac{2^i}{2^i?1}\times \sum _{k=1}^{i?1}\frac{1}{2^{i?k+1}}\times dp[i?1][k]\end{array}$$

經過這么一番處理我們發現，每一層的dp[i][1]實際上只和i-1層的狀態有關,所以可以直接處理出來

那么已知dp[i][1]的狀態,第i層的所有狀態也就可以遞推處理出來了

至此我們可以將轉移方程更新為：
$$dp[i][j]=\{\begin{array}{ll}\frac{1}{2}\times dp[i?1][j?1]+\frac{1}{2}\times dp[i][j?1]& (j\ne 1)\\ \frac{2^i}{2^i?1}\times {\sum }_{k=1}^{i?1}\frac{1}{2^{i?k+1}}\times dp[i?1][k]& \end{array}$$
初始已知$dp[1][1]=1$，最后要求的是$f[n][1],f[n][2],f[n][3]......f[n][n]$

代碼

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353,mxn=3e3+5;
int dp[mxn][mxn];
int fastpow(int a,int power=mod-2){int res=1;while(power){if(power&1)res=res*a%mod;a=a*a%mod;power>>=1;}return res;
}
int inv(int x){return fastpow(x);}
void solve(){int n;cin>>n;int inv2=inv(2);dp[1][1]=1;for(int i=2;i<=n;i++){for(int k=1;k<=i-1;k++)dp[i][1]+=inv(fastpow(2,i-k+1))*dp[i-1][k]%mod,dp[i][1]%=mod;//先求dp[i][1]dp[i][1]=dp[i][1]*fastpow(2,i)%mod*inv((fastpow(2,i)-1+mod)%mod)%mod;for(int j=2;j<=i;j++)dp[i][j]=(inv2*dp[i-1][j-1]%mod+inv2*dp[i][j-1]%mod)%mod;}for(int i=1;i<=n;i++)cout<<dp[n][i]<<" ";
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T__=1;//cin>>T__;while(T__--)solve();return 0;
}