Codeforces Round 916 (Div. 3) G2. Light Bulbs (Hard Version)（思维题 随机化哈希）

本文主要是介绍Codeforces Round 916 (Div. 3) G2. Light Bulbs (Hard Version)（思维题 随机化哈希），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

2n(2<=n<=2e5)个灯泡，

灯泡分n种，每种颜色恰有两个，灯泡颜色用1到i表示

你可以执行以下两种操作若干次：

1. 选择两个同色的灯泡i、j，如果一个亮，但是另一个不亮，就把另一个点亮

2. 选择三个不同位置的灯泡i,j,k(i<j<k)，如果i和k都亮了，但是j不亮，就把j点亮

你初始时，可以手动点亮若干个灯泡，

求初始时最少手动点亮灯泡的个数，以及满足个数等于最少灯泡数时选择灯泡的方案数，

使得后续通过以上两种操作，可以将所有灯泡都点亮

答案对998244353取模

实际t(t<=1e4)组样例，但保证sumn不超过2e5

思路来源

jiangly代码

题解

手玩不难发现，对于一个区间，

如果完整包含另一个区间，1 2 2 1，则内层灯泡无需初始点亮

即区间包含内层区间无需点亮，区间相交时，点亮两个区间任意一个都可以

1 2 3 3 5 1 2 5 6 7 7 6，

对于这种情况，显然是1、2、5三个灯泡中选一个，然后6这个灯泡必取

也就是说，整个2n长度的区间，

首先可以看成是最少个不相交的区间

满足每个区间内所有灯泡都出现两次，称每个这样的区间是一个闭区间

其中1 2 3 3 5 1 2 5是一个区间，6 7 7 6这个是一个区间

这个可以通过随机化哈希的方式实现，为每个颜色random一个哈希值，求前缀异或，

冲突的概率很低，所以前缀异或和为0的位置即认为是合法的分界位置

第一问就解决了，即前缀哈希值为0的个数

考虑第二问，对于形如1 2 3 3 5 1 2 5这样的区间，

希望先1跳到2，2再跳到5，5跳到1跳到2跳到5，

也就是跳跃过程中，忽略不会出现在最小个数的数，

其他位置的值则由于区间相交，则对方案数都有贡献，

最后125的这6个位置任取一个就能覆盖全部

观察跳跃过程，实际每次是跳跃到前缀异或值的最后一个位置，

每个前缀异或值，要么出现一次，要么中间包含了若干闭区间

导致这样的异或值是可以出现两次的，

那么对于出现两次的位置，肯定是选择忽略到中间异或和为0的这一段

所以每次的操作是将当前位置j，

飞到异或值相同的最后一个位置，j=las[sum[j]]，再令j++，到下一个区间相交的位置

统计每个闭区间段内有贡献的值，最后将若干个闭区间的值相乘，即为第二问方案数

代码

#include<bits/stdc++.h>
// #include<iostream>
// #include<map>
// #include<random>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
mt19937_64 rng((ll) chrono::steady_clock::now().time_since_epoch().count());
const int N=2e5+10,mod=998244353;
int t,n,a[N<<1];
ll sum[N],hs[N];
map<ll,int>las;
int main(){//freopen("1.out","w",stdout);sci(t);while(t--){sci(n);rep(i,1,n)hs[i]=rng();int cnt=0,ans=1;las.clear();rep(i,1,2*n){sci(a[i]);sum[i]=sum[i-1]^hs[a[i]];las[sum[i]]=i;if(!sum[i])cnt++;//printf("i:%d sum:%d\n",i,sum[i]);}rep(i,0,2*n-1){if(sum[i])continue;int j=i+1,c=1; // 1 2 2 1while(sum[j]){// 1 2 3 1 3 2j=las[sum[j]]; // 走到相同异或值的最后一个位置j++;c++;if(!sum[j])break;//printf("i:%d j:%d\n",i,j);}ans=1ll*ans*c%mod;}printf("%d %d\n",cnt,ans);}return 0;
}

这篇关于Codeforces Round 916 (Div. 3) G2. Light Bulbs (Hard Version)（思维题 随机化哈希）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---