20170906模擬賽
啊，ditoly大牛的題真良心，我這種蒟蒻都rank4了23333
不過其實是可以再多拿10分的，巨神有幾組特殊數據忘出了，場面一度十分尷尬。
不管怎樣，加油吧！
T1：
切糕（cut）
【問題描述】
小R意外獲得了一塊切糕，他準備把切糕分給n個小伙伴。切糕的形狀是一個底邊長為a，高為b的等腰三角形。小R打算橫著或豎著切n-1刀把切糕切成面積相等的n塊分給小伙伴，請你告訴他要在哪些地方切。
【輸入格式】
輸入文件cut.in
輸入包含四個整數n,a,b,c，表示要切成n塊，切糕的三個頂點分別位于(0,0),(a,0),(a/2,b)，若c=0，表示要橫著切；若c=1，表示要豎著切。
【輸出格式】
輸出文件cut.out
輸出共n-1行，每行一個實數，從小到大輸出各切割處的位置，若c=0，每輸出一個整數a，表示在直線y=a處切一刀；若c=1，每輸出一個整數a，表示在直線x=a處切一刀。當你的輸出與標準輸出的絕對誤差不超過時，判為正確。
【樣例輸入1】
3 5 2 0
【樣例輸出1】
0.3670068381
0.8452994616
【樣例輸入2】
2 5 3 1
【樣例輸出2】
2.5
【數據范圍】
對于全部數據，2<=n<=1000，1<=a,b<=10^5；
對于50%的數據，c=0；
對于另外50%的數據，c=1。
題解：（這幾次比賽最良心題解）
首先考慮c=0的情況，如圖
圖中，S△AOC=n*S△ADE，易證△AOC相似△ADE，則h1=√n*b,h2=(√n/√2)*b,依此類推
接著考慮c=1的情況，可以直接剛出直線AO的斜截式y=b/(2*a)*x，就可以通過坐標計算出面積。x1=√[(a^2)/2*n],x2=√[(a^2*2)/2*n],依此類推
由于兩邊嚴格對稱，可以只計算一半，另一半用a去減。
詳細的過程還是得看代碼：（寫得實在是太臭了）
#include<cstdio> #include<cmath> typedef double d; int a,b,n,f; d l[2005]; int main(){ freopen("cut.in","r",stdin); freopen("cut.out","w",stdout); scanf("%d%d%d%d",&n,&a,&b,&f); if(f){ d k=(d)(b)/a,s=(d)(b)*a/2/n;l[n-1]=sqrt(s/k); for(int i=2;i<=n/2-(~(n&1));i++)l[n-i]=sqrt(s*i/k); if(n&1){ for(int i=1;i<=n/2;i++)printf("%.10lf\n",l[n-i]); for(int i=n/2+1;i<n;i++)printf("%.10lf\n",(d)(a)-l[i]); } else{ for(int i=1;i<n/2;i++)printf("%.10lf\n",l[n-i]); printf("%.10lf\n",(d)(a)/2); for(int i=n/2+1;i<n;i++)printf("%.10lf\n",(d)(a)-l[i]); } return 0; } d n1=sqrt((d)n);l[n-1]=(d)b-(d)(b)/n1; for(int i=2;i<n;i++)l[n-i]=(d)b-(d)(b)*sqrt((d)i)/n1; for(int i=1;i<n;i++)printf("%.10lf\n",l[i]); return 0; }
T2：
采購（buy）
【問題描述】
小R有一個愛好，他經常去雜貨市場上采購一些奇奇怪怪的物品。今天小R來到市場，發現有n個攤位，每個攤位出售不同的貨物，第i個攤位出售的貨物價格為ai。這些攤位的老板很奇怪，他們不喜歡你購買其他攤位的物品，如果你購買了k件其他攤位的物品，你在購買第i個攤位出售的物品時需要額外支付k*bi的錢，為了防止你買完一個攤位的物品后再去買另一家的物品，他們商量好要求你同時結賬，現在小R有m元錢，他想知道自己最多能買多少種不同的物品。
【輸入格式】
輸入文件buy.in
第一行兩個正整數n和m，表示攤位數和小R的錢數。
接下來n行，每行兩個非負整數ai,bi，意義同問題描述。
【輸出格式】
輸出文件buy.out
輸出一個非負整數，表示答案。
【樣例輸入】
3 7
1 3
2 1
3 0
【樣例輸出】
2
【數據范圍】
對于20%的數據，n<=20；
對于40%的數據，n<=1000；
對于另外10%的數據，bi=0；
對于另外20%的數據，所有bi均相等；
對于100%的數據，n,ai,bi<=100,000，m<=10^9。
題解：（真的沒時間不然傻逼二分早就打出來了）
比賽的時候只有10分鐘打T2了，只能剛了一個暴力了（誰知道有幾組特殊數據被吃了）
#include<cstdio> #include<algorithm> using std::sort; using std::max; typedef long long ll; int n,m,ans; int a[100005],b[100005]; void dfs(int st,ll sum,int cnt,ll bsum){ if(st==n+1){ ll tot=sum+bsum*cnt; if(tot<=m)ans=max(ans,cnt); return; } dfs(st+1,sum+a[st],cnt+1,bsum+b[st]); dfs(st+1,sum,cnt,bsum); } int main(){ freopen("buy.in","r",stdin); freopen("buy.out","w",stdout); scanf("%d%d",&n,&m); bool f=1; for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]),f=b[i]==0; if(n<21){ dfs(1,0ll,0,0ll); printf("%d\n",ans); return 0; } if(f){ sort(a+1,a+1+n); for(int i=1;i<=n;i++){ if(m<a[i])break; m-=a[i];ans++; } printf("%d\n",ans); return 0; } printf("%d\n",n); return 0; }
實際上看到題目和數據范圍就應該想到二分，可以直接用一個數組c記錄買mid個商品在某個鋪子上所花的錢，再sort一遍，貪心選取，check一遍。
結束了?。?！
#include<cstdio> #include<algorithm> using std::sort; #define mid (l+r>>1) typedef long long ll; int n,m,ans; int a[100005],b[100005]; ll c[100005]; int main(){ freopen("buy9.in","r",stdin); freopen("buy.out","w",stdout); scanf("%d%d",&n,&m);ll s;int l=0,r=n; for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]); while(l<=r&&!(s=0)){ for(int i=1;i<=n;i++)c[i]=1ll*b[i]*(mid-1)+a[i]; sort(c+1,c+1+n); for(int i=1;i<=mid;i++)s+=c[i]; if(s<=m)ans=mid,l=mid+1;else r=mid-1; } printf("%d\n",ans); return 0; }
（這是第一次暴力打的比正解長2333）
由于時間原因，T3暫時沒有打出來，請各位大佬諒解！
浙公網安備 33010602011771號