1. 小挖的X献身
先想一下暴力的做法就是枚举每一行,每一行再选两个数一左一右遍历所有的
X
,如果check
成功ans ++
for (int row = 1; row <= n; row ++ )
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ ){
...
}
BUT, 预估的时间复杂度是$O(n ^ 4)$, $n = 100$是不够用的
不过,解决方法就是把每个斜线的长度都预处理出来即可达到$O(n ^ 3)$
$$ len[x][y][0]表示左斜线长度\ \ \ \ \ \ \ \ \ \ \ \ \ len[x][y][1]表示右斜线长度 $$
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
char s[N][N];
int len[N][N][2], cnt[N];
int dx[] = {1, 1};
int dy[] = {-1, 1};
int xx, yy, ans, sum;
void solve(int i, int j, int k){ // O(n)的时间复杂度完成预处理
xx = i, yy = j, ans = 1;
while (s[xx][yy] == '1'){
xx += dx[k];
yy += dy[k];
if (s[xx][yy] == '1') ans ++ ;
}
len[i][j][k] = ans;
}
int main(){
scanf("%d", &n);
memset(s, '*', sizeof s);
for (int i = 0; i < n; i ++ ){
scanf("%s", s[i]);
for (int j = 0; j < n; j ++ )
if (s[i][j] == '1')
cnt[i] ++ ; // 如果每行只有一个就不用枚举了
}
// O(n ^ 3)
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (s[i][j] == '1'){
solve(i, j, 0); // 第(i, j)的左半边的长度
solve(i, j, 1); // 第(i, j)的右半边的长度
}
// O(n ^ 3) + 剪枝
for (int row = 0; row < n; row ++ )
if (cnt[row] >= 2) // 特判
for (int a = 0; a < n; a ++ )
if (s[row][a] == '1')
for (int b = a + 1; b < n; b ++ )
if (s[row][b] == '1'){
int cha = b - a + 1; // 这里是一个性质,可以自己探索一下
// 即取i点和j点的下边的差 + 1,就是这个差的长度
int ltor = len[row][a][1];
int rtol = len[row][b][0];
if (ltor >= cha && rtol >= cha)
sum ++ ;
}
printf("%d\n", sum);
return 0;
}
2. 小挖的时间
只得了 30 分的就是没有考虑下一个12小时的
像我根据枚举可发现,12小时内就只会有31个等差数列
就得到了下面的超简洁代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int ans[32] = {0, 34, 71, 83, 95, 107, 119, 130, 142, 154, 166, 178, 201, 213, 225, 237, 260, 272, 284, 296, 331, 343, 355, 390, 402, 414, 461, 473, 520, 532, 591, 671};
int n, q;
int main(){
scanf("%d", &n);
while (n -- ){
int t; scanf("%d", &t);
int c = t / 720; // 天数
t %= 720; // MOD上720即60 * 12否则会超时
for (int i = 31; i >= 0; i -- )
if (t >= ans[i]){
printf("%d\n", i + c * 31);
break;
}
}
return 0;
}
3. 小挖的买花
01背包问题
时间复杂度天花板$O(n ^ 3)$
由于q是1e6,所以输入一次计算一次
用 01 背包预处理即可
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1000010;
int n, m1, m2, q;
int cost[N], be[N], fr[N];
int f[N][N];
// 买花的要求:
// f[i][j]表示花费不超过 i 的钱去买到新鲜值为j的花的最大美丽度
int c[M], fresh[M];
int main(){
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i ++ ) scanf("%d%d%d", &cost[i], &fr[i], &be[i]);
for (int i = 1; i <= q; i ++ ) {
scanf("%d%d", &c[i], &fresh[i]);
m1 = max(m1, c[i]);
m2 = max(m2, fresh[i]);
}
for (int i = 1; i <= n; i ++ )
for (int j = m1; j >= cost[i]; j -- ) // 01背包
for (int k = m2; k >= 0; k -- )
if (k <= fr[i]) f[j][k] = max(f[j][k], f[j - cost[i]][0] + be[i]);
else if (f[j - cost[i]][k - fr[i]]) f[j][k] = max(f[j][k],f[j - cost[i]][k - fr[i]] + be[i]);
for (int i = 1; i <= q; i ++ ) printf("%d\n", f[c[i]][fresh[i]]);
return 0;
}
4. 小挖的核燃料填充
留坑待填
4题好像是搜索加剪枝 我还没做出来
对对对,反正好难,大佬有时间的话可以发我下
AC
代码呀!谢谢