多比特杯武汉工程大学第六届ACM新生赛 A,L

admin管理员组

文章数量:1123195

多比特杯武汉工程大学第六届ACM新生赛 A,L

为什么要演奏春日影！！！

看到题目所说，若 b i b_i bi​在 i i i 之前，则…,那么很容易联想到拓扑排序，再仔细看题，对于每个 b i b_i bi​,我们都想其对应的 i 进行连边，那么我们很容易得到到一个图，又因为题目所给定的为 n +1 个点，n 条边，所以显然整个图的构成为一条链加上多个环，且0这个点一定是处于链上，若在链上的 b i b_i bi​不为 0 ，那么其贡献一定为 c ，否则贡献则为 a。再考虑环对于答案的贡献，对于环上的点，其中一个点的贡献为 a ，剩余点的贡献为 c ，我们贪心去算出每个点为 a 时其环的对应的价值即可，然后取最大。

整个题的实现方法有两种，第一种就是拓扑排序找链，然后剩下入度不为 0 的点则为环，然后对环去dfs即可。

#include <bits/stdc++.h>using namespace std;
const int N = 4e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"vector<pll> e[N];
int d[N];
ll res;
void dfs(int x)
{for(auto [u,w]: e[x]){if(d[u]){d[u]=0;res=max(res,w);dfs(u);}}
}
void solve()
{int n;cin>>n;ll ans=0;for(int i=1;i<=n;i++){int a,b,c;cin>>a>>b>>c;if(b==0){ans+=a;}else ans+=c;e[b].push_back({i,a-c});d[i]++;}//cout<<ans<<endl;queue<int >q;for(int i=0;i<=n;i++){if(!d[i]) q.push(i);}while(!q.empty()){auto t=q.front();q.pop();for(auto [x,y]: e[t]){d[x]--;if(d[x]==0) q.push(x);}}for(int i=1;i<=n;i++){if(d[i]){res=-1e18;dfs(i);ans+=res;
//             cout<<i<<" ";
//             cout<<res<<endl;}}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

第二种则是求出每个强连通分量，对于强连通分量大小为 1 的点，其一定在链上，可以直接计算其价值，否则直接对所在的强连通分量进行遍历即可。

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9 + 7;
const int maxv = 4e6 + 5;
// #define endl "\n"struct node
{ll a,b,c;
}z[N];
vector<int> e[N];
int n;
int tot, dfsn[N], ins[N], low[N];
stack<int> s;
vector<vector<int>> scc;
vector<int> b(N);
ll val[N];
void dfs(int x)
{low[x] = dfsn[x] = ++tot, ins[x] = 1, s.push(x);for (auto u : e[x]){if (!dfsn[u]){dfs(u);low[x] = min(low[x], low[u]);}else if (ins[u])low[x] = min(low[x], dfsn[u]);}if (dfsn[x] == low[x]){vector<int> c;while (1){auto t = s.top();c.push_back(t);ins[t] = 0;s.pop();b[t] = scc.size();val[scc.size()]+=z[t].c;if (t == x)break;}scc.push_back(c);}
}void solve()
{cin>>n;ll tar=0;for(int i=1;i<=n;i++){ll a,b,c;cin>>a>>b>>c;z[i]={a,b,c};int u=b,v=i;e[u].push_back(v);if(b==0) tar+=a-c;}for (int i = 1; i <= n; i++){if (!dfsn[i]){dfs(i);}}ll ans=0;for(int i=0;i<scc.size();i++){if(scc[i].size()==1) ans+=val[i];else{ll res=-1e18;for(auto u: scc[i]){res=max(val[i]-z[u].c+z[u].a,res);}ans+=res;}}cout<<ans+tar<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t = 1;// cin>>t;while (t--){solve();}system("pause");return 0;
}

开心消消乐

一道很新奇的并查集。
因为数据范围只有1e5，所以我们可以预处理出所有情况，我们暴力处理出 1e5 内的所有数字，然后去O(n) 的统计即可。

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int find(int x)
{if(p[x]!=x){return p[x]=find(p[x]);}return x;
}
int p[N];
void solve()
{int n;cin>>n;vector<int> a(N);for(int i=1;i<N;i++) p[i]=i;for(int i=1;i<=n;i++){int x;cin>>x;a[x]=1;}for(int i=1;i<N;i++){for(int j=i;j<N;j+=i){if(a[i]&&a[j]){int fa=find(i),fb=find(j);p[fa]=fb;}}}int cnt=0;for(int i=1;i<N;i++){if(a[i]){if(p[i]==i) cnt++;}}cout<<cnt<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}

本文标签： 多比特杯武汉工程大学第六届ACM新生赛 AL