Gravatar
yrtiop
积分:2101
提交:309 / 808

令 $N=| S|$。

首先发现,枚举 $C$ 再判断前缀消耗的时间很多,这样行不通。

转向考虑枚举 $AB$,得出所有的 $(AB)^i$,不难发现可以用哈希+调和做到 $O(N\ln N)$。

现在考虑 $f(A)\le f(C)$ 的限制。

设 $pre(i)=f(S_{1\sim i}),suf(i)=f(S_{i+1\sim n})$。

当前枚举到 $AB$ 的长度为 $x$,则 $AB$ 对答案的贡献为 $\sum\limits_{i}\sum\limits_{j=1}^x [pre(j)\le suf(x\times i+1)]$。

预处理出 $pre(1\sim n),suf(1\sim n)$,用树状数组维护,时间复杂度为 $O(TN\ln N\log N)$。

虽然常数小,但只有 $84\text{pts}$。

仔细地思考下,这个东西真的必须要用树状数组维护吗?

设 $sum(i,j)= \sum\limits_{k=1}^i [pre(i)\le j]$,则 $AB$ 的贡献变为 $\sum\limits_{i}sum(x,x\times i+1)$。

而 $sum$ 数组显然可以用前缀和维护。

时间复杂度 $O(T(N\ln N+N\times 26))$,足以通过。



题目3509  [NOIP 2020]字符串匹配 AAAAAAAAAAAAAAAAAAAAAAAAA      11      评论
2024-06-22 16:46:08    
Gravatar
yrtiop
积分:2101
提交:309 / 808

考虑枚举 $r$,计算出所有满足题意的 $l$ 的数量。

设 $S$ 为 $A$ 的前缀和数组,若 $L \le S_r - S_l \le R$,则区间 $(l,r]$ 满足题意。

作一个简单的变化就能求出 $S_l$ 的范围:$S_r - R\le S_l\le S_r - L$。

那么我们依次枚举 $1\ldots N$ 作为 $r$,维护 $S_0 \ldots S_{r - 1}$ 即可。

可以使用树状数组+离散化或者动态开点权值线段树,我选择的是树状数组+离散化。

时间复杂度 $O(N\log N)$。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
const int maxm = 4e5 + 5;
int n,cnt;
ll L,R,a[maxn],d[maxm],c[maxm],s[maxn];
int sum[maxm];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int y) {
	if(!x)return ;
	for(;x <= cnt;x += lowbit(x))sum[x] += y;
	return ;
}
int query(int x) {
	int ans = 0;
	for(;x;x -= lowbit(x))ans += sum[x];
	return ans;
}
int main() {
	scanf("%d%lld%lld",&n,&L,&R);
	d[++ cnt] = s[0] = 0;
	for(int i = 1;i <= n;++ i) {
		scanf("%lld",&a[i]);
		s[i] = s[i - 1] + a[i];
		d[++ cnt] = s[i];
		d[++ cnt] = s[i] - L;
		d[++ cnt] = s[i] - R;
	}
	for(int i = 1;i <= cnt;++ i)c[i] = d[i];
	sort(c + 1 , c + 1 + cnt);
	cnt = unique(c + 1 , c + 1 + cnt) - c - 1;
	for(int i = 1;i <= 3 * n + 1;++ i)d[i] = lower_bound(c + 1 , c + 1 + cnt , d[i]) - c;
	add(d[1] , 1);//提前插入 s[0]
	ll ans = 0;
	for(int i = 1;i <= n;++ i) {
		ans += query((int)d[3 * i]) - query((int)d[3 * i + 1] - 1);
		add((int)d[3 * i - 1] , 1);
	}
	printf("%lld",ans);
	return 0;
}


题目3687  [BJOI2016]回转寿司      7      评论
2024-06-22 16:44:05    
Gravatar
yrtiop
积分:2101
提交:309 / 808

首先可以证明,当 $A$ 数组和 $B$ 数组均为升序排列时,$\sum\limits_{i=1}^n (a_i-b_i)^2$ 最小。

(upd:现在学到了,这个结论的原理是排序不等式)

但在这道题中,我们只需要让在升序排列中,两数组中下标相同的数对应即可。

以样例中 $A,B$ 数组为例,将它们分别离散后列出:

$A: 2 \ \ 3 \ \ 1 \ \ 4$

