第十三届蓝桥杯
创始人
2024-05-28 18:42:48
0次

这里写目录标题

    • 一、刷题统计（ceil函数返回的是等值于某最小整数的浮点值，不强制转换回int就wa，没错就连和int整数相加都wa
    • 二、修剪灌木（主要应看清楚会调转方向
    • 三、统计子矩阵（前缀和+滑动窗口⭐）
    • 四、[积木画](https://www.lanqiao.cn/problems/2110/learning/)
    • 顺子日期
    • 五、X进制减法
    • [ 六、扫雷](https://www.lanqiao.cn/problems/2113/learning/)
    • 七、李白打酒加强版
    • 八、砍竹子

一、刷题统计（ceil函数返回的是等值于某最小整数的浮点值，不强制转换回int就wa，没错就连和int整数相加都wa

在这里插入图片描述
ceil函数我给你跪了，总之ceil（x) 返回的是 等值于 大于或等于x(一般为浮点数，可能是整数）的最小整数 的浮点数
在这里插入图片描述

#include 
using namespace std;
#define int long long int
signed main()
{
int res=0,sum=0;
int a,b,n;
cin>>a>>b>>n;int x=5*a+2*b;
res+=(n/x*7);
sum+=n/x*x;
int y=n-sum;
//x=0;
//while(y>0){
//	x++;
//	if(x<=5)y-=a;
//	else y-=b;//}
//res+=x;
if(y>5*a){res=res+5+(int)ceil((y-5*a)*1.0/b);
}
else res+=(int)ceil(1.0*y/a);
//if(y>5*a){
//	res+=5;
//	int z=((y-5*a)%b==0)?(y-5*a)/b:(y-5*a)/b+1;
//	res+=z;
//}
//else{
//	int z=((y%a)==0)?y/a:y/a+1;
//	res+=z;
//}
cout<

二、修剪灌木（主要应看清楚会调转方向

在这里插入图片描述

#include 
using namespace std;
#define int long long int
int n;
const int N=10000;
int a[N];
int b[N];
signed main(){
//在第一天的 早晨, 所有灌木的高度都是 0 厘米  每天从早上到傍晩会长高 1 厘米
//当修剪了最右侧的灌木后, 她会调转方向
cin>>n;for(int i=1;i<=n;i++){a[i]=2*max(n-i,i-1);cout<max 重复
//	固定模式的哪个时刻出现最高高度呢？
//	刚把a[x]砍到0后，向左（或向右）走到底a[n]，再往回走到a[x]的时候return 0;
}

三、统计子矩阵（前缀和+滑动窗口⭐）

结错婚是惨过输钱，看错题惨过。。。 是不超过k不是等于k啊大佬

#include 
using namespace std;
#define int long long int
int n,m,k;
const int N=1005;
int a[N][N];
int b[N][N];//b[i][j],第i列 前j行的前缀和
int res=0;
void fun(int x,int y){int s[N];int sum[N];memset(s,sizeof(s),0);memset(sum,sizeof(sum),0);for(int i=1;i<=n;i++){s[i]=b[i][y]-b[i][x-1];sum[i]=sum[i-1]+s[i];}//这里是暴力枚举区间，在双重循环下暴力导致超时//用滑动窗口(maybe)
//	for(int l=1;l<=n;l++){
//		for(int r=l;r<=n;r++){
//			if((sum[r]-sum[l-1])<=k)res++;
//		}
//	}int l=1,r=1;for(int r=l;r<=n;r++){while(sum[r]-sum[l-1]>k){l++;}res+=r-l+1;
//此时sum[r]-sum[l-1]<=k,由于枚举的是右端点，以r为右端点，有r-l+1个空间满足条件}	
//	l l+1 l+2 l+3    (l,l+3) (l+1,l+3) (l+2,l+3) (l+3,l+3)
}
void fun1(int i,int ii){
//	这里a[i][j]是第j列前i行的前缀和
//我的题解b[i][j]是第i列前j行的前缀和int l = 1, r = 1;//滑动窗口的左右端点int sum = 0;//区间前缀和：[l,r]区间的累计和for(r = 1; r <= n; r++)//遍历右端点，根据区间和调整左端点{sum += a[ii][r] - a[i-1][r];//加上右端点处的和while(sum > k)//区间和了，左端点右移，区间变小{sum -= a[ii][l] - a[i-1][l];//减去移出去的左端点处的和l++;}res += r - l + 1;//方法数就是找到的区间大小累加}
}
signed main(){cin>>m>>n>>k;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];b[j][i]=b[j][i-1]+a[i][j];}}
//	子矩阵的和
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){	
//			cout<for(int j=i;j<=m;j++){fun(i,j);}}cout<

三个样例运行超时了

#include 
using namespace std;
#define int long long int
int n,m,k;
const int N=1005;
int a[N][N];
int b[N][N];//b[i][j],第i列 前j行的前缀和
int res=0;
void fun(int x,int y){int s[N];int sum[N];memset(s,sizeof(s),0);memset(sum,sizeof(sum),0);for(int i=1;i<=n;i++){s[i]=b[i][y]-b[i][x-1];sum[i]=sum[i-1]+s[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){if((sum[j]-sum[i-1])<=k)res++;}}}
signed main(){cin>>m>>n>>k;for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){cin>>a[i][j];b[j][i]=b[j][i-1]+a[i][j];}}
//	子矩阵的和
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++){	
//			cout<for(int j=i;j<=m;j++){fun(i,j);}}cout<

四、积木画

在这里插入图片描述
在这里插入图片描述

我一直以为我是对的来着（0%通过率，excuse me？呜呜呜）
fine，我看完n=3的情况下意识地以为 组合情况 要么 长方形单独拼，L形单独拼，或者是 长方形和L形混拼（而且下意识觉得两种混拼的形式只有n=3情况中枚举的这么几种），但显然简单化了（稍微动脑想想，n=5，一个L形两个长方形，这种组合情况就超出了n=3枚举的那些情况

#include 
using namespace std;
#define int long long int
int n,m,k;
const int mod=1000000007;
const int N=10000005;
int dp[N];signed main(){cin>>n;dp[1]=1;dp[2]=2;dp[3]=5;for(int i=4;i<=n;i++){dp[i]=(dp[i-1]*1%mod+dp[i-2]*2%mod+dp[i-3]*5%mod)%mod;}cout<

递归还是讲究一个状态转移，那么对于第 iii 列可能会有哪几种情况呢？

在这里插入图片描述
(，阴影部分表示第 i−1i-1i−1 列已经拼好的状态，由于长方形和L形都只占两列，只需要观察第 i−1i-1i−1 列和第 iii 列)
最后所求的方案数 等值于 dp[n][4]dp[n][4]dp[n][4]
不用担心除了第n列之外的列上下没有被覆盖满，因为看我们的状态转移图，转移方式无一不会使得第 i−1i-1i−1 列存在未被覆盖的情况，由此拼图方式递推，推到第 iii 列时，不管第 iii 列状态咋样，第 i−1i-1i−1 列一定被覆盖满了
正当我以为我要AC的时候，没有一声不好意思，竟让我崩溃至此

当需要开很大的数组（这里高达 1e71e71e7 ),尽量不要开longlong，实在不行将中途结果用强制转化成longlong的方法防止爆int,其次就是空间本来就已经不够了，数组下标还是不要作妖从1开始，从0开始节省一点
在这里插入图片描述
这里给256M

一、数组太大，超内存

#define int long long int
const int N=10000005;
int dp[N][5];

vector> dp(n + 1, vector(5));

数开八位的真敢啊你，清一色的runerror，以后超过六位数就用vector(等等， 不对，vector似乎更占空间，看这题最后的一块题解，同样不开long long，vector反而不行了，这里能过30%不过是因为是根据n的大小针对性开的，有部分测试样例n比较小

二、初始化
没错的，都是内存的错

 dp[1][4]=1;dp[1][0]=1;

但为什么这个能过35%
即便避开了上面两个任意让人过%0的点，也只有勉强的30%

#include 
using namespace std;
#define int long long int
int n,m,k;
const int mod=1000000007;
// const int N=10000005;
// int dp[N][5];signed main(){cin>>n;vector> dp(n + 1, vector(5));// dp[1][4]=1;// dp[1][0]=1;dp[0][4] = 1;for(int i=1;i<=n;i++){dp[i][1]=(dp[i-1][4])%mod;dp[i][2]=(dp[i-1][1]+dp[i-1][3])%mod;dp[i][3]=(dp[i-1][1]+dp[i-1][2])%mod;dp[i][4]=(dp[i-1][4]+dp[i-1][3]+dp[i-1][2]+dp[i-1][1])%mod;}cout<

AC代码 人已疯，仍然不知道在数组越界的情况下是怎么AC的，都要怀疑自己二维数组的表示一直以来是错的了

#include 
using namespace std;
#define LL long long int
int n,m,k;
const int mod=1000000007;
const int N=10000005;
LL dp[N][3];//改成4 变 35%，。全是超过内存限制signed main(){cin>>n;//    vector> dp(n + 1, vector(4));这种数组声明 30% 运行错误or超内存
//忘记LL直接0%,二维长度改成3 全军覆没0%，运行错误（数组越界
//难道两种数组声明二维长度的含义不同？dp[0][3] = 1;for (int i = 1; i <= n; i++) {dp[i][0] = dp[i - 1][3];dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;}cout<< dp[n][3];return 0;
}

如果要是开long long 的dp，则会因为空间太大，错误。要是开int的dp数组，又会因为数据类型不够大，在多个int数据相加时，会超出int的范围，导致答案错误…
真正的解决办法

当需要开很大的数组（这里高达 1e81e81e8 ),尽量不要开longlong，实在不行将中途结果用强制转化成longlong的方法防止爆int,其次就是空间本来就已经不够了，数组下标还是不要作妖从1开始，从0开始节省一点

