当前位置:网站首页>牛客月赛-分组求对数和
牛客月赛-分组求对数和
2022-07-01 21:45:00 【山中一扶苏】
原题链接
题目描述
牛牛幼稚园的小朋友在做游戏。
幼稚园共有 n 个小朋友,第 i 个小朋友有 s i s_i si个数字,第 i 个小朋友手中的第 jj 个数字记为 a i j ( 1 ≤ j ≤ s i ) a_{ij}(1\leq j \leq s_i) aij(1≤j≤si)。
现在牛牛老师想要知道有多少种不同的方式从两个不同的小朋友手中各取一个数字使得数字的和大于等于 k ?
由于可能的方式可能十分多,所以你只需要告诉牛牛这个方案数模 998244353 之后的结果就可以了(同一个小朋友手中相同的数字分别组成的答案看作是不同的)。
输入样例
3 7
4 2 3 1 5
2 4 1
2 8 2
输出样例
9
算法
(容斥原理思想 + 二分查找)
本题首先想到的是爆搜枚举,一一枚举搜索所有的相加大于 k 的可能,但这显然会超时,是平方级别的复杂度
所以,我们可以想到,本题 k 已经给出,所以我们只要求出每个数字与 k 的差值更大的数有多少个即可,那么就不难想到先排序然后用二分查找。
由于每个数字查找不能包含本组数字,我们就可以每次查找分两个区间,将大区间查找的数减去小区间中的数,最后累加即是答案。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;const ll mod = 998244353;
int main()
{
ll n,k,cnt;
cin >> n >> k;
vector<ll> v[N],all;
for (int i = 0;i < n;i ++ ) {
int m;
cin >> m;
for (int j = 0;j < m;j ++ ) {
int x;
cin >> x;
v[i].push_back(x);
all.push_back(x);
cnt ++;
}
sort(v[i].begin() , v[i].end());
}
sort(all.begin(),all.end());
ll res = 0,t1 = 0,t2 = 0;
for (int i = 0;i < n;i ++ ) {
for (int j = 0;j < v[i].size();j ++ ) {
t1 = 0,t2 = 0;
t1 = lower_bound(v[i].begin(),v[i].end(),k - v[i][j]) - v[i].begin();
t1 = (ll)v[i].size() - t1;
t2 = lower_bound(all.begin(),all.end(),k - v[i][j]) - all.begin();
t2 = cnt - t2;
//cout << t2 << ' ' << t1 << '\n';
res = (res + t2 - t1) % mod;
}
}
cout << res / 2 << '\n';
return 0;
}
边栏推荐
猜你喜欢
随机推荐
Four methods of JS array splicing [easy to understand]
Go — 相关依赖对应的exe
黑马程序员-软件测试--06阶段2-linux和数据库-01-08第一章-linux操作系统阶段内容说明,linux命令基本格式以及常见形式的说明,操作系统的常见的分类,查看命令帮助信息方法,
并发编程系列之FutureTask源码学习笔记
“丝路正青春 风采看福建”在闽外籍青年短视频大赛火热征集作品中
灵动微 MM32 多路ADC-DMA配置
基于三维GIS的不动产管理应用
详解JMM
[noip2013] building block competition [noip2018] road laying greed / difference
Training on the device with MIT | 256Kb memory
CSDN购买的课程从哪里可以进入
String type conversion BigDecimal, date type
[STM32] stm32cubemx tutorial II - basic use (new projects light up LED lights)
选择在同花顺上炒股开户可以吗?安全吗?
Chapter 9 Yunji datacanvas company has been ranked top 3 in China's machine learning platform market
二叉树的基本操作
Why does blocprovider feel similar to provider?
Design and practice of new generation cloud native database
QT版本华睿相机的Demo程序实现
What is the difference between PMP and NPDP?