Codeforces Round 916 (Div. 3)(E:贪心 F贪心dfs G tarjan+topsort +线段树优化建图)

A：直接暴力统计每个字符的次数是否达标即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];void solve()
{cin>>n;string s;cin>>s;map<int,int> mp;for(auto x:s)mp[x-'A'+1]++;int res=0;for(int i=1;i<=n;i++){if(mp[i]>=i) res++;}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

B：直接先输出所需要的k，然后降序输出剩下的即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];
PII d[N];
void solve()
{cin>>n>>k;int l=1,r=n;for(int i=n-k;i<=n;i++){cout<<i<<" ";}for(int i=n-k-1;i>=1;i--) cout<<i<<" ";cout<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

C：

直接枚举最后操作到哪个位置就行了，然后贪心一直操作1到i的位置的b最大值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];void solve()
{cin>>n>>k;vector<int> s(n+10);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];int mx=0;int res=0,now=0;for(int i=1;i<=n;i++){if(i>k) break;now+=a[i];mx=max(mx,b[i]);res=max(res,now+mx*(k-i));}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

D：

先固定第一次是A 第二次是B 第三次是C

枚举B为中介点i，然后求1到i-1的A的最大值，和i+1到n的C最大值即可

然后三个数有6个排列暴力枚举即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];void solve()
{cin>>n;vector<int> a(n+10),b(n+10),c(n+10);for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) cin>>c[i];auto get=[&](vector<int>&a,vector<int>&b,vector<int>&c){int mx=0;vector<int> l(n+10),r(n+10);for(int i=1;i<=n;i++) l[i]=max(a[i],l[i-1]);for(int i=n;i>=1;i--) r[i]=max(r[i+1],c[i]);for(int i=2;i<n;i++){mx=max(mx,l[i-1]+r[i+1]+b[i]);}return mx;};cout<<max({get(a,b,c),get(a,c,b),get(b,a,c),get(b,c,a),get(c,a,b),get(c,b,a)})<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

E:这个题我好像杭电多校做过...

范围那么大不太可能dp，不如从贪心切入

先想某个人取i位置贡献是啥，贡献是这个人获得了（a[i]-1），另外一个人失去了b[i]

所以这个人其实一共获得了a[i]-1+b[i]的价值

所以我们直接拿个堆维护当前a[i]+b[i]的最大值即可

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];
PII d[N];
void solve()
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];vector<bool> st(n+10);priority_queue<PII> q;for(int i=1;i<=n;i++){q.emplace(a[i]+b[i],i);}//sort(d+1,d+1+n);int res=0;int now=0;int l=1,r=n;for(int i=1;i<=n;i++,now^=1){if(now==0){auto x=q.top();res+=a[x.second]-1;q.pop();}else{auto x=q.top();res-=(b[x.second]-1);q.pop();}}cout<<res<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

F：

贪心吧我觉得

手玩一下样例可以发现，这跟子树大小有关的

假如1的子树有三个

x,y,z，他们不能内部消化的点分别是是 4 2 1

x,y,z，他们本身的子树大小是 4 6 4

我们的目标是让内部不能消化的点通过匹配其他点来消失

我们可以发现x的4个不能内部消化的点，可以和y和z一共3个不能消化的点配对

那么是不是就多出了一个不能消化点呢？

答案是错误的，不妨这么想，x的四个点直接和y子树的随便四个点来配合，

y的两个不能内部消化的点和z可以内部消化的点和不能内部消化的点都能拿来随便用。

可是如果x的子树不能配对的子树大小是10，那么这10个子树不能通过y,z的子树的点来全部配对完

肯定还有剩余的，且这些剩余的不能内部消化

贪心的假设当前点u的儿子节点x不能配对的数最大是 mx，那么如果，他其他子树的全部节点都不够这个mx大，即拿其他子树的全部节点都不能匹配完当前最大子树不能内部消化的点数，那么

他剩下既不能跟其他子树匹配且不能内部消化的剩余的点mx-(sz[u]-size[x])的往上传，让父节点的其他节点来匹配

所以我们维护一个当前u点不能配对的数 res.first

res.second就是维护的当前子树的大小

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;
int N;
vector<int>G[2<<17];
int ch[2<<17];
int dfs0(int u)
{ch[u]=1;for(int v:G[u])ch[u]+=dfs0(v);return ch[u];
}
int dfs1(int u,int L)
{int mx=0,mxv=-1;for(int v:G[u]){if(mx<ch[v])mx=ch[v],mxv=v;}if(ch[u]-1-mx>=mx){return min(L,(ch[u]-1)/2*2);}else{assert(mxv!=-1);int nL=mx-(ch[u]-1-mx);int ret=dfs1(mxv,nL);ret+=(ch[u]-1-mx)*2;return min(L,ret);}
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;for(;T--;){cin>>N;for(int i=0;i<N;i++)G[i].clear();for(int i=1;i<N;i++){int p;cin>>p;G[p-1].push_back(i);}dfs0(0);cout<<dfs1(0,N)/2<<"\n";}
}

G1:

操作题先想操作的性质

比如例子

3 2 1 3 1 2

我们操作2，那么两个2之间就能全部点亮，再通过3再点亮第一个3

即我们颜色为2的点，可以点亮3 1的点，再通过3 1的点再点亮其他

假设最坏情况下，可以一直点亮是什么情况呢

是整个区间都变成一个环

为什么呢

比如 1 2 1 2

点1可以到点2

点2可以到点1，构成环

