首页 > 其他分享 >P4729 [HNOI2009] 积木游戏

P4729 [HNOI2009] 积木游戏

时间：2023-09-07 21:00:12浏览次数：52  
标签：const 积木 int return P4729 HNOI2009 MOD id define

P4729 [HNOI2009] 积木游戏

Solution

2023.09.06。八个月前做这个题调了六个小时。现在看来，除开欧拉定理的部分，整道题的思路极其清晰易懂，虽然码量大，但并不难码。尽管如此，融合了数据结构、图论（模型构建 + 三元环计数）、拓扑论（欧拉定理）多方面知识点，而且还有四面共角的细节问题，它仍然算得上是一道高位紫。

upd：原来有非图论做法。至少图论做法是真的逆天。

首先用数据结构维护，模拟出天降积木的过程，可以得到各块积木的上下边界的纵坐标，这部分的处理是独立的。

然后对具有 公共角 的的矩形（或地面）进行连边（可以对横纵分别考虑，双指针实现。注意建出的图不能包含重边！），容易证明边数是 \(O(n)\) 的（你可以对矩阵的四条边分别考虑）。

容易想到洞的数量与图上 简单环 的数量有一定的联系。

但这时并不能着急着将环数（以下的环数均表示简单环）当作洞数处理：比如三元环，以及如何处理四面共角。

给出一个统计的思路：数环的总数 \(\to\) 减去三元环的数量 \(\to\) 调整四面共角对正确答案的影响。

三元环计数是相对容易的，这里不赘述其 \(O(n\sqrt{n})\) 的做法。

数总环数可以使用平面图的欧拉定理：\(f + v - e = 2\)（面数 \(f\) 包含 \(1\) 个无穷平面）。注意由于存在四面共角的情况（即存在若干 \(K_4\)），原图并不能当作一个平面图，因此无法嵌入 \(S_0\) 进行考虑（也就是说，你并不能直接使用公式 \(f + v - e = 2\)）。

给一个非平面图的例子：\(2 \times 3\) 个 \(K_4\) 拼接在一起，形成 \(3 \times 4\) 的点阵。

取边长为 \(3\) 的两边的中点，再在边长为 \(4\) 的两边各取中间四个点。

如果你圈出了这 \(6\) 个点组成的六边形，你不难发现，此处有一个图与 \(K_{3, 3}\) 同胚。

