首页 > 其他分享 >Codeforces Round 911 (Div. 2)

Codeforces Round 911 (Div. 2)

时间:2023-11-27 12:11:22浏览次数:35  
标签:cnt Submission sum Codeforces 端点 Div 911 对应 dp

A - Cover in Water

三个连续的 . 就可以造出无限水,这时直接输出 \(2\),否则输出区间长度和。

Submission

B - Laura and Operations

每次操作不会改变不需要的两个数的个数的和的奇偶性,而当这个和为偶数的时候,通过若干操作一定可以全部变成另一个。

Submission

C - Anji's Binary Tree

设 \(dp_u\) 表示从 \(u\) 走到叶子最少需要修改多少个点,于是有 \(dp_u = \min(dp_{ls_u} + [s_u \neq 'L'], dp_{rs_u} + [s_u \neq 'R'])\),dfs 一遍即可。

Submission

D - Small GCD

先把 \(a\) 排序,枚举最大的数 \(a_i\),并维护 \(sum = \sum\limits_{j=1}^{i-1} \sum\limits_{k=j+1}^{i} \gcd(a_j,a_k)\),注意到 \(i\) 每增加 \(1\),\(sum\) 增加 \(\sum\limits_{j=1}^{i-2} \gcd(a_{i-1},a_j)\),于是快速求出这个式子即可。

注意到 \(a_i \le 10^5\),于是 \(a_i\) 最多有 \(128\) 个因子,因此可以维护一个 \(cnt_x\) 表示是 \(x\) 的倍数的 \(a_i\) 有多少个。之后容易想到用 \(128^2\) 的时间去容斥(从大到小枚举因子,统计 \(cnt'_x\) 表示和 \(a_i\) 的 \(\gcd\) 为 \(x\) 的数有多少个,算出 \(cnt'_x\) 后枚举小于 \(x\) 的因子,将 \(x\) 的因子对应的位置的 \(cnt'\) 减去 \(cnt'_x\)),但是速度难以接受。不过发现枚举 \(x\) 的因子这一步可以通过预处理出所有可能的 \(x\) 的因子来加速,复杂度不会证,但是暴力找出最劣情况发现它并不会很慢。

Submission

E - Transitive Graph

\(H\) 中存在一条边 \(u \rightarrow v\) 当且仅当 \(G\) 中从 \(u\) 出发可以沿 \(G\) 中的边到达 \(v\)。

于是 \(G\) 的强连通分量在 \(H\) 中对应一个完全图,可以按任意顺序访问其中所有点。\(G\) 中不在同一强连通分量中的点对间只有单向边。

于是把 \(G\) 按强连通分量缩成 DAG,定义 DAG 中每个点的 \(size\) 为它对应的 SCC 的大小,权值为它对应的 SCC 中的点的权值和,\(H\) 中的最长路径即为 DAG 中满足经过的点的 \(size\) 之和最大的路径。这个可以用 dp 求出。要求路径权值最小则可以在 dp 的同时维护一个最小权值。

DAG 不需要建出来,因为 Tarjan 算法得到 SCC 的顺序是逆拓扑序。

Submission

F - Local Deletions

先考虑对全局的询问(\(l=1,r=n\)),注意到一个点是局部最小值(最大值)时,它周围的两个点一定不是,于是每次操作留下来的数不超过原来的一半,直接暴力就是 \(O(n)\) 的。

现在考虑 \(l > 1,r < n\) 的询问,先暴力求出全局的答案,并记录每层剩余的数。

对于第一层,发现如果一个位置 \(i\) 不在询问的端点上(\(i \neq l, i \neq r\))则这个位置能被保留,当且仅当在对全局操作第一次的时候,这个位置被保留。因为这个位置是否是局部最值仅由它左右两个数决定。之后每一层同理。

于是除了两边的两个点,中间的位置在操作后对应的新序列对应对全局操作后对应的新序列上的一段区间,容易二分找出下一层中新区间的端点。

对于两边的点,则视作在一个区间的左右各添加一个数,根据第一段的分析,添加的数和区间的端点至多保留其一。于是每次操作都默认区间左右端点收缩一位,并更新左右添加的数,这样就得到了一个子问题,可以递归处理。

