C 题：

首先暴力的想，对于每一个加湿器的位置去 上下左右扩展是 n+m 的复杂度
。最多会有 nm 个加湿器。所以复杂度到达了n^3 。肯定超时了。
我们可以发现 对于一个点 会标记很多次，这回导致超时。
可以采用类似 bfs 求最短路的形式，找到每个点 距离 加湿器的最近距离，统计答案。
这样是nm 的复杂度。每个点只会进队一次

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;struct node
{int x = 0, y = 0;int d = 0;
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
void solve()
{int n, m, lim;cin >> n >> m >> lim;vector<vector<char>> g(n, vector<char>(m));vector<vector<int>> vis(n, vector<int>(m));queue<node> q;int ans=0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> g[i][j];if (g[i][j] == 'H'){q.push({i, j, 0});vis[i][j] = 1;ans++;}}}while (!q.empty()){auto [x, y, d] = q.front();q.pop();for (int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if (nx >= 0 && nx < n && ny >= 0 && ny < m){if (vis[nx][ny]||g[nx][ny]=='#')continue;vis[nx][ny]=1;if (d+1>lim)continue;else{q.push({nx,ny,d+1});ans++;}}}}cout<<ans<<"\n";
}
int main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}

D题


所以 9= 19 说明合法的数是一个质数的8次幂
9=33 说明合法的数也可以是两个质数的二次幂的乘积
要求 不超过n ，所以只用处理 sqrt(n) 内的质数就可以了。
（因为如果是> sqrt(n) 的质数，那么相乘一定超过了n）
处理 出来质数之后 ，就对两种情况直接暴力的求就可以了，（这种的复杂度我不会分析，感觉比较玄）

对于 ttt<n 的情况，为了避免 t tt 溢出，可以写成
t<n/tt

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
int read()
{int x = 0, f = 1;char ch = getchar();while (!isdigit(ch)){if (ch == '-')f = -1;ch = getchar();}while (isdigit(ch)){x = (x << 1) + (x << 3) + ch - '0';ch = getchar();}return x * f;
}
const int N = 3e6 + 5;
int is_prime[N];
int prime[N];
int cnt = 0;
int ans[N];
void pre(int n)
{for (int i = 2; i <= n; i++)is_prime[i] = 1;for (int i = 2; i <= n; i++){if (is_prime[i] == 1)prime[++cnt] = i;for (int j = 1; j <= cnt && i * prime[j] <= n; j++){is_prime[i * prime[j]] = 0;if (i % prime[j] == 0)break;}}
}void solve()
{int n;cin >> n;int t = sqrt(n);pre(t);set<int> se;// int ans = 0;// 八次幂的形式的for (int i = 1; i < cnt; i++){int t = prime[i] * prime[i];t = t * t * t * t;if (t <= n){se.insert(t);}else break;}// 两个 二次幂相乘for (int i = 1; i < cnt; i++){int t = prime[i] * prime[i];for (int j = i + 1; j < cnt; j++){int tt = prime[j] * prime[j];// if(t*tt>n)// break;if (t  > n/tt){break;}elsese.insert(t*tt);}}cout<<se.size()<<"\n";
}
signed main()
{std::cin.tie(nullptr)->sync_with_stdio(false);int t = 1;// cin>>t;while (t--){solve();}return 0;
}