第一次参加蓝桥杯，复习（yuxi）完期末了，本蒟蒻写一篇博客记录一下
答案： 1478
思路：根据进制定义，就是2*9^0 + 2*9^1 + 0*9^2 + 2*9^3 = 1478
B 顺子日期(100%）答案： 14
思路： 这题题意有争议，我找的是连续的3个上升顺子。这题是蓝桥杯常考的日期算法，枚举从20220101~20221231中合法的日期，然后检查一下日期中是否出现顺子即可。
代码：
#includeusing namespace std; int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int res; bool cheak(int x) { int year = x / 10000, month = x / 100 % 100, day = x % 100; //取出年，月，日，然后判断该日期是否合法 if(day == 0 || month == 0 || month > 12) return false; if(month != 2 && day > days[month]) return false; if(month == 2) { int flag = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0); //闰年时，flag为1，否则为0 if(day > days[2] + flag) return false; //闰年时2月有29天，否则就是28天 } //经过上面代码块后，到这里的日期都是合法的日期，此时判断该日期是否为顺子日期即可 int d[9] = {0}; for(int i = 1; i <= 8; i ++ ) { d[i] = x % 10; //倒叙存储到d数组中,则下面找递减的顺子日期 x /= 10; } for(int i = 1; i + 2 <= 8; i ++ ) { if(d[i] - 1 == d[i + 1] && d[i + 1] - 1 == d[i + 2]) return true; } return false; //不是顺子日期，则return false; } int main() { for(int i = 20220101; i <= 20221231; i ++ ) if(cheak(i)) res ++ ; cout << res << endl; return 0; }
C: 刷题统计
思路：根据数据范围，肯定不能一天一天的加，那么可以将1周的刷题量算出来，为5a+2b，然后分类讨论，当n<5a+2b，则可以模拟一天一天的算。 当n>= 5a+2b，则可以算出总共有多少个星期也就是day = (n / (5a + 2b)) * 7，然后n %= (5a+2b)算出剩余的刷题量。然后将剩余<1周的刷题量再次通过一天一天的模拟获得.
代码如下：
#includeusing namespace std; typedef long long ll; ll a, b, n; ll day, sum; int main() { cin >> a >> b >> n; ll z = 5 * a + 2 * b; //z表示一周的刷题量 int cnt = 1; if(n < z) //如果总刷题量<一周的，那么单独一天天的算 { while(sum <= n) { if(cnt < 5) sum += a; else sum += b; day ++ ; cnt ++ ; if(cnt == 8) cnt = 1; } } else //反之，可以通过除法快速获得 { day += (n / z) * 7; n %= z; while(sum < n) { if(cnt < 5) sum += a; else sum += b; day ++ ; cnt ++ ; if(cnt == 8) cnt = 1; } } cout << day << endl; return 0; }
D:修剪灌木(100%）
思路：可以发现，爱丽丝一来一回的剪，那么对于任意一棵灌木爱丽丝要么是去剪它的路上，要么是剪完它了然后继续往下走。那么很明显，对任意灌木，能够生长的最大时间就是爱丽丝剪完它之后的这个过程，这个过程有左边和右边两个选择，所以就是对剪完它之后对左边和右边取最大
代码如下：
#includeusing namespace std; const int N = 20000; int n, f[N]; int main() { cin >> n; for(int i = 1; i <= n; i ++ ) f[i] = max(2 * (n - i), 2 * (i - 1)); for(int i = 1; i <= n; i ++ ) cout << f[i] << endl; return 0; }
E：X 进制减法
这题没有读懂.......略过
F: 统计子矩阵
思路：在做这题时感觉时间不太够，所以写了一个暴力就看下面了,下来听了聚聚们说是双指针，暴力思路就是二位前缀和处理一下，然后枚举左上角的端点，然后枚举右下角的端点。这样就确定了一个矩形，然后通过二位前缀和O(1)的算出矩阵中所有数字之和然后判断是否大于K即可，时间复杂度为O(n^4),可以过一半以上的数据。
双指针思路：将所有矩阵化为1维(用列的前缀和数组pre来处理)，相当于只有了一个数组，然后枚举上界线和下界线，再用双指针l和r来枚举列，在枚举r的过程中，如果大于K了，那么此时r再往右移是没有意义的，此时只需要l右移。那么这样列的枚举是O(n）的，那么时间复杂度就是O(n^3)
代码如下：
#includeusing namespace std; const int N = 550; typedef long long ll; int n, m, S; ll pre[N][N]; int main() { cin >> n >> m >> S; for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) { cin >> pre[i][j]; pre[i][j] += pre[i - 1][j]; } ll res = 0; for(int i = 1; i <= n; i ++ ) //枚举上边界 for(int j = i; j <= n; j ++ ) //枚举下边界 { ll sum = 0; for(int l = 1, r = 1; r <= m; r ++ )//双指针扫描 { sum += s[j][r] - s[i - 1][r]; while(sum > S) //若此时sun>S,则l右移，且把l那一列的值减去 sum -= s[j][l] - s[i - 1][l], l ++ ; res += r - l + 1; //每次r右移，都会有新的一部分块加入矩阵，用这个块和其他块组合得到的也是 } //新的子矩阵。而用不是新的子矩阵来组合则会重复 } //所以每次加入的新的子矩阵就是r - l + 1 cout << res << endl; return 0; }
G: 积木画
思路：这题是简化版的蒙德里安的梦想，可以用状压dp，也可以采用递推的思路，这里讲述递推的做法，通过最后一步完整的拼成一个矩形来划分。
为什么可以这样划分？因为放三角后你只能放横着的矩形，如果你放竖着的中间就会有一个空着的就会不合法。所以三角和矩形的组合只能这样组合。这样的划分就可以将要求的原问题划分成一个个不重复(因为最后一步的处理不同，是不重复的)的子问题，这些子问题之和就是答案。既定义f[n]为铺满n块的方案种数，所以f[n] = f[n - 1] + f[n - 2] + 2*f[n - 3] + 2 * f[n - 4]…………（因为三角形可以倒着放，所以有三角形的划分需要乘以2），可以得到f[n] = f[n - 1] + f[n - 2] + pre;pre就是方案种数的前缀和，f数组忘记开LL了，卒。
递推代码如下：
#includeusing namespace std; typedef long long LL; const LL N = 1e7 + 10, mod = 1000000007; LL n, f[N], pre; int main() { cin >> n; f[0] = 1, f[1] = 1, f[2] = 2; for(int i = 3; i <= n; i ++ ) { pre += 2 * f[i - 3], pre %= mod; f[i] = f[i - 1] + f[i - 2] + pre, f[i] %= mod; } cout << f[n] << endl; return 0; }
状态压缩dp代码如下：
#include#include using namespace std; const int N = 1e7 + 10, mod = 1000000007; int n, f[2][4]; int g[4][4] = { {1, 1, 1, 1}, {0, 0, 1, 1}, {0, 1, 0, 1}, {1, 0, 0, 0}, }; void init(int x) { for(int j = 0; j < 4; j ++ ) f[x & 1][j] = 0; } int main() { cin >> n; f[1][0] = 1; for(int i = 1; i <= n; i ++ ) { init(i + 1); for(int j = 0; j < 4; j ++ ) for(int k = 0; k < 4; k ++ ) f[(i + 1) & 1][k] = (f[(i + 1) & 1][k] + f[i & 1][j] * g[j][k]) % mod; } cout << f[n + 1 & 1][0] << endl; return 0; }
H: 扫雷
思路：这题暴力骗分了，思路就是枚举排雷火箭，看看它能引爆哪些炸雷，然后dfs去将这一个连通块用vis全部标记，最后再去统计看看有多少地雷被引爆。能否引爆就根据圆心距和半径和的关系来判断(高中数学？？...）
代码如下：
#include#include using namespace std; const int N = 1e6; struct e { double x, y, r; }k[N+N]; int n, m; bool st[N + N]; void dfs(int u) { for(int i = 1; i <= n + m; i ++ ) { if(!st[i] && u != i) //枚举所有没有爆炸过的地雷和火箭 { double d = sqrt((k[i].x - k[u].x) * (k[i].x - k[u].x) + (k[i].y - k[u].y) * (k[i].y - k[u].y)); //圆心距 if(d <= k[u].r) //圆心距 == r1 + r2，则相切， 圆心距 < r1 + r2，则相交。满足条件则代表可以引爆 { st[i] = true; //标记i被引爆了 dfs(i); //被引爆的继续枚举，看看它可以连锁反应哪些 } } } } int main() { cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> k[i].x >> k[i].y >> k[i].r; //输入地雷 for(int i = n + 1; i <= n + m; i ++ ) cin >> k[i].x >> k[i].y >> k[i].r; //输入引爆火箭 for(int i = n + 1; i <= n + m; i ++ ) { st[i] = true; //搜索所有火箭，将这个火箭的连通块枚举出来(相互引爆的必然是一个连通块) dfs(i); } int res = 0; for(int i = 1; i <= n; i ++ ) //枚举炸弹，看看哪些炸弹被引爆了，不要枚举火箭 if(st[i]) res ++ ; cout << res << endl; return 0; }
在代码源上过了40的数据
I: 李白打酒加强版
思路：本蒟蒻又又又暴力了QAQ，不过下来看了dp的思路。这里暴力就不说了就是一个dfs，这里说说dp的做法；dp的重点是描述状态，怎么才能把本题的状态描述清楚呢？ 定义f[i][j][k][0]代表遇花i次，遇店j次，壶中有酒k，当前在花，f[i][j][k][1]表示…………当前在店。
所以f[i][j][k][0] += (f[i - 1][j][k + 1][0] + f[i - 1][j][k + 1][1]);
同理f[i][j][k][1] += (f[i][j - 1][k / 2][0] + f[i][j - 1][k / 2][1]);所以得代码：
#includeusing namespace std; const int N = 110, MOD = 1000000007; int f[N][N][N][2], n, m; int main() { cin >> m >> n; f[0][0][2][0] = 1; for(int i = 0; i <= n; i ++ ) for(int j = 0; j <= m; j ++ ) for(int k = 0; k <= n + 2; k ++ ) { if(i == 0 && j == 0) continue; int &v = f[i][j][k][0], &u = f[i][j][k][1]; if(i - 1 >= 0) v = (v + f[i - 1][j][k + 1][0]) % MOD, v = (v + f[i - 1][j][k + 1][1]) % MOD; if(j - 1 >= 0 && k % 2 == 0) u = (u + f[i][j - 1][k / 2][0]) % MOD, u = (u + f[i][j - 1][k / 2][1]) % MOD; } cout << f[n][m][0][0] << endl; return 0; }
J: 砍竹子
蒟蒻不会，23333
总结：感觉这次省赛难度还好,但是还有点粗心，拼积木那题忘记开LL，民间数据只过了4个点,水得了一个省一。