$B: 3 \ \ 2 \ \ 1 \ \ 4$

根据上述结论,当 $A_i = x$ 时,$B_i$ 也应该等于 $x$。

也就是说,如果建立一个数组 $C$,令 $C_{A_i}=B_i$ 的话,应该满足 $C_i=i$。

但在样例中,可以列出 $C$ 数组:

$C: 1 \ \ 3 \ \ 2 \ \ 4$

我们的目标是让 $C$ 数组升序排列,而每次交换最多消除一个逆序对。

故题目的答案就是 $C$ 数组的逆序对数。

求逆序对可以用树状数组或归并排序,代码中使用的是归并排序。

时间复杂度 $O(N\log N)$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
	int x,id;
	node() {
		x = id = 0;
	}
	node(int x,int id):x(x),id(id){}
	bool operator < (const node& p)const {
		return x < p.x;
	}
}a[maxn],b[maxn];
int n,c[maxn],d[maxn];
typedef long long ll;
const ll mod = 1e8 - 3;
ll ans = 0;
void MergeSort(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	MergeSort(l , mid);
	MergeSort(mid + 1 , r);
	for(int k = l,i = l,j = mid + 1;k <= r;++ k) {
		if(j > r||(i <= mid&&d[i] < d[j])) {
			c[k] = d[i ++];
		}
		else c[k] = d[j ++],(ans += mid - i + 1) %= mod;
	}
	for(int k = l;k <= r;++ k)d[k] = c[k];
	return ;
}
int main() {
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)scanf("%d",&a[i].x),a[i].id = i;
	for(int i = 1;i <= n;++ i)scanf("%d",&b[i].x),b[i].id = i;
	sort(a + 1 , a + 1 + n);
	sort(b + 1 , b + 1 + n);
	for(int i = 1;i <= n;++ i)d[a[i].id] = b[i].id;
	MergeSort(1 , n);
	printf("%lld",ans);
	return 0;
}


题目1438  [NOIP 2013]火柴排队      7      评论
2024-06-22 16:42:45    
Gravatar
yrtiop
积分:2101
提交:309 / 808

(不知道为什么很多人把这题划分为树形 DP,我觉得是贪心)


Subtask 1:$m=1$


对于 $m=1$ 的情况,直接求树的直径即可。

时间复杂度 $O(n)$,期望得分 $\rm{20\ pts}$。


Subtask 2:$a_i=1$


菊花图的情况,按边权从大到小排序。


答案为 $\min\limits_{i=1}^m \{l_i+l_{2m-i+1}\}$。


时间复杂度 $O(n\log n)$,期望得分 $\rm{15\ pts}$


Subtask 3:$b_i=a_i+1$

一条链的情况,显然二分答案,贪心判断即可。

时间复杂度 $O(n\log n)$,期望得分 $\rm{20\ pts}$。 

Correct Answer

显然这道题的主体是二分答案。

考虑判断当前答案 $k$ 是否满足。

我们要构造 $\ge m$ 条长度 $\ge k$ 的路径,而且还不能有重边。

一开始我在尝试淀粉质,但发现无重边这个东西实在是难以处理。

不如另辟蹊径,我们考虑枚举一个点 $u$ 对答案的贡献。

也就是经过点 $u$,且 $u$ 的深度是路径上所有点中深度的最小值的路径个数。

首先,递归到子树里,并把子树里 $\lt k$ 的最大一条路径长度穿上来,保存在一个 `std::multiset` 中。

然后利用 `std::multiset` 的二分统计答案,在这个过程中统计出 $\lt k$ 的最大路径长度,递归回去。

时间复杂度 $O(n\log^2 n)$。

// Problem: #438. 【NOIP2018】赛道修建
// Contest: UOJ
// URL: https://uoj.ac/problem/438
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define SIT std::multiset<int>::iterator
typedef std::pair<int,int> pii;

const int maxn = 5e4 + 5;
std::vector<pii> G[maxn];
int n,m,dp[maxn],ans,res;

void DFS(int u,int fa) {
	for(auto& [v , w] : G[u]) {
		if(v == fa)continue ;
		DFS(v , u);
		res = std::max(res , dp[u] + dp[v] + w);
		dp[u] = std::max(dp[u] , dp[v] + w);
	}
	return ;
}

