A - Captain Flint and Crew Recruitment

剛開始還想篩法求質數，最后發現是個腦筋急轉彎

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> using namespace std; int main() {IO;int T;cin>>T;while(T--){int x;cin>>x;if(x>30) {cout<<"YES"<<endl;if(x==36||x==40||x==44) cout<<6<<" "<<10<<" "<<15<<" "<<x-31<<endl;else cout<<6<<" "<<10<<" "<<14<<" "<<x-30<<endl;}else cout<<"NO"<<endl;}return 0; }

B - Captain Flint and a Long Voyage

$9$的二進制是$1001$，$8$的二進制是$1000$，想要刪去后剩下數最大只能讓二進制位數最長，因此只能用9和8拼湊，分析可知到剩下數最大時原數最小是$?\frac{n}{4}?$ 個$8$和$n??\frac{n}{4}?$個9組成。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> int main() {IO;int T;cin>>T;while(T--){int n;cin>>n;int a=(n+3)/4,b=n-a;while(b--) cout<<9;while(a--) cout<<8;cout<<endl;}return 0; }

剛開始做完不敢提交，怕掉分，結果做了兩個感覺不會掉分了就全交了（已經過了50min了）tcl，最終做了兩個還是掉分了，曲折是最美的???

C - Uncle Bogdan and Country Happiness

Happiness detectors are installed in each city to monitor the happiness of each person who visits the city.
這題以為不定時測幸福值，結果上面那句話是每個人只要經過該城市就會當作幸福值的測試數據。我哭了！！！
翻譯一下就是每個點測的幸福值總人數是子樹的總人數
那么分析可知good[u]+bad[u]=sz[u]和good[u]-bad[u]=happy[u]，即good[u]=happy[u]+sz[u]>>1，bad[u]=sz[u]-happy[u]。
不矛盾由以下條件

• good[u]人數不能小于0并且不是小數即①good[u]>=0②happy[u]+sz[u]必須是偶數
• bad[u]人數不能小于0
• 由于心情只能變差不能編號，那么子樹中心情好的人數一定小于子樹祖宗節點心情好的人數即sgood<=good[u]

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=200010; int h[N],e[N],ne[N],idx; int happy[N],cnt[N]; ll sz[N],good[N],bad[N]; int n,m; bool flag; void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } void dfs(int u,int fa) {int sgood=0;sz[u]=cnt[u];for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(j==fa) continue;dfs(j,u);sz[u]+=sz[j];sgood+=good[j];}good[u]=sz[u]+happy[u];if(good[u]&1||good[u]<0) flag=0;good[u]>>=1;if(good[u]<sgood) flag=0;bad[u]=sz[u]-happy[u];if(bad[u]<0) flag=0; } int main() {IO;int T;cin>>T;while(T--){cin>>n>>m;for(int i=1;i<=n;i++) h[i]=-1;idx=0;for(int i=1;i<=n;i++) cin>>cnt[i];for(int i=1;i<=n;i++) cin>>happy[i];for(int i=1;i<n;i++){int a,b;cin>>a>>b;add(a,b),add(b,a);}flag=1;dfs(1,-1);if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0; }

這題由于沒看清題，給自己造成了非常大的難度，希望以后認真看題，挖掘更多條件。

D -Captain Flint and Treasure

題中暗示說有向無環圖，那么基本就是拓撲排序了，如果該位置的值大于0那么肯定先加上他，它會使后面加的值變大。輸出就是如果值大于0說明對后面有影響先輸出正拓撲序輸出。如果值小于0那么它不能先輸出否則會對后面有影響因此逆拓撲序輸出。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #define debug(x) cout<<#x<<": "<<x<<" " #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int N=200010; int h[N],e[N],ne[N],idx; int din[N],q[N]; ll a[N]; int n; void add(int a,int b) {e[idx]=b;ne[idx]=h[a];h[a]=idx++; } void topsort() {int tt=-1,hh=0;for(int i=1;i<=n;i++)if(din[i]==0) q[++tt]=i;while(tt>=hh){int u=q[hh++];for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(a[u]>0) a[j]+=a[u];if(--din[j]==0) q[++tt]=j;}} } int main() {IO;memset(h,-1,sizeof h);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) {int b;cin>>b;if(b!=-1){add(i,b);din[b]++;}}topsort();ll res=0;for(int i=1;i<=n;i++) res+=a[i];cout<<res<<endl;for(int i=0;i<n;i++)if(a[q[i]]>0) cout<<q[i]<<" ";for(int i=n-1;i>=0;i--) if(a[q[i]]<=0) cout<<q[i]<<" ";cout<<endl;return 0; }

要加油哦~~

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。