第十三届蓝桥杯省赛大学B组编程题(c++)

D.刷题统计

二分(AC):

注意:二分时右边界 right 的确定

#include<iostream>
using namespace std;
long long a,b,n;
bool check(long long x){
    long long t=x/7;
    x%=7;
    long long temp=0;
    if(x<=5) temp=x*a;
    else temp=5*a+(x-5)*b;
    long long cnt=t*(5*a+2*b)+temp;
    return cnt>=n;
}
int main(){
    cin>>a>>b>>n;
    long long left=0,right=n/min(a,b)+1;
    while(left<right){
        long long mid=(left+right)/2;
        if(check(mid)) right=mid; 
        else left=mid+1;
    }
    cout<<left<<endl;
    return 0;
}

E.修剪灌木

数学思维(AC):

#include<iostream>
using namespace std;
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int left=2*(i-1);
        int right=2*(n-i);
        cout<<max(left,right)<<endl;
    }
    return 0;
}

F.X 进制减法

暴力+模拟(AC):

十年OI一场空,不开浪浪见祖宗

#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll mod=1e9+7;
ll n,ma,mb,ans1,ans2,a[N],b[N],x[N],v[N];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n>>ma;
    for(int i=ma-1;i>=0;i--) cin>>a[i];
    cin>>mb;
    for(int i=mb-1;i>=0;i--) cin>>b[i];
    for(int i=max(ma-1,mb-1);i>=0;i--) x[i]=max((long long)2,max(a[i]+1,b[i]+1));
    for(int i=0;i<=max(ma,mb)-1;i++){
        if(i==0) v[i]=1;
        else{
            v[i]=v[i-1]*x[i-1];
            v[i]%=mod;
        }
    }
    for(int i=ma-1;i>=0;i--) ans1+=v[i]*a[i],ans1%=mod;
    for(int i=mb-1;i>=0;i--) ans2+=v[i]*b[i],ans2%=mod;
    cout<<(ans1-ans2+mod)%mod<<endl;
    return 0;
}

G.统计子矩阵

二维前缀和+暴力(70 points):

#include<iostream>
using namespace std;
const int N=505;
int n,m,k,a[N][N];
long long ans;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int x=1;x<=i;x++){
                for(int y=1;y<=j;y++){
                    if(k>=(a[i][j]+a[x-1][y-1]-a[x-1][j]-a[i][y-1])){
                        ans++;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

优化(AC):

#include<iostream>
using namespace std;
const int N=505;
int n,m,k,a[N][N];
long long ans;
int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>a[i][j];
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int l=1,r=1;r<=m;r++){
                while(l<=r&&k<(a[j][r]+a[i-1][l-1]-a[j][l-1]-a[i-1][r])){
                    l++;
                }
                ans+=r-l+1;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

这题暴力70足以...... 

H.积木画

递推与递归(AC):

#include<iostream>
using namespace std;
const long long mod=1e9+7;
const int N=1e7+5;
int n,f[N];
int main(){
    cin>>n;
    f[1]=1,f[2]=2,f[3]=5;
    if(n>=4){
        for(int i=4;i<=n;i++){
            f[i]=2*f[i-1]%mod+f[i-3]%mod;
            f[i]%=mod;
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

思路和洛谷题单算法1-4递推与递归 P1990 覆盖墙壁 一模一样......

I.李白打酒加强版

动态规划+记忆化搜索(AC):

#include<iostream>
#include<cstring>
using namespace std;
const int N=105;
const int mod=1e9+7;
int n,m,dp[N][N][N];//当前酒量,剩余遇见店的次数,剩余遇见花的次数
int dfs(int x,int y,int z) {
    //出现负数不合法
    if(x<0||y<0||z<0) return 0;
    //当前酒量不可能大于剩余遇见花的次数"
    if(x>z) return 0;
    //最后一次必须遇见花并且酒量只剩1
    if(z==1) return y==0&&x==1;
    //记忆化
    if(dp[x][y][z]!=-1) return dp[x][y][z];
    //逢店加倍,遇花减一
    dp[x][y][z]=(dfs(x*2,y-1,z)+dfs(x-1,y,z-1))%mod;
    return dp[x][y][z];
}
int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n>>m;
    cout<<dfs(2,n,m)<<endl;
    return 0;
}

J.砍竹子

unorder_set特点:无序不重复的集合
//头文件:
#include<unordered_set>
//常用函数:
unorder_set.empty();  //判断容器是否为空,空为true,反之为false
unorder_set.size();   //返回容器大小
unorder_set.begin();  //返回迭代器开始
unorder_set.end();    //返回迭代器结束
unorder_set.find(x);  //返回x在迭代器的位置
unorder_set.count(x); //返回x在容器的个数
unorder_set.insert(x);//将x插入到容器中
unorder_set.erase(x); //删除x,成功返回1,反之返回0
unorder_set.clear();  //清空容器

解释样例:

#include<iostream>
#include<unordered_set>
#include<cmath>
typedef long long ll;
using namespace std;
ll ans;            //累计不同的数的个数
unordered_set<ll>s;//保存上次出现过的数
int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) {
        ll temp;
        cin>>temp;
        unordered_set<ll>cur;  //每次读取一个数时,用来记录当前数的所有中间结果
        while(temp!=1) {
            cur.insert(temp);  //将当前数加入当前集合
            if (s.find(temp)==s.end()) ans++;//如果当前数不在之前的集合内,ans自增
            temp = sqrtl(temp/2+1);          //计算下一个数
        }
        s=cur; //更新保存所有出现过的数的集合
    }
    cout<<ans<<endl;
    return 0;
}

这题真难想......