文章目錄

• 前言
• CF54A Presents
• • $\text{Description}$
  • $\text{Solution}$
• CF54B Cutting Jigsaw Puzzle
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF54C First Digit Law
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF54D Writing a Song
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$
• CF54E Vacuum Сleaner
• • $\text{Description}$
  • $\text{Solution}$
  • $\text{Code}$

前言

整場比賽的數(shù)據(jù)范圍都很良心
A是水題.
B是惡心的模擬，有一點鍛煉代碼能力
C是很水的數(shù)數(shù)套貪心題
D是被數(shù)據(jù)范圍禍害了的構(gòu)造題
E是一個很適合（像我一樣）的不會計算幾何的人做的計算幾何題，只需要基本的向量知識

CF54A Presents

$\text{Description}$

你有 $n$ 天時間，在這 $n$ 天內(nèi)，在給出的 $c$ 個特定日期一定會得到禮物，此外，如果連續(xù) $k$ 天沒有收到禮物，就會得到禮物.
$1\le k\le n\le 365,1\le c\le n$

$\text{Solution}$

如果 $n\le 10^{18}$，那可能還會有一些細節(jié)需要處理.
但是這個垃圾數(shù)據(jù)范圍，直接模擬就行了…

#include<bits/stdc++.h> using namespace std; #define ll long long //#define double long double #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k; int a[400]; signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();k=read();m=read();for(int i=1;i<=m;i++){int x=read();a[x]=1;}int now=0,tot(0);for(int i=1;i<=n;i++){++now;//printf("i=%d now=%d\n")if(now==k||a[i]){++tot;now=0;}}printf("%d\n",tot);return 0; } /**/

CF54B Cutting Jigsaw Puzzle

$\text{Description}$

有一個 $n\times m$ 的字符串矩形，你可以指定一個大小 $(x,y)$，然后把矩形分割成 $\frac{n}{x}\times \frac{m}{y}$ 個小矩形（$x|n,y|m$），若所有的小矩形（可以旋轉(zhuǎn)，但不能翻轉(zhuǎn)）后均互不相同，則稱這種分割是合法的.
求合法 分割的方案總數(shù)以及子矩形最小的分割方案.
$n,m\le 20$.

$\text{Solution}$

一道復(fù)雜度怎么做應(yīng)該都太不可能 TLE 的模擬題.
手玩出旋轉(zhuǎn)對坐標的映射關(guān)系.
分別枚舉因數(shù)暴力哈希 check 即可.
時間復(fù)雜度大概是 $O(n^3)$.

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long //#define double long double #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=2e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k; char s[25][25]; int key=31; struct node{char a[25][25];inline ull calc(){ull res(0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) res=res*key+a[i][j]-'A'+1;}return res;} }now,pre,w[6]; map<ull,int>mp; int mn,x,y,res,num; bool work(int a,int b,int x,int y){//memset(now.a,0,sizeof(a));num=0;for(int i=1;i<=max(n,m);i++){for(int j=1;j<=max(n,m);j++) now.a[i][j]=0;}for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){//printf(" %d %d c=%c\n",a+i-1,b+j-1,s[a+i-1][b+j-1]);now.a[i][j]=s[a+i-1][b+j-1];}}/*printf("(%d %d)\n",a,b);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) printf("%c",now.a[i][j]?now.a[i][j]:'0');putchar('\n');}printf("calc=%llu\n",now.calc());*/if(mp[now.calc()]) return false;w[++num]=now;for(int o=1;o<=3;o++){memcpy(pre.a,now.a,sizeof(now.a));for(int i=1;i<=max(n,m);i++){for(int j=1;j<=max(n,m);j++) now.a[i][j]=0;}for(int i=1;i<=x;i++){for(int j=1;j<=y;j++){//printf(" (%d %d)-> (%d %d)\n",i,j,j,x-i+1);now.a[j][x-i+1]=pre.a[i][j];}}swap(x,y); if(o==2||x==y){/*for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) printf("%c",now.a[i][j]?now.a[i][j]:'0');putchar('\n');}printf("calc=%llu\n",now.calc());*/if(mp[now.calc()]) return false;w[++num]=now;}}for(int i=1;i<=num;i++) mp[w[i].calc()]=1;return true; } bool check(int x,int y){//printf("\nx=%d y=%d\n",x,y);mp.clear();for(int i=1;i<=n;i+=x){for(int j=1;j<=m;j+=y){if(!work(i,j,x,y)) return false;}}return true; } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();m=read();mn=2e9;for(int i=1;i<=n;i++){scanf(" %s",s[i]+1);}for(int i=1;i<=n;i++){if(n%i) continue;for(int j=1;j<=m;j++){if(m%j) continue;if(check(i,j)){++res;//printf("------------ok! (%d %d)\n",i,j);if(mn>i*j){mn=i*j;x=i;y=j;}}}}printf("%d\n%d %d\n",res,x,y);return 0; } /**/

