A?An abandoned sentiment from past

水題

#include<bits/stdc++.h>using namespace std;int a[300],b[300],n,k; bool cmp(int a,int b) {return a>b; } int main() {//freopen("t.txt","r",stdin);scanf("%d%d",&n,&k);for(int i=0;i<n;i++) scanf("%d",&a[i]);for(int i=0;i<k;i++) scanf("%d",&b[i]);sort(b,b+k,cmp );for(int i=0,j=0;i<n&&j<k;i++){if(a[i]==0)a[i]=b[j++];}for(int i=1;i<n;i++)if(a[i]<=a[i-1]){printf("YES\n");return 0;}printf("NO\n");return 0; }

B?An express train to reveries

水題

#include<bits/stdc++.h>using namespace std; const int N=2000; int a[N],b[N],ans[N],color[N],n,vis[N];int main() {//freopen("t.txt","r",stdin);scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);for(int i=0;i<n;i++)scanf("%d",&b[i]);int sum=0;vector<int>ad;ad.clear();for(int i=0;i<n;i++)if(a[i]==b[i])ans[i]=a[i],sum++,color[a[i]]++;else ad.push_back(i);vector<int>numa;numa.clear();for(int i=1;i<=n;i++)if(color[i]==0)numa.push_back(i);if(sum==n-1){ans[ad[0]]=numa[(int)(numa.size()-1)];}else{if((a[ad[0]]==numa[0]&&b[ad[1]]==numa[1])||(b[ad[0]]==numa[0]&&a[ad[1]]==numa[1])){ans[ad[0]]=numa[0];ans[ad[1]]=numa[1];}else{ans[ad[1]]=numa[0];ans[ad[0]]=numa[1];}}for(int i=0;i<n-1;i++)printf("%d ",ans[i]);printf("%d\n",ans[n-1]);return 0; }

C?An impassioned circulation of affection

水題

#include<bits/stdc++.h>using namespace std;int dp[26][1510][1510],maxx[26][1510],ti[26][1510],n,q; char ss[1510]; int main() {//freopen("t.txt","r",stdin);scanf("%d",&n);scanf("%s",&ss);for(int i=0;i<26;i++)for(int j=0;j<n;j++){int k=j;while(k<n&&ss[k]==char(i+'a'))ti[i][j]++,k++;}for(int i=0;i<26;i++){for(int j=0;j<n;j++){for(int k=1;j+k<=n;k++){if(dp[i][j][k-1]>=n){dp[i][j][k]=n;maxx[i][k]=max(maxx[i][k],dp[i][j][k]);continue;}dp[i][j][k]=dp[i][j][k-1]+ti[i][min(n,j+dp[i][j][k-1])]+1+ti[i][min(n,j+dp[i][j][k-1]+ti[i][j+dp[i][j][k-1]]+1)];if(dp[i][j][k]>n)dp[i][j][k]=n;maxx[i][k]=max(maxx[i][k],dp[i][j][k]);}}}//memset(dp,0,sizeof(dp));scanf("%d",&q);for(int i=0;i<q;i++){char c;int jk;getchar();scanf("%d %c",&jk,&c);int num=c-'a';printf("%d\n",min(n,maxx[num][jk]));}return 0; }

D?An overnight dance in discotheque

比較難的一道貪心題

可以證明 只要把最底層的圓扔到另一個(gè)半場(chǎng) 就達(dá)到了最優(yōu)態(tài)?

為什么呢？

在這個(gè)狀態(tài)下無論我們?cè)趺匆苿?dòng) 都無法讓答案變好。

簡(jiǎn)單證明一下：

我們可以把任意幾個(gè)圓（順序無關(guān)）扔到底層圓上，

這幾個(gè)圓組成的覆蓋，對(duì)某些面積（sb）進(jìn)行了偶數(shù)次覆蓋，對(duì)某些面積（sa）進(jìn)行了奇數(shù)次覆蓋。

而被覆蓋的最底層圓，所有的面積都被奇數(shù)次（1次）覆蓋，而偶數(shù)次的覆蓋無法改變奇偶性，

奇數(shù)次的覆蓋會(huì)將原本所有的奇數(shù)次覆蓋變成偶數(shù)次覆蓋（同時(shí)將偶數(shù)次覆蓋變成奇數(shù)次）。

所以我們想要移動(dòng)的這些圓無論處在什么位置 都比放在底層圓上對(duì)答案貢獻(xiàn)大?

所以往單獨(dú)在另一半場(chǎng)的底層圓（最大圓）移動(dòng)任何圓的集合都不會(huì)讓答案變好。

