1. Toy模板网首页
  2. > Toy博客

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

10月前 作者：南岸以南南岸哀 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了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)文章来源地址https://www.toymoban.com/news/detail-796770.html

到了这里，关于Codeforces Round 916 (Div. 3)(E:贪心 F贪心dfs G tarjan+topsort +线段树优化建图)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Codeforces Round 882 (Div. 2)

    Codeforces Round 882 (Div. 2)

    目录 A. The Man who became a God  题目分析: B. Hamon Odyssey 题目分析: C. Vampiric Powers, anyone? 题目分析:  n个人分成k组，每一组的力量都是 这样的，那么如果分成k组那么就会有k-1个力量不被统计，将力量总和减去前k-1个最大的力量就是最小的结果   将数组分组，每个组内进行按位与

    2024年02月05日
    浏览(50)
  • Codeforces Round 871 (Div. 4)

    Codeforces Round 871 (Div. 4)

    给定n个长度为10的字符串，问其与codeforces字符串的对应下标字母不同的个数。 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 给定长度为n的数组，问连续相邻为0的最大长度 维护一个全局最大长度res，和当前连续序列的长度cnt。从前往后扫

    2024年02月03日
    浏览(52)

  • Codeforces Round 894 (Div. 3)

    签到题 a数组里，大于等于前一个值的a[i]会被写到b里。直接遍历b，如果b[i]比前一个小就在它前面插一个相等的值 计算反过来的长度，判断是否相等就行 对于没有重复口味的集合，能选出的方案是n*(n-1)/2 （从n个里面选2个的组合数）。二分找出需要多少不同口味的冰淇淋，

    2024年02月11日
    浏览(44)

  • Codeforces Round 867 (Div. 3)

    从所有a[i]+i-1=t的选择种取个max即可 实际上就是取同符号乘积的最大值 找规律，发现结果与边长n的关系是：res = n * (n + 3) - (n - 2) ①当n为奇数时，除了1其他均无解 ②当n为偶数时，我们可以构造一个形如n,1,n - 2,3,...的数列 首先我们可以发现n必定出现在起始位置。如果n不在起

    2024年02月02日
    浏览(48)

  • Codeforces Round 912 (Div. 2)

    大等于2依据冒泡排序即可排序，因此判断下1即可 对每一个数字找哪一位肯定为0填0其他的填1 从后往前考虑加到当前集合或新立一个集合 从最高位开始考虑能否为1，计算能否时每个数当前位为1

    2024年02月04日
    浏览(44)

  • Codeforces Round 866 (Div. 2)

    给出一个仅由_或^组成的字符串，你可以在任意位置添加_或^字符，使得字符串满足： 任意字符要么属于^_^的一部分，要么属于^^的一部分。求最少添加的字符数量。 对于_我们只需处理没有组成^_^的_: ①如果_在首位置且左边没有^则添加^ ②如果_在尾位置且右边没有^则添加

    2023年04月25日
    浏览(56)

  • Codeforces Round 881 (Div. 3)

    给定一个数组，给每个元素涂色。求最大的代价。 代价为每个颜色的代价和。 每个颜色的代价为涂了该颜色的元素的极差。 因为是极差，每个元素要么对答案有正的贡献，要么有负的贡献，要么无贡献。且正负贡献的个数要相同。 因为要最大值，自然就是想有正贡献的是最

    2024年02月09日
    浏览(43)

  • Codeforces Round 926 (Div. 2)

    类似于倍投法，就是在一赔一的情况下,第一次压一块钱,每输一次就押注上一次两倍的金额. 假如资金无限的话,这种方法赢的期望为无穷大.原理类似于二进制，不论你输再多次,只要赢一次总额就增加了1.比如 15 二进制1111，前3把一直输，但是只要第4把赢，就一定可以增加 1

    2024年02月20日
    浏览(44)
  • Codeforces Round 874 (Div. 3)

    Codeforces Round 874 (Div. 3)

    用最少的长度为2的字符串按一定规则拼出s。规则是：前一个字符串的尾与后一个字符串的首相同。 统计s中长度为2的不同字符串数量。 给定数组a[n]和b[n]，重排b后，令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。 将a和b分别按从小到大的顺序匹配便是最优的，一定能满足

    2024年02月05日
    浏览(37)
  • Codeforces Round 868 Div 2

    Codeforces Round 868 Div 2

    要求构造一个仅包含 (1) 和 (-1) 的长度为 (n) 的数组 (a) ，使得存在 (k) 个下标对 ((i, j), i j) 满足 (a_i times a_j = 1) 。 当有 (x) 个 (1) ， (y) 个 (-1) 时，其满足条件的下标对数量为 (frac{x (x - 1)}{2} + frac{y (y - 1)}{2}) 。 由于 (n) 只有 (100) ，直接枚举 (x) 即可。

    2024年02月01日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包