CF54C First Digit Law

$\text{Description}$

給出 $n$ 個數(shù)，然后給出 $n$ 行，每行 $l_i,r_i$，代表第 $i$ 個數(shù)在區(qū)間 $[l_i,r_i]$ 中，求一個概率使得這 $n$ 個數(shù)中有 $k\%$ 的數(shù)是 $1$ 開頭的.
$n\le 1000,1\le l_i\le r_i\le 10^{18}$.

$\text{Solution}$

設(shè) $f_x$ 為 $[1,x]$ 符合條件的數(shù)的個數(shù)，$su{m}_x={\sum }_{x=0}^{x}10^i$，$w_x$ 為滿足 $10^i\le x$ 的最大的 $i$.
就有：
$$f_x=\min (2\times 10^{w_x}?1,x)?10^{w_x}+1+su{m}_{w_x?1}$$

那么第 $i$ 個數(shù)符合條件的概率就是 $\frac{f_{r_i}?f_{l_i?1}}{r_i?l_i+1}$.
求出每個變量的概率之后，簡單 $n^2$ dp即可.
細節(jié)上，注意 $10^{18}$ 乘 $10$ 會爆 longlong，所以求 $w_x$ 判斷時要乘轉(zhuǎn)除.

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long //#define double long double #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1050; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k; ll sum[20],mi[20]; double dp[N][N],p[N]; ll calc(ll x){if(x==0) return 0;int o=0;while(x/mi[o]>=10) ++o;return (o?sum[o-1]:0)+min(x,2*mi[o]-1)-mi[o]+1; } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifmi[0]=sum[0]=1;for(int i=1;i<=18;i++){mi[i]=mi[i-1]*10;sum[i]=sum[i-1]+mi[i];}n=read();for(int i=1;i<=n;i++){ll l=read(),r=read();p[i]=1.0*(calc(r)-calc(l-1))/(r-l+1);//printf("i=%d p=%lf\n",i,p[i]);}dp[0][0]=1;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){dp[i+1][j+1]+=dp[i][j]*p[i+1];dp[i+1][j]+=dp[i][j]*(1-p[i+1]);}}int k=read();double res=0.0;for(int i=(n*k+99)/100;i<=n;i++) res+=dp[n][i];printf("%.10lf",res);return 0; } /**/

CF54D Writing a Song

$\text{Description}$

要求構(gòu)造一個字符串 $s$，滿足該串長度為 $n$，只出現(xiàn)字母表中前 $k$ 個字母，并且在指定位置必須出現(xiàn)指定字符串 $p$，或者報告無解.
$n\le 100$.

$\text{Solution}$

