首页 > 其他分享 >「闲话随笔」「DROI」Round 2

「闲话随笔」「DROI」Round 2

时间:2023-05-30 21:11:08浏览次数:55  
标签:return ll 2i DROI inline 随笔 Round

「闲话随笔」「DROI」Round 2

点击查看目录

目录

题挺好玩的。

P9373 「DROI」Round 2 构造与取模

发现 \(k, n - k\) 即为一组正确构造,\(k \ge n - k\) 时无解。

为啥无解啊?不难发现 \(k \ge n - k\) 时 \(k \ge \dfrac{n}{2}\),则一组合法构造 \((x, y)\) 必然满足 \(x, y \le k\),你模数比 \(k\) 小你余数怎么等于 \(k\)?

P9374 「DROI」Round 2 单图

不拿发现当一个点出入度均不为零时,指向它的一个点和它指向的一个点之间连或不连一条边构成的两种图本质相同,因此一个合法图的任意一个点出入度必须至少有一个为零。

这个结论是错的,因为存在两点环。不存在两点环时这个结论是正确的。

那么枚举两点环数量 \(i\),考虑分别计算两点环方案数 \(f(i)\) 和无两点环的图的方案数 \(g(i)\)。则答案为:

\[\sum_{i = 1}^{\left\lfloor\frac{n}{2}\right\rfloor}\dbinom{n}{2i}f(2i)g(n - 2i) \]

首先考虑两点环计数,依次选取两个点即可,但是依次选会带有本来不该有的顺序,所以要除去 \(i!\)。

\[\begin{aligned} f(2i) &= \frac{1}{i!}\prod_{j = 1}^{i}\dbinom{2i - 2j + 2}{2}\\ &= \frac{1}{i!}\prod_{j = 1}^{i}\frac{(2i - 2j + 2)(2i - 2j + 1)}{2}\\ &= \frac{1}{i!}\prod_{j = 1}^{i}(i - j + 1)\prod_{j = 1}^{i}(2i - 2j + 1)\\ &= \prod_{j = 1}^{i}(2j + 1)\\ \end{aligned} \]

然后计算无两点环的图方案数 \(g(i)\)。我们把图分成「有入度」和「无入度」两类点,显然方案数就是两类点之间随便连边的方案数。注意不能一条边不连,因为前一类点定义是「有入度」。

\[\begin{aligned} g(i) &= \sum_{j = 0}^{i}\dbinom{i}{j}(2^{i - j} - 1)^{j} \end{aligned} \]

