A题：九进制转十进制

(2022)9 = 2 * 9^0 + 2 * 9^1 + 2 * 9^3 = 1478 (√)

B题：顺子日期

012也是顺子！！！，但逆序不是！！！

1月0101-0131：0123， 0121， 0122， 0124, 0125， 0126， 0127， 0128， 0129

10月1001-1031：1012

11月1101-1130：1123

12月1201-1231：1230, 1231，1210，

共14个（√）

代码实现：

#include
using namespace std;
int month[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main()
{int cnt = 0;// mmdd for(int i = 0;i < 2; i++){ //第一个 m for(int j = 0;j <= 9; j++){ //第二个 m int k = j + 1; //第一个d，直接将第二个m加一即可int m = i * 10 + j;           if(m < 1 || m > 12) continue;for(int l = 0; l <= 9; l++){//第二个d int d = k * 10 + l;if(d >= 1 && d <= month[m] && (j == i + 1 || l == k + 1))cnt++;}}} cout << cnt << endl;return 0;
}

C题：刷题统计

直接while 60% + 40%（TLE）才知道这道题都没满分！

#include
using namespace std;long long a, b, n, sum;
int main()
{cin >> a >> b >> n;int i = 1; while(sum < n){if(i % 6 && i % 7)sum += a, i++;else sum += b, i++;}cout << i - 1;return 0; 
}

正解: 计算几周：剩余的按照循环计算天数

#include
using namespace std;long long a, b, n, sum, t, week, day;
int main()
{cin >> a >> b >> n;t = 5 * a + 2 * b;week = n / t;day = week * 7;sum = n % t;int i = 1; while(sum > 0){if(i % 6 && i % 7)sum -= a;else sum -= b;i++, day++;}cout << day << endl;return 0; 
}

D题：修建灌木

假设点i刚被修剪完为0，然后会向右/向左，端点会被遍历1次，i与端点间的点会被遍历2次，而重新修剪i的当天早上（因为是傍晚修剪，所以当天也会被算上）达到最大高度。

即：最大长度=中间节点数 * 2 + 1（端点）+ 1（自生）

= max ( 左边， 右边节点数 ) * 2

左边端点数：i - 1右边端点数：n - i

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

E题：X进制减法

1. (a + b) % p = (a % p + b % p) % p

2. (a - b) % p = (a % p - b % p) % p

3. (a * b) % p = (a % p * b % p) % p

4. a ^ b % p = ((a % p)^b) % p

例：321（进制从高到低依次是：8， 10， 2）转为十进制为：

3 * 10 * 2 + 2 * 2 + 1 = 64（按照从低位向高位进位逆运算）这个理解了好大一会！

#include 
using namespace std;int n, ma, a[100005], mb, b[100005];
long long mod = 1000000007, ans, jz, base = 1, A, B;
int main()
{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 = 0; i < ma; i++){//A > B ==> ma >= mb jz = max(max(a[i], b[i]) + 1, 2);// 这里会频繁出现越界的情况ans = (ans + (a[i] - b[i]) * base) % mod;base = (base * jz) % mod; }cout << ans << endl;return 0;
}

F题：统计子矩阵

前缀和（70% + 30% （TLE）原来此题也只得了70分）

因为每个值>=0所以范围越大和越大，越小和越小，因此可用尺取！！将O(n*n)==>O(nlogn)

正解：

1. 使用前缀和+滑动窗口 ，但是这里是二维矩阵，所以要先计算出纵向的前缀和，qz[i][j]表示前i行第j列之和

2. 然后遍历上边界i和下边界ii，再这个上下边界内使用滑动窗口，由于前面维护了纵向前缀和，所以转化成类似一维的滑动窗口。

3. 滑动窗口[l, r]：遍历右端点，根据区间和调整左端点，如果区间和大了，左端点右移。注意区间和也要移除左端点，直到找到满足的区间，区间大小r-l+1就是以r为右端点的满足条件子矩阵个数。

#include 
using namespace std;const int maxn = 505;
int a[maxn][maxn], qz[maxn][maxn];
long long ans = 0;
int main()
{int n, m, k;cin >> n >> m >> k;for(int i = 1; i <= n ; i++){for(int j = 1; j <= m; j++){cin >> a[i][j];qz[i][j] = qz[i-1][j] + a[i][j];//纵向前缀和 }}//遍历上边界和下边界for(int x1 = 1; x1 <= n; x1++){//遍历上边界for(int x2 = x1; x2 <= n; x2++){//遍历下边界int y1 = 1, y2 = 1;//滑动窗口的左右端点int sum = 0;//区间前缀和：[l,r]区间的累计和for(y2 = 1; y2 <= m; y2++){//遍历右端点，根据区间和调整左端点sum += qz[x2][y2] - qz[x1-1][y2];//加上右端点处的和while(sum > k){//左端点右移，区间变小sum -= qz[x2][y1] - qz[x1-1][y1];//减去移出去的左端点处的和y1++;} ans += y2 - y1 + 1;//方法数就是找到的区间大小累加}}} cout << ans << endl;return 0;
}

G题：积木画

一：https://blog.csdn.net/qq_54809548/article/details/128356269

二：二维的矩阵看成了一维的,所以I型积木就是等于1个方格,所以我们记为i-1,L型积木就是等于1.5个方格,但是L型积木不能单独出现,必须成双的出现,所以我们记为i-3,又由于I型积木出现在一个位置有两种方式,所以我们乘以二,L型积木出现只有一直方式我们乘以1,就结束了。（其实hai有点懵）

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

H题：扫雷

#include 
using namespace std;int n, m, ans, x, y, r;
struct node{int x, y, r;node(int i, int j, int k){x = i, y = j, r = k;}
};
int get_len(int x, int y, int i, int j){return (x - i) * (x - i) + (y - j) * (y - j);
}
map, int> mp;
set> s;
queue q;
int main()
{cin >> n >> m;for(int i = 0; i < n; i++){cin >> x >> y >> r;int tmp = mp[{x, y}] + 100;//百位数+1表示数量 mp[{x, y}] = max(tmp, tmp / 100 * 100 + r);//个位数表示最大半径 }for(int i = 0; i < m; i++){cin >> x >> y >> r;q.push(node(x, y, r));//排雷 }while(q.size()){int tx = q.front().x;int ty = q.front().y;int tr = q.front().r;q.pop();for(int i = tx - tr; i <= tx + tr; i++){for(int j = ty - tr; j <= ty + tr; j++){//排雷覆盖范围 pair p(i, j);if(s.count(p)) continue; //已经扫过 if(! mp.count(p)) continue;//没有雷 if(get_len(tx, ty, i, j) > tr * tr)continue;//虽然有雷，但是超出此范围s.insert(p);q.push(node(i, j, mp[p] % 100));ans += mp[p] / 100;}}} cout << ans << endl;return 0;
}

I题：李白打酒加强版

动态规划:

f[i][j][k] 表示经过第i次店、第j次花、当前有k斗酒的方案数。

状态转移方程为 : f[i][j][k] = f[i][j-1][k+1] + f[i-1][j][k/2]

其中可以加第一项的条件为j > 0；

第二项的条件为i > 0，且k必须为2的倍数,且最后一次遇到的是花，因此当前若有0斗酒，则不可再遇店，因此k不等于0的。

#include 
using namespace std;int f[105][105][105], n, m;
int main(){cin >> n >> m;f[0][0][2] = 1;//初始状态for(int i = 0; i <= n; i++){//第i次遇店 for(int j = 0; j <= m; j++){//第j次遇花 for(int k = 0; k <= m; k++){//有酒k斗 ,最多m斗，遇m次花最后 为0 if(j > 0) f[i][j][k] = f[i][j - 1][k + 1];if(k % 2 == 0 && i > 0 && k) f[i][j][k] += f[i - 1][j][k / 2];f[i][j][k] %= 1000000007;}}} cout << f[n][m][0];return 0;
}/* --------------------------------------------------------------------- */#include 
using namespace std;int f[105][105][105], n, m;
int main(){cin >> n >> m;f[0][0][2] = 1;for(int i = 0; i <= n; i++){//第i次遇店 for(int j = 0; j <= m; j++){//第j次遇花 for(int k = 0; k <= m; k++){//有酒k斗 ,最多m斗，遇m次花最后 为0 if(j && k) f[i][j][k] = f[i][j - 1][k + 1];if(!(k % 2) && i) f[i][j][k] += f[i - 1][j][k / 2];f[i][j][k] %= 1000000007;}}} cout << f[n][m - 1][1];return 0;
}
//因为没有酒遇到花是不合法的，所以循环的时候没有执行f[][m][0]的所有情况
//因为最后一步必须是遇到花，所以f[n][m-1][1]的值等于我们想要的f[n][m][0]

J题：砍竹子

sqrt: double型数据

sqrtf：float型数据

sqrtl：long double 型数据

对于long long数据开方：sqrtl

#include
using namespace std;typedef long long ll;
ll h[200010];//记录竹子高度
int n, p[200010], maxn, ans;//记录每个竹子对应的单独砍伐次数
int main(){cin >> n;for(int i = 0; i < n; i++){cin >> h[i];ll t = h[i];while(t - 1){p[i]++;t = sqrtl((t / 2) + 1);//使用魔法 } maxn = max(maxn, p[i]);//次数最多的}for(int i = maxn; i > 0; i--){//数据顶峰1e18,单独砍伐不超过64次for(int j = 1; j <= n; j++){//从高到低枚举第i次要砍的竹子if(p[j - 1] != i)continue;//高度相同则单独砍的次数也同if(h[j] == h[j-1]);//说明连续 能一次砍多棵else ans++;//代价在最后一棵相同竹子上p[j - 1]--;h[j - 1] = sqrtl((h[j - 1] / 2) + 1);//砍了一次后对应的数据要变化}} cout << ans << endl;return 0;
}