2017级八年级第二学期期中测试

解题报告

T1: 收件箱

模拟
1. 连着的1点一次向后一格
2. 1中间的1个0也点击一次
3. 连着两个零及以上选择跳出循环，转入下一个1，过程中需要两次点击
4. 用临时变量，存储还有多少未读

• AC 代码

 #include<bits/stdc++.h>
using namespace std;
int main() {
    int n,a[1010],j=0;
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        if(a[i]==1)j++;
    }
    a[n+1]=-1;
    int ans=0;
    for(int i=1; i<=n; i++) {
        if(a[i]==1) {
            int t=0;
            while((a[i] || a[i+1]) && j) {
                if(a[i]==1) j--;
                a[i]=0,t++,i++;
            }
            ans+=t;
            if(j) ans+=1  ;
        }
    }
    cout<<ans;
    return 0;
}

T2:冰镇杨梅汁

1. 预处理：
   $if 2*a[i]<a[i+1]　　a[i+1]=2*a[i]$也可写作$a[i+1]=min(a[i],2*a[i+1])$

2. dfs:
   预处理后，第n家店的杨梅汁的单价是最低的，所以dfs从最后一家店开始搜索。
   考虑两种情况

   1. 一次性买完 p 份
   2. 不一次性买完 p-1 份

• AC代码

#include<bits/stdc++.h>
#define LL long long  
LL ans=1e18,v[33],p[33],l,n;
using namespace std;
void dfs(int n,int l, LL m ) {
    if(l==0 || n==0) return ;
    LL tmp=((l-1)/v[n]+1)*p[n]+m;
    ans=min(ans,tmp);
    dfs(n-1,l%v[n],m+l/v[n]*p[n]);
}
int main() {
    cin>>n>>l;
    for(int i=1; i<=n; i++) {
        cin>>p[i];//价格 
        v[i]=pow(2,i-1);//体积 
    }
    for(int i=2; i<=n; i++) {
        p[i]=min(2*p[i-1],p[i]);
    }
    dfs(n,l,0);// 第几家店   ；  还要多少    ；   花了多少
    cout<<ans;
    return 0;
}

T3:一座塔

搜索；
传三个参数 a： 还能放多少体积； b：已经放到多高； c：放了多少体积
每一层选择放木块或不放木块；
1. 放木块将 a-木块体积； b+1； c+木块体积
2. 不放木块 a-> 当前木块体积-1（避免下层继续选择同体积木块）； b不变；c不变

• AC代码

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x)&-(x)
#define N 10010
#define P 10007
#define D double
#define ull unsigned ll
using namespace std;
int n;
struct nod {
    int t,v;
} ans[100010];
int cnt;
bool cmp(nod a, nod b) {
    if(a.t!=b.t) return a.t>b.t;
    else return a.v>b.v;
}
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&& ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}
void dfs(int need,int nv,int nh)  {
    int x;
    for(x=1; x*x*x<=need; x++);//枚举边长
    if(need<=7) {
        ans[cnt].t=nh+need;
        ans[cnt].v=nv+need;
        cnt++;
        return ;
    }
    dfs(need-pow(x-1,3),nv+pow(x-1,3),nh+1);
    dfs(pow(x-1,3)-1,nv,nh);
}
int main() {
    n=read();
    dfs(n,0,0);
    sort(ans,ans+cnt,cmp);
    cout<<ans[0].t<<" "<<ans[0].v<<endl;
    return 0;
}

T4：乘法表

规律+二分

• 代码

#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x)&-(x)
#define N 10010
#define P 10007
#define D double
#define ull unsigned ll
using namespace std;
inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&& ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}
ll m,n,k;
ll find(LL x) { // 计算比x小的数的个数df
    ll sum=0;
    for(int i=1; i<=n; i++) {
        sum += (m <= x/i)?m:(x/i);     // min(m,x/i) 是每一行中比x小的数的个数(若i*m<=x,则会有m个数满足要求，否则会有x/i个数满足)，也可以用if，else的写法 或 ? : 表达式的写法.
    }
    return sum;
}
ll ef(ll l, ll r, ll k) {
    ll mid;
    while(l <= r) {
        mid=(l+r)/2;
        if(find(mid) < k) l=mid+1;    // 要找的数在后面，区间下限继续增大
        else r=mid-1;                          // 要找的数在前面，区间上限继续减小
    }
    return l;
}
int main() {
    cin>>m>>n>>k;
    cout<ef(1,n*m,k);
    cout<<endl;
    return 0;