两种初始化方法都行

	dp[1][0] = 1;dp[1][1] = 0;dp[1][2] = 0;dp[1][3] = 1;for(int i=2;i<=n;i++){

dp[0][3] = 1;for(int i=1;i<=n;i++){

#include 
using namespace std;
#define ll long long int
int n,m,k;
const int mod=1000000007;const int N=10000005;int dp[N][4];signed main(){cin>>n;
//    vector> dp(n + 1, vector(4));
//     dp[1][3]=1;
//     dp[1][0]=1;dp[0][3] = 1;for(int i=1;i<=n;i++){dp[i][0]=((ll)dp[i-1][3])%mod;dp[i][1]=((ll)dp[i-1][0]+(ll)dp[i-1][2])%mod;dp[i][2]=((ll)dp[i-1][0]+(ll)dp[i-1][1])%mod;dp[i][3]=((ll)dp[i-1][3]+(ll)dp[i-1][2]+(ll)dp[i-1][1]+(ll)dp[i-1][0])%mod;}cout<

问题又来了，即使不开 longlong数组，这里用vector声明二维数组的时候又只能过35%，我不理解
在这里插入图片描述

力扣原题-动态规划解释
找规律解释（类似这种的动态规划找方法数都有规律？）

顺子日期

#include 
using namespace std;
int a[10];
int mon[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool ok(int x){int y=x/10000;int m=(x%10000)/100;int d=x%100;if(m<1||m>12)return false;if(d<1)return false;if(d>mon[m])return false;return true;
}
int main()
{int res=0;for(int i=20220101;i<=20221231;i++){if(!ok(i))continue;int cnt=0;int x=i;while(x){a[cnt++]=x%10;x/=10;}//翻转了，判断是否 321for(int j=0;j<6;j++){if(a[j+1]==a[j]-1&&a[j+2]==a[j]-2){res++;break;}}
}
cout<

五、X进制减法

在这里插入图片描述
样例输入

11
3
10 4 0
3
1 2 0

样例输出

94

在这里插入图片描述
在这里插入图片描述
首先是找规律，第 iii 位的权重是累乘 111 ~ i−1i-1i−1 的所有进制
最小的差值，我下意识以为要暴力搜索所有权值的组合情况，因为毕竟虽然 A>=BA>=BA>=B ,难免可能统一位上 A[i] 但也许是贪心思想，每一位都取最低的权值，就能得到最小的差值
暴力搜索版（过了30%，剩下的超时了）

#include 
using namespace std;
#define ll long long int
const int mod=1000000007;
const int N=100005;
int n,x,y;
int a[N],b[N],c[N];
ll res=0x3f3f3f3f;
int X[N];
void dfs(int u){if(u==x+1){ll tmp=a[1];ll base=1;for(int i=2;i<=x;i++){base=base*X[i-1]%mod;tmp=(tmp+a[i]*base)%mod;}res=min(tmp,res);return ;}for(int i=2;i<=n;i++){if(i>=c[u]){X[u]=i;			dfs(u+1);}}
}
signed main(){scanf("%d",&n);scanf("%d",&x);
for(int i=x;i>=1;i--)scanf("%d",&a[i]);scanf("%d",&y);for(int i=y;i>=1;i--)scanf("%d",&b[i]);
//	最小的差
//	既然A>=B ,那么x一定大于等于y
// 每一数位上的数 字要小于其进制for(int i=1;i<=x;i++){c[i]=max(a[i],b[i])+1;//进制大于等于c[i]a[i]=a[i]-b[i];if(c[i]<2)c[i]=2;}dfs(1);cout<

贪心AC版
解释一
因为每一位进制都会 乘到 A 和 B里面，当 base 越大的时候 A 和 B都会越大，但是因为 A >= B 的，所以 A 的增长速率是始终大于 B 的， 所以 base越大，A - B 的差值就越大，所以我们只要每次取 base 最小，就能满足 A - B 的差值最小了，又因为每一位的值都是由前面每一位的进制乘起来的

解释二
借位思想，极限思维， 一旦碰到A[i]=BA>=BA>=B，最后一定可以使得 每个位置都有A[i]>=B[i]A[i]>=B[i]A[i]>=B[i]
解释三
秦九韶算法

#include 
using namespace std;
#define ll long long int
const int mod=1000000007;
const int N=100005;
int n,x,y;
int a[N],b[N],c[N];
ll res=0;
signed main(){scanf("%d",&n);scanf("%d",&x);for(int i=x;i>=1;i--)scanf("%d",&a[i]);scanf("%d",&y);for(int i=y;i>=1;i--)scanf("%d",&b[i]);
//	最小的差
//	既然A>=B ,那么x一定大于等于y
// 每一数位上的数 字要小于其进制ll base=1;for(int i=1;i<=x;i++){c[i]=max(a[i],b[i])+1;//进制大于等于c[i]a[i]=a[i]-b[i];//不要改变了a[i]的含义又去用原a[i]的值 不要交换两句顺序if(c[i]<2)c[i]=2;res=(res+a[i]*base)%mod;base=base*c[i]%mod;}cout<

六、扫雷

我连暴力的bfs都TT，错得很彻底
看来想要暴力水得部分分都要更加奋发努力
力扣原题题解

#include 
using namespace std;
#define ll long long int
const int N=1e3+5;
int n,m;
typedef struct node{int x, y, r;node(int xx,int yy,int rr):x(xx),y(yy),r(rr){}	
}node;
queue Q;
//map,vector > mp;
//node a[N];
vector a;
bool vis[N][N];
bool inside(int x,int y){return x>=0&&y>=0&&xreturn sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
}
int res=0;
signed main(){scanf("%d %d",&n,&m);int x,y,r;for(int i=1;i<=n;i++){scanf("%d %d %d",&x,&y,&r);a.push_back(node(x,y,r));}     for(int i=1;i<=m;i++){           scanf("%d %d %d",&x,&y,&r);b.push_back(node(x,y,r));Q.push(node(x,y,r));
//		vis[x][y]=true;  共引爆了几颗炸雷，而一个点可以储存多个炸雷与排雷}while(!Q.empty()){node t=Q.front();Q.pop();int sx=t.x,sy=t.y,sr=t.r;for(int i=sx-r;i<=sx+r;i++){for(int j=sy-r;j<=sy+r;j++){if(inside(i,j)&&!vis[i][j]&&fun(i,j,sx,sy)-sr<1e-1){vis[i][j]=true;for(int k=0;kif(a[k].x==i&&a[k].y==j){Q.push(node(i,j,a[k].r));res++;}}}}}}cout<

七、李白打酒加强版

八、砍竹子

总题解1
总题解2

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：Linux内核4.14版本——drm框架分析(5)——plane分析

下一篇：《计算机系统基础》—— 运算

相关内容

热门资讯

苹果系统安卓爱思助手,系统兼容... 你有没有发现，手机的世界里，苹果系统和安卓系统就像是一对欢喜冤家，总是各有各的粉丝，各有各的拥趸。而...
安卓系统占用很大内存,揭秘内存... 手机里的安卓系统是不是让你感觉内存不够用，就像你的房间堆满了杂物，总是找不到地方放新东西？别急，今天...
安卓系统p30,安卓系统下的摄... 你有没有发现，最近安卓系统P30在手机圈里可是火得一塌糊涂呢！这不，我就来给你好好扒一扒这款手机的那...
siri被安卓系统进入了,智能... 你知道吗？最近科技圈可是炸开了锅，因为一个大家伙——Siri，竟然悄悄地溜进了安卓系统！这可不是什么...
最强挂机系统和安卓区别,揭秘安... 亲爱的读者，你是否曾在游戏中遇到过这样的困扰：一边想要享受游戏带来的乐趣，一边又不想放弃手中的零食或...
安卓系统为什么设系统盘,保障稳... 你有没有想过，为什么安卓系统里会有一个叫做“系统盘”的东西呢？这可不是随便设置的，背后可是有大学问的...
王者怎么加安卓系统的,轻松提升... 你有没有想过，你的手机里那款超酷的王者荣耀，怎么才能让它更好地在你的安卓系统上运行呢？别急，今天就来...
安卓手机系统怎么开热点,共享网... 你有没有想过，当你身处一个没有Wi-Fi信号的地方，而你的安卓手机里却存满了精彩视频和游戏时，是不是...
安卓系统11的平板电脑,性能升... 你有没有发现，最近平板电脑市场又热闹起来了？没错，安卓系统11的新一代平板电脑正在悄悄地走进我们的生...
安卓手机系统创始人,安卓手机系... 你有没有想过，那些陪伴我们每天生活的安卓手机，它们的灵魂是谁赋予的呢？没错，就是那位神秘而又传奇的安...
安卓11系统速度提升,体验再升... 你知道吗？最近安卓系统又升级啦！这次可是直接跳到了安卓11，听说速度提升了不少呢！是不是很心动？那就...
安卓5.1原生系统设置apk,... 你有没有想过，你的安卓手机里那些看似普通的设置，其实隐藏着不少小秘密呢？今天，就让我带你一探究竟，揭...
手机安卓系统玩音游,畅享指尖音... 你有没有发现，现在手机上的游戏种类越来越丰富，尤其是音游，简直让人爱不释手！今天，就让我来给你详细介...
安卓系统与win10,系统融合... 你有没有想过，为什么你的手机里装的是安卓系统，而电脑上却是Windows 10呢？这两种操作系统，就...
苹果系统王者安卓系统可以登吗,... 你有没有想过，为什么苹果系统的手机那么受欢迎，而安卓系统的手机却也能在市场上占有一席之地呢？今天，咱...
安卓系统怎么重制系统还原,安卓... 手机用久了是不是感觉卡得要命，想给它来个大变身？别急，今天就来教你怎么给安卓手机重置系统，让它焕然一...
安卓9系统怎样应用分身,轻松实... 你有没有发现，手机里的APP越来越多，有时候一个APP里还要处理好多任务，分身功能简直就是救星啊！今...
获取安卓系统的ip地址,轻松获... 你有没有想过，你的安卓手机里隐藏着一个神秘的IP地址？没错，就是那个能让你在网络世界里找到自己的小秘...
LG彩电安卓系统升级,畅享智能... 你家的LG彩电是不是最近有点儿“闹别扭”，屏幕上时不时地跳出个升级提示？别急，今天就来给你详细说说这...
阴阳师安卓苹果系统,安卓与苹果... 亲爱的玩家们，你是否曾在深夜里，手握手机，沉浸在阴阳师的神秘世界？今天，就让我带你一起探索这款风靡全...