C>>>>>>>>D。
A
模拟即可。
B
唯一坑点是被染湿的格子不一定要和加湿器连通，枚举两个加湿器然后计算所有点即可，时间复杂度 \(O(h^3m^3)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1);
for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
#define maxn 11
int h,w,d;
char ch[maxn][maxn];
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
bool vis[maxn][maxn];
int check(int x,int y,int dep) {
int res=0;
For(i,1,h) For(j,1,w) {
if(!vis[i][j]&&ch[i][j]!='#'&&abs(i-x)+abs(j-y)<=d) {
vis[i][j]=1;
res++;
}
}
return res;
}
void work() {
cin>>h>>w>>d;
For(i,1,h) For(j,1,w) cin>>ch[i][j];
int ans=0;
For(i,1,h) For(j,1,w)
{
if(ch[i][j]=='#') continue;
For(k,1,h) For(l,1,w) {
if(k==i&&l==j) continue;
if(ch[k][l]=='#') continue;
m0(vis);
int res=check(i,j,d)+check(k,l,d);
ans=max(ans,res);
}
}
cout<<ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _=1;
// int _=read();
For(i,1,_) {
work();
}
return 0;
}
C
用一个优先队列，每一次将能走最多的步数的点弹出进行搜索，因为先走最多步数一定更优。
实际上就是一个 bfs。
由于每个点只会被遍历一次，所以时间复杂度是 \(O(hw)\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1);
for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
#define maxn 1010
int h,w,d;
char ch[maxn][maxn];
bool vis[maxn][maxn];
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};
struct node {
int x,y,dep;
bool operator<(const node &x) const {
return dep<x.dep;
}
};
void work() {
cin>>h>>w>>d;
priority_queue<node> q;
For(i,1,h) For(j,1,w) {
cin>>ch[i][j];
if(ch[i][j]=='H') q.push({i,j,d});
}
while(!q.empty()) {
auto [x,y,d]=q.top(); q.pop();
if(vis[x][y]) continue;
vis[x][y]=1;
For(i,1,4) {
int X=x+dx[i],Y=y+dy[i];
if(X>0&&X<=h&&Y>0&&Y<=w&&!vis[X][Y]&&ch[X][Y]!='#'&&d>0) q.push({X,Y,d-1});
}
}
int ans=0;
For(i,1,h) For(j,1,w) ans+=vis[i][j];
cout<<ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int _=1;
// int _=read();
For(i,1,_) {
work();
}
return 0;
}
D
简单计数题。
因为一共有 \(9\) 个因子，根据小学学过的只有完全平方数才有奇数个因子的特性，想到枚举完全平方数。然后你发现这并不可行。
怎么优化？我们首先可以察觉到，这个完全平方数一定绝大部分是形如 \(a^2b^2\)（满足 \(a\ne b\) 且 \(a,b\) 均为质数），他的因子分别是 \(a,a^2,b,b^2,ab,a^2b,ab^2,ab^2,a^2b^2\)。
同时，还有这样一种 \(a^8\)（\(a\) 为质数），他的因子分别为 \(a\) 的 \([1,8]\) 次幂。
我们筛出质数然后查找就好啦！大样例告诉我们答案不会很大，所以可行！
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define ll long long
#define i128 __int128
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1);
for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
#define maxn 200050
int pr[1100010],top;
bool vis[1100010];
int n;
void work() {
For(i,2,1100000) {
if(vis[i]) continue;
pr[++top]=i;
for(int j=i+i;j<=1100000;j+=i) {
vis[j]=1;
}
}
cin>>n;
int ans=0;
// For(i,1,top) For(j,i+1,top) For(k,j+1,top) if(pr[i]*pr[i]*pr[j]*pr[k]<=n) ans++;
For(i,1,top){
if(pr[i]*pr[i]*pr[i]*pr[i]>n) break;
if(pr[i]<=100&&pr[i]*pr[i]*pr[i]*pr[i]*pr[i]*pr[i]*pr[i]*pr[i]<=n) ans++;
For(j,i+1,top) {
if(pr[i]*pr[i]*pr[j]*pr[j]<=n) ans++;
else break;
}
}
cout<<ans;
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
int _=1;
// int _=read();
For(i,1,_) {
work();
}
return 0;
}
/*
*/