点击查看代码
const ll N = 1010;
namespace SOLVE {
	ll n, P, c[N][N], f[N], g[N], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline ll FastPow (ll a, ll b) {
		ll ans = 1;
		while (b) {
			if (b & 1) ans = ans * a % P;
			a = a * a % P, b >>= 1;
		}
		return ans;
	}
	inline void Init () {
		_for (i, 0, 1000) {
			c[i][0] = 1;
			_for (j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % P;
		}
		f[0] = 1;
		_for (i, 1, 500) f[i] = f[i - 1] * (2 * i + 1) % P;
		_for (i, 0, 1000) {
			g[i] = 0;
			_for (j, 0, i) g[i] = (g[i] + c[i][j] * FastPow (FastPow (2, i - j) - 1, j) % P) % P;
		} 
		return;
	}
	inline void In () {
		n = rnt ();
		return;
	}
	inline void Solve () {
		ans = g[n];
		_for (i, 1, n / 2) ans = (ans + c[n][2 * i] * f[i - 1] % P * g[n - 2 * i] % P) % P;
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

P9375 「DROI」Round 2 划分

考虑爆搜,感觉状态数很大,但是其实是跑不满的。所以我们直接把状态哈希一下然后记忆化搜索即可。

好像是之前有一场校内模拟赛有类似的题目,所以考场上也有这种直觉,只是不太信自己。当时那道题还是场切了的,这回就没切,真是越学越倒退。

哈希时取模超时了,所以贺了题解的神奇写法。

点击查看代码
const ll N = 130, P = 1e6 + 3;
namespace SOLVE {
	ll n, m, a[N], c[N], b[N][N], vis[P];
	class STA {
	public:
		ll len, cnt[N];
		inline ll GetHash () {
			ll tmp = 0;
			for_ (i, n, 1) tmp = (tmp * (c[i] + 1) + cnt[i]);
			return tmp;
		}
	} qwq;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline ll Dfs (STA s) {
		ll h = s.GetHash ();
		if (vis[h] > -1) return vis[h];
		ll mx = 0;
		_for (i, 1, n) {
			if (!s.cnt[i]) continue;
			STA st = s;	st.len -= i, --st.cnt[i];
			mx = std::max (mx, Dfs (st) + b[st.len + 1][s.len]);
		}
		vis[h] = mx;
		return mx;
	}
	inline void In () {
		qwq.len = n = rnt ();
		_for (i, 1, n) a[i] = rnt ();
		_for (i, 1, n) qwq.cnt[i] = c[i] = rnt (), m += i * c[i];
		return;
	}
	inline void Solve () {
		if (m != n) return;
		memset (vis, -1, sizeof (vis));
		_for (i, 1, n) {
			_for (j, 1, i) {
				ll l = 0, r = 0;
				_for (k, j, i) {
					ll q1 = std::abs(a[k] - a[j]), q2 = std::abs(a[i] - a[k]);
					l += ((ll)(sqrt (q1)) * (ll)(sqrt (q1)) == q1);
					r += ((ll)(sqrt (q2)) * (ll)(sqrt (q2)) == q2);
				}
				b[j][i] = l * r;
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", (m == n) ? Dfs (qwq) : -1);
		return;
	}
}

P9376 「DROI」Round 2 进制与操作

有空再补。

标签:return,ll,2i,DROI,inline,随笔,Round
From: https://www.cnblogs.com/Keven-He/p/chat_20230530.html

相关文章

  • 《可伸缩服务架构-框架与中间件》-00-随笔计划
    初步计划大约花费9*5天时间精细阅读本书。目标输出:每个篇章输出一篇随笔,分析架构和逻辑内容。第一章:分布式发号器(5月31号--6月4号)第二章:消息队列(6月5号--6月9号)第三章:数据库分库分表(6月10号--6月14号)第四章:缓存(6月15号--6月19号)第五章:ES(6月20号--6月24号)第六章:定制任务(6月2......
  • Unity发布IOS发布Android版本出现屏幕问题 UGUI半屏被压缩 另一半黑屏
    项目场景:用Unity做的app发布的ios和Android版本,ui做屏幕自适应,来适配多机型,unity版本是2019.4,用的UGUI。问题描述:极个别机型有个偶发的问题,就是在app息屏,再开屏的时候,会出现半边屏幕被压缩,半边屏幕黑屏的问题,但是ui交互的位置还是正常的,bug效果图如下:跟这张图一样的<hrstyle="bor......
  • android开发java.lang.NoClassDefFoundError: org/jetbrains/kotlin/cli/common/Prope
    问题:编译Android项目出现java.lang.NoClassDefFoundError:org/jetbrains/kotlin/cli/common/PropertiesKt原因:项目使用发JDK版本和Kotlin版本不一致或者说不对应导致gradle找不到对应的类解决方法:我的解决方法是降低JDK的版本到1.8,具体操作是OpenModulesSettings->SDKLoc......
  • Android 12 startActivity梳理
    前面梳理了WM中Window容器的概念,今天梳理一下startActivity的流程,看一下window容器的体现。其实在server端Window最终都会表现为WindowState对象。而之所以存在划分层级的window容器,是为了有层级的管理,目的是实现Android的一些列feature,如:任务栈Task,Task引出Activity的生命周期......
  • Codeforces Round 875 (Div. 2) A-D
    A.TwinPermutations题意:给出一个由[1,2,...,n]组成的数组a,构造另一个由[1,2,...,n]组成的数组b,使得a[1]+b[1]<=a[2]+b[2]<=...<=a[n]+b[n]Solution可以想到只要让他们全为n+1就行了,这样是一定有解的voidsolve(){ intn;cin>>n; for(inti=1;i<=n;i++) { cin>>a[i]; ......
  • Codeforces Round 875 (Div
    CodeforcesRound875(Div.2)C-D题解CProblem-C-Codeforces我们发现题述所形成的父亲节点一定比子节点先画出,并且如果子节点顺序在父节点后面,则父,子节点为同一个周期加入。反之,则子节点的周期为父节点+1。所以做法考虑树上dp,维护第i个节点加入树的周期。转移方程如下:\[......
  • Codeforces Round 875 (Div. 2)
    Preface难得现场打一次,这天下午打了三个半小时的校内赛,然后八点打了两小时ARC,最后再接上两个半小时的CF真是爽歪歪不过有一说一其实很多时候都在坐牢,这场CF也差不多,一个小时写完ABCD然后开始坐牢,其实E基本想出来了但是没想到用随机赋值的方法来实现不过由于这场手很稳因此排名......
  • UE5 custom node随笔
    前言UE蓝图的customnode不像unity一样灵活,且貌似因为渲染框架的更改4.2之前使用customnode的方式和如今大不相同,经过捣鼓一番总算是知道如何使用,本篇会介绍如何使用customnodeCode主要问题在于customnode的Code处,在UE4.2时以前使用方式是在你的项目下新建Shaders文件夹......
  • Unity,发布ios和Android的包,UGUI,异形屏适配问题。
    Unity,发布ios和Android的包,UGUI,异形屏适配问题。@TOC<hrstyle="border:solid;width:100px;height:1px;"color=#000000size=1">前言unity发布移动端需要做ui的适配,我们用的是UGUI,暂且提供一种我们自己的ui适配解决方案,包含异形屏的。<hrstyle="border:solid;width:100px;h......
  • Codeforces Round 874 (Div. 3)
    A.MusicalPuzzle#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn;strings;cin>>n>>s;set<string>cnt;for(inti=0;i+1<n;i++)cnt.insert(s.substr(i,2));......