首页 > 其他分享 >CF套题4翻译(uoj转载)

CF套题4翻译(uoj转载)

时间:2024-09-27 08:50:55浏览次数:8  
标签:输出 结点 方案 所有 CF 整数 uoj 节点 套题

\(A\)题:CF1098A

给你一棵树,树根为\(1\)号点。每个点\(i\)有一个非负整数权值\(a_i\),记点\(i\)到根的路径上经过的所有点(包括根和自身)的权值总和为\(s_i\)。

现在擦去所有深度为偶数的点的\(s_i\),求\(\sum a_i\)最小可能是多少,如果无解,输出\(-1\)。

被擦去的\(s_i\)在输入文件中被替换为\(−1\)。


\(B\)题:CF1286B

有一棵形态确定的有根树,结点编号为\(1,\cdots,n\)每个结点\(i\)有权值\(a_i\)。

定义\(c_i\)表示:满足\(j\)在\(i\)子树内且\(a_j < a_i\)的\(j\)的个数。

现在给定所有的\(c_i\),请你构造一种\(a_i\)的方案使得所有\(c_i\)成立,你构造的方案要满足\(1\leq a_i\leq 10^9\)且\(a_i\) 是整数。

输入中,第一行为表示结点数量的\(n(n \leq 2000)\),之后\(n\)行中第\(i\)行两个整数依次为\(p_i\)和\(c_i\),\(p_i\)表示\(i\)的父结点,根节点的\(p_i=0\)。

若存在一组\(a_i\) 满足方案,第一行输出 YES 并在第二行依次输出所有\(a_i\);否则输出一行 NO。


\(C\)题:CF698B

给你一个数组\(p\),让你修改它使它变成一个有效数组。

其中数组有效是指:

1.其对应一棵树。

2.有且只有一个索引\(r\),符合\(p_r=r\)。其中顶点\(r\)是树的根。

3.对于其余的\(\forall i\),\(i\)与\(p_i\)之间有边

请你输出最小修改次数,及一种修改方案(输出修改后数组)。


\(D\)题:CF29D

蚂蚁想要访问树中的每个节点并返回到根,每条边都要恰好经过两次。此外,他想以特定的顺序访问节点。你要找到蚂蚁的可能路线。

输入:

第一行包含整数\(N\) \((3 \le N \le 300)\)代表树中的顶点数量。接下来的\(N-1\)行描述边。每个边用两个整数来描述,即它连接的顶点的编号。均为无向边。顶点从\(1\)开始编号,\(1\)是根节点。最后一行包含\(k\)个整数,其中\(k\)是树中叶子的数量。这些数字描述了叶节点应该被访问的顺序。保证每个叶节点只出现一次。

输出:

如果所需的路径不存在,输出\(-1\)。否则,输出\(2N-1\)个数字,描述路径。每次蚂蚁到达一个节点时,输出它的编号。


\(E\)题:CF260D

树中的每个节点都涂成黑色或白色,不会有两个颜色相同的节点通过边连接。 每条边都包含写在其上的非负整数值。

一个坏男孩 Vasya 走到黑板上并在每个节点\(v\)附近写下数字\(s_v\)——所有与该节点相关的边的值的总和。 然后 Vasya 从板上取下和它们的值。

您的任务是通过节点颜色和数字\(s_v\)恢复原始树(给出任意方案即可,保证有解)。


\(F\)题:CF1566E

对于一棵有根树,定义一个节点\(i\)是叶子结点,仅当\(i\)没有子节点。

进一步定义一个节点\(i\)是“可移动节点”,仅当\(i\)不是根、不是叶子节点且其所有直接相连的子节点都是叶子结点。

你可以对任意“可移动节点”\(i\)进行下列操作任意次:

断开\(i\)与其父亲节点的边,选择任意一个不属于节点\(i\)及其子树的节点\(j\)并在\(i\),\(j\)间连边。

给定一棵以节点\(1\)为根的\(n\)个节点的有根树,求经过若干次操作后,这棵树最少有几个叶子结点。\(T\)组数据。

\(1≤T≤10^4\),\(1≤n\),\(∑n≤2×10^5\)

给定的是棵树.


\(G\)题:CF1586E

给定一个\(n\)个点\(m\)条边的无向连通图,无重边自环。

给出\(q\)个形如\(x\) \(y\)的操作,你要选定一条从\(x\)到\(y\)的路径,并将其上所有边的权值(初始为\(0\))\(++\)。

要求\(q\)次操作完后,所有边边权为偶数。

如果可以,输出YES并给出一组方案。

