day 10 下午
2025-02-07 20:25:57
发布于：上海
16阅读
0回复
0点赞
最大连通块
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200005;
vector<int> g[maxn];
bool vis[maxn];
int num;
void dfs(int x) {
vis[x] = true;
num++; // 更新 num
for (int i = 0; i < g[x].size(); i++) {
int y = g[x][i];
if (!vis[y]) {
dfs(y);
}
}
}
int main() {
int n, m, mx = 0;
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
num = 0;
dfs(i);
mx = max(mx, num);
}
}
cout << mx;
return 0;
}
不可思议的游戏
#include<bits/stdc++.h>
using namespace std;
const int N = 10000010;
int n, m;
bool st[N];
int d[N];
int main() {
cin >> n >> m;
queue<int> q;
q.push(n);
st[n] = true;
d[n] = 0;
while(q.size()) {
int u = q.front();
q.pop();
if(u==m){
cout<<d[u]<<endl;
return 0;
}
int k = u * 5;
if(k < N && !st[k]) {
q.push(k);
d[k] = d[u] + 1;
st[k] = true;
}
k = u - 5;
if(k >= 0 && !st[k]) {
q.push(k);
d[k] = d[u] + 1;
st[k] = true;
}
k = u - 1;
if(k >= 0 && !st[k]) {
q.push(k);
d[k] = d[u] + 1;
st[k] = true;
}
}
return 0;
}
回文数列
#include<iostream>
using namespace std;
int main(){
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++)cin>>a[i];
long long ans = 1;
for(int i=1;i<=n/2;i++)ans*=min(a[i],a[n-i+1]);
if(n%2==1)ans*=a[n/2+1];
cout<<ans;
return 0;
}
奶牛要降温
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct air_conditioner{
int begin,end,degree,money;
};
air_conditioner b[100010];
int a[100010];
int ans=2147483647;
int maxx=-1,s,t,c;
void dfs(int idx,int sum){
if (idx==m+1){
for (int i=1;i<=maxx;i++){
if (a[i]>0) return;
}
ans=min(ans,sum);
return;
}
dfs(idx+1,sum);
for (int i=b[idx].begin;i<=b[idx].end;i++){
a[i]-=b[idx].degree;
}
dfs(idx+1,sum+b[idx].money);
for (int i=b[idx].begin;i<=b[idx].end;i++){
a[i]+=b[idx].degree;
}
}
int main(){
cin>>n>>m;
maxx=-1;
for (int i=1;i<=n;i++){
cin>>s>>t>>c;
for (int j=s;j<=t;j++){
a[j]+=c;
}
maxx=max(maxx,t);
}
for (int i=1;i<=m;i++){
cin>>b[i].begin>>b[i].end>>b[i].degree>>b[i].money;
}
dfs(1,0);
cout<<ans<<endl;
}
子树与路径美丽度查询
#include<iostream>
#include<vector>
using namespace std;
int val[200005];//每个节点的值
vector<int> g[200005];//存图
int val_sum[200005];//每个节点的子树的值的和
int ans_sum[2000005];//每个节点的子树的值的和等于k的个数
int dis[200005];//每个节点到1的距离
int ans_dis[2000005];//每个节点到1的距离等于k的个数
void dfs(int u,int fa){
val_sum[u]=val[u];//更新每个节点的子树的值的和
for(int v:g[u]){//遍历每个节点的子节点
if(v==fa) continue;//如果子节点是父节点，跳过
dis[v]=dis[u]+val[v];
dfs(v,u);//递归遍历子节点
val_sum[u]+=val_sum[v];//更新每个节点的子树的值的和
}
}
int main(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>val[i];
}
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dis[1]=val[1];
dfs(1,0);
for(int i=1;i<=n;i++){//统计每个节点的子树的值的和的个数
ans_sum[val_sum[i]]++;
}
for(int i=2;i<=n;i++){//统计每个节点到1的距离的个数
ans_dis[dis[i]]++;
}
for(int i=1;i<=q;i++){
int op,k;
cin>>op>>k;
if(op==1){
cout<<ans_sum[k]<<endl;
}else if(op==2){
cout<<ans_dis[k]<<endl;
}
}
return 0;
}
蜘蛛交友 2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir;
void solve() {
int n, k;
cin >> n >> k;
vector<int> r(n + 1);
for (int i = 1; i <= n; i++) cin >> r[i];
// 初始化每只蜘蛛拥有1个毛绒玩具
vector<int> have(n + 1, 1);
int ans = 0;
// 使用拓扑排序检查是否成环
vector<int> indegree(n + 1, 0);
for (int i = 1; i <= n; i++) {
indegree[r[i]]++; // 计算每个节点的入度
}
int count = 0; // 记录已处理的节点数量
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
count++;
}
}
if (count == 0) {
cout << 2 << "\n"; // 输出2表示成环
return;
}
while (true) {
vector<int> next_have(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (have[i] > 0) {
next_have[i] = have[i] - 1;
}
}
// 每只蜘蛛给目标蜘蛛一个毛绒玩具
for (int i = 1; i <= n; i++) {
if (have[i] > 0) {
next_have[r[i]] += 1;
}
}
// 更新拥有数量，并限制最多保留k个
for (int i = 1; i <= n; i++) {
if (next_have[i] > k) next_have[i] = k;
}
// 检查是否稳定
if (next_have == have) {
break;
}
have = next_have;
ans++;
}
cout << (ans + 2) << "\n"; // 加1以包含最后一次稳定的步骤
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
}
这里空空如也
有帮助，赞一个