void GetMaxLength() {
	res = 0;
	DFS(1 , 0);
	return ;
}

int dfs(int u,int fa,int k) {
	std::multiset<int> s;
	for(auto& [v , w] : G[u]) {
		if(v == fa)continue ;
		int t = dfs(v , u , k) + w;
		if(t >= k)++ ans;
		else s.insert(t);
	}
	
	int Max = 0;
	for(;!s.empty();) {
		res = *s.begin();
		s.erase(s.begin());
		SIT it = s.lower_bound(k - res);
		if(it == s.end())Max = std::max(Max , res);
		else s.erase(it),++ ans;
	}
	
	return Max;
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i = 1,u,v,t;i < n;++ i) {
		scanf("%d %d %d",&u,&v,&t);
		G[u].pb(v , t);
		G[v].pb(u , t);
	}
	
	GetMaxLength();
	int l = 1,r = res,mid;
	while(l <= r) {
		mid = (l + r) >> 1;
		ans = 0;
		dfs(1 , 0 , mid);
		if(ans >= m)l = mid + 1;
		else r = mid - 1;
	}
	
	printf("%d\n",r);
	return 0;
}


题目3055  [NOIP 2018]赛道修建      7      评论
2024-06-22 16:38:33    
Gravatar
yrtiop
积分:2101
提交:309 / 808

首先,两两互质等价于两个集合的质数集无交集。

那么从质数的方面考虑,不难想到状态压缩 DP。

但是打个表发现 $500$ 以内的质数接近 $100$ 个,显然压缩不了。

考虑一个解决这种问题相当常用的方法:根号分治。

注意到 $22$ 以内的质数只有 $8$ 个,而 $22$ 以上的质数至多会被一个数包含一次,称这些质数为「大质数」。

因为它们至多被包含一次,我们可以直接分类讨论它们在哪个集合。

具体地,我们把前 $8$ 个质数压缩状态,把 $2\sim n$ 除去前 $8$ 个质数的结果升序排序。

依次枚举 $2\sim n$,开三个 DP 数组:

$f(j,k)$:表示当前第一个集合状态为 $j$,第二个集合状态为 $k$ 的方案数。

$F(j,k)$:表示当前第一个集合状态为 $j$,第二个集合状态为 $k$,且当前枚举到的「大质数」都在第一个集合的方案数。

$G(j,k)$:表示当前第一个集合状态为 $j$,第二个集合状态为 $k$,且当前枚举到的「大质数」都在第二个集合的方案数。

注:其实这里本该是 $f(i,j,k)$,不过可以直接滚动数组滚掉第一维的阶段,所以我没有写在式子里。

转移相当简单:$F(j|s,k)=\sum F(j,k),G(j,k|s)=\sum G(j,k)$

而 $f$ 数组较为特殊:$f(j,k)=F(j,k)+G(j,k)-f(j,k)$

原因不难理解:$F(j,k),G(j,k)$ 都经过了一轮转移,但 $f(j,k)$ 还保留着上一轮的结果。

直接 $F(j,k)+G(j,k)$ 会将 $f(j,k)$ 计算两遍,所以要再减回来。

还有一些小细节:比如 $f(j,k)$ 复制到 $F(j,k),G(j,k)$,以及 $f(j,k)$ 的计算条件可以参考代码。

时间复杂度 $\mathcal{O}(n\times 2^{16})$


// Problem: #129. 【NOI2015】寿司晚宴
// Contest: UOJ
// URL: https://uoj.ac/problem/129
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
typedef long long ll;
typedef std::pair<int,int> pii;

const int maxn = 505;
int n,prime[10] = {2 , 3 , 5 , 7 , 11 , 13 , 17 , 19};
pii a[maxn];
ll p,f[maxn][maxn],F[maxn][maxn],G[maxn][maxn];