如果是1 2 2 1

1可以到点2，但是点2不能到1

把环缩成点后就变成了经典的拓扑排序问题

第一个答案就是这个拓扑排序入度为0的点，

方案数就是入度为0的点之间的大小相乘即可

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N],b[N];
vector<int> g[N];int dfn[N],low[N];
int scc_cnt,timestamp;
int stk[N],id[N];
bool in_stk[N];
int sz[N],in[N];
int top;
void tarjan(int u){dfn[u] = low[u] = ++ timestamp;stk[ ++ top] = u, in_stk[u] = true;for (auto j:g[u]){if (!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if (in_stk[j]) low[u] = min(low[u], dfn[j]);}if (dfn[u] == low[u]){++ scc_cnt;int y;do {y = stk[top -- ];in_stk[y] = false;id[y] = scc_cnt;sz[scc_cnt]++;} while (y != u);}}
void solve()
{cin>>n; scc_cnt=timestamp=top=0;for(int i=1;i<=n;i++){g[i].clear();dfn[i]=low[i]=0;in_stk[i]=false;sz[i]=id[i]=in[i]=0;}vector<int> l(n*2+10),r(n*2+10);for(int i=1;i<=n*2;i++){cin>>a[i];if(l[a[i]]==0) l[a[i]]=i;else r[a[i]]=i;}   vector<PII> E;for(int i=1;i<=n;i++){for(int j=l[i]+1;j<=r[i]-1;j++){g[i].push_back(a[j]);E.push_back({i,a[j]});}}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);for(auto [u,v]:E){if(id[u]==id[v]) continue;in[id[v]]++;}int ans=1,cnt=0;for(int i=1;i<=scc_cnt;i++){if(!in[i]){cnt++;ans=2ll*ans*sz[i]%mod;}}cout<<cnt<<" "<<ans<<"\n";
}signed main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t=1;cin>>t;while(t--) solve();
}

G2:

线段树优化建图，每个点最多有nlogn个出边

用线段树优化建图后

我前面有个博客写过tarjan缩点后

因为是拓扑序大的 scc_cnt小，因为tarjan是先到底部的，底部的点会先缩，再回溯到上面缩，

所以拓扑排序正常是从scc_cnt大入度小，所以从scc_cnt大的点开始拓扑排序回去即可

每个点再把他当前联通块的点标记，标记为入度不为0即可

#include<iostream>
#include<cstring>
#include<vector>
#include<array>
using namespace std;
using LL = long long;
const int maxn = 4e5 + 5, mod = 998244353;struct SCC{vector<vector<int> > g, scc;vector<int> dfn, low, stk, id;vector<bool> ins;int ts, n;SCC(const vector<vector<int> > &g) : g(g){n = (int)g.size();dfn.assign(n, 0);low.assign(n, 0);id.assign(n, -1);ins.assign(n, false);stk.reserve(n);ts = 0;build();}void tarjan(int u){dfn[u] = low[u] = ++ts;stk.push_back(u);ins[u] = 1;for(auto j : g[u]){if (!dfn[j]){tarjan(j);low[u] = min(low[u], low[j]);}else if (ins[j]) low[u] = min(low[u], dfn[j]);}if (dfn[u] == low[u]){int scc_cnt = scc.size();scc.push_back({});int y;do{y = stk.back();stk.pop_back();id[y] = scc_cnt;ins[y] = 0;scc.back().push_back(y);}while(y != u);}}void build(){for(int i = 0; i < n; i++){if (!dfn[i]){tarjan(i);}}}
};vector<vector<int> > g;
int a[maxn];
int n;int b[maxn];
void build(int u, int l, int r){if (l == r){g[u].push_back(8 * n + a[r]);g[8*n+a[r]].push_back(u);return;}int mid = (l + r) / 2;g[u].push_back(2 * u);g[u].push_back(2 * u + 1);build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
}void modify(int u, int l, int r, int L, int R, int x){if (l > R || r < L) return;if (l >= L && r <= R){g[x].push_back(u);return;}int mid = (l + r) / 2;modify(2 * u, l, mid, L, R, x);modify(2 * u + 1, mid + 1, r, L, R, x);
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int T;cin >> T;while(T--){cin >> n;vector<array<int, 2> > pos(n + 1);for(int i = 1; i <= 2 * n; i++){cin >> a[i];if (pos[a[i]][0] == 0){pos[a[i]][0] = i;}else{pos[a[i]][1] = i;}}g.assign(9 * n + 1, {});build(1, 1, 2 * n);for(int i = 1; i <= n; i++){auto [l, r] = pos[i];if (l + 1 <= r - 1){modify(1, 1, 2 * n, l + 1, r - 1, 8 * n + i);}}SCC scc(g);const int m = scc.scc.size();vector<int> c(m);for(int i = 0; i < m; i++){int s = 0;for(auto x : scc.scc[i]){s += (x > 8 * n);}c[i] = s;}int cnt = 0, sum = 1;vector<int> bad(m);for(int i = m - 1; i >= 0; i--){if (!bad[i] && c[i] > 0){cnt += 1;sum = 2LL * sum * c[i] % mod;}bad[i] |= (c[i] > 0);for(auto x : scc.scc[i]){for(auto j : g[x]){if (scc.id[j] != i){bad[scc.id[j]] |= bad[i];}}}}cout << cnt << ' ' << sum << '\n';}}

不会线段树优化建图的看这篇文章

「算法笔记」线段树优化建图 - maoyiting - 博客园 (cnblogs.com)