我们思考这个四面共角的情况对洞数的贡献是 没有任何意义的，于是可以将 \(K_4\) 转成四元环，考察各数值的变化量。具体如下考虑：

  • 记原图为 \(G\)。删掉 \(G\) 中所有 \(K_4\) 的任意两条没有公共点的边 \(e_1, e_2\)，每个 \(K_4\) 形成一个四元环。记改造的 \(K_4\) 数量为 \(c\)，变换后的图为 \(G^{'}\)。易知 \(G^{'}\) 一定为平面图。

  • 考察对 \(G\) 错误使用欧拉定理计算的答案 与 对 \(G^{'}\) 正确使用欧拉定理计算的答案（即正确答案）以及 \(G\) 与 \(G^{'}\) 相关量之间的联系。

  • 记原图中非 \(K_4\) 内三元环数为 \(t\)。

  • 记 \(G\) 中点数为 \(v\)，边数为 \(e\)，面数为 \(f\)（错误的算法下）。错误使用欧拉定理，得 \(三元环数 + 洞数 + 1 = f = e + 2 - v \xrightarrow{三元环数 = 4c + t} 洞数ans = e - v + 1 - t - 4c\)。

  • 记 \(G^{'}\) 中点数为 \(v^{'} = v\)，边数为 \(e^{'} = e - 2c\)，面数为 \(f^{'}\)（正确的算法下）。正确使用欧拉定理，得 \(三元环数 + 四元环数 + 洞数 + 1 = f^{'} = e^{'} + 2 - v^{'} \xrightarrow{三元环数 = t, 四元环数 = c} 洞数ans^{'} = e - 2c + 2 - v - (c + 1) - t = e - v + 1 - t - 3c\)。

  • 我们发现：\(ans^{'} - ans = c\)。不难猜测，每一个 \(K_4\) 在错误使用欧拉定理的算法下，都会少算 \(-1\) 的代价。事实上，如果你对每个 \(K_4\) 分别考虑，确实会得到这样的结论。不妨自己想一想。

于是，四面共角的偏移量居然如此简洁：只需要在原来的错误算法上，对每个 \(K_4\) 增加 \(1\) 个贡献。

最后回到原题，要求的是每落下一块积木对洞数造成的偏移量。

对此，我们只需要把贡献累计到与对应信息相关联的点中，出现时间最晚的那个即可。

从实现角度来讲，建边的过程是最痛苦的。

#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define lowbit(x) x & (-x)
#define PII pair<int, int>
#define MP make_pair
#define VI vector<int>
#define VII vector<int>::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define SI set<int>
#define SII set<int>::iterator
#define QI queue<int>
using namespace std;
template<typename T> void chkmn(T &a, const T &b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T &b) { (a < b) && (a = b); }
int inc(const int &a, const int &b) { return a + b >= MOD ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return a - b < 0 ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		Sqr(x), k >>= 1;
	}
	return res;
}
const int N = 1e5 + 5;
struct Rectangle
{
	int l, r, bot, top, id;
}R1[N], R2[N];
int n;
struct SGT
{
	struct SegTree
	{
		int l, r;
		int v;
		int tag;
	}tr[N << 2];
	void pushup(int p)
	{
		tr[p].v = max(tr[ls(p)].v, tr[rs(p)].v);
	}
	void build(int p, int l, int r)
	{
		tr[p].l = l;
		tr[p].r = r;
		tr[p].v = 0;
		if(l == r)
			return;
		int mid = l + (r - l) / 2;
		build(ls(p), l, mid);
		build(rs(p), mid + 1, r);
	}
	void cal(SegTree &u, int v)
	{
		u.tag = v;
		u.v = v;
	}
	void pushdown(int p)
	{
		if(tr[p].tag)
		{
			cal(tr[ls(p)], tr[p].tag);
			cal(tr[rs(p)], tr[p].tag);
			tr[p].tag = 0;
		}
	}
	void modify(int p, int l, int r, int v)
	{
		if(tr[p].l >= l && tr[p].r <= r)
		{
			cal(tr[p], v);
			return;
		}
		pushdown(p);
		int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
		if(mid >= l) modify(ls(p), l, r, v);
		if(mid < r) modify(rs(p), l, r, v);
		pushup(p);
	}
	int query(int p, int l, int r)
	{
		if(tr[p].l >= l && tr[p].r <= r)
			return tr[p].v;
		pushdown(p);
		int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
		int res = 0;
		if(mid >= l) chkmx(res, query(ls(p), l, r));
		if(mid < r) chkmx(res, query(rs(p), l, r));
		return res;
	}
}T;
vector<int> G[N]; int d[N];
map<PII, int> mp;
void add(int x, int y)
{
	if(mp[MP(x, y)] || x == y)
		return;
	// printf("edge %d %d\n", x, y);
	mp[MP(x, y)] = mp[MP(y, x)] = 1;
	G[x].EB(y);
	G[y].EB(x);
	++d[x], ++d[y];
}
bool cmp(int x, int y)
{
	return d[x] == d[y] ? x > y : d[x] > d[y];
}
int tag[N];
int ans[N];
int cnt;
struct node
{
	int x, y, id;
}a[N << 2];

vector<int> to[N];
int main()
{
	scanf("%d", &n);
	T.build(1, 1, N - 5);
	for(int i = 1; i <= n; ++i)
	{
		int l, r, h;
		scanf("%d %d %d", &l, &r, &h);
		int x = T.query(1, l + 1, r);
		int bot = x, top = bot + h;
		// printf("%d %d\n", bot, top);
		T.modify(1, l + 1, r, top);
		R2[i] = R1[i] = (Rectangle){l, r, bot, top, i};
		if(bot == 0) add(0, i);
	}
	R1[0] = R2[0] = (Rectangle){-1, -1, -1, -1, 0};

	// horizontally
	sort(R1, R1 + n + 1, [&](Rectangle A, Rectangle B){
		return A.l == B.l ? A.bot < B.bot : A.l < B.l;
	});
	sort(R2, R2 + n + 1, [&](Rectangle A, Rectangle B){
		return A.r == B.r ? A.bot < B.bot : A.r < B.r;
	});
	for(int i = 1, j = 0; i <= n; ++i)
	{
		// printf("cas %d\n", i);
		while(R2[j].r < R1[i].l) ++j;
		while(R2[j].r == R1[i].l && R2[j].bot <= R1[i].top) 
		{
			if(R2[j].top >= R1[i].bot)
				add(R1[i].id, R2[j].id);
			++j;
		}
		--j; if(j) --j;
		// printf("horizontally %d %d\n", R1[i].id, R2[j].id);
	}

	// vertically
	sort(R1, R1 + n + 1, [&](Rectangle A, Rectangle B){
		return A.bot == B.bot ? A.l < B.l : A.bot < B.bot;
	});
	sort(R2, R2 + n + 1, [&](Rectangle A, Rectangle B){
		return A.top == B.top ? A.l < B.l : A.top < B.top;
	});
	for(int i = 1, j = 0; i <= n; ++i)
	{
		// printf("cas %d\n", i);
		while(R2[j].top < R1[i].bot) ++j;
		while(R2[j].top == R1[i].bot && R2[j].l <= R1[i].r) 
		{
			if(R2[j].r >= R1[i].l)
				add(R1[i].id, R2[j].id);
			++j;
		}
		--j; if(j) --j;
		// printf("vertically %d %d\n", R1[i].id, R2[j].id);
	}

	for(int u = 0; u <= n; ++u)
	{
		for(auto v : G[u])
		{
			if(!cmp(u, v)) continue;
			// printf("!!! %d %d\n", u, v);
			ans[max(u, v)]++;
		}
		ans[u]--;
	}

	for(int u = 0; u <= n; ++u)
		for(auto v : G[u])
		{
			if(d[u] > d[v] || (d[u] == d[v] && u > v))
				to[u].EB(v);
		}
	
	for(int u = 0; u <= n; ++u)
	{
		for(auto v : to[u])
		{
			tag[v] = u + 1;
		}
		for(auto v : to[u])
		{
			for(auto w :to[v])
			{
				if(tag[w] == u + 1)
					ans[max({u, v, w})]--;
			}
		}
	}
	
	for(int i = 1; i <= n; ++i)
	{
		a[++cnt] = (node){R1[i].l, R1[i].bot, R1[i].id};
		a[++cnt] = (node){R1[i].l, R1[i].top, R1[i].id};
		a[++cnt] = (node){R1[i].r, R1[i].bot, R1[i].id};
		a[++cnt] = (node){R1[i].r, R1[i].top, R1[i].id};
	}
	sort(a + 1, a + cnt + 1, [&](node A, node B){
		return A.x == B.x ? A.y < B.y : A.x < B.x;
	});
	for(int i = 1; i + 3 <= cnt; ++i)
	{
		PII p1 = MP(a[i].x, a[i].y);
		PII p2 = MP(a[i + 1].x, a[i + 1].y);
		PII p3 = MP(a[i + 2].x, a[i + 2].y);
		PII p4 = MP(a[i + 3].x, a[i + 3].y);
		if(p1 == p2 && p2 == p3 && p3 == p4)
			ans[max({a[i].id, a[i + 1].id, a[i + 2].id, a[i + 3].id})]++;
	}

	for(int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
	return 0;
}

// 4
// 1 2 1
// 2 3 1
// 1 2 1
// 2 3 1

标签：const,积木,int,return,P4729,HNOI2009,MOD,id,define
From： https://www.cnblogs.com/Schucking-Sattin/p/17686048.html

相关文章

  • 从积木式到装配式云原生安全
    云原生安全风险随着云原生架构的快速发展，核心能力逐渐稳定，安全问题日趋紧急。在云原生安全领域不但有新技术带来的新风险，传统IT基础设施下的安全威胁也依然存在。要想做好云原生安全，就要从这两个方面分别进行分析和解决。新技术带来新的安全风险云原生的概念定义本身就比较抽象......
  • 阿里云亮相数据库顶会 VLDB 2023 特邀主旨演讲：云数据库要像乐高积木一样好用
    北京时间8月30日，数据库国际顶会VLDB在加拿大温哥华开幕，来自阿里云、达摩院及合作者的论文共入选17篇，其中工业赛道（Industrial Track）收录7篇阿里云论文，均刷新中国企业纪录。在VLDB大会现场，阿里云数据库负责人李飞飞作大会特邀主旨演讲时表示，随着云计算基础设施的完善和......
  • P8675 [蓝桥杯 2018 国 B] 搭积木 题解
    总述此题用区间dp解决，二维前缀和优化。朴素做法阶段：自上而下数每一层。状态：\(dp_{i,l,r}\)表示自上而下数第\(i\)行中在\([l,r]\)摆积木的方案数。状态转移方程：根据题意可知，若要在\([l,r]\)中摆积木，那么\([l,r]\)中不允许有\(\tt{X}\)，而第\(i\)层的\([l,r]\)......
  • jeecg-boot/积木报表基于SSTI的任意代码执行漏洞
    漏洞简介JeecgBoot受影响版本中由于积木报表/jeecg-boot/jmreport/queryFieldBySqlApi接口未进行身份校验，使用Freemarker处理用户用户传入的sql参数，未经授权的攻击者可发送包含恶意sql参数的http请求，通过SSTI在应用端执行任意代码。漏洞复现fofa语法：body="jeecg-b......
  • 上海KTV酒店装饰电镀卡通不锈钢积木熊雕塑厂家报价
    上海KTV酒店装饰电镀卡通不锈钢积木熊雕塑厂家报价Bearbrick卡通不锈钢积木熊雕塑是一个独特的塑料玩具，它的形象是一个可爱的、独特的拟人化熊公仔，带有大肚皮。卡通不锈钢积木熊雕塑虽然是一个简单的塑料玩具，但世界上一些最大的时装公司和设计师已经采用它来展示他们最新的设计和......
  • 【2023.08.06】乐高Lego福运成双80110积木评测
    前言本人是自费购买积木，购买原因是给妹妹培养动手能力，减少短视频占用时间，其次是给家里做摆饰，所以选择积木多考虑了美观非专业评测，如果想看更多积木评测请点进我的博客主页分类查看正文这次的积木整体创意挺好的，斜着拼装红色和金色电镀件很好看，金色的电镀件颜色反射非常均匀......
  • 【2023.07.18】Keeppley栖云小筑K18002建筑积木评测
    前言本人是自费购买积木，购买原因是给妹妹培养动手能力，减少短视频占用时间，其次是给家里做摆饰，所以选择积木多考虑了美观非专业评测，如果想看更多积木评测请点进我的博客主页分类查看正文这是第一次拼大型建筑类的积木灯光件的设计不是很喜欢，需要把单层拆下来，然后将那个开关积......
  • 【2023.07.17】keeppley周杰伦DZ0157周同学积木评测
    前言本人是自费购买积木，购买原因是给妹妹培养动手能力，减少短视频占用时间，其次是给家里做摆饰，所以选择积木多考虑了美观非专业评测，如果想看更多积木评测请点进我的博客主页分类查看正文这次的说明书颜色真的印刷质量感觉不太好（单指颜色，拼装过程说明还是很不错的），颜色真的很杂......
  • P5372 SNOI2019 积木
    P5372SNOI2019积木不难想到图论建模（也没啥别的思路了），考虑用一张图刻画网格板上的任意一种状态：图有\(n\timesm\)个点，形成点阵，和网格板对应。网格板上，一个积木对应一条边，积木占据的两个格子，对应这条边连接的两个点。比如第一个样例中，起始时的网格板状态：33nnnuuuo<>......
  • 若依微服务版本集成积木报表
    一、项目结构新建报表微服务模块，这是我的项目结构图。二、执行初始化数据脚本运行积木报表的初始化脚本，创建相关表结构，github速度太慢，推荐使用gitee地址。选择你要建表的数据库，我是跟业务库放到了一起，执行完后会新增以下这几张表。三、pom中引入积木报表依赖在顶级父pom......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99