否则输出NO,并回答至少添加多少个额外的询问才能有合法方案。


各处P来的翻译qwq

标签:输出,结点,方案,所有,CF,整数,uoj,节点,套题
From: https://www.cnblogs.com/zsj6315/p/18434948

相关文章

  • CF1592F2-Alice and Recoloring 2-分析、二分图
    link:https://codeforces.com/contest/1592/problem/F2题意:给定一个\(n\)行\(m\)列的目标矩阵,矩阵元素只有W或B,并且你有一个初始矩阵,元素全为W。现在你可以矩阵实施以下操作:使用一块钱,选定一个包含\((1,1)\)的子矩阵,把矩阵中的元素全部反转(W变B,B变W)。使用......
  • CF1063E Lasers and Mirrors题解
    一道很好的手玩题,被薄纱了。首先判掉\(\foralli,p_i=i\)的情况(显然是\(n\))然后考虑按照\(p_i\)连边,先构造每一个环的方案。发现可以简单放置两面镜子使得\(i\)射到\(p_i\),而且只要从高到底构造,一定不会产生影响。但是每一个环的最后一个点很特殊,因为第1个点下面放置了让第1个......
  • 题解:CF437B The Child and Set
    CF437BTheChildandSet题解这题目就一个问题。啥是\(\operatorname{lowbit}\)?\(\operatorname{lowbit}(x)\)是指\(x\)的二进制表示中最低位的\(1\)所表示的值。例如\((14)_{10}=(1110)_2\),其中最低位的\(1\)在第二位,表示\((2)_{10}\),即\(\operatorname{lo......
  • Abp 使用app.UseStaticFiles配置静态文件中间件以达到创建虚拟路径
    若访问项目文件wwwroot以外的其他静态文件使用如下方式访问1.配置文件中配置路径(appsetting)"App":{"ServerRootAddress":"https://localhost:44301/","ClientRootAddress":"https://localhost:4200/","CorsOrigins":"......
  • 12位院士齐聚CCF HPC China,热议科研新范式:超智融合/算网融合/科学智能计算……
    图灵奖得主JimGray曾划分了科学研究的四大范式,即实验科学、理论科学、计算科学与数据密集型科学。近年来,随着AI的爆发式发展,也有业内人士称「科研的第五范式已经到来」。在科学研究范式的迭代中,数据的核心作用从未改变。可喜的是,随着科研范式从计算走向AI,数据产出的成本也在......
  • CCF CSP-S 2024 提高组初赛解析
    CertifiedSoftwareProfessional-Senior非专业级软件能力认证测试本解析不提供阅读程序与完善程序题目的代码,如有需要请通过luogu.com.cn相关链接下载如有谬误烦请指正答案AACBBBDABDACBCD✓××BC✓✓✓BCC✓×✓CACAAAAAAABAA单项选择1在Linux系统中,如......
  • 题解:CF1799F Halve or Subtract
    \(\text{Link}\)介绍一下一种高维wqs的方法。此方法来自@YeahPotato的专栏严谨的WQS二分方法。题意给定一个长为\(n\)的序列\(v_{1\dotsn}\),三个常数\(d,a,b\)。你可以执行若干次以下两种操作:选择\(1\lei\len\),令\(v_i\gets\lceil\frac{v_i}{2}\rceil\)。......
  • [CF1842H]Tenzing and Random Real Numbers
    题面原题传送门题面机翻有\(n\)个介于0和1之间(包括0和1)的均匀随机实变量,记为\(x_1,x_2,\ldots,x_n\)。Tenzing有\(m\)个条件。每个条件的形式为\(x_i+x_j\le1\)或\(x_i+x_j\ge1\)。Tenzing想要知道所有条件都满足的概率,模为\(998~244~353\)。形式上......
  • CF1207E XOR Guessing
    思路设答案为\(a\),第一次异或的数为\(b\),第二次异或的数为\(c\),则可以通过两次询问知道\(a\oplusb\)和\(a\oplusc\),所以\(b\oplusc=(a\oplusb)\oplus(a\oplusc)\)。因为范围为\([0,2^{14}-1]\),且每次询问只有\(100\)次,所以可以让第一次询问\(\{1,2,\cdots......
  • 题解:CF573D Bear and Cavalry
    因为这是远古题目,所以根据现在的评测机速度,用\(O(nq)\)的做法也是可以过的。也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种\(O(n)\)的算法求解答案。这道题类似资源分配型动态规划,所以我们可以设\(dp_i\)表示分配前\(i\)个人的答案。直接写是不行的,我......