2017.10.10 NOIP模拟赛

题解 套题

目录

• 2017.10.10 NOIP模拟赛
  • 排队
    • 思路
    • 代码
  • 蛋糕
    • 思路
    • 代码
  • 差异
    • 思路
    • 代码

排队

思路

• 这题看似是人类智慧题，其实就是个构造；
• 显然我们一定可以确定最矮的人在哪，因为任何人都比他高，所以若他对应的数是$cnt_i$则他就在$cnt_i+1$处；
• 之后我们就可以确定第二矮的，第三矮的。。。
• 可以加个树状数组并二分答案优化到$O(n \log^2 n)$，但$O(n^2)$就可以了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
const int MAXN=5005;
int n;
int cnt[MAXN],ans[MAXN];
int main(){
#ifdef DEBUG
    setIO("a");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(cnt[i]);
    for(int i=1;i<=n;++i){
        for(int j=1,k=0;j<=n;++j){
            if(ans[j]) continue;
            if(++k==cnt[i]+1){
                ans[j]=i;
                break;
            }
        }
    }
    for(int i=1;i<=n;++i)
        write(ans[i],' ');
    return 0;
}

蛋糕

思路

• 考虑分别统计在大的里和在小的里，一减即可；
• 只考虑大正方形则有$(x+1)\times(y+1)$个；
• 设在这个小正方形里横竖切的个数分别为$cntx,cnty$，则产生了$\max(cntx-1,0)\times\max(cnty-1,0)$个空正方形，因为外面的那一圈可以连到大正方形上，并且要避免$cnt$减成负的；
• 但是还要特判只切了一个方向的，只要不弄混就很容易切了（不像我orz）。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <cmath>
#include <algorithm>
using std::abs;
using std::max;
const int MAXXY=5005;
int n,m,x,y,ans,cntx,cnty;
int posx[MAXXY],posy[MAXXY];
int main(){
#ifdef DEBUG
    setIO("b");
#endif
    int T;
    read(T);
    while(T--){
        read(n),read(m);
        read(x),read(y);
        for(int i=1;i<=x;++i)
            read(posx[i]);
        for(int i=1;i<=y;++i)
            read(posy[i]);
        cntx=cnty=0;
        for(int i=1;i<=x;++i){
            if(abs(posx[i])<=m) ++cntx;
        }
        for(int i=1;i<=y;++i){
            if(abs(posy[i])<=m) ++cnty;
        }
        ans=0;
        if((!cntx || !cnty) && (cntx || cnty)) ans+=max(cntx-1,cnty-1);
        cntx=max(cntx-1,0),cnty=max(cnty-1,0);
        ans+=(x+1)*(y+1)-cntx*cnty;
        write(ans,'\n');
    }
    return 0;
}

差异

思路

• 考虑如果$b$是一个数而不是数列的话，$b=\overline{a}$时差异度最小（就是方差吗，如果$b \neq\overline{a}$的话，相当于在$a$中添了一个数$a'$，使$\overline{a}'=b$，且$a' \neq\overline{a}$，那$a$数列的离散程度变大，方差更大）；
• 那么，现在$b$是一个数列，显然如果不考虑限制，$b_i=a_i$最优，进一步可以推出，将$a$分成尽可能多的段，$b_i$分别是那些段的平均数最优；
• 现在$b$有了限制，我们可以贪心的构造，让$b$满足条件的情况下将$a$分成尽可能多的段即可；
• 知道了这些，实现具体看代码就能明白了。

代码

#include <cstdio>
#include <cctype>
#include <string>
using std::string;
inline void setIO(string file){
    string in=file+".in",out=file+".out";
    freopen(in.c_str(),"r",stdin);
    freopen(out.c_str(),"w",stdout);
}
template<typename type>
inline void read(type &x){
    int pm=1; char c;
    do{
        c=getchar();
        if(c=='-') pm=-1;
    }while(!isdigit(c));
    x=c^'0';
    while(c=getchar(),isdigit(c))
        x=x*10+(c^'0');
    x*=pm;
}
template<typename type>
void write(type x,char c=0){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10|'0');
    if(c) putchar(c);
}
#include <algorithm>
#include <iostream>
#include <cmath>
using std::__gcd;
using std::ostream;
using std::cout;
using std::abs;
const int MAXN=200005;
int n,tot;
int a[MAXN],lp[MAXN],rp[MAXN];
long long sum[MAXN];
struct frac{
    long long up,dwn;
    frac(long long up=0,long long dwn=1):up(up),dwn(dwn){
        if(this->dwn<0) this->up=-this->up,this->dwn=-this->dwn;
        long long gcd=__gcd(abs(this->up),abs(this->dwn));
        this->up/=gcd,this->dwn/=gcd;
    }
    friend bool operator> (frac a,frac b){
        long long lcm=a.dwn*b.dwn/__gcd(a.dwn,b.dwn);
        a.up*=lcm/a.dwn;
        b.up*=lcm/b.dwn;
        return a.up>b.up;
    }
    friend ostream& operator<< (ostream &out,frac &a){
        write(a.up,'/');
        write(a.dwn);
        return out;
    }
}ans[MAXN];
int main(){
#ifdef DEBUG
    setIO("c");
#endif
    read(n);
    for(int i=1;i<=n;++i)
        read(a[i]);
    lp[1]=rp[1]=1,sum[1]=a[1];
    tot=1;
    long long tmp;
    for(int i=2;i<=n;++i){
        ++tot;
        lp[tot]=rp[tot]=i;
        sum[tot]=a[i];
        while(tot>1 && frac(sum[tot-1],rp[tot-1]-lp[tot-1]+1)>frac(sum[tot],rp[tot]-lp[tot]+1)){
            sum[tot-1]+=sum[tot];
            rp[tot-1]=rp[tot];
            --tot;
        }
    }
    for(int i=1;i<=tot;++i){
        for(int j=lp[i];j<=rp[i];++j)
            ans[j]=frac(sum[i],rp[i]-lp[i]+1);
    }
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<' ';
    return 0;
}