A - Humidifier 1
照题意模拟即可，时间复杂度\(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 110
using namespace std;
int n,t[N],v[N],sum;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
for(int i=1;i<=n;i++){
sum=max(0ll,sum-(t[i]-t[i-1]));
sum+=v[i];
}
cout<<sum<<"\n";
return 0;
}
B - Humidifier 2
\(O((nm)^2)\)枚举两个加湿器的位置，再\(O(nm)\)统计答案。
总时间复杂度\(O((nm)^3)\)。
点击查看代码
#include<bits/stdc++.h>
#define N 15
using namespace std;
int n,m,d,ans;
string s[N];
signed main(){
cin>>n>>m>>d;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]=' '+s[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[i][j]=='#') continue;
for(int k=1;k<=n;k++){
for(int l=1;l<=m;l++){
if(s[k][l]=='#') continue;
int cnt=0;
for(int o=1;o<=n;o++){
for(int p=1;p<=m;p++){
if(s[o][p]=='#') continue;
cnt+=(abs(o-i)+abs(p-j)<=d||abs(o-k)+abs(p-l)<=d);
}
}
ans=max(ans,cnt);
}
}
}
}
cout<<ans<<"\n";
return 0;
}
C - Humidifier 3
对于一个位置，我们显然要让最优的状态先遍历到它，所以使用BFS解决。
初始将所有H所在位置加入队列，然后正常进行BFS即可。
时间复杂度\(O(nm)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 1010
using namespace std;
struct Status{int x,y,d;};
int n,m,d,dx[4]{-1,0,1,0},dy[4]{0,1,0,-1};
bitset<N> vis[N];
queue<Status> q;
string s[N];
signed main(){
cin>>n>>m>>d;
for(int i=1;i<=n;i++) cin>>s[i],s[i]=' '+s[i];
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
if(s[i][j]=='H') q.push({i,j,0});
while(!q.empty()){
Status sta=q.front();
q.pop();
int x=sta.x,y=sta.y;
if(vis[x][y]) continue;
vis[x][y]=1;
if(sta.d==d) continue;
for(int i=0;i<4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1||yy<1||xx>n||yy>m||s[xx][yy]=='#') continue;
q.push({xx,yy,sta.d+1});
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=vis[i][j];
}
}
cout<<ans<<"\n";
return 0;
}
D - 9 Divisors
因数个数公式：对于\(n=p_1^{a_1}\times p_2^{a_2}\times\dots\times p_l^{a_k}\)（\(p_i\)表示互不相同的质数），\(n\)的因数个数是\(\prod\limits_{i=1}^k (a_i+1)\)。
根据上面的公式，我们发现一个数\(x\)拥有恰好\(9\)个因数，当且仅当下面一项成立：
- \(x=p_1^2\times p_2^2\)。
- \(x=p_8\)。
显然成立的\(p\)一定在\(O(\sqrt n)\)以内，所以我们线性筛得到\(\sqrt n\)以内的素数，按上面的方法计算出所有答案，再统计\(\le n\)的有多少个即可。
显然答案一定远小于\(\sqrt n\)（这个看最后一个样例也能得到），所以时间复杂度不会超过\(O(\sqrt n)\)。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define V 2000010
#define CNT 500010
using namespace std;
int n,ans[CNT],idx,prime[V],idxp;
bitset<V> vis;
void euler(){
vis[0]=vis[1]=1;
for(int i=2;i<=V;i++){
if(!vis[i]) prime[++idxp]=i;
for(int j=1;j<=V;j++){
if(i*prime[j]>V) break;
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
signed main(){
cin>>n;
euler();
for(int i=1;i<=idxp;i++){
int ii=prime[i]*prime[i];
for(int j=i+1;j<=idxp;j++){
int jj=prime[j]*prime[j];
if(ii>4e12/jj) break;
ans[++idx]=ii*jj;
}
}
for(int i=1;i<=idxp;i++){
int v=prime[i];
v=v*v*v*v*v*v*v*v;
if(v>4e12) break;
ans[++idx]=v;
}
int cnt=0;
for(int i=1;i<=idx;i++) cnt+=(ans[i]<=n);
cout<<cnt<<"\n";
return 0;
}
E - Sum of Max Matching
最小化两点间边权最大值，是无向图的最小瓶颈路问题，我们通常使用最小生成树或Kruskal重构树（此处使用前者）来解决。
结论：原图上两点间最大边权的最小值，就是最小生成树上两点间的最大边权。
由此我们可以得到一个贪心思路：
- 初始将每个节点看作一个集合。对于\(u\)所在的集合，进行如下规定：
- 如果\(u\in A\)则该集合包含\(1\)个红色点。
- 如果\(u\in B\)则该集合包含\(1\)个蓝色点。
- 否则该集合为空。
- 按边权从小到大为边集排序，依次遍历每一条边\((u,v,w)\)：
- 如果加入该边后形成环，则跳过这条边。
- 否则，将\(u,v\)所在集合合并，红蓝点两两配对消去。设消去\(s\)个红蓝点对，那么对答案的贡献就是\(s\times w\)。
根据一开始的结论，可以得出这样做是正确的。
时间复杂度\(O(m(\log m+\alpha(n)))\)。
点击查看代码
#include<bits/stdc++.h>
#define N 200010
#define M 200010
#define int long long
using namespace std;
struct edge{int u,v,w;}e[M];
int n,m,k,ca[N],cb[N],idx,fa[N],ans;
vector<edge> G[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
signed main(){
cin>>n>>m>>k;
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
e[++idx]={u,v,w};
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,u;i<=k;i++) cin>>u,ca[u]++;
for(int i=1,u;i<=k;i++) cin>>u,cb[u]++;
sort(e+1,e+1+idx,[](edge a,edge b){return a.w<b.w;});
for(int i=1;i<=m;i++){
int u=find(e[i].u),v=find(e[i].v);
if(u==v) continue;
fa[u]=v,ca[v]+=ca[u],cb[v]+=cb[u];
int siz=min(ca[v],cb[v]);
ca[v]-=siz,cb[v]-=siz;
ans+=siz*e[i].w;
}
cout<<ans<<"\n";
return 0;
}
F - Diversity
周二更新
标签：AtCoder,idx,Beginner,int,题解,long,ans,include,define From： https://www.cnblogs.com/Sinktank/p/18593243