int main() {
	scanf("%d %lld",&n,&p);
	
	for(int i = 2;i <= n;++ i) {
		auto& [s , res] = a[i];
		res = i;
		for(int k = 0;k < 8;++ k) {
			if(res % prime[k])continue ;
			s |= 1 << k;
			for(;!(res % prime[k]);res /= prime[k]);
		}
	}
	
	std::sort(a + 2 , a + n + 1 , [&](const pii& p,const pii& q) {
		return p.second < q.second;
	});
	
	f[0][0] = 1;
	for(int i = 2;i <= n;++ i) {
		auto& [s , res] = a[i];
		if(res == 1||res != a[i - 1].second) {
			memcpy(F , f , sizeof(f));
			memcpy(G , f , sizeof(f));
		}
		for(int j = 255;~ j;-- j) {
			for(int k = 255;~ k;-- k) {
				if(j & k)continue ;
				if(!(s & k))(F[j | s][k] += F[j][k]) %= p;
				if(!(s & j))(G[j][k | s] += G[j][k]) %= p;
			}
		}
		if(i == n||res == 1||res != a[i + 1].second) {
			for(int j = 0;j < 256;++ j) {
				for(int k = 0;k < 256;++ k) {
					if(j & k)continue ;
					f[j][k] = (F[j][k] + G[j][k] - f[j][k] + p) % p;
				}
			}
		}
	}
	
	ll ans = 0;
	for(int j = 0;j < 256;++ j) {
		for(int k = 0;k < 256;++ k) {
			if(j & k)continue ;
			(ans += f[j][k]) %= p;
		}
	}
	
	printf("%lld",ans);
	return 0;
}



题目2020  [NOI 2015]寿司晚宴      7      评论
2024-06-22 16:32:43    
Gravatar
yrtiop
积分:2101
提交:309 / 808

学习 Hiengon 大神,开头应该有一句原神语录或者日文歌词,但是我不玩原神,也不是罕见,所以略过。

个人感觉,其实这题的重点不在后面的多项式优化,而在这个容斥系数的推导。这其实展示了一类不太平凡的容斥系数的通用推法。

这个题解本身就是复读论文,后面加点自己的理解。

首先最终的式子是 $f_i = \sum\limits_{0<j<i} f_{i-j}\mathrm C_{i}^{j} 2^{j(i-j)} (-1)^{j-1}$,重点在于那个 $(-1)^{j-1}$ 从哪来。

首先我们有最基本的容斥:

$$g(S) = \sum_{T\subseteq S} f(T)\\f(S) = \sum_{T\subseteq S} (-1)^{|S|-|T|}g(T)$$

可以看作 $\sum\limits_{i=0}^n (-1)^i \mathrm C_{n}^{i}=[n=0]$ 的外在表现,具体的组合双射得参考上面这个的(不知道有没有就是了),反正我不会。这个式子集合关系反过来也是对的,下面要用。

然后我们思考这个题咋做。设 $f(i,S)$ 表示 $i$ 个点,目前零度点集合 恰好 为 $S$ 的方案数,$g(i,S)$ 表示 $i$ 个点,钦定 $S$ 内部均为零度点的方案数。显然有:

$$g(n,S)=\sum_{S\subseteq T} f(n,T)\\f(n,S)=\sum_{S\subseteq T} (-1)^{|T|-|S|} g(n,T)$$

现在我们要算 $g(n,\emptyset)$,直接开始大力推式子:

$$\begin{aligned}g(n,\emptyset) & = \sum_{m=1}^n \sum_{|T|=m} \sum_{T\subseteq S}(-1)^{|T|-|S|} g(n-|S|,\emptyset) 2^{|S|(n-|S|)}\\& = \sum_{S\neq \emptyset} g(n-|S|, \emptyset) 2^{|S|(n-|S|)} \sum_{m=1}^{|S|} (-1)^{|S|-m} \mathrm C_{|S|}^{m}\\& = \sum_{j=1}^{n} g(n-j,\emptyset) \mathrm C_{n}^{j} 2^{j(n-j)} (-1)^{j-1}\end{aligned}$$

每行都解释一下:第一行就是大力展开递推式,第二行交换求和顺序,第三行枚举 $|S|$ 大小直接算,后面那个 $(-1)^{j-1}$ 其实是凑了个 $m=0$ 化二项式定理,然后再减回去。

于是我们就得到了这样一个容斥系数。事实上引起我注意的是最上面的那个最基本的容斥式子,经过之前和 DarkMoon 大神的讨论,发现其实莫反,二项式反演都可以从这个直接理解。

好了,你已经学会有标号 DAG 计数的方法了,快去试试切掉 联合省选2024 d2t2 吧!



题目2353  [HZOI 2015] 有标号的DAG计数 I      5      评论
2024-06-22 16:18:57