但是当区间长度小于 \(3\) 时,上面的操作就不成立了,这时直接暴力即可。

注意特判:如果添加的数和端点都不会保留,则将添加的数更新为下一层中对应新区间的对应端点,如果新区间为空,则可以直接在添加的两个数中取出答案。

Submission

标签:cnt,Submission,sum,Codeforces,端点,Div,911,对应,dp
From: https://www.cnblogs.com/xzmxzm/p/cf1900.html

相关文章

  • 汇编div的注意
    无符号除法32位模式下,DIV(无符号除法)指令执行8位、16位和32位无符号数除法,结果以余数和商的方式表现。格式如下:DIV8位寄存器或内存DIV16位寄存器或内存DIV32位寄存器或内存被除数除数商余数AXreg/mem8ALAHDX:AXreg/mem16AXDXEDX:EAXreg/mem32EAXEDX根据以上表格可......
  • Codeforces Round 911 (Div. 2) A
    真的太菜了……题目链接:Problem-A-Codeforces//Problem:A.CoverinWater//Contest:Codeforces-CodeforcesRound911(Div.2)//URL:https://codeforces.com/contest/1900/problem/0#//MemoryLimit:256MB//TimeLimit:1000ms////PoweredbyCPEd......
  • [Codeforces] CF1799B Equalize by Divide
    序列操作(divide.cpp)—CF1799B—1200题目描述给您一个\(a_1,a_2,\dotsa_n\)这样的正整数数组,您可以对它进行多次(可以是零次)这样的操作:选择两个索引\(i,j(1\leqi,j\leqn,i\neqj)\);将\(a_i\)赋值为\(\lceil\frac{a_i}{a_j}\rceil\)。这里的\(\lceilx\rceil\)......
  • [Codeforces] CF1747C Swap Game
    游戏(game.cpp)—CF1747C—1200\(时间:1s\space|\space空间:250MB\)题面翻译Alice和Bob两个人在玩游戏。有一个长度为\(n\)的序列\(a\),Alice和Bob两人轮流完成一个操作,Alice先开始。每个人可以将数列的第一个数减\(1\),并将它与后面序列的一个数进行交换,如果一个......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)A-JaggedSwaps解题思路:若\(a[1]=1\),则可以。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<int,int>pii;#definefifirst#definesesecondvoidsolve(){......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)A-JaggedSwapsintmain(){IOS;for(cin>>_;_;--_){cin>>n;rep(i,1,n)cin>>a[i];while(true){boolf=0;rep(i,......
  • CodeTON Round 7 (Div. 1 + Div. 2) 解题报告
    CodeTONRound7(Div.1+Div.2)ContestLink广告:本场比赛博主使用了CCH完成,体验很好,推荐高rating用户使用(低rating受cloudflare影响很大)。A.JaggedSwaps\(\text{Status:\color{green}+\color{black}00:03}\)结论:输出YES当且仅当\(a_1=1\)。证明:如......
  • CF 158 (Rated for Div
    CF-158这次比赛较上次也是有进步,成功地多AC了一道题。但第4题也是很遗憾只差一点了。A.LineTrip题意:车在数轴上从$0$点到达$x$点又返回$0$点,有$k$点的油,可以走$k$个单位,在数轴上$a_1,a_2,a_3...a_n$处可以加油到$k$点,$0$点处和$x$点处无法加油,问$k$的最小值。思路:那么根据题......
  • CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound7(Div.1+Div.2,Rated,Prizes!)基本情况A题花了快半小时,做出来了但是不如正解。B题又是老毛病,一条路走到黑,爆搜打出来超时就死命想剪枝和记忆化,没想过换方法(觉得贪心不可行)。A-JaggedSwaps我的解法没啥好说的,纯模拟。看到\(n\leq10\)知道能过。......
  • Educational Codeforces Round 158 (Rated for Div. 2)
    EducationalCodeforcesRound158(RatedforDiv.2)基本情况A题很水,几分钟秒了。B题想到一个解,被自己hack掉之后没有重新想,一直想在自己一开始的基础上改好,结果最后B都没拿下。B.ChipandRibbon我的思路其实也是找规律,根本没严谨地证明正确性。不应该一条路走到黑的......