首页 > 其他分享 >24.10.07

24.10.07

时间:2024-10-07 22:02:56浏览次数:7  
标签:le 07 int max 宠物 24.10 克制 转移

A

质朴的想法,每一行都放 ryxyryx...,然后因为有 \(40\) 列所以最后一列完全没用,所以把那一行竖着放进去,算一下有 \(2223\) 个。

然后枚举填多少行,如果数量多了就在最后一行选一个位置插入字符(这样后面就没有斜着的贡献了)。还多就从后往前覆盖 y。然后总可以构造出来。

B

5k 翻译版题面:

同学的策略形如 \(\{p_n\}\),其中 \(p_i\) 表示救 \(i\) 房间里的人的概率,而且显然有 \(0\le p_i\le 1,\sum p_i\le 1\)。
求最小的 \(m\),使得存在一种同学的策略,满足无论老师刀哪个房间的人,刀掉的期望人数都不超过 \(m\)。

学生选 \(i\) 的概率是 \(p_i\)。那么老师选 \(i\) 的期望人数是 \((1-p_i)a_i\)。

二分答案,学生要使老师选任何房间的期望都 \(\le mid\),如果 \(a_i > mid\),学生需要分配一个概率使 \((1-p_i)a_i\) 恰好等于 \(mid\)。最后合法的要求是 \(\sum_{i=1}^n p_i \le 1\)。

C

考虑给你一个排列 \(p\),如何快速计算所有的 \(F\)。可以将所有 \(p\) 按从大到小的顺序加入,那么假设加入了 \(\ge k\) 的 \(p\) 后最大连续段长度为 \(L\),我们令 \(F(L), F(L - 1),\dots F(1)\) 都对 \(k\) 进行 chkmax 即可。

反过来,如果有了 \(F\),那么相当于一些限制条件:加入了所有 \(\ge k\) 的 \(p\) 后,最大连续段长度恰好为 \(L\)。考虑逆向操作,即删除 \(< k\) 的 \(p\)(从小往大删除)。维护当前的连续段情况,每次即选择一条连续段裂开,长度减一。这样做的好处是连续段之间不作区分,可以排序,总状态数即为划分数。直接 DP 即可。

D

省集原神。

感觉省集题面亲民多了。

省集:

有 \(n\) 个宠物在进行宠物对战,每只宠物是水(\(A\))、火(\(B\))、佬(\(C\))、菜(\(D\))四种属性之一。宠物分别编号为 \(1\) 到 \(n\)。

属性克制关系如下:

- “水”和“火”互相克制

- “佬”分别克制“水”“火”“菜”三种属性

- “佬”“水”“火”三种属性都克制“菜”

- 其它上述没有提到的都不克制

很显然,这是个极度不平衡的游戏,所以大家两两对战若干场之后就再也没人玩了,只留下了一份比赛中克制关系的记录。

现在你拿到了这份残缺不全的记录,也就是 \(n\) 只宠物之间一部分对战场次的克制关系。你想要从中恢复这 \(n\) 只宠物各自的属性信息,不过因为符合条件的属性信息可能有多种,你只需要输出任意一种解即可。

第一行两个非负整数 \(n,m\) 依次表示宠物个数和已知的克制关系条数。

接下来 \(m\) 行每行三个整数 \(x,y,z\) 表示一条记录。其中 \(z=0\) 表示已知 \(x\) 号不克制 \(y\) 号,\(z=1\) 表示已知 \(x\) 号克制 \(y\) 号。


形式化题面:

给定一个 0/1 权有向图,给每个点赋权 ABCD 中的一个使每条有向边 \((u,v,w)\) 都满足 \(w=1 \Leftrightarrow (a_u, a_v) \in \{(A.B),(A,D), (B,A), (B,D), (C,A), (C,B),(C,D)\}\)。

发现佬和菜是很强的,如果一个点能填佬菜那么填上不会亏。

填完佬菜就是平凡染色问题了。

考虑怎么填佬菜。0 边的反图和 1 边的图是相似的,但是 1 边的图限制更强,0 边的反图可以相等,1 边图不行。

考虑 0 边的反图和 1 边的图,一个点可以填佬当且仅当在两个图里没有入度,但是 0 边可以相等,所以对 0 边反图缩点之后拓扑,对于当前没有入度的强连通分量,里面的每一个点在 1 边图都没有入度,那么这个连通分量都可以是佬。

菜是类似的,要求没有出度。


P6764

P6764 [APIO2020] 粉刷墙壁

观察数据范围:令 \(f(k)\) 表示喜欢第 \(k\) 种颜色的承包商数量,\(\sum f(k)^2\le400000\)。