而所有的狀態(tài)都可以從這個(gè)狀態(tài)移動(dòng)得到！

代碼很簡(jiǎn)單（我這個(gè)蒟蒻想了半天DP方程 然而 O（n）貪心）

#include <bits/stdc++.h> using namespace std;typedef long long LL;const long double pi = 3.14159265358979;#define N 100010int x[N], y[N], r[N], dep[N], n;LL dist(int x, int y){ return 1ll * x * x + 1ll * y * y; }int main(){///freopen("in.txt", "r", stdin);scanf("%d", &n);for(int i = 1; i <= n; i ++){scanf("%d %d %d", x + i, y + i, r + i);}for(int i = 1; i <= n; i ++){for(int j = 1; j <= n; j ++)if(r[j] > r[i]) {if( dist( x[i] - x[j], y[i] - y[j]) <= 1ll * r[j] * r[j] ){dep[i] ++;}}}LL ans = 0;for(int i = 1; i <= n; i ++){if(dep[i] == 0) ans += 1ll * r[i] * r[i];else if(dep[i] & 1) ans += 1ll * r[i] * r[i];else ans -= 1ll * r[i] * r[i];}long double res = pi * ans;printf("%.10lf\n", (double) res);}

　　

E?An unavoidable detour for home

?非常具有技巧性的一道計(jì)數(shù)題

題目給定一個(gè)圖的某些性質(zhì)，要求我們構(gòu)造一個(gè)層次圖。每個(gè)點(diǎn)要么連接2個(gè)點(diǎn)要么連接3個(gè)點(diǎn)。

求不同的構(gòu)圖方法數(shù)量。

我們通過分層來計(jì)數(shù)。

solve(i,f)表示解決a[i]之后的序列答案，且第一層有f個(gè)元素。

connect(two,three,after)表示對(duì)于當(dāng)前層次，有two個(gè)節(jié)點(diǎn)需連接2個(gè)節(jié)點(diǎn)，有three個(gè)節(jié)點(diǎn)要連接3個(gè)點(diǎn)，且構(gòu)圖后有after個(gè)可連接位（即下一層需要after個(gè)節(jié)點(diǎn)）

剩下的看代碼吧 關(guān)鍵地方注釋了 connect函數(shù)的轉(zhuǎn)移非常有趣

#include <bits/stdc++.h> using namespace std; using LL=long long; #define f(i,n) for(LL i=0;i<(n);i++)const LL M=1e9+7;LL n,d[50],cn[51][51][51],sl[51][51],n3[51];LL connect(LL twos, LL threes, LL after){if(twos<0||threes<0) return 0;LL &cur=cn[twos][threes][after];if(cur!=-1) return cur;if(after) return cur=(twos*connect(twos-1,threes,after-1)%M//拿出一個(gè)two +threes*connect(twos+1,threes-1,after-1)%M)%M;//拿出一個(gè)three 向下有一個(gè)空位 相當(dāng)于增加了一個(gè)two if(twos) return cur=((twos-1)*connect(twos-2, threes, after)%M//選出一對(duì)two互相連接 +threes*connect(twos,threes-1,after)%M)%M;//選出一個(gè)three和一個(gè)two連接后變成一個(gè)two if(!threes) return 1;return cur=((threes-1)*(threes-2)/2)*connect(2,threes-3,0)%M;//選出三個(gè)three后相當(dāng)于增加了2個(gè)two }LL solve(LL i, LL f){if(i+f>n) return 0;if(i==n) return f==0;if(f==0) return 0;LL &cur=sl[i][f];if(~cur) return cur;LL r=0, threes=n3[i+f]-n3[i], twos=f-threes;for(LL cl=0;cl<=n-(i+f);cl++)r = (r+connect(twos, threes, cl)*solve(i+f,cl)%M)%M;return cur=r; }main(){freopen("t.txt","r",stdin);ios::sync_with_stdio(0),cin.tie(0);memset(cn,-1,sizeof(cn));memset(sl,-1,sizeof(sl)); cin>>n;f(i,n){cin>>d[i];n3[i+1]=n3[i]+(d[i]==3);}cout<<solve(1,d[0])<<'\n'; }

　　

倆小時(shí)做了三道水題 還被Hack了一道 該拿什么拯救我的coding? 我這么菜可怎么辦？？

轉(zhuǎn)載于:https://www.cnblogs.com/heisenberg-/p/6959619.html

總結(jié)

以上是生活随笔為你收集整理的codeforces round 418 div2 补题 CF 814 A-E的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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