20170906模拟赛

阳光穿透心脏的1/2处 2021-09-30 00:06 288阅读 0赞

啊，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的情况，如图![1129409-20170906223930257-977796380.png][]

图中，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去减。

详细的过程还是得看代码：（写得实在是太臭了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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

【样例输出】

【数据范围】

对于20%的数据，n<=20；

对于40%的数据，n<=1000；

对于另外10%的数据，bi=0；

对于另外20%的数据，所有bi均相等；

对于100%的数据，n,ai,bi<=100,000，m<=10^9。

题解：（真的没时间不然傻逼二分早就打出来了）

比赛的时候只有10分钟打T2了，只能刚了一个暴力了（谁知道有几组特殊数据被吃了）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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一遍。

结束了！！！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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暂时没有打出来，请各位大佬谅解！

转载于:https://www.cnblogs.com/Marser/p/7487538.html

[1129409-20170906223930257-977796380.png]: /images/20210725/9a7861fb74cf4a9ebb9832146a81126b.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20210725/2223e3b0f56b4649801c2aa95c5b4330.png