小啊,很小啊(

设 \(f_{i, j}\) 表示在 \(i\) 让 \(j\) 承包商开始刷最远刷多远。那么 \(f_{i, j} = f_{i + 1,(j + 1)\bmod m} + 1\)。

然后枚举对每个 \(i\) 只枚举喜欢 \(C_i\) 的承包商,然后用滚动数组优化。根据数据范围时间复杂度可以接受。

然后对于每个 \(i\),如果存在一个 \(j\) 使得 \(f_{i, j} \ge m\) 那么这个起点就是合法的。

知道哪些起点合法就是简单贪心了。

P3354

P3354 [IOI2005] Riv 河流

根据树形 dp 经典讨论,肯定有一维是 \(x\),有一维表示子树内建了 \(k\) 个厂,0/1 表示根是否建厂。

但是这些状态不太能算花费,如果在 \(x\) 建厂时结算。把运费放状态里更是扯淡。

所以考虑在出发时就把终点定好。

设 \(f_{x, u, i, 0/1}\) 表示考虑到 \(x\) 点子树内最近的建厂祖先是 \(u\),子树内一共建了 \(i\) 个厂,\(x\) 是否建厂的最小花费。

由于转移时和最后求答案都不关注根节点的建厂情况,所以可以在处理完 \(x\) 后把 \(1\) 状态统一并入 \(0\) 状态简化转移时的讨论。

现在对于子节点 \(f_{y, u, i, 0}\) 表示子树内最近的目标是 \(u\),建了 \(i\) 个厂的最小花费。

for (int u = x; ~u; u = fa[u]) {
    per(j, k, 0) {
        f[x][u][j][0] += f[y][u][0][0];
        f[x][u][j][1] += f[y][x][0][0];
        rep(l, 0, j) {
            chkmin(f[x][u][j][0], f[x][u][j - l][0] + f[y][u][l][0]);
            chkmin(f[x][u][j][1], f[x][u][j - l][1] + f[y][x][l][0]);
        }
    }
}

最后将 \(1\) 状态并入 \(0\) 状态,注意上面算的时候没有把建在 \(x\) 的厂统计进状态。

for (int u = x; ~u; u = fa[u])
    rep(j, 0, k) {
        f[x][u][j][0] += w[x] * (dis[x] - dis[u]);
        if (j >= 1) chkmin(f[x][u][j][0], f[x][u][j - 1][1]);
	}

P3647

P3647 [APIO2014] 连珠线

换根 dp。

如果指定起始珠子(指定根节点),那么合法蓝线一定是跨 \(fa_x -x-son_x\)。

设 \(f_{x, 0/1}\) 表示 \(x\) 是否是蓝线中点的最大得分。

转移时 \(0\) 的转移平凡,\(1\) 的转移枚举选那个儿子转移最大。

\[f_{x, 0} \gets f_{x, 0} + \max(f_{y, 0}, f_{y, 1} + w(x, y))\\ f_{x, 1} \gets f_{x, 0} + \max(f_{y, 0} + w(x, y) - \max(f_{y, 0}, f_{y, 1} + w(x, y))) \]

现在不指定根,考虑换根,在 \(x\) 成为 \(y\) 的儿子时,首先失去了 \(y\) 子树的贡献,其次如果 \(x\) 有父亲的话还有从父亲转移过来。

\(y\) 减少的贡献一是对 \(f_{x, 0}\) 的贡献,二是如果 \(f_{x, 1}\) 从 \(y\) 转移也不能用了,所以还需记录 \(1\) 的转移的次大值。

在转移时注意 \(1\) 的转移还要和 \(fa_x\) 的贡献取 \(\max\)。

学到一种新的写法,在第一遍 dfs 是处理出 \(x\) 对于每个儿子的 dp 数组和最大值,第二遍 dfs 时可以直接拿来用了。

P3554

P3554 [POI2013] LUK-Triumphal arch

原题面的故事挺有趣的。最坏情况确实可以等价于 B 采取最优决策博弈。

答案显然满足可二分性。考虑如何判断一个 \(k\) 是否合法。

B 采取最优决策显然不会走回头路,那么是一路从根走到叶子。

A 输了也就是 B 在 \(x\) 时 A 未将 \(x\) 的所有儿子染黑。

那么 \(x\) 的儿子数 \(> k\) 时就需要祖先救一下,设 \(f_x\) 表示 \(x\) 子树内需要祖先提前染多少点。

那么 \(f_x = \max(0, soncnt_x - k + \sum f_y)\)。

如果最后 \(f_1 = 0\) 那么 \(k\) 合法,不然不合法。

这套题单里代码最好写的紫,但是想不到。

弦化

经典 subtask 随便绑导致随机部分分。

考到衡中一年前的原题然后被一年前的 int_R5k 踩爆了/kk

考试时一道题开了两个链式前向星四个 vector 吓得我下午在 DP 题里完成了存图的缺省源/jk

namespace GRAPH {
	const int N = 3e5 + 10, M = 3e5 + 10;
	struct Edge {int y, nxt; long long w;};
	struct Graph {
		Edge e[M << 1]; int ly[N], ltp;
		void add(int x, int y, long long w = 0) {e[++ltp] = {y, ly[x], w}; ly[x] = ltp;}

		Edge &operator[](int x) {return e[x];}
	};
}
using GRAPH::Graph;
#define redg(i, e, x, y) for (int i = e.ly[x], y; y = e[i].y, i; i = e[i].nxt)
Graph e;

说到弦化其实我觉得小画家不戴眼镜比戴眼镜好看。

标签:le,07,int,max,宠物,24.10,克制,转移
From: https://www.cnblogs.com/KinNa-Sky/p/18450734

相关文章

  • 2024.10.05 刷题记录
    2024.10.05刷题记录P7597「EZEC-8」猜树加强版不难发现\(u\)的儿子的条件是在\(u\)的子树内且深度比\(u\)恰好大\(1\)。每次询问子树内的所有节点深度或许可以解决此题,但询问次数达到了\(n^2\)。在\(u\)的子树内,如果知道所属其他儿子的子树的节点,知道属于\(u\)......
  • SS241007B. 逆序对(inverse)
    SS241007B.逆序对(inverse)题意给你一个长度为\(n\)的排列,你可以选择一对\((i,j)\),交换\(p_i,p_j\),或者不操作,使减少的逆序对个数最多,求最多减少几个逆序对。思路首先考虑交换\(i,j\)会对哪些部分的逆序对数量产生影响。不难发现,如果我们画一个二维平面,上面有\(n\)个点......
  • 20241007
    sequence我们会发现,我们每次删的一定是长度最短的那个,所以我们可以最开始按照长的排一下序,然后用线段树维护每一个区间中还有几个数,每次加上答案后在两个端点打上标记即可#include<bits/stdc++.h>#define_1(__int128)1usingnamespacestd;usingll=longlong;vo......
  • 2024.10.7 鲜花
    【UNR#3】百鸽笼花の塔君が持ってきた漫画くれた知らない名前のお花今日はまだ来ないかな?初めての感情知ってしまった窓に飾った絵画をなぞってひとりで宇宙を旅してそれだけでいいはずだったのに君の手を握ってしまったら孤独を知らないこの街にはもう二度と帰ってく......
  • 软考07——数据库
    ◆数据:是数据库中存储的基本对象,是描述事物的符号记录.数据的种类:文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等。◆数据库DB:是长期存储在计算机内、有组织的、可共享的大量数据的集合.◆数据库的基本特征数据按一定的数据模型组织、描述和存储;可为各种用户共......
  • 2024/10/07 模拟赛总结
    \(20+55+25+0=100\),压线拿到小饼干!#A.A可以发现\(u_i=A,v_i=B,w_i=C\)至少有一个成立,将这些点抽象到三位空间中。则原长方体一定被一个从\((1,1,1)\)出发的长方体打穿,但是似乎重叠部分比较难实现对于从底打到顶的长方体,可以用后缀\(\max\)解决,然后原长方体就变成了阶梯......
  • 团队训练记录2024.10.7
    赛时依然和本校强队差两题比赛链接:https://codeforces.com/gym/104901A.ManyManyHeads这里先用栈处理好第一个状况,然后根据层数进行第二个状况是否存在判断#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;llgcd(llx,lly){if(y==0)retu......
  • HO引擎近况20241007
    又好几个月没更新,原因是感觉人生有点迷茫了6月这被公司裁员了8月才找到工作,还是原同事推荐的,只凭简历的话根本没可能新的公司又让我长见识了,完全不考虑程序的设计和日后的扩展及维护,只求快速出东西,俩月出一个DEMO,次留好就继续,不好就砍掉项目继续也不是重新正式开发,它没有一个......
  • 2024.10.7 test
    nf#33B有一棵包含\(n\)个节点的有根树,且树的高度不超过\(100\)。每次操作时可以选择一个节点\(u\),使其与父节点断开(如果有),成为一颗新树的根节点,然后删除以节点\(u\)为根的树中的所有叶节点。求删除所有节点所需的最少操作次数和通过最少次操作删除所有节点的方案数。\(n......
  • 707_设计链表
    707_设计链表【问题描述】你可以选择使用单链表或者双链表,设计并实现自己的链表。单链表中的节点应该具备两个属性:val和next。val是当前节点的值,next是指向下一个节点的指针/引用。如果是双向链表,则还需要属性prev以指示链表中的上一个节点。假设链表中的所有节点下标......