The BOSS Can Count Pairs
算法本质
思维
题目大意
给定长度n的数组a[] b[]，其元素范围是[1~n]。
输出其中满足a[i]*a[j]==b[i]+b[j] && i<j的情况数。
时间限制 4s
n <= 2e5思路推演
观察时限大概是n^1.5^的复杂度，观察元素范围，表示需要用类似桶排序的方式。
题目条件给的很少，所以可以直接挨个尝试：
b[i] = a[i]*a[j] - b[j]a[i] = (b[i]+b[j]) / a[j]
这两个式子转换后并无法求解，但是其指出a[i]和a[j]的值不会特别大——其乘积不超过2n，结合复杂度，猜测是暴力+对取值限制。
a[i]和a[j]的小值一定小于sqrt(2n)，则可以维护f[x][y]=z：表示a[]值为x、b[]值为y的对数有z个，同时只记录x <= sqrt(2n)的情况。
然后遍历即可，注意考虑a[]相等、a[] b[]都相等的情况。
ac核心代码
注意，内存和时间都卡的比较极限，时间上用数组O(1)查询、内存上不能开全局longlong，给答案开即可。
头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
cin>>n;
int top = sqrt(2*n)+1;
vector<int> a(n+5), b(n+5);
vector<vector<int>> mp(top+1, vector<int>(n+1));
rep(i,1,n) cin>>a[i];
rep(i,1,n)
{
cin>>b[i];
if (a[i] <= top)
mp[a[i]][b[i]]++;
}
long long ans=0;
for (int i=1; i<=n; i++) // 考虑不同a[]情况
{
int v1=a[i];
for (int v2=1; v2<=min(v1-1, top); v2++)
{
int z = v1*v2-b[i];
if (z>=0 && z<=n)
ans += mp[v2][z];
}
}
long long res=0;
for (int i=1; i<=n; i++) // 考虑相同的a[]情况
{
if (a[i]>top) continue;
if (a[i]*a[i] == 2*b[i]) // 考虑相同b[]情况
res += mp[a[i]][b[i]]-1;
else if (a[i]*a[i]-b[i]>=0 && a[i]*a[i]-b[i]<=n)
res += mp[a[i]][a[i]*a[i]-b[i]];
}
res /= 2;
ans += res;
cout<<ans<<endl;
return;
}Hyperregular Bracket Strings
算法本质
思维
题目大意
由玩家构建长度n的正则括号序列，且满足题目给出的m个条件：
- 每个条件会指定
l r，要求[l~r]也是正则括号序列
输出可行的方案数。
思路推演
正则括号序列，与卡特兰数有关。
主要思考不同区间之间的关系。
如果两个区间有交集，可以简单证明出其交集也必然是正则括号序列。
但如果是包含关系，那相对来说复杂一些，比如有某个大区间[1~10]，现在有2个被包含的小区间[1~4]和[7~8]，则剩余4个空间也需要是正则括号序列。
以上规律推理相对简单，但是笔者没有想到实现部分的代码，下面是作者思路
观察其本质发现，其核心在于某个点被哪些线段覆盖，如果多个点被覆盖的线段一致，则其需要构成正则括号序列。
这可以用hash来搞定，同时搭配线段树即可。
当然线段树只是一种思考方式，随后就发现因为本身需要遍历结果，所以用一个差分数组即可维护。
ac核心代码
关于这道题，我们只关心hash最后的值是否相同，所以需要取模足够大，这时可以用unsigned long long，会自动减去超出部分，再配合随机数即可。
头文件、宏定义、快读模板、常见变量、常见变量等略。
int f[maxn];
mt19937_64 rnd(random_device{}());
uniform_int_distribution<unsigned long long> dist(0, ULLONG_MAX); // 生产ull范围内任意一个随机数
inline void solve()
{
cin>>n>>m;
vector<unsigned long long> v(n+5);
while (m--)
{
int l, r;
cin>>l>>r;
unsigned long long w=dist(rnd);
v[l] += w; // 差分计算
v[r+1] -= w;
}
map<unsigned long long, int> mp; // 计算不同类型的点的数目
unsigned long long now=0;
for (int i=1; i<=n; i++)
{
now += v[i];
mp[now]++;
}
int ans=1;
for (auto [val, cnt] : mp)
{
if (cnt%2) ans = 0; // 不可行
else ans = ans * f[cnt/2] % mod;
}
cout<<ans<<endl;
return;
}
inline void solve_init()
{
f[0] = 1;
for (int i=1; i<=3e5; i++) // 预处理卡特兰数
f[i] = (4*i-2) * f[i-1] % mod * qpow(i+1, mod-2, mod) % mod;
return;
}title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
title
算法本质
题目大意
思路推演
ac核心代码
头文件、宏定义、快读模板、常见变量、常见变量等略。
评论 (0)