第一眼：毒瘤計數(shù)題…
看完題意：惡心貪心題…
看到數(shù)據(jù)范圍：就這？
或許貪心構(gòu)造還是可做的，但是對于這個數(shù)據(jù)范圍，我們不必冒著 WA 的風險動腦.
首先 KMP 預(yù)處理一下，然后設(shè)計 $d{p}_{i,j}$ 表示填到第 $i$ 位，匹配到 $p$ 的第 $j$ 位是否合法.
轉(zhuǎn)移暴力在 kmp 上跳即可，這數(shù)據(jù)范圍也不需要預(yù)處理加速了.
對于輸出方案，dp 過程中記錄一下轉(zhuǎn)移路徑即可.

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long //#define double long double #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=105; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k; int dp[N][N],frm[N][N],id[N][N]; int p[N],jd[N]; char s[N]; void kmp(){p[1]=0;for(int i=1,j=0;i<m;i++){while(j&&s[i+1]!=s[j+1]) j=p[j];if(s[i+1]==s[j+1]) ++j;p[i+1]=j;}//for(int i=1;i<=m;i++) printf("i=%d p=%d\n",i,p[i]);return; } int find(int j,int id){char c='a'+id-1;while(j&&s[j+1]!=c) j=p[j];if(s[j+1]==c) ++j;return j; } void print(int k,int pl){if(!k) return;print(k-1,frm[k][pl]);putchar('a'+id[k][pl]-1); } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();k=read();scanf(" %s",s+1);m=strlen(s+1);for(int i=1;i<=n-m+1;i++) scanf("%1d",&jd[i+m-1]);kmp();dp[0][0]=1;for(int i=0;i<=n;i++){ if(jd[i]){if(!dp[i][m]){printf("No solution\n");return 0;}for(int j=0;j<m;j++) dp[i][j]=0;//dp[i][p[m]]=1;frm[i][p[m]]=dp[i][m];id[i][p[m]]=id[i][m];}else{dp[i][m]=0;}if(i==n) break;for(int j=0;j<=m;j++){if(!dp[i][j]) continue;for(int p=1;p<=k;p++){int to=find(j,p);//printf("k=%d (%d %d) -> (%d %d)\n",p,i,j,i+1,to);dp[i+1][to]=1;frm[i+1][to]=j;id[i+1][to]=p;}}}for(int i=0;i<=m;i++){if(dp[n][i]){print(n,i);return 0;}}printf("No Solution\n");return 0; } /**/

CF54E Vacuum Сleaner

$\text{Description}$

對于一個 $n$ 個結(jié)點的凸包形狀的吸塵器，問你這個吸塵器在清理矩形的角落時，遺留下的最小面積，可以旋轉(zhuǎn).
$n\le 4\times 10^4$.

$\text{Solution}$

可能是入門難度的計算幾何了.
不難發(fā)現(xiàn)最優(yōu)的時候墻一定和一條邊重合（可以通過畫圓證明）.
那么我們就暴力枚舉這條邊，雙指針維護墻另一條邊過的頂點即可.
最后把所有點翻轉(zhuǎn)過來再做一次.
實現(xiàn)上的技巧：

尋找另一條墻邊過的點可以通過判斷向量在當前邊上投影的大小來實現(xiàn).

計算面積時用墻的三角形面積減去多邊形兩個頂點截出的多邊形面積，這個多邊形面積可以處理一個面積關(guān)于頂點叉積的前綴和再減去這兩個頂點叉積求出（建議畫圖理解）.（算出的面積 可能為負，所以要取絕對值）

墻角三角形的邊長一條可以通過投影來求，另一條勾股定理即可.

具體實現(xiàn)建議參考代碼理解.

$\text{Code}$

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long //#define double long double #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1e5+100; const int mod=1e9+7; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m,k; struct P{double x,y; }p[N]; inline P operator + (P a,P b){return (P){a.x+b.x,a.y+b.y};} inline P operator - (P a,P b){return (P){a.x-b.x,a.y-b.y};} inline double operator * (P a,P b){return a.x*b.x+a.y*b.y;} inline double operator ^ (P a,P b){return a.x*b.y-a.y*b.x;} inline double dis(P a,P b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} inline double calc(double x,double y){return sqrt(x*x-y*y);} double sum[N]; double solve(){double res=2e18;for(int i=n+1;i<=n+n;i++) p[i]=p[i-n];for(int i=2;i<=n+n;i++) sum[i]=sum[i-1]+(p[i]^p[i-1])/2;int j=1;for(int i=1;i<=n;i++){j=max(j,i+1);while(j+1<=n*2&&(p[i+1]-p[i])*(p[j+1]-p[i])>=(p[i+1]-p[i])*(p[j]-p[i])) ++j;if(j==i+1) res=0;if(j>2*n) break;double s=sum[j]-sum[i]+(p[i]^p[j])/2;double x=(p[j]-p[i])*(p[i+1]-p[i])/dis(p[i+1],p[i]);double y=calc(dis(p[i],p[j]),x);res=min(res,x*y/2-abs(s));//printf("i=%d j=%d s=%lf x=%lf y=%lf res=%lf\n",i,j,s,x,y,x*y/2-s);}return res; } signed main(){#ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout);#endifn=read();for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read();double ans=solve();reverse(p+1,p+1+n);ans=min(ans,solve());printf("%.10lf\n",ans);return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的CodeForces:54的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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