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;//最后一次必须遇见花并且酒量只剩1if(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;
}这题真难想......
